Watershed Graphs for Faster Path Planning in Binary Occupancy Grids

  • Patrick Chisan Hew Australian Defence Science and Technology Group

Abstract

We speed up path planning in binary occupancy grids by using the watershed transform to construct a ‘watershed graph’ of the terrain’s topology, thereby cueing the path planner via a heuristic for the search, setting subgoals, or declaring cells to be blocked. Experiments with A*, Theta*, and Phi* showed that the time invested in constructing the watershed graph can be recovered when repeatedly planning paths through the same terrain, or planning paths over longer distances. Speedup factors exceeding 5× were obtained with only modest inflations in path length. This article will help developers and users of path planners who are looking to reduce runtime without disrupting their algorithm architecture.

Published
2020-10-01