AAAI Publications, Sixth European Conference on Planning

Font Size: 
OBDD-Based Optimistic and Strong Cyclic Adversarial Planning
Rune Møller Jensen, Manuela M. Veloso, Michael H. Bowling

Last modified: 2014-05-21


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 (as in e.g. robotics soccer). We present two new OBDD-based universal planning algorithms for such adversarial nondeterministic 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 ad- verserial 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 Multi-agent OBDD-based Planner, UMOP, using the Non-deterministic Agent Domain Language, NADL.

Full Text: PDF