Towards optimal path computation in a simplicial complex

Computing optimal path in a configuration space is fundamental to solving motion planning problems in robotics and autonomy. Graph-based search algorithms have been widely used to that end, but they suffer from drawbacks. We present an algorithm for computing the shortest path through a metric simplicial complex that can be used to construct a piece-wise linear discrete model of the configuration manifold. In particular, given an undirected metric graph, G, which is constructed as a discrete representation of an underlying configuration manifold (a larger “continuous” space typically of dimension greater than one), we consider the Rips complex, [Formula: see text], associated with it. Such a complex, and hence shortest paths in it, represent the underlying metric space more closely than what the graph does. Our algorithm requires only a local connectivity-based description of an abstract graph, [Formula: see text], and a cost/length function, [Formula: see text], as inputs. No global information such as an embedding or a global coordinate chart is required. The local nature of the proposed algorithm makes it suitable for configuration spaces of arbitrary topology, geometry, and dim