Jan Mikula presents "Robotics RG": Solving the watchman route problem on a grid with heuristic search

On 2021-11-05 09:00:00 at KN:E-128
Jan Mikula will present paper:
Seiref, S., Jaffey, T., Lopatin, M., & Felner, A. (2020). Solving the watchman
route problem on a grid with heuristic search. Proceedings International
Conference on Automated Planning and Scheduling, ICAPS, 30(Icaps), 249–257.


In this paper we optimally solve the Watchman Route Problem (WRP) on a grid. 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. We formalize WRP as a heuristic search
problem and solve it with an A*-based algorithm. We develop a series of
admissible heuristics with increasing difficulty and accuracy. In particular,
our heuristics abstract the problem into line-of-sight clusters graph. Then,
solutions for the minimum spanning tree (MST) and the traveling salesman problem
(TSP) on this graph are used as admissible heuristics for WRP. We theoretically
and experimentally study these heuristics and show that we can optimally and
suboptimally solve problems of increasing difficulties.

Link for online participation: https://meet.google.com/dss-udrm-xbo

Responsible person: Petr Pošík