Proceedings

Simple and Fast Strong Cyclic Planning for Fully-Observable Nondeterministic Planning Problems

Jicheng Fu, Vincent Ng, Farokh B. Bastani, I-Ling Yen

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 1949-1953.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-326

Abstract

We address a difficult, yet under-investigated class of planning problems: fully-observable nondeterministic (FOND) planning problems with strong cyclic solutions. The difficulty of these strong cyclic FOND planning problems stems from the large size of the state space. Hence, to achieve efficient planning, a planner has to cope with the explosion in the size of the state space by planning along the directions that allow the goal to be reached quickly. A major challenge is: how would one know which states and search directions are relevant before the search for a solution has even begun? We first describe an NDP-motivated strong cyclic algorithm that, without addressing the above challenge, can already outperform state-of-the-art FOND planners, and then extend this NDP-motivated planner with a novel heuristic that addresses the challenge.

Jicheng Fu, Vincent Ng, Farokh B. Bastani, and I-Ling Yen. 2011. Simple and Fast Strong Cyclic Planning for Fully-Observable Nondeterministic Planning Problems. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 1949–1953. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-326
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards