db-ECBS:一种考虑交互作用的多机器人运动规划新方法

《IEEE Transactions on Robotics》:db-ECBS: Interaction-Aware Multi-Robot Kinodynamic Motion Planning

【字体: 大 中 小 】 时间:2025年12月09日 来源:IEEE Transactions on Robotics 10.5

编辑推荐:

  本文推荐一种名为db-ECBS的新型运动规划算法,用于解决多机器人系统在考虑动力学和空气动力相互作用时的运动规划问题。该算法结合了Enhanced Conflict-Based Search (ECBS)、discontinuity-bounded A* (db-A*) 和非线性轨迹优化,能够在密集场景中为多达16个机器人规划出时间最优轨迹,并显著降低轨迹成本。该研究对提高多机器人系统的自主性和安全性具有重要意义。

  
在当今机器人技术快速发展的时代,多机器人系统在物流配送、协同运输和搜救任务等领域展现出广阔的应用前景。然而,当多个机器人在共享空间中协同作业时,如何规划出既满足动力学约束又能避免碰撞的轨迹,一直是个棘手难题。特别是对于空中机器人而言,当它们在近距离飞行时会产生复杂的空气动力相互作用力,这些力会显著影响飞行稳定性,但传统规划方法往往忽视这一重要因素。
现有的大多数多机器人运动规划器要么基于简化假设(如忽略机器人动力学和相互作用力),要么只能产生高度次优的解决方案。特别是在密集场景中,机器人间需要保持紧密队形时,忽略空气动力相互作用可能导致轨迹不准确甚至引发不安全状况。随着机器人数量的增加,规划问题的复杂性呈指数级增长,使得传统方法难以在合理时间内找到可行解。
针对这些挑战,来自柏林工业大学和纽约大学的研究团队在《IEEE Transactions on Robotics》上发表了题为"db-ECBS: Interaction-Aware Multi-Robot Kinodynamic Motion Planning"的研究论文。该研究提出了一种新型运动规划器db-ECBS,能够在考虑机器人动力学、驱动限制和空气动力相互作用的前提下,为异质机器人团队规划出高质量的轨迹。
为了验证db-ECBS的性能,研究团队在包含65个问题的基准测试集上进行了全面评估,涵盖了六种不同的机器人动力学模型。结果显示,与传统规划器相比,db-ECBS生成的轨迹成本降低了一半以上,且在考虑相互作用力方面表现出独特优势。
db-ECBS的核心技术方法主要包括三个层面:首先采用基于运动基元的图搜索方法为单个机器人规划轨迹,允许运动基元间存在有界不连续性;其次通过高层冲突检测与消解机制处理机器人间的碰撞和相互作用力违规问题;最后利用带有不连续性的解作为初始猜测,进行联合状态空间的轨迹优化。该方法还引入了有界次优性概念,通过子最优因子ω平衡解质量与计算效率。
在单机器人规划层面,db-ECBS采用了discontinuity-bounded A* (db-A) 算法,该算法是A算法在动力学运动规划领域的推广。与传统的A算法不同,db-A在运动基元之间允许存在有界的不连续性(由参数δ控制),这使得算法能够在连续状态空间中高效搜索可行解。运动基元是通过求解两点边值问题离线生成的短轨迹,这些轨迹尊重机器人动力学约束,并提供了良好的状态空间覆盖。
s、xg、xc和kc'>
多机器人协调层面,db-ECBS扩展了Enhanced Conflict-Based Search (ECBS) 算法,将其应用于连续领域。ECBS原本是多智能体路径查找(MAPF)问题的有界次优求解器,db-ECBS通过引入不连续性有界的概念,使其能够处理连续状态空间和动力学约束。算法维护两个优先级队列(OPEN和FOCAL),通过焦点启发式函数引导搜索过程,优先处理冲突较少的节点。
相互作用力建模方面,研究采用深度集(Deep Sets)神经网络来近似残差相互作用力ψ(·)。该模型能够根据机器人间的相对状态信息预测空气动力效应,使规划器能够在密集编队飞行中考虑这些力的影响。对于异质机器人团队,模型能够根据邻居机器人的类型和相对状态,准确估计总的相互作用力。
轨迹优化环节,db-ECBS将离散搜索得到的解作为初始猜测,在机器人的联合状态空间中进行非线性优化。优化问题考虑所有机器人的动力学约束、控制限制和碰撞避免要求,目标是最小化总到达时间或控制努力。优化过程使用微分动态规划(DDP)等数值优化方法,确保最终轨迹既平滑又可行。
研究团队在多种基准问题上对db-ECBS进行了全面评估,涵盖了经典案例、随机生成场景和真实世界应用。在经典交换位置(swap)问题中,db-ECBS在成功率和解质量方面均优于对比算法,找到了成本仅为13.3秒的解决方案,而SST*为26.9秒,S2M2为16.0秒。
在具有挑战性的凹室(alcove)场景中,一个机器人需要暂时进入凹室以让另一个机器人通过,db-ECBS展现了出色的性能,成功率为100%,而K-CBS完全失败,SST*的成功率仅为50%。db-ECBS找到的解成本为23.9秒,显著低于S2M2的29.2秒。
s和xg分别表示开始和目标状态'>
scalability测试表明,随着机器人数量增加,db-ECBS保持稳定性能。在8个机器人的随机场景中,db-ECBS的成功率达到100%,而db-CBS仅为10%,S2M2和K-CBS完全失败。对于异质机器人系统,db-ECBS同样表现优异,在8个异质机器人的场景中保持100%的成功率。
相互作用力感知能力的评估通过窗口(window)场景进行,该场景要求多个飞行机器人通过狭窄窗口,需要紧密编队飞行。db-ECBS-R(使用神经网络建模相互作用力)在8机器人场景中的成功率为100%,而db-ECBS-C(采用保守的椭球体碰撞形状假设)的成功率仅为20%。这表明在密集场景中,精确的相互作用力建模对规划成功至关重要。
k在时间步k与两个相邻机器人轨迹发生碰撞'>
实时性分析显示,db-ECBS的计算时间随机器人数量增加而增长,但仍在可接受范围内。对于16个飞行机器人的场景,离散搜索平均需要54.5秒,轨迹优化需要1030.3秒。联合状态空间优化的计算复杂度与时间步数呈线性关系,与动力学维度呈立方关系,这限制了算法在超大规模机器人团队中的应用。
算法组件的消融研究表明,在低层规划中采用重新布线(rewiring)策略比始终添加节点(always-add nodes)的策略更高效,尤其在机器人数量较多时差异更为明显。焦点启发式函数的选择也影响性能:L1启发式(逐状态检查所有机器人对碰撞)在机器人数量多时表现更好,而L2启发式(每时间步单一碰撞检查)在机器人数量少时计算更高效。
物理机器人实验验证了db-ECBS在真实环境中的有效性。在窗口场景中,8个Crazyflie 2.1无人机成功完成了位置交换任务。在异质机器人场景中,4个地面差分驱动机器人和4个飞行机器人协同工作,飞行机器人需要穿过安装在地面机器人上的竹竿,展示了算法处理复杂异质系统的能力。
理论研究证明,db-ECBS具有概率完备性(probabilistic completeness)和渐近有界次优性(asymptotically bounded suboptimality)。这意味着如果存在可行解,算法在极限情况下一定能找到它,并且解质量与最优解的差距在极限情况下趋近于零。这些理论性质使db-ECBS成为可靠的任意时间(anytime)规划器,可以在任何时候中断并返回当前最好解。
1和L2'>
尽管db-ECBS在多机器人运动规划方面取得了显著进展,但仍存在一些局限性。运动基元的生成依赖环境特性,大规模环境中需要更长的基元以提高效率。联合状态空间轨迹优化在超大规模机器人团队中计算成本高昂,限制了算法的可扩展性。未来工作可能探索生成模型(如扩散模型)来生成环境适应的运动基元,以及元优化策略来动态分组机器人。
ω*中关键组件的时间分析'>
该研究的创新点在于首次将相互作用力感知纳入多机器人运动规划框架,同时保证了算法的可扩展性和解质量。通过结合离散搜索和连续优化的优势,db-ECBS为复杂环境中的多机器人协同作业提供了实用解决方案。
研究表明,db-ECBS算法在多种测试场景中均优于现有方法,特别是在需要考虑空气动力相互作用的密集飞行场景中表现突出。算法的概率完备性和渐近有界次优性为实际应用提供了理论保证,而物理机器人实验验证了其在真实环境中的有效性。
这项研究为多机器人系统的自主协作提供了重要技术支撑,特别是在物流仓储、灾害救援等需要密集协同作业的场景中具有广泛应用前景。通过解决动力学约束和相互作用力感知等关键问题,db-ECBS推动了多机器人运动规划技术向更实用、更安全的方向发展。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号