ICAPS 2015 Tutorial
LP-based Heuristics for Cost-optimal Classical Planning

Florian Pommerening, Gabriele Röger, Malte Helmert
ICAPS 2015, Jerusalem, Israel
Sunday, June 7, 2015, 16:00-17:30
Room C

Description

Linear programs (LPs) provide a powerful optimization framework and can be efficiently solved in polynomial time. Therefore, they appear to be well-suited to form the basis for highly informed heuristics for classical planning. Since solving a typical planning instance optimally requires to evaluate a heuristic for millions of individual states, it nevertheless was for a long time expected to be too time-intensive to solve a LP for every single state. However, several recent heuristics show that this can not only be practically feasible but also be very beneficial.

This tutorial will cover most of these recent LP-based heuristics: optimal cost partitioning for abstractions, post-hoc optimization of heuristic estimates, optimal estimates from disjunctive action landmarks, the state-equation heuristic, potential heuristics, and an LP-based heuristic for relaxed planning. We also will introduce a unifying framework that allows to beneficially combine these heuristics. Participants need no background on linear programming but basic knowledge about heuristic search is desirable.

Outline

1.	Introduction and Overview (PDF)
2.	Cost Partitioning (PDF)
3.	Operator Counting (PDF)
4.	Potential Heuristics (PDF)
5.	Bibliography (PDF)