Planning of Obstacle-aided Navigation for Multi-legged Robots using a Sampling-based Method over Directed Graphs

Most of the existing work in mobile robot navigation approaches the problem with the assumption of flat, rigid ground and requires avoidance of all robot-obstacle contacts. Here we develop a method that allows multi-legged robots to achieve desired dynamics by taking advantage of their interactions with obstacles. Our method utilizes a discrete-time reduced-order robophysics model which faithfully captures the obstacle-modulated, horizontal-plane robot dynamics. We discretize this reduced-order model by constructing a directed graph that can be used to approximate the long-term behaviors of our system. The directed graph allows for systematic analysis of steady-state behaviors and begins to provide guarantees on stability and robustness. Searching over the graph using sampling-based planners can provide feasible paths in the robot's gait space to achieve desired locomotion and navigation goals by exploiting robot-obstacle interactions. A standout feature of a path so found by our planning algorithm is the explicit use of obstacles to aid in the navigation. We demonstrate the capabilities of our method in finding obstacle-aided navigational strategies through simulation as well as physical experiments on a quadrupedal robot traversing over a periodic obstacle field.