  Locomotion for legged robots poses considerable challenges when confronted by
obstacles and adverse environments. Footstep planners are typically only
designed for one mode of locomotion, but traversing unfavorable environments
may require several forms of locomotion to be sequenced together, such as
walking, crawling, and jumping. Multi-modal motion planners can be used to
address some of these problems, but existing implementations tend to be
time-consuming and are limited to quasi-static actions. This paper presents a
motion planning method to traverse complex environments using multiple
categories of actions. We introduce the concept of the "Possibility Graph",
which uses high-level approximations of constraint manifolds to rapidly explore
the "possibility" of actions, thereby allowing lower-level single-action motion
planners to be utilized more efficiently. We show that the Possibility Graph
can quickly find paths through several different challenging environments which
require various combinations of actions in order to traverse.
