Accelerating Signal-Temporal-Logic-Based Task and Motion Planning of Bipedal Navigation using Benders Decomposition

--T ask and motion planning under Signal T emporal Logic constraints is known to be NP-hard. A common class of approaches formulates these hybrid problems, which involve discrete task scheduling and continuous motion planning, as mixed-integer programs (MIP). However, in applications for bipedal locomotion, introduction of non-convex constraints such as kinematic reachability and footstep rotation exacerbates the computational complexity of MIPs. In this work, we present a method based on Benders Decomposition to address scenarios where solving the entire monolithic optimization problem is prohibitively intractable. Benders Decomposition proposes an iterative cutting-plane technique that partitions the problem into a master problem to prototype a plan that meets the task specification, and a series of subproblems for kinematics and dynamics feasibility checks. Our experiments demonstrate that this method achieves faster planning compared to alternative algorithms for solving the resulting optimization program with nonlinear constraints. A project website can be found at http: //bipedal-stl.github.io/. Note to Practitioners -- Bipedal robots are increasingly demanded in warehouses and factories for complex automation tasks such as stacking, delivering, and interacting with other robots under strict time and safety constraints. However, planning such operations under formal language instructions such as Signal T emporal Logic (STL) specifications often results in large-scale mixed-integer programs that are impractical to be solved in a timely manner . This paper introduces an accelerated task and motion planning (T AMP) approach via Benders Decomposition that splits the task into a high-level scheduling problem and lower-level motion feasibility checks, allowing practitioners to find feasible and optimal task and motion plans far more efficiently. Compared to conventional monolithic solvers or alternative decomposition methods, our approach can generate solutions more than twenty times faster while rigorously satisfying kinematic and dynamic constraints. Benchmark scenarios, including factory delivery and warehouse logistics, demonstrate how our method handles realistic automation scenarios involving long planning horizons and complicated task specifications.