OBDD-based Universal Planning in Multi-Agent, Non-Deterministic Domains

Recently model checking representation and search techniques were shown
to be efficiently applicable to planning, in particular to non-deterministic planning. Such planning approaches use Ordered Binary Decision Diagrams (OBDDs) to encode a planning domain as a non-deterministic finite automaton (NFA) and then apply fast algorithms from model checking to search for a solution. OBDDs can effectively scale and can provide universal plans for complex planning domains. This thesis presents UMOP, a new universal OBDD-based planning framework for non-deterministic, multi-agent domains, which is also applicable to deterministic single-agent domains as a special case. A new planning domain description language, NADL’, is introduced to specify non-deterministic, multi-agent domains. The language contributes the explicit definition of controllable agents and uncontrollable environment agents. The syntax and semantics of NADL is described, and it is shown how to build an efficient OBDD-based representation of an NADL description. The UMOP planning system uses NADE and different OBDD-based universal planning algorithms. It includes the previously developed strong and strong cyclic planning algorithms. In addition, a new optimistic planning algorithm is introduced, which relaxes optimality guarantees and generates plausible universal plans in some domains where no strong or strong cyclic solution exist. Empirical results are presented from domains ranging from deterministic and single-agent with no environment actions to non-deterministic and multi-agent with complex environment actions. UMOP is shown to be a rich and efficient planning system.