Abstract
The ability to find strong solutions to fully observable nondeterministic (FOND) planning problems, if they exist, is desirable because unlike weak and strong-cyclic solutions, strong solutions are guaranteed to achieve the goal. However, only limited work has been done on FOND planning with strong solutions. In this paper, we present a sound and complete strong planning algorithm and incorporate it into our planner, FIP, which has achieved outstanding performance on strong cyclic planning problems. This new strong planning approach enables FIP to first search for strong solutions, and then search for strong-cyclic solutions only if strong solutions do not exist. We conduct extensive experiments to evaluate the new strong planning approach to (1) find a strong solution if one exists and (2) determine the non-existence of a strong solution. Experimental results demonstrate the superior performance of our planner to Gamer and MBP, the two best-known planners capable of solving strong FOND planning problems, on a variety of benchmark problems. Not only is our planner on average three orders of magnitude faster than Gamer and MBP, but it also scales up to larger problems.
Similar content being viewed by others
Abbreviations
- FOND:
-
Fully Observable Nondeterministic Planning
- LNF:
-
Least Nondeterministic First
- IEO:
-
Intended Effect Only
- FEO:
-
Failed Effect Only
- REO:
-
Random Effect Only
References
Littman, M.L., Goldsmith, J., Mundhenk, M.: The computational complexity of probabilistic planning. J. Artif. Intell. Res. 9, 1–36 (1998)
Kuter, U., Nau, D., Reisner, E., Goldman, R.P.: “Using classical planners to solve nondeterministic planning problems”. In: Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS) (2008)
Levesque, H.J.: Planning with loops. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp 509–515 (2005)
Mattmüller, D.-I.R.: “Informed Progression Search for Fully Observable Nondeterministic Planning,” Ph.D. Dissertation, Universitätsbibliothek Freiburg (2013)
Cimatti, A., Pistore, M., Roveri, M., Traverso, P.: Weak, strong, and strong cyclic planning via symbolic model checking. Artif. Intell. 147, 35–84 (2003)
Kissmann, P., Edelkamp, S.: “Solving fully-observable non-deterministic planning problems via translation into a general game”. In: Mertsching, B., Hund, M., Aziz, Z. (eds.) KI 2009: Advances in Artificial Intelligence, vol. 5803, pp 1–8. Springer, Berlin, Heidelberg (2009)
Fu, J., Ng, V., Bastani, F., Yen, I.-L.: Simple and fast strong cyclic planning for fully-observable nondeterministic planning problems. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp 1949–1954 (2011)
Hoffmann, J., Nebel, B.: The FF planning system: fast plan generation through heuristic search. J. Artif. Intell. Res. 14, 253–302 (2001)
Alford, R., Kuter, U., Nau, D., Goldman, R.P.: Plan aggregation for strong cyclic planning in nondeterministic domains. Artif. Intell. 216, 206–232 (2014)
Muise, C.J., McIlraith, S.A., Beck, J.C.: “Improved non-deterministic planning by exploiting state relevance”. In: Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS) (2012)
Edelkamp, S., Kissmann, P.: Optimal symbolic planning with action costs and preferences. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp 1690–1695 (2009)
Cimatti, A., Roveri, M.: Conformant planning via symbolic model checking. J. Artif. Intell. Res. 13, 305–338 (2000)
Shaparau, D., Pistore, M., Traverso, P.: Contingent planning with goal preferences. In: Proceedings of the National Conference on Artificial Intelligence, pp 927–934 (2006)
Bertoli, P., Cimatti, A., Roveri, M., Traverso, P.: Strong planning under partial observability. Artif. Intell. 170, 337–384 (2006)
Pistore, M., Traverso, P.: Planning as model checking for extended goals in non-deterministic domains. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp 479–486 (2001)
Dal Lago, U., Pistore, M., Traverso, P.: Planning with a language for extended goals. In: Proceedings of the AAAI Conference on Artificial Intelligence, pp 447–454 (2002)
Edelkamp, S.: Symbolic pattern databases in heuristic search planning. In: Proceedings of the Artificial Intelligence Planning Systems Conference, pp 274–283 (2002)
Edelkamp, S., Kissmann, P., Torralba, A.: BDDS strike back (in AI planning). In: Proceedings of the AAAI Conference on Artificial Intelligence, pp 4320–4321 (2015)
Kuter, U., Nau, D.: Forward-chaining planning in nondeterministic domains. In: Proceedings of the AAAI Conference on Artificial Intelligence, pp 513–518 (2004)
Kuter, U., Nau, D., Pistore, M., Traverso, P.: Task decomposition on abstract states, for planning under nondeterminism. Artif. Intell. 173, 669–695 (2009)
Jaramillo, A.C., Fu, J., Ng, V., Bastani, F.B., Yen, I.-L.: Fast strong planning for FOND problems with multi-root directed acyclic graphs. Int. J. Artif. Intell. Tools. 23 (2014)
Hoffmann, J., Brafman, R.: “Contingent planning via heuristic forward search with implicit belief states”. In: Proceedings of the International Conference on Automated Planning and Scheduling (2005)
Bryce, D., Buffet, O.: “6Th International planning competition: uncertainty part”. In: Proceedings of the International Planning Competition (2008)
Bryce, D., Buffet, O.: The Uncertainty Part of the 6th International Planning Competition 2008 (IPPC). Available: http://ippc-2008.loria.fr/wiki/index.html (2008)
Tarjan, R.: “Depth-first search and linear graph algorithms”. In: Switching and Automata Theory, 12th Annual Symposium, pp 114–121 (1971)
Bryce, D., Buffet, O.: “International planning competition uncertainty part: benchmarks and results”. In: Proceedings of the International Planning Competition (2008)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported in part by the National Institute of General Medical Sciences of the National Institutes of Health through Grant Number 8P20GM103447 and the Oklahoma Center for the Advancement of Science and Technology (OCAST HR12-036).
Rights and permissions
About this article
Cite this article
Fu, J., Calderon Jaramillo, A., Ng, V. et al. Fast strong planning for fully observable nondeterministic planning problems. Ann Math Artif Intell 78, 131–155 (2016). https://doi.org/10.1007/s10472-016-9517-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-016-9517-7