Paper Info
Title
OBDD-based universal planning for synchronized agents in non-deterministic domains
Abstract
Recently model checking representation and search techniques were shown to be efficiently applicable to planning, in particular to non-deterministic planning. Such planning approaches use Ordered Binary Decision Diagrams (OBDDS) to encode a planning domain as a non-deterministic finite automaton and then apply fast algorithms from model checking to search for a solution. 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 article, we present UMOP, a new universal OBDD-based planning framework for non-deterministic, multi-agent domains. We introduce a new planning domain description language, NADL, to specify 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 system uses NADL and different OBDD-based universal planning algorithms. It includes the previously developed strong and strong cyclic planning algorithms. In addition, we introduce our new optimistic planning algorithm that relaxes optimality guarantees and generates plausible universal plans in some domains where no strong nor strong cyclic solution exists. We present empirical results applying UMOP to domains ranging from deterministic and single-agent with no environment actions to non-deterministic and multi-agent with complex environment actions. UMOP is shown to be a rich and efficient planning system.
Year
DOI
Venue
2011
10.1613/jair.649
Journal of Artificial Intelligence Research
Keywords
DocType
Volume
non-deterministic domain,umop planning system,planning domain,different obdd-based universal planning,new optimistic planning algorithm,efficient planning system,new universal obdd-based planning,new planning domain description,planning approach,complex planning domain,multi-agent domain,artificial intelligent,model checking
Journal
abs/1106.0229
Issue
ISSN
Citations 
1
1076-9757
30
PageRank 
References 
Authors
1.48
35
2
Name
Order
Citations
PageRank
Rune M. Jensen11749.27
Manuela Veloso28563882.50