Flow-based heuristics for optimal planning: Landmarks and merges

Blai Bonet, Menkes Van Den Briel

    Research output: Contribution to journalConference articlepeer-review

    28 Citations (Scopus)

    Abstract

    We describe a flow-based heuristic for optimal planning that exploits landmarks and merges. The heuristic solves a linear programming (LP) problem that represents variables in SAS+ planning as a set of interacting network flow problems. The solution to the LP provides a reasonable admissible heuristic for optimal planning, but we improve it considerably by adding constraints derived from action landmarks and from variable merges. Merged variables, however, can quickly grow in size and as a result introduce many new variables and constraints into the LP. In order to control the size of the LP we introduce the concept of dynamic merging that allows us to partially and incrementally merge variables, thus avoiding the formation of cross products of domains as done when merging variables in the traditional way. The two types of improvements (action landmarks and variable merges) to the LP formulation are orthogonal and general. We measure the impact on performance for optimal planning of each improvement in isolation, and also when combined, for a simple merge strategy. The results show that the new heuristic is competitive with the current state of the art.

    Original languageEnglish
    Pages (from-to)47-55
    Number of pages9
    JournalProceedings International Conference on Automated Planning and Scheduling, ICAPS
    Volume2014-January
    Issue numberJanuary
    Publication statusPublished - 2014
    Event24th International Conference on Automated Planning and Scheduling, ICAPS 2014 - Portsmouth, United States
    Duration: 21 Jun 201426 Jun 2014

    Fingerprint

    Dive into the research topics of 'Flow-based heuristics for optimal planning: Landmarks and merges'. Together they form a unique fingerprint.

    Cite this