Fast Strong Planning for FOND Problems with Multi-Root Directed Acyclic Graphs

Jicheng Fu, Andres Calderon Jaramillo, Vincent Ng, Farokh B. Bastani, and I-Ling Yen.
Proceedings of the 25th IEEE International Conference on Tools in Artificial Intelligence (ICTAI), 2013.

Click here for the PDF version. The talk slides are available here.

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.

BibTeX entry

@InProceedings{Fu+al:13a,
  author = {Jicheng Fu and Andres Calderon Jaramillo and Vincent Ng and Farokh Bastani and I-Ling Yen},
  title = {Fast Strong Planning for FOND Problems with Multi-Root Directed Acyclic Graphs},
  booktitle = {Proceedings of the 25th IEEE International Conference on Tools in Artificial Intelligence},

  year = 2013
}