Online graph pruning for pathfinding on grid maps

Daniel Harabor, Alban Grastien

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

90 Citations (Scopus)

Abstract

Pathfinding in uniform-cost grid environments is a problem commonly found in application areas such as robotics and video games. The state-of-the-art is dominated by hierarchical pathfinding algorithms which are fast and have small memory overheads but usually return suboptimal paths. In this paper we present a novel search strategy, specific to grids, which is fast, optimal and requires no memory overhead. Our algorithm can be described as a macro operator which identifies and selectively expands only certain nodes in a grid map which we call jump points. Intermediate nodes on a path connecting two jump points are never expanded. We prove that this approach always computes optimal solutions and then undertake a thorough empirical analysis, comparing our method with related works from the literature. We find that searching with jump points can speed up A*by an order of magnitude and more and report significant improvement over the current state of the art.

Original languageEnglish
Title of host publicationProceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence
Place of PublicationMenlo Park, Calif
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages1114-1119
Number of pages6
Volume2
ISBN (Print)9781577355090
Publication statusPublished - 2011
Externally publishedYes
EventAAAI Conference on Artificial Intelligence 2011 - Hyatt Regency, San Francisco, United States of America
Duration: 7 Aug 201111 Aug 2011
Conference number: 25th
http://www.aaai.org/Conferences/AAAI/aaai11.php

Conference

ConferenceAAAI Conference on Artificial Intelligence 2011
Abbreviated titleAAAI 2011
CountryUnited States of America
CitySan Francisco
Period7/08/1111/08/11
Internet address

Cite this