  Trajectory planning tasks for non-holonomic or collaborative systems are
naturally modeled by state spaces with non-Euclidean metrics. However, existing
proofs of convergence for sample-based motion planners only consider the
setting of Euclidean state spaces. We resolve this issue by formulating a
flexible framework and set of assumptions for which the widely-used PRM*, RRT,
and RRT* algorithms remain asymptotically optimal in the non-Euclidean setting.
The framework is compatible with collaborative trajectory planning: given a
fleet of robotic systems that individually satisfy our assumptions, we show
that the corresponding collaborative system again satisfies the assumptions and
therefore has guaranteed convergence for the trajectory-finding methods. Our
joint state space construction builds in a coupling parameter $1\leq p\leq
\infty$, which interpolates between a preference for minimizing total energy at
one extreme and a preference for minimizing the travel time at the opposite
extreme. We illustrate our theory with trajectory planning for simple coupled
systems, fleets of Reeds-Shepp vehicles, and a highly non-Euclidean fractal
space.
