Multi-target search in Euclidean Space with ray shooting

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


The shortest path problem (SPP) asks us to find a minimum length path between two points, usually on a graph. In a Euclidean environment the points are in a 2D plane and here the path must avoid a set of polygonal obstacles. Solution methods for this Euclidean SPP (ESPP) typically convert the continuous 2D map into a discretised representation, like a graph or navigation mesh. RayScan is a recent and fast ESPP algorithm which avoids the preprocessing step by using a combination of “ray shooting” and polygon scanning. In this paper we improve the performance of RayScan using spatial reasoning and ray caching techniques. We also extend the algorithm, from single-target search to a multi-target setting. Comparative game map experiments show a substantial speedup.

Original languageEnglish
Title of host publicationProceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS 2021)
EditorsHang Ma, Ivan Serina
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages3
ISBN (Electronic)9781713834557, 9781577358701
Publication statusPublished - 2021
EventInternational Symposium on Combinatorial Search 2021 - Online, Guangzhou, China
Duration: 26 Jul 202130 Jul 2021
Conference number: 14th (Proceedings)

Publication series

Name14th International Symposium on Combinatorial Search, SoCS 2021
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)


ConferenceInternational Symposium on Combinatorial Search 2021
Abbreviated titleSoCS 2021
Internet address

Cite this