Generating Safe Assumption-Based Plans for Partially Observable, Nondeterministic Domains

Reactive planning using assumptions is a well-known approach to tackle complex planning problems for nondeterministic, partially observable domains. However, assumptions may be wrong; this may cause an assumption-based plan to fail. In general, it is not possible to decide at runtime whether an assumption has failed and is putting at danger the success of the plan; thus, plan execution has to be controlled taking into account every possible success-endangering assumption failure. The possibility of tracing such failures strongly depends on the actions performed by the plan. In this paper, focusing on a simple assumption language, we provide two main contributions. First, we formally characterize "safe" assumption-based plans, i.e. plans that not only succeed whenever the assumption holds, but also guarantee that any success-endangering assumption failure is traced by a suitable monitor. In this way, replanning may be triggered only when actually needed. Second, we extend the planner in a reactive platform in order to produce safe assumption-based plans. We experimentally show that safe assumption-based (re)planning is a good alternative to its unsafe counterpart, minimizing the need for replanning while retaining the efficiency in plan generation