  We study the geodesic motion planning problem for complete Riemannian
manifolds and investigate their geodesic complexity, an integer-valued isometry
invariant introduced by D. Recio-Mitter. Using methods from Riemannian
geometry, we establish new lower and upper bounds on geodesic complexity and
compute its value for certain classes of examples with a focus on homogeneous
Riemannian manifolds. Methodically, we study properties of stratifications of
cut loci and use results on their structures for certain homogeneous manifolds
obtained by T. Sakai and others.
