From Constrained Delaunay Triangulations to Roadmap Graphs with Arbitrary Clearance
This addresses path planning for robotics or autonomous systems by enabling flexible obstacle avoidance with adjustable safety margins, though it appears incremental as it builds on constrained Delaunay triangulations.
The paper tackles the problem of building roadmap graphs for path planning around polygonal obstacles in 2D space, presenting a refinement algorithm for constrained Delaunay triangulations that generates graphs supporting arbitrary clearance distances without recomputation. The result is a simpler and significantly more efficient approach compared to existing solutions.
This work studies path planning in two-dimensional space, in the presence of polygonal obstacles. We specifically address the problem of building a roadmap graph, that is, an abstract representation of all the paths that can potentially be followed around a given set of obstacles. Our solution consists in an original refinement algorithm for constrained Delaunay triangulations, aimed at generating a roadmap graph suited for planning paths with arbitrary clearance. In other words, a minimum distance to the obstacles can be specified, and the graph does not have to be recomputed if this distance is modified. Compared to other solutions, our approach has the advantage of being simpler, as well as significantly more efficient.