  Hybrid locomotion, which combines multiple modalities of locomotion within a
single robot, enables robots to carry out complex tasks in diverse
environments. This paper presents a novel method for planning multi-modal
locomotion trajectories using approximate dynamic programming. We formulate
this problem as a shortest-path search through a state-space graph, where the
edge cost is assigned as optimal transport cost along each segment. This cost
is approximated from batches of offline trajectory optimizations, which allows
the complex effects of vehicle under-actuation and dynamic constraints to be
approximately captured in a tractable way. Our method is illustrated on a
hybrid double-integrator, an amphibious robot, and a flying-driving drone,
showing the practicality of the approach.
