Contact Planning for Multi-Legged Robots under Constraints through Parallel MCTS 

Contact planning for multi-legged robots is a challenging sequential decision-making problem due to the interplay of gaits, footholds, configurations, and physical constraints from both the robot and the environment. Existing multi-contact planners often fail to find feasible sequences within a limited time in complex scenarios and to ensure physical possibility. We propose a parallel Monte Carlo Tree Search (MCTS)-based planner that leverages multi-constraint reachability to efficiently generate physically valid contact sequences. The method accelerates planning through a hash-driven parallel approach, prioritizing promising candidates while pruning trapped nodes via valueless node evaluation. It employs depth-first backup for long-horizon planning and uses virtual loss to balance parallel exploration. To ensure feasible transitions between contact states, we establish comprehensive reachability conditions for multi-legged robots, incorporating the presented stability, collision avoidance, kinematics, joint torques, and contact constraints into the planning framework. In experiments in sparse foothold environments, our planner outperforms mainstream contact planning approaches in traversability, solution quality and physical feasibility, while achieving a competitive planning speed. Furthermore, simulation and hardware validation on hexapod and humanoid robots exhibit successful locomotion across various terrains while satisfying constraints. 

Code is available here. github.com/BetterEthan/MCTS_Contact_Planner