RI: Small: Probabilistic Planning with Reduced Models

概率规划对于构建能够在不确定性面前稳健运行的自主系统至关重要——从简单的家用产品到太空探索飞行器。随着这些系统执行的任务范围的扩大，计划的复杂性也在增加。该项目通过简化模型研究自动化规划的基础，简化模型包含较少的手头问题细节，从而促进更快规划算法的开发。确定性的惊人成功促使人们对简化模型的规划重新产生兴趣，它采用经典的规划技术，忽略不确定性，并在现有计划失败时在线创建新计划。这些方法在第一次国际概率规划竞赛中的成功表明了它们的巨大潜力，但最近的工作也揭示了重大的缺点。这个项目的主要目标是利用简化模型的成功规划方法所提供的见解，同时暴露并解决它们固有的缺点。特别是，该项目解决了四个关键挑战：(1)如何使用一个简化的模型进行规划，同时在一定程度上考虑完整的模型；(2)如何执行为简化模型构建的计划，同时最大限度地减少达到无有效行动可用状态的变化；(3)如何同时进行计划和执行，利用一切可用的时间来改进计划；(4)如何以一种适合于形式化分析的方式制定这种持续规划范式，从而可以在整体性能上建立保证。该项目通过引入一种新的规划范式，对这些挑战进行了全面的处理，该范式概括了确定的概念，并创建了一系列简化模型，这些模型在两个关键维度上彼此不同：在简化模型中完全考虑到的每个状态-行为对的结果数量，以及提前计划的剩余结果的出现次数。该项目为不确定性下的计划和执行提供了基本的贡献，将以前的工作放在更广泛的背景下简化模型上，并揭示了它们在实践中的有效使用。项目成果包括新的规划和计划执行算法，培训该领域的本科生和研究生，以及一系列外展活动。

Probabilistic planning is essential for the construction of autonomous systems that can operate robustly in the face of uncertainty---from simple household products to space exploration vehicles. As the range of the tasks performed by such systems grows, so does the complexity of planning. This project studies the foundations of automated planning with reduced models---models that include less detail on the problem at hand and thereby facilitate the development of faster planning algorithms. Renewed interest in planning with reduced models was prompted by the surprising success of determinization, which employs classical planning techniques that ignore uncertainty and creates new plans online whenever the exiting plan fails. The success of such methods at the first international probabilistic planning competition indicated their great potential, but recent works have also revealed significant drawbacks.The main goal of this project is to exploit the insights offered by successful methods for planning with reduced models, while exposing and addressing their inherent drawbacks. In particular, the project addresses four key challenges: (1) how to plan with a reduced model, yet factor in, to some limited extent, the complete model; (2) how to execute plans constructed for a reduced model, while minimizing the change of reaching a state for which no valid action is available; (3) how to perform planning and execution concurrently, exploiting all the available time to improve the plan; and (4) how to formulate this continual planning paradigm in a way that is amenable to a formal analysis, so that guarantees can be established on the overall performance. The project offers a comprehensive treatment of these challenges by introducing a new planning paradigm that generalizes the concept of determinization and creates a whole spectrum of reduced models that differ from each other along two key dimensions: the number of outcomes per state-action pair that are fully accounted for in the reduced model, and the number of occurrences of the remaining outcomes that are planned for in advance. The project offers fundamental contributions to planning and execution under uncertainty, placing previous works on reduced models in a broader context and shedding light on their effective use in practice. Project outcomes include new planning and plan execution algorithms, training undergraduate and graduate students in this area, and a range of outreach activities.