TY - JOUR AU - Hew, Patrick PY - 2020/10/01 Y2 - 2024/03/29 TI - Watershed Graphs for Faster Path Planning in Binary Occupancy Grids JF - Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment JA - AIIDE VL - 16 IS - 1 SE - Full Oral Papers DO - 10.1609/aiide.v16i1.7410 UR - https://ojs.aaai.org/index.php/AIIDE/article/view/7410 SP - 74-80 AB - <p class="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.</p> ER -