Forward-chaining partial-order planning

Coles, A. J. and Coles, A. I. and Fox, M. and Long, D.; Brafman, Ronen and Geffner, Hector and Hoffmann, Jorg and Kautz, Henry, eds. (2010) Forward-chaining partial-order planning. In: Proceedings of the 20th international conference on automated planning and scheduling, ICAPS 2010. AAAI Press, CAN. ISBN 9781577354499 (http://www.cis.strath.ac.uk/cis/research/publicati...)

[thumbnail of strath_cis_publication_2437.pdf]
Preview
 PDF. Filename: strath_cis_publication_2437.pdf
Accepted Author Manuscript
Download (213kB)| Preview

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.

CORE (COnnecting REpositories)