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

Rune Møller Jensen, Manuela M. Veloso

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


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.
Original languageEnglish
Title of host publicationProceedings of the 5th International Conference on Artificial Intelligence Planning Systems (AIPS-00)
Number of pages10
PublisherAAAI Press
Publication date2000
ISBN (Print)978-1-57735-111-5
Publication statusPublished - 2000
Externally publishedYes


  • Non-deterministic planning
  • Ordered Binary Decision Diagrams (OBDDs)
  • Multi-agent domains
  • Universal planning
  • Optimistic planning algorithm


Dive into the research topics of 'OBDD-based Universal Planning for Multiple Synchronized Agents in Non-Deterministic Domains,'. Together they form a unique fingerprint.

Cite this