Dual Euclidean Shortest Path Search (Extended Abstract)
Ryan Hechenberger, Peter J. Stuckey, Pierre Le Bodic, Daniel Harabor · Proceedings of the International Symposium on Combinatorial Search · 2022
The Euclidean Shortest Path Problem (ESPP) asks us to find a minimum length path between two points on a 2D plane while avoiding a set of polygonal obstacles. Existing approaches for ESPP, based on Dijkstra or A* search, are primal methods that gradually build up longer and longer valid paths until they reach the target. In this paper we define an alternative algorithm for ESPP which can avoid this problem. Our approach starts from a path that ignores all obstacles, and generates longer and longer paths, each avoiding more obstacles, until eventually the search finds an optimal valid path.