OBDD-based Universal Planning for Multiple Synchronized Agents in Non-Deterministic Domains,

Model checking representation and search techniques were recently shown to be efficiently applicable to planning, in particular to non-deterministic planning. Ordered Binary Decision Diagrams (OBDDs) encode a planning domain as a non-deterministic finite automaion (NFA) and fast algorithms from model checking search for a solution plan. With proper encodings, OBDDs can effectively scale and can provide universal plans for complex planning domains. We are particularly interested in addressing the complexities arising in non-deterministic, multi-agent domains. In this paper, we present UMOP,' a new universal OBDD-based planning framework applicable to non-deterministic and multi-agent domains, We introduce a new planning domain description language, NADL,’ to include the specification of such non-deterministic, multi-agent domains. The language contributes the explicit definition of controllable agents and uncontrollable environment agents. We describe the syntax and semantics of NADL and show how to build an efficient OBDD-based representation of an NADL description, The UMOP planning systems uses NADL and it includes the previously developed strong and strong cyclic planning algorithms. In addition, we introduce a new optimistic planning algorithm, which relaxes optimality guarantees and generates plausible universal plans in some domains where no strong or strong cyclic solution exists. We present empirical results in a previously tested non-deterministic domains. We also introduce three new multi-agent domains with complex environment actions. UMOP is shown to be a rich and efficient planning system.