Learning by Abstraction and Analogy: Acquiring Planning Expertise in Complex Domains

这是该奖项为期三年的第一年。要在复杂的大规模任务中进行计划，需要精心设计和昂贵的知识工程和编程，以设计和实现特定于任务的计划器。而一般规划方法由于其固有的组合搜索特性，只适用于小型约束任务。尽管现代规划者（如SIPE）已经取得了一些有价值的进展，将一般规划方法与手工制作的领域启发式相结合，但本研究考虑了一种不同的选择：集中控制知识的机器学习来指导搜索。特别是，完全实现的PRODIGY规划器为研究多种学习方法提供了理想的基础。以前基于解释的学习被成功地整合到PRODIGY中。本研究解决了用于分层规划的抽象空间的自动获取、基于案例的衍生类比学习以及它们的协同集成。在部分可分解的域中适当的抽象提供了主要的性能改进，并且自动化抽象消除了手工编码抽象的瓶颈。衍生类比提供了一种极其灵活的基于案例的重播机制，当子目标的解决方案不能转移时，可以回归到总体规划。总之，这两种方法应该被证明更加有效，抽象为基于案例的内存搜索（那些不能抽象掉的特征，比如瓶颈点或依赖网络的根）提供了关键索引，派生类比加速了抽象空间内的搜索。通过这种控制知识的自动获取，规划者将能够解决日益复杂的规划领域。

This is the first year of a three year continuing award. To plan in complex, large-scale tasks requires elaborate and costly knowledge engineering and programming to design and implement task-specific planners. General planning methods, on the other hand, apply only to small constrained tasks because of the inherent combinatiorial search. Although some worthy inroads have been made by modern planners, such as SIPE, to combine general planning methods with hand-crafted domain heuristic, This research considers a different alternative: focused machine learning of control knowledge to guide search. In particular, the fully-implemented PRODIGY planner presents the ideal substrate on which to investigate multiple learning methods. Previously explanation-based learning was successfully integrated in PRODIGY. This research addresses automated acquisition of abstraction spaces for hierarchical planning, case-based learning with derivational analogy, and their synergistic integration. Proper abstractions in partially-decomposable domains provide major performance improvements, and automated abstraction eliminates the bottleneck of laborious hand-coded abstraction. Derivational analogy provides and extremely flexible case-based replay mechanism, falling back to general planning when solution to subgoals do not transfer. Together, both methods should prove even more effective, with abstraction providing the key indices for case-based memory search (those features that cannot abstracted away, such as bottleneck points or roots of dependency networks), and derivational analogy speeding up search within abstraction spaces. Through this automated acquisition of control knowledge, planners will be able to solve increasingly complex planning domains.