Planning and Acting with Nondeterministic Models

Abstract

We can model uncertainty in planning domains with nondeterministic actions, i.e., actions that can have more than one possible outcome. We can use nondeterministic models for planning (choosing which actions to perform in which circumstances) but also for acting (deciding how to perform those actions in the actor’s environment and context). Our claim is that some form of reasoning is required not only to choose actions, but also to perform actions in order to achieve the action’s intended effects.

In this talk, I will claim that, while nondeterministic models for planning are (in some cases) a design choice, they are necessary for acting. I will explain the idea of hierarchical operational models, which describe how to perform an action and organize action refinements with rich control structures. I will then briefly review some off-line and on-line planning techniques that work with nondeterministic models and that can be used for planning and acting. Finally, I will introduce the idea of (hierarchical) input/output automata and discuss how we can use them to represent operational models and to reason about them.