AAAI

Association for the Advancement of Artificial Intelligence

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

Suboptimally Solving the Watchman Route Problem on a Grid with Heuristic Search

Authors

Tamir Yaffe,Shawn Skyler,Ariel Felner

SISE Department, Ben-Gurion University of the Negev, Be'er-Sheva, Israel,SISE Department, Ben-Gurion University of the Negev, Be'er-Sheva, Israel,SISE Department, Ben-Gurion University of the Negev, Be'er-Sheva, Israel


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 14

Volume

Issue:

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

Track:

Long Papers

Downloads:

Download PDF

Abstract:

In the Watchman Route Problem (WRP) we are given a grid map with obstacles and the task is to (offline) find a (shortest) path through the grid such that all cells in the map can be visually seen by at least one cell on the path. WRP was recently formalized and optimally solved with heuristic search. In this paper we show how the previous optimal methods can be relaxed and modified to obtain suboptimal solvers that are much faster than the optimal solvers without sacrificing too much the quality of the solution. In particular, we present three methods that intelligently prune away large subtrees. We then derive bounded suboptimal solvers, suboptimal solvers without bounds and anytime variants of these. All these algorithms are backed up with experimental evidence that show their benefits compared to existing approaches.

DOI:

10.1609/socs.v12i1.18557


SOCS

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