Forward-Chaining Partial-Order Planning

Research output: Chapter in Book/Report/Conference proceedingConference paper

207 Citations (Scopus)

Abstract

Over the last few years there has been a revival of interest in the idea of least-commitment planning with a number of researchers returning to the partial-order planning approaches of UCPOP and VHPOP. In this paper we explore the potential of a forward-chaining state-based search strategy to support partial-order planning in the solution of temporal-numeric problems. Our planner, POPF, is built on the foundations of grounded forward search, in combination with linear programming to handle continuous linear numeric change. To achieve a partial ordering we delay commitment to ordering decisions, timestamps and the values of numeric parameters, managing sets of constraints as actions are started and ended. In the context of a partially ordered collection of actions, constructing the linear program is complicated and we propose an efficient method for achieving this. Our late-commitment approach achieves flexibility, while benefiting from the informative search control of forward planning, and allows temporal and metric decisions to be made - as is most efficient - by the LP solver rather than by the discrete reasoning of the planner. We compare POPF with the approach of constructing a sequenced plan and then lifting a partial order from it, showing that our approach can offer improvements in terms of makespan, and time to find a solution, in several benchmark domains.
Original languageEnglish
Title of host publicationProceedings of the Twentieth International Conference on Automated Planning and Scheduling (ICAPS-10)
Place of PublicationMenlo Park
PublisherAAAI Press
Pages42-49
Number of pages8
ISBN (Print)9781577354499
Publication statusPublished - 2010

Fingerprint

Dive into the research topics of 'Forward-Chaining Partial-Order Planning'. Together they form a unique fingerprint.

Cite this