Watershed Graphs for Faster Path Planning in Binary Occupancy Grids

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.