C. Voss, M. Moll, and L. E. Kavraki, “A Heuristic Approach to Finding Diverse Short Paths,” in IEEE International Conference on Robotics and Automation, Seattle, WA, 2015, pp. 4173–4179.
We present an algorithm that seeks to find a set of diverse, short paths through a roadmap graph. The usefulness of a such a set is illustrated in robotic motion planning and routing applications wherein a precomputed roadmap of the environment is partially invalidated by some change, for example, relocation of obstacles or modification of the robot. Our algorithm employs the heuristic that configurations near each other are likely to be invalidated by the same change in the environment. To find short, diverse paths, the algorithm finds a detour that is the shortest path avoiding a selection of balls in the configuration space. Different collections of these balls, or simulated obstacles, yield different and diverse short paths. Paths may then be checked for validity as a cheap alternative to checking or reconstructing the entire roadmap. We describe a formal definition of path set diversity and several measures on which to evaluate our algorithm. We compare the speed and quality of our heuristic algorithm’s results against an exact algorithm that computes the optimally shortest set of paths on the roadmap having a minimum diversity. We will show that, with a tolerable loss in path shortness, our algorithm produces equally diverse path sets orders of magnitude faster.
Publisher: http://dx.doi.org/10.1109/ICRA.2015.7139774
PDF preprint: http://kavrakilab.org/publications/voss-moll2015heuristic-approach-to.pdf