A Hybrid Evolutionary Approach for Multi Robot Coordinated Planning at Intersections
作者: Victor Parque
分类: cs.RO, cs.AI, cs.NE, math.OC, stat.CO
发布日期: 2024-12-02
备注: Paper accepted/presented as a regular paper at The Twelfth International Symposium on Computing and Networking (CANDAR 2024)
💡 一句话要点
提出一种混合进化算法，用于解决多机器人交叉路口协同规划问题。
🎯 匹配领域: 支柱一：机器人控制 (Robot Control)
关键词: 多机器人协同 运动规划 进化算法 RRT 交叉路口 路径规划
📋 核心要点
- 多机器人交叉路口协同运动规划面临计算复杂度高的挑战，尤其是在采样点数量较大时。
- 该论文提出一种混合进化算法，结合参数化格子配置和离散RRT，以实现高效的无碰撞多机器人规划。
- 实验结果表明，该算法在复杂交叉路口场景中优于其他七种相关方法，验证了其可行性和优越性。
📝 摘要（中文）
在道路、工厂和仓库中，多机器人交叉路口协同运动规划是安全移动的关键。快速探索随机树（RRT）算法在多机器人运动规划中应用广泛。然而，生成图配置空间并在复合张量配置空间中搜索，对于大量采样点而言，计算成本很高。本文提出了一种新的基于进化算法的方法，该方法使用参数化基于格子的配置和基于离散的RRT，用于交叉路口无碰撞多机器人规划。在复杂的交叉路口规划场景下的计算实验表明，与其它七种相关方法相比，该算法具有可行性和优越性。我们的结果为多机器人导航的优化方法提供了新的采样和表示机制。
🔬 方法详解
问题定义：论文旨在解决多机器人在交叉路口进行协同运动规划的问题。现有方法，特别是基于RRT的算法，在处理大量采样点时，由于需要生成和搜索高维配置空间，计算成本非常高，难以满足实时性要求。
核心思路：论文的核心思路是结合进化算法的全局搜索能力和RRT算法的快速探索能力，同时利用参数化格子配置来降低搜索空间的维度。通过进化算法优化机器人的路径，并使用RRT算法在局部进行路径规划，从而在保证规划质量的同时，降低计算复杂度。
技术框架：该算法主要包含以下几个阶段：1) 初始化：生成初始种群，每个个体代表一组机器人的路径规划方案。2) 适应度评估：评估每个个体的适应度，即路径的代价，包括路径长度、碰撞风险等。3) 选择：根据适应度选择优秀的个体，用于产生下一代。4) 交叉：对选中的个体进行交叉操作，生成新的个体。5) 变异：对新生成的个体进行变异操作，引入新的搜索方向。6) RRT局部规划：使用RRT算法对个体中的路径进行局部优化，确保路径的无碰撞性。7) 迭代：重复执行选择、交叉、变异和RRT局部规划，直到满足终止条件。
关键创新：该方法最重要的创新点在于将进化算法和RRT算法相结合，并引入了参数化格子配置。进化算法负责全局搜索，RRT算法负责局部优化，参数化格子配置则降低了搜索空间的维度，从而提高了规划效率。与传统的RRT算法相比，该方法能够更快地找到高质量的路径。
关键设计：论文中关键的设计包括：1) 参数化格子配置的设计，需要根据具体的场景进行调整，以平衡搜索空间的大小和规划精度。2) 适应度函数的设计，需要综合考虑路径长度、碰撞风险等因素，以保证规划结果的合理性。3) 进化算法的参数设置，如种群大小、交叉概率、变异概率等，需要根据具体的场景进行调整，以保证算法的收敛性和搜索效率。
🖼️ 关键图片
📊 实验亮点
实验结果表明，该算法在复杂的交叉路口规划场景中，与其它七种相关方法相比，具有显著的优势。具体而言，该算法能够在更短的时间内找到无碰撞的路径，并且路径的质量更高，例如路径长度更短、碰撞风险更低。这些结果验证了该算法的可行性和优越性。
🎯 应用场景
该研究成果可应用于各种需要多机器人协同运动规划的场景，如智能仓储、自动驾驶、柔性制造等。通过提高多机器人协同规划的效率和安全性，可以显著提升生产效率、降低运营成本，并为未来的智能交通和智能制造提供关键技术支撑。
📄 摘要（原文）
Coordinated multi-robot motion planning at intersections is key for safe mobility in roads, factories and warehouses. The rapidly exploring random tree (RRT) algorithms are popular in multi-robot motion planning. However, generating the graph configuration space and searching in the composite tensor configuration space is computationally expensive for large number of sample points. In this paper, we propose a new evolutionary-based algorithm using a parametric lattice-based configuration and the discrete-based RRT for collision-free multi-robot planning at intersections. Our computational experiments using complex planning intersection scenarios have shown the feasibility and the superiority of the proposed algorithm compared to seven other related approaches. Our results offer new sampling and representation mechanisms to render optimization-based approaches for multi-robot navigation.