OBDD-based Universal Planning: Specifying and Solving Planning Problems for Synchronized Agents in Non-Deterministic Domains
- ,
- Manuela M. Veloso
- Carnegie Mellon University
Publikation:
Konference artikel i Proceeding eller bog/rapport kapitel
Bidrag til bog/antologi
Forskning
Open Access
Resume
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 (OBDD) to encode a planning domain as a non-deterministic finite automaton (NFA) 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 chapter, we present UMOP a new universal OBDD-based planning framework for non-deterministic multi-agent domains, which is also applicable to deterministic single-agent domains as a special case, 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, which relaxes optimality guarantees and generates plausible universal plans in some domains where no strong or strong cyclic solution exist. We present empirical results from 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.<br/><br/>
Publikation information
Produktionstype
Publikation:
Konference artikel i Proceeding eller bog/rapport kapitel
Bidrag til bog/antologi
Forskning
Undertitel på værtspublikation
Recent Trends and DevelopmentsOriginalsprog
EngelskSider fra-til (Antal sider)
Sider 213-258 (36 sider)Publikationsmilepæle
- Udgivet - 1999
Publikationsstatus
Udgivet - 1999
Forlag
Springer, USA, TysklandISBN (Trykt)
978-3-540-66428-4Titel på værtspublikation
Artificial Intelligence TodayAdgang til dokumenter
Forlagets udgivne version, 328.42 KB
