OBDD-Based Optimistic and Strong Cyclic Adversarial Planning

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

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer 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
TitelProceedings of the Sixth European Conference on Planning (ECP-01)
Antal sider14
ForlagAAAI Press
ISBN (Elektronisk)978-1-57735-629-5
StatusUdgivet - 2001
Udgivet eksterntJa


Dyk ned i forskningsemnerne om 'OBDD-Based Optimistic and Strong Cyclic Adversarial Planning'. Sammen danner de et unikt fingeraftryk.