OBDD-based Deterministic Planning using the UMOP Planning Framework

Model checking representation and search techniques were recently shown to be efficiently applicable to planning. Ordered Binary Decision Diagrams (OBDDs) encode a planning domain as a finite transition system and fast algorithms from model checking search for a solution plan. With proper encodings, OBDDs can effectively scale and can provide plans for complex planning domains. In this paper, we present. results obtained in classical deterministic domains using UMOP, a new universal OBDD-based planning framework applicable to non-deterministic and multi-agent domains. A key difference between UMOP and previous OBDD-based planning systems is that the OBDD encoding of planning problems is partitioned. This representation is known from model checking to scale up the problem size that. can be handled (Ranjan et al., 1995). Experimental results from the strips track of the ATPS’98 planning competition show that this is also the case for OBDD-based planning. The results further indicate that UMOP is an efficient deterministic planning system.