Finding Diverse Paths for Robot Navigation Using a Fast Random Walk Approach

Finding a set of diverse paths among dynamic obstacles is an appealing navigation strategy for mobile robots to qualitatively reason about multiple path hypotheses to the goal. We introduce an efficient randomized approach, based on weighted random walks, that finds K diverse paths on the Voronoi diagram of the environment, where each path represents a distinct homotopy class. We show experimentally that our approach is significantly faster at finding paths of higher diversity in distinct homotopy classes than two state-of-the-art methods. Moreover, we prove that our method is probabilistically complete.