A Theory of Abstraction for Hierarchical Planning
A Theory of Abstraction for Hierarchical Planning
复制标题
分层规划的抽象理论
DOI：
10.1007/978-1-4613-1523-0_5
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
Craig A. Knoblock
中科院分区：
文献类型：
--
作者：
Craig A. Knoblock
分层规划被广泛认为是减少搜索的有效技术，但使该技术有效的属性还没有得到很好的理解。本文正式定义了分层规划，表明该技术可以减少指数搜索空间的线性，并确定了假设下，这种分析。由于这些假设将难以保证一般，本文确定的单调性属性，一个启发式评估抽象空间。最后，本文提出了一种算法，产生抽象与此属性，然后描述了该算法如何完全自动化的河内塔难题，减少了搜索空间的难题从指数线性的重新制定。
Hierarchical planning is widely acknowledged as an effective technique for reducing search, but the properties that make the technique effective are not well understood. This paper formally defines hierarchical planning, shows that the technique can reduce an exponential search space to a linear one, and identifies the assumptions under which this analysis holds. Since these assumptions would be difficult to guarantee in general, the paper identifies the monotonicity property, a heuristic for evaluating abstraction spaces. Lastly, the paper presents an algorithm for producing abstractions with this property and then describes how the algorithm completely automates a reformulation of the Tower of Hanoi puzzle, which reduces the search space of the puzzle from exponential to linear.