Planning via Petri Net Unfolding
Planning via Petri Net Unfolding
复制标题
DOI：
--
复制
发表时间：
2007-01
期刊：
影响因子：
--
通讯作者：
Sarah L. Hickmott;J. Rintanen;S. Thiébaux;L. White
中科院分区：
文献类型：
--
作者：
Sarah L. Hickmott;J. Rintanen;S. Thiébaux;L. White
Petri网的因子状态表示和并发语义与并发规划域密切相关，但规划和Petri网分析是独立发展的，很少有交叉受精的尝试，通常是不令人信服的。在本文中，我们研究和开发了这两个领域之间的关系，重点是Petri网展开，这是一种有吸引力的可达性分析方法，因为它可以自然地识别和单独解决独立的子问题。一方面，在展开的基础上，提出了一种新的成本最优部分阶规划的前向搜索方法，其效率比状态空间搜索要高得多。另一方面，受著名的规划启发式的启发，我们研究了启发式的自动生成来指导展开，从而为Petri网提供了一个更有效、更直接的可达性分析工具。
The factored state representation and concurrency semantics of Petri nets are closely related to those of concurrent planning domains, yet planning and Petri net analysis have developed independently, with minimal and usually unconvincing attempts at cross-fertilisation. In this paper, we investigate and exploit the relationship between the two areas, focusing on Petri net unfolding, which is an attractive reachability analysis method as it naturally enables the recognition and separate resolution of independent subproblems. On the one hand, based on unfolding, we develop a new forward search method for cost-optimal partial-order planning which can be exponentially more efficient than state space search. On the other hand, inspired by well-known planning heuristics, we investigate the automatic generation of heuristics to guide unfolding, resulting in a more efficient, directed reachability analysis tool for Petri nets.