Multi-target search in Euclidean Space with ray shooting

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

Multi-target search in Euclidean Space with ray shooting

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

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Other

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.

Original language	English
Title of host publication	Proceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS 2021)
Editors	Hang Ma, Ivan Serina
Place of Publication	Palo Alto CA USA
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Pages	176-178
Number of pages	3
ISBN (Electronic)	9781713834557, 9781577358701
Publication status	Published - 2021
Event	International Symposium on Combinatorial Search 2021 - Online, Guangzhou, China Duration: 26 Jul 2021 → 30 Jul 2021 Conference number: 14th https://ojs.aaai.org/index.php/SOCS (Proceedings)

Publication series

Name	14th International Symposium on Combinatorial Search, SoCS 2021
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Number	1
Volume	12

Conference

Conference	International Symposium on Combinatorial Search 2021
Abbreviated title	SoCS 2021
Country/Territory	China
City	Guangzhou
Period	26/07/21 → 30/07/21
Internet address	https://ojs.aaai.org/index.php/SOCS (Proceedings)

Access to Document

372167938-oaFinal published version, 912 KB

https://ojs.aaai.org/index.php/SOCS/article/view/18575

Cite this

Hechenberger, R., Harabor, D. D., Cheema, M. A., Stuckey, P. J., & Le Bodic, P. (2021). Multi-target search in Euclidean Space with ray shooting. In H. Ma, & I. Serina (Eds.), Proceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS 2021) (pp. 176-178). (14th International Symposium on Combinatorial Search, SoCS 2021; Vol. 12, No. 1). Association for the Advancement of Artificial Intelligence (AAAI). https://ojs.aaai.org/index.php/SOCS/article/view/18575

Hechenberger, Ryan ; Harabor, Daniel D. ; Cheema, Muhammad Aamir et al. / Multi-target search in Euclidean Space with ray shooting. Proceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS 2021). editor / Hang Ma ; Ivan Serina. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2021. pp. 176-178 (14th International Symposium on Combinatorial Search, SoCS 2021; 1).

@inproceedings{55107f470c634ed48be7bc9f2ce5c136,

title = "Multi-target search in Euclidean Space with ray shooting",

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.",

author = "Ryan Hechenberger and Harabor, {Daniel D.} and Cheema, {Muhammad Aamir} and Stuckey, {Peter J.} and {Le Bodic}, Pierre",

note = "Publisher Copyright: Copyright {\textcopyright} 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; International Symposium on Combinatorial Search 2021, SoCS 2021 ; Conference date: 26-07-2021 Through 30-07-2021",

year = "2021",

language = "English",

series = "14th International Symposium on Combinatorial Search, SoCS 2021",

publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",

number = "1",

pages = "176--178",

editor = "Hang Ma and Ivan Serina",

booktitle = "Proceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS 2021)",

address = "United States of America",

url = "https://ojs.aaai.org/index.php/SOCS",

}

Hechenberger, R, Harabor, DD , Cheema, MA , Stuckey, PJ & Le Bodic, P 2021, Multi-target search in Euclidean Space with ray shooting. in H Ma & I Serina (eds), Proceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS 2021). 14th International Symposium on Combinatorial Search, SoCS 2021, no. 1, vol. 12, Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto CA USA, pp. 176-178, International Symposium on Combinatorial Search 2021, Guangzhou, China, 26/07/21. <https://ojs.aaai.org/index.php/SOCS/article/view/18575>

Multi-target search in Euclidean Space with ray shooting. / Hechenberger, Ryan; Harabor, Daniel D.; Cheema, Muhammad Aamir et al.

Proceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS 2021). ed. / Hang Ma; Ivan Serina. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2021. p. 176-178 (14th International Symposium on Combinatorial Search, SoCS 2021; Vol. 12, No. 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Other

TY - GEN

T1 - Multi-target search in Euclidean Space with ray shooting

AU - Hechenberger, Ryan

AU - Harabor, Daniel D.

AU - Cheema, Muhammad Aamir

AU - Stuckey, Peter J.

AU - Le Bodic, Pierre

N1 - Conference code: 14th

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

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

M3 - Conference Paper

AN - SCOPUS:85124580730

T3 - 14th International Symposium on Combinatorial Search, SoCS 2021

SP - 176

EP - 178

BT - Proceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS 2021)

A2 - Ma, Hang

A2 - Serina, Ivan

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

CY - Palo Alto CA USA

T2 - International Symposium on Combinatorial Search 2021

Y2 - 26 July 2021 through 30 July 2021

ER -

Hechenberger R, Harabor DD , Cheema MA , Stuckey PJ , Le Bodic P. Multi-target search in Euclidean Space with ray shooting. In Ma H, Serina I, editors, Proceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS 2021). Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI). 2021. p. 176-178. (14th International Symposium on Combinatorial Search, SoCS 2021; 1).

Multi-target search in Euclidean Space with ray shooting

Abstract

Publication series

Conference

Access to Document

Other files and links

A Ubiquitous System for Indoor Location-Based Services

Improved Constraint Reasoning for Robust Multi-agent Path Planning

Personalised Public Transport

Cite this

Multi-target search in Euclidean Space with ray shooting

Abstract

Publication series

Conference

Access to Document

Other files and links

Projects

A Ubiquitous System for Indoor Location-Based Services

Improved Constraint Reasoning for Robust Multi-agent Path Planning

Personalised Public Transport

Cite this