Not Logged In

OBDD-Based Optimistic and Strong Cyclic Adversarial Planning

Full Text: OBDD.pdf PDF

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 adverserial 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.

Citation

R. Jensen, M. Veloso, M. Bowling. "OBDD-Based Optimistic and Strong Cyclic Adversarial Planning". European Conference on Planning (ECP), pp 265-276, September 2001.

Keywords:  
Category: In Conference

BibTeX

@incollection{Jensen+al:ECP01,
  author = {Rune Jensen and Manuela Veloso and Michael Bowling},
  title = {OBDD-Based Optimistic and Strong Cyclic Adversarial Planning},
  Pages = {265-276},
  booktitle = {European Conference on Planning (ECP)},
  year = 2001,
}

Last Updated: March 09, 2007
Submitted by AICML Admin Assistant

University of Alberta Logo AICML Logo