  We present the `Basic S*' algorithm for computing shortest path through a
metric simplicial complex. In particular, given a metric graph, $G$, which is
constructed as a discrete representation of an underlying configuration space
(a larger "continuous" space/manifold typically of dimension greater than one),
we consider the Rips complex, $\mathcal{R}(G)$, associated with it. Such a
complex, and hence shortest paths in it, represent the underlying metric space
more closely than what the graph does. While discrete graph representations of
continuous spaces is convenient for motion planning in configuration spaces of
robotic systems, the metric induced in them by the ambient configuration space
is significantly different from the metric of the configuration space itself.
We remedy this problem using the simplicial complex representation. Our
algorithm requires only an abstract graph, $G=(V,E)$, and a cost/length
function, $d:E\rightarrow \mathbb{R}_+$, as inputs, and no global information
such as an embedding or a global coordinate chart is required. The complexity
of the Basic S* algorithm is comparable to that of Dijkstra's search, but, as
the results presented in this paper demonstrate, the shortest paths obtained
using the proposed algorithm represent/approximate the geodesic paths in the
original metric space significantly more closely.
