Forward-Chaining Partial-Order Planning

By Amanda Jane Coles, Andrew Coles, Maria Fox, Derek Long. 2010

338 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Explainable Planning (2017, methodology): “Here is the plan found by POP-F [Coles et al., 2010].”
ROSPlan: Planning in the Robot Operating System (2015, methodology): “Our objective is to provide a modular architecture into which different temporal planners can easily be plugged: for example, POPF (Coles et al. 2010) (used in the case study described in this paper) can be replaced by Temporal Fast Downward (Eyerich, Mattmüller, and Röger 2012), LPG (Gerevini and”
AUV mission control via temporal planning (2014, background): “The first step for planning an inspection task is to define an abstraction of the environment.”
Temporal Planning with Preferences and Time-Dependent Continuous Costs (2012, methodology): “In this work we build on the planner POPF (Coles et al. 2010).”