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.