AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Symposium on Combinatorial Search, 14

Multi-Target Search in Euclidean Space with Ray Shooting

Authors

Ryan Hechenberger,Daniel D. Harabor,Muhammad Aamir Cheema,Peter J. Stuckey,Pierre Le Bodic

Faculty of Information Technology, Monash University, Australia,Faculty of Information Technology, Monash University, Australia,Faculty of Information Technology, Monash University, Australia,Faculty of Information Technology, Monash University, Australia,Faculty of Information Technology, Monash University, Australia


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 14

Volume

Issue:

Vol. 14 No. 1 (2021): Fourteenth International Symposium on Combinatorial Search

Track:

Extended Abstracts

Downloads:

Download PDF

Abstract:

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.

DOI:

10.1609/socs.v12i1.18575


SOCS

Vol. 14 No. 1 (2021): Fourteenth International Symposium on Combinatorial Search