Safe LTL Assumption-Based Planning

All Papers

Planning for partially observable, nondeterministic domains is a very significant and computationally hard problem. Often, reasonable assumptions can be drawn over expected/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 assumptions, and we provide two main contributions. First, we describe an effective, symbolic forward-chaining mechanism to build (conditional) assumption-based plans for partially observable, 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 univocally 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.