Topology-Guided ORCA: Smooth Multi-Agent Motion Planning in Constrained Environments
作者: Fatemeh Cheraghi Pouria, Zhe Huang, Ananya Yammanuru, Shuijing Liu, Katherine Driggs-Campbell
分类: cs.RO
发布日期: 2024-07-23 (更新: 2024-08-20)
备注: Accepted by Unsolved Problems in Social Robot Navigation workshop in conjunction with RSS 2024
💡 一句话要点
提出拓扑引导的ORCA算法，解决复杂环境下多智能体平滑运动规划问题
🎯 匹配领域: 支柱一：机器人控制 (Robot Control)
关键词: 多智能体 运动规划 ORCA 拓扑引导 静态障碍物
📋 核心要点
- ORCA在复杂环境中处理静态障碍物时存在不足，容易导致智能体陷入困境，无法有效导航。
- 拓扑引导的ORCA通过构建拓扑图来表示环境的可通行区域，并利用路径规划器生成路径点引导智能体运动。
- 实验结果表明，该方法在受限环境中能够生成更平滑、自然的智能体运动，优于传统ORCA算法。
📝 摘要（中文）
本文提出了一种拓扑引导的ORCA算法，旨在替代ORCA，用于在具有静态障碍物的环境中规划平滑的多智能体运动。尽管ORCA在模拟自由空间中的多智能体群体运动方面表现出色，但在引导智能体通过静态障碍物时遇到了重大挑战。ORCA忽略静态障碍物，直到智能体过于靠近障碍物，如果障碍物拦截了智能体通往目标的路径，智能体就会陷入困境。为了解决这个问题，拓扑引导的ORCA构建了一个图来表示环境的可通行区域的拓扑结构。我们使用路径规划器来规划连接每个智能体的起点和目标位置的路径点。这些路径点被用作引导ORCA的一系列目标。在受限环境中的人群模拟实验表明，我们的方法在受限环境中生成多个智能体的平滑和自然运动方面优于ORCA，这表明拓扑引导的ORCA具有作为训练受限社交导航策略的有效模拟器的巨大潜力。
🔬 方法详解
问题定义：ORCA算法在自由空间的多智能体运动模拟中表现良好，但当环境中存在静态障碍物时，ORCA会忽略这些障碍物，直到智能体过于接近，导致智能体可能被障碍物阻挡，无法到达目标点。因此，需要解决的问题是如何在复杂、受限的环境中，使多智能体能够平滑、有效地避开静态障碍物。
核心思路：核心思路是利用环境的拓扑信息来引导ORCA算法。首先，构建一个图来表示环境的可通行区域的拓扑结构，然后使用路径规划器在该图上规划一条从起点到终点的路径，并将路径上的关键点（waypoints）作为ORCA算法的中间目标点，从而引导智能体避开障碍物，平滑地到达最终目标。
技术框架：该方法的技术框架主要包括以下几个步骤：1. 环境拓扑建模：构建环境的可通行区域的拓扑图。2. 路径规划：使用路径规划算法（如A算法）在拓扑图上规划从起点到终点的路径，生成一系列路径点。3. ORCA引导*：将路径点作为ORCA算法的中间目标点，引导智能体按照规划的路径运动。ORCA算法本身负责局部避障和速度调整。
关键创新：关键创新在于将全局拓扑信息融入到ORCA算法中。传统的ORCA算法只考虑局部避障，容易陷入局部最优。而拓扑引导的ORCA通过全局路径规划，为ORCA算法提供了一个明确的运动方向，从而避免了智能体被静态障碍物阻挡的问题。与现有方法本质区别在于，它不是直接修改ORCA的避障机制，而是通过外部的路径规划来引导ORCA的行为。
关键设计：关键设计包括：1. 拓扑图的构建方式：如何有效地表示环境的可通行区域，例如使用Voronoi图或Visibility图。2. 路径规划算法的选择：选择合适的路径规划算法，如A算法或RRT算法，以生成高质量的路径。3. 路径点的选取策略：如何选取路径上的关键点作为ORCA的中间目标点，例如根据路径的曲率或障碍物的位置来选取。4. ORCA参数的调整*：根据环境的复杂程度和智能体的数量，调整ORCA算法的参数，以获得最佳的性能。
🖼️ 关键图片
📊 实验亮点
实验结果表明，拓扑引导的ORCA算法在受限环境中能够生成更平滑、自然的智能体运动，显著优于传统的ORCA算法。具体来说，在相同环境下，拓扑引导的ORCA能够使智能体更有效地避开静态障碍物，减少碰撞的发生，并更快地到达目标点。该方法为在复杂环境中进行多智能体运动规划提供了一种有效的解决方案。
🎯 应用场景
该研究成果可应用于机器人导航、自动驾驶、游戏AI等领域。在机器人导航中，可以使机器人在复杂环境中更安全、高效地移动。在自动驾驶中，可以提高车辆在拥挤道路上的行驶安全性。在游戏AI中，可以使游戏角色更智能地避开障碍物，提高游戏体验。未来，该方法可以进一步扩展到动态环境，处理移动障碍物的情况。
📄 摘要（原文）
We present Topology-Guided ORCA as an alternative simulator to replace ORCA for planning smooth multi-agent motions in environments with static obstacles. Despite the impressive performance in simulating multi-agent crowd motion in free space, ORCA encounters a significant challenge in navigating the agents with the presence of static obstacles. ORCA ignores static obstacles until an agent gets too close to an obstacle, and the agent will get stuck if the obstacle intercepts an agent's path toward the goal. To address this challenge, Topology-Guided ORCA constructs a graph to represent the topology of the traversable region of the environment. We use a path planner to plan a path of waypoints that connects each agent's start and goal positions. The waypoints are used as a sequence of goals to guide ORCA. The experiments of crowd simulation in constrained environments show that our method outperforms ORCA in terms of generating smooth and natural motions of multiple agents in constrained environments, which indicates great potential of Topology-Guided ORCA for serving as an effective simulator for training constrained social navigation policies.