COLIN: Planning with Continuous Linear Numeric Change
COLIN: Planning with Continuous Linear Numeric Change
复制标题
DOI：
10.1613/jair.3608
复制
发表时间：
2012-05
期刊：
影响因子：
--
通讯作者：
A. Coles;A. Coles;M. Fox;D. Long
中科院分区：
文献类型：
--
作者：
A. Coles;A. Coles;M. Fox;D. Long
在本文中，我们描述了COLIN，一个前向链接的启发式搜索规划，能够推理连续线性数值变化，除了完整的时间语义的PDDL2.1。通过这项工作，我们提出了两个进步的国家的最先进的表达推理能力的规划者：连续线性变化的处理，并结合持续时间不等式，这两个都需要紧密耦合的时间和数值推理在规划过程中的持续时间相关的影响的处理。COLIN结合了FF风格的前向链搜索，使用线性规划（LP）来检查每个状态下相互作用的时间和数值约束的一致性。LP用于计算每个状态中变量值的界限，减少了应用程序需要考虑的操作范围。此外，我们开发了一个扩展的时间松弛规划图启发式的CRIKEY3，支持推理直接与连续变化。我们扩展的范围内的任务变量被认为是合适的候选人指定的梯度的连续数值变化的影响的行动。最后，我们探讨了潜在的采用混合整数规划作为优化的时间戳的行动计划中的工具，一旦一个解决方案已经找到。为了支持这一点，我们进一步贡献了选择扩展的基准域，包括连续的数字效果。我们目前的结果COLIN证明其可扩展性的基准范围内，并比较现有的国家的最先进的规划师。
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 PDDL2.1. 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.