用分块优化加速双足机器人在逻辑约束下的任务与运动规划。
Accelerating Signal-Temporal-Logic-Based Task and Motion Planning of Bipedal Navigation using Benders Decomposition
- 将复杂规划问题分解为任务层与运动层迭代求解
- 相比传统方法，规划速度显著提升，满足非凸约束要求
- 适合需要快速响应的双足机器人自主导航场景
在信号时序逻辑约束下的任务与运动规划被证明是NP难问题。现有方法常将其建模为混合整数规划（MIP），但在双足步行应用中，引入如运动可达性、步态旋转等非凸约束会大幅增加MIP的计算复杂度。本文提出基于贝德斯分解（Benders Decomposition）的方法，针对整体优化问题难以求解的情形，通过迭代切平面技术将问题分解为：主问题生成满足任务规范的初步计划，子问题逐次验证运动学与动力学可行性。实验表明，该方法在处理含非线性约束的优化问题时，相较其他算法具备更快的规划速度。
原文摘要 · Abstract (English)
Task and motion planning under Signal Temporal 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。