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.