Efficient Path Generation with Reduced Coordinates

Abstract

Path generation is an important problem in many fields, especially robotics. One way to create a path between a source point z and a target point y inside a complex planar domain W is to define a non-negative distance function d(y; z), such that following the negative gradient of d (by z) traces out such a path. This presents two challenges: (1) The mathematical challenge of defining d, such that d(y; z) has a single minimum at z = y for any fixed y, because the gradient-descent path may otherwise terminate at a local minimum before reaching y; (2) The computational challenge of defining d, such that it can be computed efficiently. Using the concepts of harmonic measure and f -divergence, we show how to assign a set of reduced coordinates to each point in W and to define a family of distance functions based on these coordinates, such that both the mathematical and the computational challenge are met. Since in practice, especially in robotics applications, the path is often restricted to follow the edges of a discrete network defined on a finite set of sites sampled from W, any method that works well in the continuous setting must be discretized appropriately to preserve the important properties of the continuous case. We show how to define a network connecting a finite set of sites, such that a greedy routing algorithm, which is the discrete equivalent of continuous gradient descent, based on our reduced coordinates is guaranteed to generate a path in the network between any two sites. In many cases, this network is close to a planar graph, especially if the set of sites is dense. Guaranteeing the existence of a greedy route between any two points in the graph is a significant advantage in practical applications, avoiding the complexity of other path-planning methods, such as the shortest-path and A* algorithms. While the paths generated by our algorithm are not the shortest possible, in practice we found that they are close to that.