Safe LTL assumption-based planning
Alexandre Albore, Piergiorgio Bertoli · 2006
Planning for partially observable, nondeterministic domains is a very significant and computationally hard problem. Often, reasonable assumptions can be drawn over ex-pected/nominal dynamics of the domain; using them to constrain the search may lead to dramatically improve the efficiency in plan generation. In turn, the execution of assumption-based plans must be monitored to prevent run-time failures that may happen if assumptions turn out to be untrue, and to replan in that case. In this paper, we use an expressive temporal logic, LTL, to describe assump-tions, and we provide two main contributions. First, we de-scribe an effective, symbolic forward-chaining mechanism to build (conditional) assumption-based plans for partially ob-servable, nondeterministic domains. Second, we constrain the algorithm to generate safe plans, i.e. plans guaranteeing that, during their execution, the monitor will be able to univo-cally distinguish whether the domain behavior is one of those planned for or not. This is crucial to inhibit any chance of useless replanning episodes. We experimentally show that exploiting LTL assumptions highly improves the efficiency of plan generation, and that by enforcing safety we improve plan execution, inhibiting useless and expensive replanning episodes, without significantly affecting plan generation. 1