Autonomous motion planning is challenging in multi-obstacle environments due to nonconvex collision avoidance constraints. Directly applying numerical solvers to these nonconvex formulations fails to exploit the constraint structures, resulting in excessive computation time. In this paper, we present an accelerated collision-free motion planner, namely regularized dual alternating direction method of multipliers (RDADMM or RDA for short), for the model predictive control (MPC) based motion planning problem. The proposed RDA addresses nonconvex motion planning via solving a smooth biconvex reformulation via duality and allows the collision avoidance constraints to be computed in parallel for each obstacle to reduce computation time significantly. We validate the performance of the RDA planner through path-tracking experiments with car-like robots in both simulation and real-world settings. Experimental results show that the proposed method generates smooth collision-free trajectories with less computation time compared with other benchmarks and performs robustly in cluttered environments. The source code is available at https://github.com/hanruihua/RDA_planner.
翻译:在多障碍物环境中自主运动规划具有挑战性,因为非凸碰撞避免约束。将数值求解器直接应用于这些非凸问题时,无法利用其约束条件,导致计算时间过长。本文提出了一种加速的无碰撞运动规划器,即正则化对偶交替方向乘子方法(RDADMM或RDA),用于模型预测控制(MPC)的运动规划问题。所提出的RDA通过对偶求解平滑双凸重构来处理非凸运动规划,可以并行计算每个障碍物的碰撞避免约束,从而显著降低计算时间。我们通过在模拟和实际环境中进行具有车辆特征的机器人路径跟踪实验,验证了RDA规划器的性能。实验结果表明,与其他基准相比,所提出的方法可以生成平稳的无碰撞轨迹,并在拥挤环境中表现出强大的鲁棒性。源代码可在 https://github.com/hanruihua/RDA_planner 获取。