A framework of Voronoi diagram for planning multiple paths in free space

Abstract

Most of the emphasis in path planning, a topic of much interest in several domains, has been on finding the optimal path or at most k optimal paths. However, in domains such as adversarial planning, one of the agents might deliberately take less optimal paths to confuse the opponent, and by the same token an agent, for inferring opponent's intent, has to consider all possible paths that the opponent might take. We introduce the notion of representative paths in free space (2D) and study the problem of computing all representative paths with different properties, such as all representative paths with at most L loops, among polygonal regions using a framework of Voronoi diagram. We prove three properties: (1) the upper and lower bounds to the number of simple paths in a Voronoi graph (2) given any path, a homotopic path can always be obtained from the Voronoi diagram of the regions and (3) all representative paths with a given property might not be always obtainable from the Voronoi graph even after searching the graph exhaustively and present an algorithm to work around this limitation. We also show how our findings can be applied for efficient entity re-identification, a problem involving a large number of dynamic entities and obstacles in the military domain.

• Voronoi diagram
• free space
• homotopy
• representative path
• number of paths
• enumerate all paths
• entity re-identification

Acknowledgements

This research was supported by participation in the Advanced Decision Architectures Collaborative Technology Alliance sponsored by the U.S. Army Research Laboratory under Cooperative Agreement DAAD19-01-2-0009.

Notes

1. There are multiple ways of defining this distance. One of them, for example, is the Hausdorff metric used in Papadopoulou and Lee (2004). However, they will all lead to a Voronoi diagram with different properties which are not relevant to our discussion. The properties of our concern are applicable to all Voronoi diagrams known to us.

2. This property is similar to that reported in a previous paper (Ó'Dúnlaing and Yap 1985) which proves that every free space path can be retracted to the Voronoi diagram. However, unlike in Ó'Dúnlaing and Yap (1985), our proof culminates in an algorithm for mapping any free space path to a homotopic path in the Voronoi diagram.

3. Since the regions may be polygonal, a shortest path might not be continuously differentiable. So instead of the normal at a corner point, we compute normals at the two neighbouring points on the two sides of the corner point. The neighbouring points are at a distance δ → 0 from the corner point.