Integration of a Graph-Based Path Planner and Mixed-Integer MPC for Robot Navigation in Cluttered Environments

📄 arXiv: 2504.13372v2 📥 PDF

作者: Joshua A. Robbins, Stephen J. Harnett, Andrew F. Thompson, Sean Brennan, Herschel C. Pangborn

分类: eess.SY, cs.RO

发布日期: 2025-04-17 (更新: 2025-07-25)

💡 一句话要点

提出一种基于图搜索和混合整数MPC的重规划策略，用于复杂环境下的机器人导航。

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 机器人导航 路径规划 模型预测控制 混合整数规划 重规划策略

📋 核心要点

  1. 自主机器人在不确定环境中导航需要具备更新路径规划的能力，现有方法在复杂环境下的重规划效率和全局一致性方面存在挑战。
  2. 论文提出一种多层规划框架，结合中间轴图规划器和混合整数MPC，通过检测局部环境约束下的终端约束可行性来触发全局重规划。
  3. 实验结果表明，该重规划策略能够有效地应对复杂环境中的障碍物变化，提升机器人导航的鲁棒性和效率。

📝 摘要（中文）

本文提出了一种重规划策略，用于在部分已知环境中自主移动机器人导航。该策略采用多层规划和控制框架。首先，基于已知障碍物，使用基于中间轴图的规划器定义全局路径，图中的每条边对应于一个独特的走廊。然后，混合整数模型预测控制（MPC）方法检测由全局计划导出的终端约束是否不可行，该终端约束受到局部环境的非凸描述的约束。不可行性检测触发通过中间轴图边删除进行高效的全局重规划。实验结果验证了所提出的重规划策略。

🔬 方法详解

问题定义：自主移动机器人在复杂、部分已知的环境中导航，需要能够根据新感知到的环境信息进行实时的路径重规划。现有方法可能面临以下问题：一是重规划计算量大，实时性难以保证；二是局部重规划可能导致路径偏离全局最优，出现绕远或陷入局部最优的情况。

核心思路：论文的核心思路是将全局路径规划和局部运动控制解耦，利用中间轴图规划器生成全局参考路径，并使用混合整数MPC进行局部轨迹优化和避障。当MPC检测到局部环境约束与全局路径规划的终端约束冲突时，触发全局重规划，从而保证路径的全局一致性和实时性。

技术框架：该方法包含以下几个主要模块：1) 中间轴图规划器：基于已知的环境信息构建中间轴图，生成全局参考路径。2) 混合整数MPC：根据局部环境信息，对全局参考路径进行局部优化，生成可执行的运动轨迹。3) 可行性检测模块：检测MPC的终端约束是否可行，如果不可行，则触发全局重规划。4) 重规划模块：删除中间轴图中导致不可行性的边，重新生成全局参考路径。

关键创新：该方法的主要创新在于将全局路径规划和局部运动控制相结合，并利用MPC的可行性检测结果来触发全局重规划。这种方法能够在保证路径全局一致性的同时，实现实时的路径调整，从而提高机器人在复杂环境中的导航能力。与传统的全局重规划方法相比，该方法能够更高效地应对环境变化。

关键设计：中间轴图规划器使用A算法搜索最短路径。混合整数MPC使用混合整数线性规划（MILP）来表示机器人的运动学约束和环境约束。可行性检测模块通过求解一个线性规划问题来判断MPC的终端约束是否可行。重规划模块通过删除中间轴图中导致不可行性的边，并重新运行A算法来生成新的全局参考路径。

🖼️ 关键图片

fig_0
fig_1

📊 实验亮点

论文通过实验验证了所提出的重规划策略的有效性。实验结果表明，该策略能够在复杂环境中快速生成可行的路径，并能够有效地应对障碍物的变化。具体的性能数据和对比基线在论文中进行了详细的描述，但此处未提供具体数值。

🎯 应用场景

该研究成果可应用于仓储物流、自动驾驶、家庭服务机器人等领域。在这些场景中，机器人需要在复杂、动态的环境中进行导航，并能够根据环境变化进行实时的路径调整。该方法能够提高机器人在这些场景中的导航效率和鲁棒性，降低人工干预的需求。

📄 摘要（原文）

The ability to update a path plan is a required capability for autonomous mobile robots navigating through uncertain environments. This paper proposes a re-planning strategy using a multilayer planning and control framework for cases where the robot's environment is partially known. A medial axis graph-based planner defines a global path plan based on known obstacles, where each edge in the graph corresponds to a unique corridor. A mixed-integer model predictive control (MPC) method detects if a terminal constraint derived from the global plan is infeasible, subject to a non-convex description of the local environment. Infeasibility detection is used to trigger efficient global re-planning via medial axis graph edge deletion. The proposed re-planning strategy is demonstrated experimentally.