Mapless Collision-Free Flight via MPC using Dual KD-Trees in Cluttered Environments

📄 arXiv: 2503.10141v3 📥 PDF

作者: Linzuo Zhang, Yu Hu, Yang Deng, Feng Yu, Danping Zou

分类: cs.RO

发布日期: 2025-03-13 (更新: 2025-08-11)

🔗 代码/项目: GITHUB

💡 一句话要点

提出基于双KD树和MPC的无地图碰撞避免飞行方法，提升复杂环境下的四旋翼飞行速度和安全性。

🎯 匹配领域: 支柱一：机器人控制 (Robot Control) 支柱二：RL算法与架构 (RL & Architecture)

关键词: 无人机 碰撞避免 模型预测控制 KD树 无地图导航 自主飞行 机器人

📋 核心要点

  1. 传统方法依赖3D地图构建和轨迹跟踪，易累积误差并产生计算延迟，限制了无人机的灵活性和安全性。
  2. 提出一种基于双KD树和模型预测控制的无地图避障方法，直接从点云和稀疏航点生成安全动作。
  3. 实验结果表明，该方法在仿真和真实环境中均优于传统方法和模仿学习方法，实现了更高的飞行速度。

📝 摘要（中文）

本文提出了一种在复杂环境中实现四旋翼无人机无碰撞飞行的新方法，无需构建详细的3D地图或生成和跟踪无碰撞轨迹。该方法利用模型预测控制（MPC）直接从稀疏航点和深度相机获取的点云生成安全动作。这些稀疏航点根据从点云检测到的附近障碍物进行在线动态调整。为此，引入了一种双KD树机制：障碍物KD树快速识别最近的障碍物以进行避障，而边缘KD树为MPC求解器提供了一个鲁棒的初始猜测，防止其在避障过程中陷入局部最小值。通过大量的仿真和真实实验验证了该方法的有效性。结果表明，该方法明显优于基于地图的方法，并且优于基于模仿学习的方法，在仿真中实现了高达12米/秒、真实测试中实现了高达6米/秒的可靠避障。该方法为现有方法提供了一种简单而鲁棒的替代方案。代码已公开。

🔬 方法详解

问题定义：现有基于地图的无人机避障方法需要构建精确的三维地图，计算量大，且地图构建过程中的误差会影响避障效果。此外，轨迹生成和跟踪的pipeline容易引入累积误差，限制了无人机在复杂环境中的快速安全飞行。因此，需要一种无需地图、直接从传感器数据进行避障的方法。

核心思路：本文的核心思路是利用模型预测控制（MPC）直接从深度相机获取的点云和稀疏航点生成安全动作，避免了地图构建和轨迹生成环节。通过在线动态调整稀疏航点，使无人机能够根据环境变化实时调整飞行路径。双KD树机制的引入，保证了MPC求解器的效率和鲁棒性。

技术框架：该方法主要包含以下几个模块：1) 点云数据获取：通过深度相机获取环境的点云数据。2) 稀疏航点生成与动态调整：根据全局规划或用户指令生成稀疏航点，并根据点云数据动态调整航点位置，使其远离障碍物。3) 双KD树构建：构建障碍物KD树和边缘KD树，分别用于快速查找最近障碍物和为MPC提供初始猜测。4) 模型预测控制：利用MPC求解器，根据当前状态、目标航点和障碍物信息，生成安全控制指令。

关键创新：该方法最重要的创新点在于提出了双KD树机制，并将其与MPC相结合。障碍物KD树能够快速找到最近的障碍物，为MPC提供避障约束；边缘KD树则为MPC提供一个良好的初始猜测，避免其陷入局部最小值。这种双KD树机制显著提高了MPC求解器的效率和鲁棒性。此外，该方法无需构建地图，直接从点云数据进行避障，降低了计算复杂度，提高了实时性。

关键设计：在MPC的设计中，需要考虑无人机的动力学模型、控制输入约束、状态约束和目标函数。目标函数通常包含跟踪目标航点的代价和避免碰撞的代价。碰撞避免代价可以通过计算无人机与障碍物之间的距离来定义。双KD树的参数设置，例如叶子节点的大小，会影响查找效率。此外，稀疏航点的密度和动态调整策略也会影响避障效果。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

该方法在仿真环境中实现了高达12 m/s的飞行速度，在真实环境中实现了高达6 m/s的飞行速度，显著优于传统的基于地图的方法和基于模仿学习的方法。实验结果表明，该方法能够有效地避开各种类型的障碍物，包括静态障碍物和动态障碍物。此外，该方法具有良好的鲁棒性，能够适应不同的环境光照条件和传感器噪声。

🎯 应用场景

该研究成果可应用于物流配送、灾害救援、环境监测等领域。在这些场景中，无人机需要在复杂、动态的环境中自主飞行，避开障碍物。该方法无需预先构建地图，能够快速适应环境变化，提高无人机的自主性和安全性。未来，该方法可以进一步扩展到多无人机协同、室内导航等更复杂的应用场景。

📄 摘要（原文）

Collision-free flight in cluttered environments is a critical capability for autonomous quadrotors. Traditional methods often rely on detailed 3D map construction, trajectory generation, and tracking. However, this cascade pipeline can introduce accumulated errors and computational delays, limiting flight agility and safety. In this paper, we propose a novel method for enabling collision-free flight in cluttered environments without explicitly constructing 3D maps or generating and tracking collision-free trajectories. Instead, we leverage Model Predictive Control (MPC) to directly produce safe actions from sparse waypoints and point clouds from a depth camera. These sparse waypoints are dynamically adjusted online based on nearby obstacles detected from point clouds. To achieve this, we introduce a dual KD-Tree mechanism: the Obstacle KD-Tree quickly identifies the nearest obstacle for avoidance, while the Edge KD-Tree provides a robust initial guess for the MPC solver, preventing it from getting stuck in local minima during obstacle avoidance. We validate our approach through extensive simulations and real-world experiments. The results show that our approach significantly outperforms the mapping-based methods and is also superior to imitation learning-based methods, demonstrating reliable obstacle avoidance at up to 12 m/s in simulations and 6 m/s in real-world tests. Our method provides a simple and robust alternative to existing methods. The code is publicly available at https://github.com/SJTU-ViSYS-team/avoid-mpc.