Anytime focal search with applications

Liron Cohen, Matias Greco, Hang Ma, Carlos Hernandez, Ariel Felner, T. K. Satish Kumar, Sven Koenig

Resultado de la investigación: Conference contribution

Resumen

Focal search (FS) is a bounded-suboptimal search (BSS) variant of A*. Like A*, it uses an open list whose states are sorted in increasing order of their f-values. Unlike A*, it also uses a focal list containing all states from the open list whose f-values are no larger than a suboptimality factor times the smallest f-value in the open list. In this paper, we develop an anytime version of FS, called anytime FS (AFS), that is useful when deliberation time is limited. AFS finds a “good” solution quickly and refines it to better and better solutions if time allows. It does this refinement efficiently by reusing previous search efforts. On the theoretical side, we show that AFS is bounded suboptimal and that anytime potential search (ATPS/ANA*), a state-of-the-art anytime bounded-cost search (BCS) variant of A*, is a special case of AFS. In doing so, we bridge the gap between anytime search algorithms based on BSS and BCS. We also identify different properties of priority functions, used to sort the focal list, that may allow for efficient reuse of previous search efforts. On the experimental side, we demonstrate the usefulness of AFS for solving hard combinatorial problems, such as the generalized covering traveling salesman problem and the multi-agent pathfinding problem.

Idioma originalEnglish
Título de la publicación alojadaProceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018
EditoresJerome Lang
EditorialInternational Joint Conferences on Artificial Intelligence
Páginas1434-1441
Número de páginas8
Volumen2018-July
ISBN (versión digital)9780999241127
EstadoPublished - 1 ene 2018
Evento27th International Joint Conference on Artificial Intelligence, IJCAI 2018 - Stockholm, Sweden
Duración: 13 jul 201819 jul 2018

Conference

Conference27th International Joint Conference on Artificial Intelligence, IJCAI 2018
PaísSweden
CiudadStockholm
Período13/07/1819/07/18

Huella dactilar

Traveling salesman problem
Costs

ASJC Scopus subject areas

  • Artificial Intelligence

Citar esto

Cohen, L., Greco, M., Ma, H., Hernandez, C., Felner, A., Satish Kumar, T. K., & Koenig, S. (2018). Anytime focal search with applications. En J. Lang (Ed.), Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018 (Vol. 2018-July, pp. 1434-1441). International Joint Conferences on Artificial Intelligence.
Cohen, Liron ; Greco, Matias ; Ma, Hang ; Hernandez, Carlos ; Felner, Ariel ; Satish Kumar, T. K. ; Koenig, Sven. / Anytime focal search with applications. Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018. editor / Jerome Lang. Vol. 2018-July International Joint Conferences on Artificial Intelligence, 2018. pp. 1434-1441
@inproceedings{7e1bd04443ec42c0872283e17433ff44,
title = "Anytime focal search with applications",
abstract = "Focal search (FS) is a bounded-suboptimal search (BSS) variant of A*. Like A*, it uses an open list whose states are sorted in increasing order of their f-values. Unlike A*, it also uses a focal list containing all states from the open list whose f-values are no larger than a suboptimality factor times the smallest f-value in the open list. In this paper, we develop an anytime version of FS, called anytime FS (AFS), that is useful when deliberation time is limited. AFS finds a “good” solution quickly and refines it to better and better solutions if time allows. It does this refinement efficiently by reusing previous search efforts. On the theoretical side, we show that AFS is bounded suboptimal and that anytime potential search (ATPS/ANA*), a state-of-the-art anytime bounded-cost search (BCS) variant of A*, is a special case of AFS. In doing so, we bridge the gap between anytime search algorithms based on BSS and BCS. We also identify different properties of priority functions, used to sort the focal list, that may allow for efficient reuse of previous search efforts. On the experimental side, we demonstrate the usefulness of AFS for solving hard combinatorial problems, such as the generalized covering traveling salesman problem and the multi-agent pathfinding problem.",
author = "Liron Cohen and Matias Greco and Hang Ma and Carlos Hernandez and Ariel Felner and {Satish Kumar}, {T. K.} and Sven Koenig",
year = "2018",
month = "1",
day = "1",
language = "English",
volume = "2018-July",
pages = "1434--1441",
editor = "Jerome Lang",
booktitle = "Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018",
publisher = "International Joint Conferences on Artificial Intelligence",

}

Cohen, L, Greco, M, Ma, H, Hernandez, C, Felner, A, Satish Kumar, TK & Koenig, S 2018, Anytime focal search with applications. En J Lang (ed.), Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018. vol. 2018-July, International Joint Conferences on Artificial Intelligence, pp. 1434-1441, 27th International Joint Conference on Artificial Intelligence, IJCAI 2018, Stockholm, Sweden, 13/07/18.

Anytime focal search with applications. / Cohen, Liron; Greco, Matias; Ma, Hang; Hernandez, Carlos; Felner, Ariel; Satish Kumar, T. K.; Koenig, Sven.

Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018. ed. / Jerome Lang. Vol. 2018-July International Joint Conferences on Artificial Intelligence, 2018. p. 1434-1441.

Resultado de la investigación: Conference contribution

TY - GEN

T1 - Anytime focal search with applications

AU - Cohen, Liron

AU - Greco, Matias

AU - Ma, Hang

AU - Hernandez, Carlos

AU - Felner, Ariel

AU - Satish Kumar, T. K.

AU - Koenig, Sven

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Focal search (FS) is a bounded-suboptimal search (BSS) variant of A*. Like A*, it uses an open list whose states are sorted in increasing order of their f-values. Unlike A*, it also uses a focal list containing all states from the open list whose f-values are no larger than a suboptimality factor times the smallest f-value in the open list. In this paper, we develop an anytime version of FS, called anytime FS (AFS), that is useful when deliberation time is limited. AFS finds a “good” solution quickly and refines it to better and better solutions if time allows. It does this refinement efficiently by reusing previous search efforts. On the theoretical side, we show that AFS is bounded suboptimal and that anytime potential search (ATPS/ANA*), a state-of-the-art anytime bounded-cost search (BCS) variant of A*, is a special case of AFS. In doing so, we bridge the gap between anytime search algorithms based on BSS and BCS. We also identify different properties of priority functions, used to sort the focal list, that may allow for efficient reuse of previous search efforts. On the experimental side, we demonstrate the usefulness of AFS for solving hard combinatorial problems, such as the generalized covering traveling salesman problem and the multi-agent pathfinding problem.

AB - Focal search (FS) is a bounded-suboptimal search (BSS) variant of A*. Like A*, it uses an open list whose states are sorted in increasing order of their f-values. Unlike A*, it also uses a focal list containing all states from the open list whose f-values are no larger than a suboptimality factor times the smallest f-value in the open list. In this paper, we develop an anytime version of FS, called anytime FS (AFS), that is useful when deliberation time is limited. AFS finds a “good” solution quickly and refines it to better and better solutions if time allows. It does this refinement efficiently by reusing previous search efforts. On the theoretical side, we show that AFS is bounded suboptimal and that anytime potential search (ATPS/ANA*), a state-of-the-art anytime bounded-cost search (BCS) variant of A*, is a special case of AFS. In doing so, we bridge the gap between anytime search algorithms based on BSS and BCS. We also identify different properties of priority functions, used to sort the focal list, that may allow for efficient reuse of previous search efforts. On the experimental side, we demonstrate the usefulness of AFS for solving hard combinatorial problems, such as the generalized covering traveling salesman problem and the multi-agent pathfinding problem.

UR - http://www.scopus.com/inward/record.url?scp=85055698099&partnerID=8YFLogxK

M3 - Conference contribution

VL - 2018-July

SP - 1434

EP - 1441

BT - Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018

A2 - Lang, Jerome

PB - International Joint Conferences on Artificial Intelligence

ER -

Cohen L, Greco M, Ma H, Hernandez C, Felner A, Satish Kumar TK y otros. Anytime focal search with applications. En Lang J, editor, Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018. Vol. 2018-July. International Joint Conferences on Artificial Intelligence. 2018. p. 1434-1441