RI: Small: Probabilistic Planning with Reduced Models

University Of Massachusetts Amherst, Amherst MA

Investigators

Abstract

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.