Watershed Graphs for Faster Path Planning in Binary Occupancy Grids


  • Patrick Chisan Hew Australian Defence Science and Technology Group


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.




How to Cite

Hew, P. (2020). Watershed Graphs for Faster Path Planning in Binary Occupancy Grids. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 16(1), 74-80. Retrieved from https://ojs.aaai.org/index.php/AIIDE/article/view/7410