OBDD-Based Optimistic and Strong Cyclic Adversarial Planning

Rune Møller Jensen, Manuela M. Veloso, Michael H. Bowling

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


Recently, universal planning has become feasible through the use of efficient symbolic methods for plan generation and representation based on reduced ordered binary decision diagrams (OBDDs). In this paper, we address adversarial universal planning for multi-agent domains in which a set of uncontrollable agents may be adversarial to us. We present two new OBDD-based universal planning algorithms for such adversarial non-deterministic finite domains, namely optimistic adversarial planning and strong cyclic adversarial planning. We prove and show empirically that these algorithms extend the existing family of OBDD-based universal planning algorithms to the challenging domains with adversarial environments. We further relate adversarial planning to positive stochastic games by analyzing the properties of adversarial plans when these are considered policies for positive stochastic games. Our algorithms have been implemented within the Multiagent OBDD-based Planner, UMOP, using the Non-deterministic Agent Domain Language, NADL
Original languageEnglish
Title of host publicationProceedings of the Sixth European Conference on Planning (ECP-01)
Number of pages14
PublisherAAAI Press
Publication date2001
ISBN (Electronic)978-1-57735-629-5
Publication statusPublished - 2001
Externally publishedYes


  • Universal planning
  • Adversarial multi-agent domains
  • OBDD-based algorithms
  • Non-deterministic finite domains
  • Positive stochastic games


Dive into the research topics of 'OBDD-Based Optimistic and Strong Cyclic Adversarial Planning'. Together they form a unique fingerprint.

Cite this