TRANSIT routing on video game maps

Leonid Antsfeld, Daniel Harabor, Toby Walsh

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearch

Abstract

TRANSIT (Bast, Funke, and Matijevic 2006) is a fast and optimal technique for computing shortest path costs in road networks. It is attractive for its usually modest memory requirements and impressive running times. In this paper we give a first analysis of TRANSIT routing on a set of popular grid-based video-game benchmarks taken from the AI pathfinding literature. We show that in the presence of path symmetries, which are inherent to most grids but normally not road networks, TRANSIT is strongly and negatively impacted, both in terms of performance and memory requirements. We address this problem by developing a new general symmetry breaking technique which adds small random ε- values to edges in the search graph, reducing the size of the TRANSIT network by up to 4 times while preserving optimality. Using our enhancements TRANSIT achieves up to four orders of magnitude speed improvement vs. A* search and uses in many cases only a small (≤ 10MB) or modest (≤ 50MB) amount of memory. We also compare TRANSIT with CPDs, a recent and very fast database-driven pathfinding approach. We find the algorithms have complementary strengths but also identify a class of problems for which TRANSIT is up to two orders of magnitude faster than CPDs using a comparable amount of memory.

Original languageEnglish
Title of host publicationProceedings of the 8th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2012
Subtitle of host publicationOctober 8–12, 2012, Stanford, California
EditorsMark Riedl, Gita Sukthankar
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages2-7
Number of pages6
ISBN (Print)9781577355823
Publication statusPublished - 2012
Externally publishedYes
EventAAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 2012 - Stanford, United States
Duration: 8 Oct 201212 Oct 2012
Conference number: 8
http://aiide12.gatech.edu/

Conference

ConferenceAAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 2012
Abbreviated titleAIIDE 2012
CountryUnited States
CityStanford
Period8/10/1212/10/12
Internet address

Cite this

Antsfeld, L., Harabor, D., & Walsh, T. (2012). TRANSIT routing on video game maps. In M. Riedl, & G. Sukthankar (Eds.), Proceedings of the 8th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2012: October 8–12, 2012, Stanford, California (pp. 2-7). Association for the Advancement of Artificial Intelligence (AAAI).
Antsfeld, Leonid ; Harabor, Daniel ; Walsh, Toby. / TRANSIT routing on video game maps. Proceedings of the 8th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2012: October 8–12, 2012, Stanford, California. editor / Mark Riedl ; Gita Sukthankar. Association for the Advancement of Artificial Intelligence (AAAI), 2012. pp. 2-7
@inproceedings{2ccddae013b540f8b0e7be5657f4a81c,
title = "TRANSIT routing on video game maps",
abstract = "TRANSIT (Bast, Funke, and Matijevic 2006) is a fast and optimal technique for computing shortest path costs in road networks. It is attractive for its usually modest memory requirements and impressive running times. In this paper we give a first analysis of TRANSIT routing on a set of popular grid-based video-game benchmarks taken from the AI pathfinding literature. We show that in the presence of path symmetries, which are inherent to most grids but normally not road networks, TRANSIT is strongly and negatively impacted, both in terms of performance and memory requirements. We address this problem by developing a new general symmetry breaking technique which adds small random ε- values to edges in the search graph, reducing the size of the TRANSIT network by up to 4 times while preserving optimality. Using our enhancements TRANSIT achieves up to four orders of magnitude speed improvement vs. A* search and uses in many cases only a small (≤ 10MB) or modest (≤ 50MB) amount of memory. We also compare TRANSIT with CPDs, a recent and very fast database-driven pathfinding approach. We find the algorithms have complementary strengths but also identify a class of problems for which TRANSIT is up to two orders of magnitude faster than CPDs using a comparable amount of memory.",
author = "Leonid Antsfeld and Daniel Harabor and Toby Walsh",
year = "2012",
language = "English",
isbn = "9781577355823",
pages = "2--7",
editor = "Riedl, {Mark } and Sukthankar, {Gita }",
booktitle = "Proceedings of the 8th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2012",
publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",
address = "United States",

}

Antsfeld, L, Harabor, D & Walsh, T 2012, TRANSIT routing on video game maps. in M Riedl & G Sukthankar (eds), Proceedings of the 8th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2012: October 8–12, 2012, Stanford, California. Association for the Advancement of Artificial Intelligence (AAAI), pp. 2-7, AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 2012, Stanford, United States, 8/10/12.

TRANSIT routing on video game maps. / Antsfeld, Leonid; Harabor, Daniel; Walsh, Toby.

Proceedings of the 8th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2012: October 8–12, 2012, Stanford, California. ed. / Mark Riedl; Gita Sukthankar. Association for the Advancement of Artificial Intelligence (AAAI), 2012. p. 2-7.

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearch

TY - GEN

T1 - TRANSIT routing on video game maps

AU - Antsfeld, Leonid

AU - Harabor, Daniel

AU - Walsh, Toby

PY - 2012

Y1 - 2012

N2 - TRANSIT (Bast, Funke, and Matijevic 2006) is a fast and optimal technique for computing shortest path costs in road networks. It is attractive for its usually modest memory requirements and impressive running times. In this paper we give a first analysis of TRANSIT routing on a set of popular grid-based video-game benchmarks taken from the AI pathfinding literature. We show that in the presence of path symmetries, which are inherent to most grids but normally not road networks, TRANSIT is strongly and negatively impacted, both in terms of performance and memory requirements. We address this problem by developing a new general symmetry breaking technique which adds small random ε- values to edges in the search graph, reducing the size of the TRANSIT network by up to 4 times while preserving optimality. Using our enhancements TRANSIT achieves up to four orders of magnitude speed improvement vs. A* search and uses in many cases only a small (≤ 10MB) or modest (≤ 50MB) amount of memory. We also compare TRANSIT with CPDs, a recent and very fast database-driven pathfinding approach. We find the algorithms have complementary strengths but also identify a class of problems for which TRANSIT is up to two orders of magnitude faster than CPDs using a comparable amount of memory.

AB - TRANSIT (Bast, Funke, and Matijevic 2006) is a fast and optimal technique for computing shortest path costs in road networks. It is attractive for its usually modest memory requirements and impressive running times. In this paper we give a first analysis of TRANSIT routing on a set of popular grid-based video-game benchmarks taken from the AI pathfinding literature. We show that in the presence of path symmetries, which are inherent to most grids but normally not road networks, TRANSIT is strongly and negatively impacted, both in terms of performance and memory requirements. We address this problem by developing a new general symmetry breaking technique which adds small random ε- values to edges in the search graph, reducing the size of the TRANSIT network by up to 4 times while preserving optimality. Using our enhancements TRANSIT achieves up to four orders of magnitude speed improvement vs. A* search and uses in many cases only a small (≤ 10MB) or modest (≤ 50MB) amount of memory. We also compare TRANSIT with CPDs, a recent and very fast database-driven pathfinding approach. We find the algorithms have complementary strengths but also identify a class of problems for which TRANSIT is up to two orders of magnitude faster than CPDs using a comparable amount of memory.

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

M3 - Conference Paper

SN - 9781577355823

SP - 2

EP - 7

BT - Proceedings of the 8th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2012

A2 - Riedl, Mark

A2 - Sukthankar, Gita

PB - Association for the Advancement of Artificial Intelligence (AAAI)

ER -

Antsfeld L, Harabor D, Walsh T. TRANSIT routing on video game maps. In Riedl M, Sukthankar G, editors, Proceedings of the 8th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2012: October 8–12, 2012, Stanford, California. Association for the Advancement of Artificial Intelligence (AAAI). 2012. p. 2-7