Cost-optimal factored planning: Promises and pitfalls

Eric Fabre*, Loïg Jezequel, Patrik Haslum, Sylvie Thiébaux

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    33 Citations (Scopus)

    Abstract

    Factored planning methods aim to exploit locality to efficiently solve large but "loosely coupled" planning problems by computing solutions locally and propagating limited information between components. However, all factored planning methods presented so far work with representations that require certain parameters to be bounded (e.g. number of coordination points between local plans considered); the satisfaction of those bounds by a given problem instance is difficult to establish a priori, and the influence of those parameters on the problem complexity is unclear. We present an instance of the factored planning framework using a representation of the (regular) sets of local plans by finite automata, which does not require any such bound. By substituting weighted automata, we can even do factored cost-optimal planning. We test an implementation of the method on the few standard planning benchmarks that we have found to be amenable to factoring. We show that this method runs in polynomial time under conditions similar to those considered in previous work, but not only under those conditions. Thus, what constitutes an essential measure of "factorability" remains obscure.

    Original languageEnglish
    Title of host publicationICAPS 2010 - Proceedings of the 20th International Conference on Automated Planning and Scheduling
    Pages65-72
    Number of pages8
    Publication statusPublished - 2010
    Event20th International Conference on Automated Planning and Scheduling, ICAPS 2010 - Toronto, ON, Canada
    Duration: 12 May 201016 May 2010

    Publication series

    NameICAPS 2010 - Proceedings of the 20th International Conference on Automated Planning and Scheduling

    Conference

    Conference20th International Conference on Automated Planning and Scheduling, ICAPS 2010
    Country/TerritoryCanada
    CityToronto, ON
    Period12/05/1016/05/10

    Fingerprint

    Dive into the research topics of 'Cost-optimal factored planning: Promises and pitfalls'. Together they form a unique fingerprint.

    Cite this