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

Alexandre Albore and Piergiorgio Bertoli

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.