Fast Algorithm for Catching a Prey Quickly in Known and Partially Known Game Maps

Jorge A. Baier, Adi Botea, Daniel Harabor, Carlos Hernández

Resultado de la investigación: Article

3 Citas (Scopus)

Resumen

In moving target search, the objective is to guide a hunter agent to catch a moving prey. Even though in game applications maps are always available at developing time, current approaches to moving target search do not exploit preprocessing to improve search performance. In this paper, we propose MtsCopa, an algorithm that exploits precomputed information in the form of compressed path databases (CPDs), and that is able to guide a hunter agent in both known and partially known terrain. CPDs have previously been used in standard, fixed-target pathfinding but had not been used in the context of moving target search. We evaluated MtsCopa over standard game maps. Our speed results are orders of magnitude better than current state of the art. The time per individual move is improved, which is important in real-time search scenarios, where the time available to make a move is limited. Compared to state of the art, the number of hunter moves is often better and otherwise comparable, since CPDs provide optimal moves along shortest paths. Compared to previous successful methods, such as I-ARA∗, our method is simple to understand and implement. In addition, we prove MtsCopa always guides the agent to catch the prey when possible.

Idioma originalEnglish
Número de artículo6851877
Páginas (desde-hasta)193-199
Número de páginas7
PublicaciónIEEE Transactions on Computational Intelligence and AI in Games
Volumen7
N.º2
DOI
EstadoPublished - 1 jun 2015

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering

Citar esto

@article{c31a58fd7359407998a8ba5d40390537,
title = "Fast Algorithm for Catching a Prey Quickly in Known and Partially Known Game Maps",
abstract = "In moving target search, the objective is to guide a hunter agent to catch a moving prey. Even though in game applications maps are always available at developing time, current approaches to moving target search do not exploit preprocessing to improve search performance. In this paper, we propose MtsCopa, an algorithm that exploits precomputed information in the form of compressed path databases (CPDs), and that is able to guide a hunter agent in both known and partially known terrain. CPDs have previously been used in standard, fixed-target pathfinding but had not been used in the context of moving target search. We evaluated MtsCopa over standard game maps. Our speed results are orders of magnitude better than current state of the art. The time per individual move is improved, which is important in real-time search scenarios, where the time available to make a move is limited. Compared to state of the art, the number of hunter moves is often better and otherwise comparable, since CPDs provide optimal moves along shortest paths. Compared to previous successful methods, such as I-ARA∗, our method is simple to understand and implement. In addition, we prove MtsCopa always guides the agent to catch the prey when possible.",
keywords = "Incremental search, moving target search, navigation, path finding, predator prey games",
author = "Baier, {Jorge A.} and Adi Botea and Daniel Harabor and Carlos Hern{\'a}ndez",
year = "2015",
month = "6",
day = "1",
doi = "10.1109/TCIAIG.2014.2337889",
language = "English",
volume = "7",
pages = "193--199",
journal = "IEEE Transactions on Computational Intelligence and AI in Games",
issn = "1943-068X",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "2",

}

Fast Algorithm for Catching a Prey Quickly in Known and Partially Known Game Maps. / Baier, Jorge A.; Botea, Adi; Harabor, Daniel; Hernández, Carlos.

En: IEEE Transactions on Computational Intelligence and AI in Games, Vol. 7, N.º 2, 6851877, 01.06.2015, p. 193-199.

Resultado de la investigación: Article

TY - JOUR

T1 - Fast Algorithm for Catching a Prey Quickly in Known and Partially Known Game Maps

AU - Baier, Jorge A.

AU - Botea, Adi

AU - Harabor, Daniel

AU - Hernández, Carlos

PY - 2015/6/1

Y1 - 2015/6/1

N2 - In moving target search, the objective is to guide a hunter agent to catch a moving prey. Even though in game applications maps are always available at developing time, current approaches to moving target search do not exploit preprocessing to improve search performance. In this paper, we propose MtsCopa, an algorithm that exploits precomputed information in the form of compressed path databases (CPDs), and that is able to guide a hunter agent in both known and partially known terrain. CPDs have previously been used in standard, fixed-target pathfinding but had not been used in the context of moving target search. We evaluated MtsCopa over standard game maps. Our speed results are orders of magnitude better than current state of the art. The time per individual move is improved, which is important in real-time search scenarios, where the time available to make a move is limited. Compared to state of the art, the number of hunter moves is often better and otherwise comparable, since CPDs provide optimal moves along shortest paths. Compared to previous successful methods, such as I-ARA∗, our method is simple to understand and implement. In addition, we prove MtsCopa always guides the agent to catch the prey when possible.

AB - In moving target search, the objective is to guide a hunter agent to catch a moving prey. Even though in game applications maps are always available at developing time, current approaches to moving target search do not exploit preprocessing to improve search performance. In this paper, we propose MtsCopa, an algorithm that exploits precomputed information in the form of compressed path databases (CPDs), and that is able to guide a hunter agent in both known and partially known terrain. CPDs have previously been used in standard, fixed-target pathfinding but had not been used in the context of moving target search. We evaluated MtsCopa over standard game maps. Our speed results are orders of magnitude better than current state of the art. The time per individual move is improved, which is important in real-time search scenarios, where the time available to make a move is limited. Compared to state of the art, the number of hunter moves is often better and otherwise comparable, since CPDs provide optimal moves along shortest paths. Compared to previous successful methods, such as I-ARA∗, our method is simple to understand and implement. In addition, we prove MtsCopa always guides the agent to catch the prey when possible.

KW - Incremental search

KW - moving target search

KW - navigation

KW - path finding

KW - predator prey games

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

U2 - 10.1109/TCIAIG.2014.2337889

DO - 10.1109/TCIAIG.2014.2337889

M3 - Article

AN - SCOPUS:84933508495

VL - 7

SP - 193

EP - 199

JO - IEEE Transactions on Computational Intelligence and AI in Games

JF - IEEE Transactions on Computational Intelligence and AI in Games

SN - 1943-068X

IS - 2

M1 - 6851877

ER -