Online computation of Euclidean Shortest Paths in two dimensions

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

Abstract

We consider the online version of Euclidean Shortest Path (ESP): a problem that asks for distance minimal trajectories between traversable pairs of points in the plane. The problem is made challenging because each trajectory must avoid a set of non-traversable obstacles represented as polygons. To solve ESP practitioners will often preprocess the environment and construct specialised data structures, such as visibility graphs and navigation meshes. Pathfinding queries on these data structures are fast but the preprocessed data becomes invalidated when obstacles move or change. In this work we propose RAYSCAN, a new algorithmic approach for ESP which is entirely online. The central idea is simple: each time we expand a node we also cast a ray toward the target. If an obstacle intersects the ray we scan its perimeter for a turning point; i.e. a vertex from which a new ray can continue unimpeded towards the target. RAYSCAN is fast, optimal and entirely online. Experiments show that it can significantly improve upon current state-of-the-art methods for ESP in cases where the set of obstacles is dynamic.

Original languageEnglish
Title of host publicationProceedings of the Thirtieth International Conference on Automated Planning and Scheduling
EditorsJ. Christopher Beck, Olivier Buffet, Jörg Hoffmann, Erez Karpas, Shirin Sohrabi
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages134-142
Number of pages9
ISBN (Electronic)9781577358244
Publication statusPublished - 1 Jun 2020
EventInternational Conference on Automated Planning and Scheduling 2020 - Nancy, France
Duration: 26 Oct 202030 Oct 2020
Conference number: 30th
https://aaai.org/ojs/index.php/ICAPS/issue/view/263 (Proceedings)
https://dblp.org/db/conf/aips/icaps2020.html (Proceedings on dblp)
https://icaps20.icaps-conference.org (Website)

Publication series

NameProceedings International Conference on Automated Planning and Scheduling, ICAPS
PublisherThe AAAI Press
Volume30
ISSN (Print)2334-0835
ISSN (Electronic)2334-0843

Conference

ConferenceInternational Conference on Automated Planning and Scheduling 2020
Abbreviated titleICAPS 2020
CountryFrance
CityNancy
Period26/10/2030/10/20
Internet address

Cite this

Hechenberger, R., Stuckey, P. J., Harabor, D., Le Bodic, P., & Cheema, M. A. (2020). Online computation of Euclidean Shortest Paths in two dimensions. In J. Christopher Beck, O. Buffet, J. Hoffmann, E. Karpas, & S. Sohrabi (Eds.), Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling (pp. 134-142). (Proceedings International Conference on Automated Planning and Scheduling, ICAPS; Vol. 30). Association for the Advancement of Artificial Intelligence (AAAI). https://aaai.org/ojs/index.php/ICAPS/article/view/6654