Forward-chaining partial-order planning

A. J. Coles, A. I. Coles, M. Fox, D. Long

Research output: Chapter in Book/Report/Conference proceedingOther chapter contribution

130 Citations (Scopus)
293 Downloads (Pure)

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 20th international conference on automated planning and scheduling, ICAPS 2010
EditorsRonen Brafman, Hector Geffner, Jorg Hoffmann, Henry Kautz
Place of PublicationPalo Alto
Number of pages8
Publication statusPublished - 1 May 2010
Event20th International Conference on Automated Planning and Scheduling (ICAPS 2010) - Toronto, Canada
Duration: 12 May 201016 May 2010

Conference

Conference20th International Conference on Automated Planning and Scheduling (ICAPS 2010)
CountryCanada
CityToronto
Period12/05/1016/05/10

Keywords

  • forward chaining
  • order planning
  • computer systems design
  • partial order planning

Fingerprint Dive into the research topics of 'Forward-chaining partial-order planning'. Together they form a unique fingerprint.

  • Cite this

    Coles, A. J., Coles, A. I., Fox, M., & Long, D. (2010). Forward-chaining partial-order planning. In R. Brafman, H. Geffner, J. Hoffmann, & H. Kautz (Eds.), Proceedings of the 20th international conference on automated planning and scheduling, ICAPS 2010