OBDD-based Universal Planning for Synchronized Agents in
  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 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.
We are particularly interested in addressing the complexities arising in
non-deterministic, multi-agent domains. In this article, we present UMOP, a new
universal OBDD-based planning framework for non-deterministic, multi-agent
domains. We introduce a new planning domain description language, NADL, to
specify 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
system uses NADL and different OBDD-based universal planning algorithms. It
includes the previously developed strong and strong cyclic planning algorithms.
In addition, we introduce our new optimistic planning algorithm that relaxes
optimality guarantees and generates plausible universal plans in some domains
where no strong nor strong cyclic solution exists. We present empirical results
applying UMOP to 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.
