Time-bounded adaptive A

Carlos Hernández, Jorge Baier, Tansel Uras, Sven Koenig

Resultado de la investigación: Contribución a los tipos de informe/libroContribución a la conferenciarevisión exhaustiva

6 Citas (Scopus)

Resumen

In this paper, we investigate real-time path planning in static terrain, as needed in video games. We introduce the game time model, where time is partitioned into uniform time intervals, an agent can execute one movement during each time interval, and search and movements are done in parallel. The objective is to move the agent from its start location to its goal location in as few time intervals as possible. For known terrain, we show experimentally that Time-Bounded A* (TBA*), an existing real-time search algorithm for undirected terrain, needs fewer time intervals than two state-of-the-art real-time search algorithms and about the same number of time intervals as A*. TBA*, however, cannot be used when the terrain is not known initially. For initially partially or completely unknown terrain, we thus propose a new search algorithm. Our Time-Bounded Adaptive A* (TBAA*) extends TBA* to on-line path planning with the freespace assumption by combining it with Adaptive A*. We prove that TBAA * either moves the agent from its start location to its goal location or detects that this is impossible - an important property since many existing realtime search algorithms are not able to detect efficiently that no path exists. Furthermore, TBAA* can eventually move the agent on a cost-minimal path from its start location to its goal location if it resets the agent into its start location whenever it reaches its goal location. We then show experimentally in initially partially or completely unknown terrain that TBAA* needs fewer time intervals than several state-of-the-art complete and real-time search algorithms and about the same number of time intervals as the best compared complete search algorithm, even though it has the advantage over complete search algorithms that the agent starts to move right away.

Idioma originalInglés
Título de la publicación alojada11th International Conference on Autonomous Agents and Multiagent Systems 2012, AAMAS 2012
EditorialInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Páginas224-231
Número de páginas8
Volumen1
EstadoPublicada - 2012
Evento11th International Conference on Autonomous Agents and Multiagent Systems 2012: Innovative Applications Track, AAMAS 2012 - Valencia, Espana
Duración: 4 jun 20128 jun 2012

Otros

Otros11th International Conference on Autonomous Agents and Multiagent Systems 2012: Innovative Applications Track, AAMAS 2012
País/TerritorioEspana
CiudadValencia
Período4/06/128/06/12

Áreas temáticas de ASJC Scopus

  • Inteligencia artificial

Huella

Profundice en los temas de investigación de 'Time-bounded adaptive A'. En conjunto forman una huella única.

Citar esto