Shawn Seiref, Tamir Jaffey, Margarita Lopatin, Ariel Felner |
PosterID:
18
PDF
Slides
Poster
BibTeX
|
| In this paper we optimally solve the Wtachman 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. WRP is a reminiscent but is different from graph covering and mapping problems which are done online on an unknown graph. 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 experimentaly study these heuristics and show that we can optimally and suboptimally solve problems of increasing difficulties. | |
| Canb | 10/28/2020, 00:00 – 01:00 |
| 10/29/2020, 17:00 – 18:00 |
| Paris | 10/27/2020, 14:00 – 15:00 |
| 10/29/2020, 07:00 – 08:00 |
| NYC | 10/27/2020, 09:00 – 10:00 |
| 10/29/2020, 02:00 – 03:00 |
| LA | 10/27/2020, 06:00 – 07:00 |
| 10/28/2020, 23:00 – 00:00 |
Revisiting Bounded-Suboptimal Safe Interval Path Planning
Konstantin Yakovlev, Anton Andreychuk, Roni Stern
Solving the Watchman Route Problem on a Grid with Heuristic Search
Shawn Seiref, Tamir Jaffey, Margarita Lopatin, Ariel Felner
Solving the Longest Simple Path Problem with Heuristic Search
Yossi Cohen, Roni Stern, Ariel Felner
Convex Hull Monte-Carlo Tree-Search
Michael Painter, Bruno Lacerda, Nick Hawes