A Study of Heuristic Search Algorithms for Planning in Artificial Intelligence
Keywords:
Artificial Intelligence, Planning, Memory-Restricted Algorithms, FOND Planning, Non-deterministic Planning, Heuristic SearchAbstract
Planning is a long-standing area of Artificial Intelligence that aims to solve goal-directed tasks. Planning tasks have compact descriptions that generate exponentially larger state-spaces, and heuristic search algorithms are the most effective methods to solve them. In this work, we study heuristic search algorithms for planning tasks. First, we propose a hybrid memory-restricted heuristic search algorithm called PEA*+IDA* that outperforms algorithms of the same class. Second, we present a complete theoretical and experimental analysis of memory-restricted algorithms helping to better understand the landscape of this class of algorithms. Finally, we propose a new depth-first search algorithm for non-deterministic planning tasks that outperforms comparable algorithms.
Downloads
Referências
Geffner, T. and Geffner, H. (2018). Compact policies for fully observable non-deterministic planning as SAT. In International Conference on Automated Planning and Scheduling.
Hansen, E. A. and Zilberstein, S. (2001). LAO*: A Heuristic Search Algorithm that Finds Solutions with Loops. Artificial Intelligence, 129(1-2).
Hart, P. E., Nilsson, N. J., and Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2).
Helmert, M. (2006). The Fast Downward planning system. Journal of Artificial Intelligence Research, 26.
Korf, R. E. (1985). Depth-First Iterative-Deepening: An Optimal Admissible Tree Search. Artificial Intelligence, 27(1).
Muise, C., McIlraith, S. A., and Beck, J. C. (2012). Improved Non-deterministic Planning by Exploiting State Relevance. In International Conference on Automated Planning and Scheduling.
Russell, S. (1992). Efficient Memory-Bounded Search Methods. In European Conference on Artificial Intelligence.
Sen, A. K. and Bagchi, A. (1989). Fast Recursive Formulations for Best-First Search That Allow Controlled Use of Memory. In International Joint Conference on Artificial Intelligence.
Stern, R., Kulberis, T., Felner, A., and Holte, R. (2010). Using Lookaheads with Optimal Best-First Search. In AAAI Conference on Artificial Intelligence.
Sturtevant, N. and Helmert, M. (2019). Exponential-Binary State-Space Search. arxiv.org/abs/1906.02912.
Yoshizumi, T., Miura, T., and Ishida, T. (2000). A* with Partial Expansion for Large Branching Factor Problems. In AAAI Conference on Artificial Intelligence.
