Weighted real-time heuristic search

Nicolás Rivera, Jorge A. Baier, Carlos Hernández

Resultado de la investigación: Conference contribution

9 Citas (Scopus)

Resumen

Multiplying the heuristic function by a weight greater than one is a well-known technique in Heuristic Search. When applied to A* with an admissible heuristic it yields substantial runtime savings, at the expense of sacrificing solution optimality. Only a few works have studied the applicability of this technique to Real-Time Heuristic Search (RTHS), a search approach that builds upon Heuristic Search. In this paper we present two novel approaches to using weights in RTHS. The first one is a variant of a previous approach by Shimbo and Ishida. It incorporates weights to the lookahead search phase of the RTHS algorithm. The second one incorporates the weight to the edges of the search graph during the learning phase. Both techniques are applicable to a wide class of RTHS algorithms. Here we implement them within LSS-LRTA * and LRTA*-LS, obtaining a family of new algorithms. We evaluate them in path-planning benchmarks and show the second technique yields improvements of up to one order-of-magnitude both in solution cost and total search time. The first technique, on the other hand, yields poor results. Furthermore, we prove that RTHS algorithms that can appropriately use our second technique terminate finding a solution if one exists.

Idioma originalEnglish
Título de la publicación alojada12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013
EditorialInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Páginas579-586
Número de páginas8
Volumen1
EstadoPublished - 2013
Evento12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013 - Saint Paul, MN, United States
Duración: 6 may 201310 may 2013

Other

Other12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013
PaísUnited States
CiudadSaint Paul, MN
Período6/05/1310/05/13

Huella dactilar

Motion planning
Costs

ASJC Scopus subject areas

  • Artificial Intelligence

Citar esto

Rivera, N., Baier, J. A., & Hernández, C. (2013). Weighted real-time heuristic search. En 12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013 (Vol. 1, pp. 579-586). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).
Rivera, Nicolás ; Baier, Jorge A. ; Hernández, Carlos. / Weighted real-time heuristic search. 12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013. Vol. 1 International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2013. pp. 579-586
@inproceedings{b9419c45d7224acd83f806f3784eb6bd,
title = "Weighted real-time heuristic search",
abstract = "Multiplying the heuristic function by a weight greater than one is a well-known technique in Heuristic Search. When applied to A* with an admissible heuristic it yields substantial runtime savings, at the expense of sacrificing solution optimality. Only a few works have studied the applicability of this technique to Real-Time Heuristic Search (RTHS), a search approach that builds upon Heuristic Search. In this paper we present two novel approaches to using weights in RTHS. The first one is a variant of a previous approach by Shimbo and Ishida. It incorporates weights to the lookahead search phase of the RTHS algorithm. The second one incorporates the weight to the edges of the search graph during the learning phase. Both techniques are applicable to a wide class of RTHS algorithms. Here we implement them within LSS-LRTA * and LRTA*-LS, obtaining a family of new algorithms. We evaluate them in path-planning benchmarks and show the second technique yields improvements of up to one order-of-magnitude both in solution cost and total search time. The first technique, on the other hand, yields poor results. Furthermore, we prove that RTHS algorithms that can appropriately use our second technique terminate finding a solution if one exists.",
keywords = "Dijkstra's algorithm, Learning real-time, Real-time heuristic search, Weighted",
author = "Nicol{\'a}s Rivera and Baier, {Jorge A.} and Carlos Hern{\'a}ndez",
year = "2013",
language = "English",
volume = "1",
pages = "579--586",
booktitle = "12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013",
publisher = "International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)",

}

Rivera, N, Baier, JA & Hernández, C 2013, Weighted real-time heuristic search. En 12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013. vol. 1, International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), pp. 579-586, 12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013, Saint Paul, MN, United States, 6/05/13.

Weighted real-time heuristic search. / Rivera, Nicolás; Baier, Jorge A.; Hernández, Carlos.

12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013. Vol. 1 International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2013. p. 579-586.

Resultado de la investigación: Conference contribution

TY - GEN

T1 - Weighted real-time heuristic search

AU - Rivera, Nicolás

AU - Baier, Jorge A.

AU - Hernández, Carlos

PY - 2013

Y1 - 2013

N2 - Multiplying the heuristic function by a weight greater than one is a well-known technique in Heuristic Search. When applied to A* with an admissible heuristic it yields substantial runtime savings, at the expense of sacrificing solution optimality. Only a few works have studied the applicability of this technique to Real-Time Heuristic Search (RTHS), a search approach that builds upon Heuristic Search. In this paper we present two novel approaches to using weights in RTHS. The first one is a variant of a previous approach by Shimbo and Ishida. It incorporates weights to the lookahead search phase of the RTHS algorithm. The second one incorporates the weight to the edges of the search graph during the learning phase. Both techniques are applicable to a wide class of RTHS algorithms. Here we implement them within LSS-LRTA * and LRTA*-LS, obtaining a family of new algorithms. We evaluate them in path-planning benchmarks and show the second technique yields improvements of up to one order-of-magnitude both in solution cost and total search time. The first technique, on the other hand, yields poor results. Furthermore, we prove that RTHS algorithms that can appropriately use our second technique terminate finding a solution if one exists.

AB - Multiplying the heuristic function by a weight greater than one is a well-known technique in Heuristic Search. When applied to A* with an admissible heuristic it yields substantial runtime savings, at the expense of sacrificing solution optimality. Only a few works have studied the applicability of this technique to Real-Time Heuristic Search (RTHS), a search approach that builds upon Heuristic Search. In this paper we present two novel approaches to using weights in RTHS. The first one is a variant of a previous approach by Shimbo and Ishida. It incorporates weights to the lookahead search phase of the RTHS algorithm. The second one incorporates the weight to the edges of the search graph during the learning phase. Both techniques are applicable to a wide class of RTHS algorithms. Here we implement them within LSS-LRTA * and LRTA*-LS, obtaining a family of new algorithms. We evaluate them in path-planning benchmarks and show the second technique yields improvements of up to one order-of-magnitude both in solution cost and total search time. The first technique, on the other hand, yields poor results. Furthermore, we prove that RTHS algorithms that can appropriately use our second technique terminate finding a solution if one exists.

KW - Dijkstra's algorithm

KW - Learning real-time

KW - Real-time heuristic search

KW - Weighted

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

M3 - Conference contribution

AN - SCOPUS:84899445067

VL - 1

SP - 579

EP - 586

BT - 12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013

PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)

ER -

Rivera N, Baier JA, Hernández C. Weighted real-time heuristic search. En 12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013. Vol. 1. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS). 2013. p. 579-586