COLIN: Planning with Continuous Linear Numeric Change
Preprint
Abstract
In this paper we describe COLIN, a forward-chaining heuristic search planner, capable of reasoning with COntinuous LINear numeric change, in addition to the full temporal semantics of PDDL. Through this work we make two advances to the state-of-the-art in terms of expressive reasoning capabilities of planners: the handling of continuous linear change, and the handling of duration-dependent effects in combination with duration inequalities, both of which require tightly coupled temporal and numeric reasoning during planning. COLIN combines FF-style forward chaining search, with the use of a Linear Program (LP) to check the consistency of the interacting temporal and numeric constraints at each state. The LP is used to compute bounds on the values of variables in each state, reducing the range of actions that need to be considered for application. In addition, we develop an extension of the Temporal Relaxed Planning Graph heuristic of CRIKEY3, to support reasoning directly with continuous change. We extend the range of task variables considered to be suitable candidates for specifying the gradient of the continuous numeric change effected by an action. Finally, we explore the potential for employing mixed integer programming as a tool for optimising the timestamps of the actions in the plan, once a solution has been found. To support this, we further contribute a selection of extended benchmark domains that include continuous numeric effects. We present results for COLIN that demonstrate its scalability on a range of benchmarks, and compare to existing state-of-the-art planners.Keywords
All Related Versions
- Version 1, 2014-01-23, ArXiv
- Published version: Journal of Artificial Intelligence Research, 44, 1.
This publication has 21 references indexed in Scilit:
- Planning solar array operations on the international space stationACM Transactions on Intelligent Systems and Technology, 2011
- Managing concurrency in temporal planning using planner-scheduler interactionArtificial Intelligence, 2009
- Branching and pruning: An optimal temporal POCL planner based on constraint programmingArtificial Intelligence, 2006
- Processes and continuous change in a SAT-based plannerArtificial Intelligence, 2005
- PDDL2.1: An Extension to PDDL for Expressing Temporal Planning DomainsJournal of Artificial Intelligence Research, 2003
- The Metric-FF Planning System: Translating ``Ignoring Delete Lists'' to Numeric State VariablesJournal of Artificial Intelligence Research, 2003
- VHPOP: Versatile Heuristic Partial Order PlannerJournal of Artificial Intelligence Research, 2003
- Constraint-Based Attribute and Interval PlanningConstraints, 2003
- The Common Optimization INterface for Operations Research: Promoting open-source software in the operations research communityIBM Journal of Research and Development, 2003
- Uppaal in a nutshellInternational Journal on Software Tools for Technology Transfer, 1997