A Study of Heuristic Search Algorithms for Planning in Artificial Intelligence

Authors

  • Frederico Messa Federal University of Rio Grande do Sul
  • André G. Pereira Federal University of Rio Grande do Sul

Keywords:

Artificial Intelligence, Planning, Memory-Restricted Algorithms, FOND Planning, Non-deterministic Planning, Heuristic Search

Abstract

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

Não há dados estatísticos.

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.

Downloads

Published

2022-07-21

Como Citar

Messa, F., & G. Pereira, A. (2022). A Study of Heuristic Search Algorithms for Planning in Artificial Intelligence. Revista Eletrônica De Iniciação Científica Em Computação, 20(3). Recuperado de https://journals-sol.sbc.org.br/index.php/reic/article/view/2693

Issue

Section

Edição Especial: CTIC/CSBC