Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

Forward-chaining partial-order planning

Coles, A. J. and Coles, A. I. and Fox, M. and Long, D. (2010) Forward-chaining partial-order planning. In: Proceedings of the 20th international conference on automated planning and scheduling, ICAPS 2010. AAAI Press, Palo Alto. ISBN 9781577354499

[img]
Preview
PDF - Submitted Version
Download (208Kb) | 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.

    Item type: Book Section
    ID code: 40353
    Keywords: forward chaining, order planning, computer systems design, partial order planning, Electronic computers. Computer science
    Subjects: Science > Mathematics > Electronic computers. Computer science
    Department: Faculty of Science > Computer and Information Sciences
    Related URLs:
    Depositing user: Pure Administrator
    Date Deposited: 06 Jul 2012 14:50
    Last modified: 02 Feb 2014 15:52
    URI: http://strathprints.strath.ac.uk/id/eprint/40353

    Actions (login required)

    View Item

    Fulltext Downloads: