Title :
Fast Strong Planning for FOND Problems with Multi-root Directed Acyclic Graphs
Author :
Jicheng Fu ; Jaramillo, Andres Calderon ; Ng, Vincent ; Bastani, Farokh B. ; I-Ling Yen
Author_Institution :
Comput. Sci. Dept., Univ. of Central Oklahoma, Edmond, OK, USA
Abstract :
We present a planner for addressing a difficult, yet under-investigated class of planning problems: Fully Observable Non-Deterministic planning problems with strong solutions. Our strong planner employs a new data structure, MRDAG (multi-root directed acyclic graph), to define how the solution space should be expanded. We further equip a MRDAG with heuristics to ensure planning towards the relevant search direction. We performed extensive experiments to evaluate MRDAG and the heuristics. Results show that our strong algorithm achieves impressive performance on a variety of benchmark problems: on average it runs more than three orders of magnitude faster than the state-of-the-art planners, MBP and Gamer, and demonstrates significantly better scalability.
Keywords :
directed graphs; planning (artificial intelligence); FOND problems; Gamer planner; MBP planner; MRDAG; fast strong planning; fully observable nondeterministic planning problems; multiroot directed acyclic graphs; search direction; solution space; Aerospace electronics; Benchmark testing; Buildings; Computer science; Data structures; Manganese; Planning; Fully Observable Non-Deterministic (FOND) planning; Strong Cyclic Planning; Strong Planning;
Conference_Titel :
Tools with Artificial Intelligence (ICTAI), 2013 IEEE 25th International Conference on
Conference_Location :
Herndon, VA
Print_ISBN :
978-1-4799-2971-9
DOI :
10.1109/ICTAI.2013.23