Caterpillar Heuristic for Gait-Free Planning With Multi-Legged Robot

In this letter, we address path planning for the quasi-static locomotion of a multi-legged walking robot on terrains with limited available footholds, such as passing a water stream over rocks. The task is to find a feasible sequence of steps to navigate the robot in environments where precise foot placement and order of the leg movements are necessary for successful traversal. A finite set of the considered footholds forms a state-space search domain, where states are defined by pairing the robot legs with footholds. The actions represent the connectivity of submanifolds of the robot configuration space approximating the robot's kinematic constraints indicating possible steps in a given stance. We propose a novel heuristic that significantly reduces the number of expanded states in the A* planner by avoiding local minima exhibited by commonly used heuristics. The computational requirements are nearly an order of magnitude lower than for the existing contact-driven solutions reported in the literature for similarly formulated planning problems. The viability of the proposed approach is further supported by an experimental deployment.

I. Introduction

Multi-legged walking robots can be considered more versatile platforms than wheeled or tracked robots as they can deliberately choose their interactions with the terrain using their legs. The enhanced locomotion capabilities come at the cost of increased computational requirements of the control and planning [1], [2]. A possible solution is to employ a regular motion gait pattern such as tripod gait that effectively transforms the multi-legged robot into a platform controllable by a velocity vector [3]. However, the robot would lose its advantage to place its legs individually on sparse footholds [4].