点击下方
卡片
，关注
「3DCV」
公众号
选择
星标
，干货第一时间送达
来源：深蓝AI
添加小助理：cv3d001，备注：方向+学校/公司+昵称，拉你入群。文末附3D视觉行业细分群。
扫描下方二维码，加入「
3D视觉从入门到精通
」知识星球
，星球内凝聚了众多3D视觉实战问题，以及各个模块的学习资料：
近20门独家秘制视频课程
、
最新顶会论文
、计算机视觉书籍
、
优质3D视觉算法源码
等。想要入门3D视觉、做项目、搞科研，欢迎扫码加入！
导读：
多智能体路径规划(MAPF)在人工智能和多智能体路径搜索领域已被广泛研究，研究人员已经对这类算法进行了改进，使其适用于实际的非完整约束机器人。本文中，碰撞检测通过占据碰撞检测算法来实现，这提高了碰撞检测的效率。此外，为解决集中式搜索多机器人解决方案效率低下的问题，作者通过合理分组来减少集中式冲突搜索(CBS)中展开的碰撞节点数量，从而更快地获得可行结果。同时，改进了基于碰撞频率的启发式多机器人搜索以减少搜索时间。最后，作者基于多机器人路径搜索结果构建了轨迹平滑问题，并将该解决方案应用于实际机器人轨迹跟踪。作者研究为解决实际场景中非完整约束移动机器人的轨迹规划问题提供了有价值的见解。
©️【深蓝AI】编译
论文题目：
HG-CBS Planner: Heuristic Group-based Motion Planning for Multi-robot
论文
作者：Weilong Liu, Jin Wang, Kewen Zhang, et al.
多智能体路径规划（MAPF）是人工智能和机器人领域广泛研究的问题。在MAPF问题中，每个智能体需要从其初始位置移动到指定目标位置，同时避免与其他智能体发生碰撞。由于其在人工智能和机器人领域的广泛应用，近年来相关研究蓬勃发展。
为了避免规划智能体之间的冲突，研究人员定义了各种冲突约束，并开发了基于这些约束优化路径结果的算法。为了将这些方法应用于实际机器人，一些研究考虑了移动机器人的运动学约束。然而，这些改进并未考虑非完整约束移动机器人的特征，无法覆盖非完整约束移动机器人的冲突场景。后续改进虽然在搜索和碰撞避免约束添加中考虑了这一特征，但考虑非完整约束运动后，可行搜索空间减小，节点扩展复杂度随规划数量增加而上升，导致求解效率低下。因此，需要一个更高效的方法来解决这个问题。同时，有必要平衡路径规划的质量和时间成本，以获得更好的路径规划结果。
本文主要研究如何针对非完整约束移动机器人的MAPF算法使用合理的搜索加速策略，并最小化碰撞避免节点的扩展，以加速多机器路径搜索问题的中央化规划。文章的主要改进和设计思路包括:
1.
改进MAPF问题求解器中的碰撞检测方法和碰撞避免约束构建，解决多智能体全局路径搜索中出现的冲突，提高碰撞检测效率。
2.
基于序贯策略的多智能体路径规划方法。对多个机器人进行合理分组和聚类，减少潜在冲突，减少多机器人中央化路径规划所需时间。
3.
提出基于碰撞频率的启发式多机器人搜索算法。该算法在多机器人无碰撞路径搜索中引入基于碰撞频率的评估指标，估计路径上潜在碰撞的概率，提高生成多碰撞无碰撞路径的效率。
4.
通过对搜索获得的路径进行平滑处理解决平滑轨迹生成问题，并为赋予速度。最终将轨迹部署在物理阿克曼底盘机器人上，并成功跟踪取得良好效果。
本文提出了一种新颖的方法来解决多机器人路径规划问题。
该方法结合了几个关键技术，包括冲突搜索树、序贯多机器人路径规划、搜索加速和轨迹优化。
通过这些技术，我们能够以更高效和协调的方式规划多个机器人的路径。
本文重点关注非完整约束机器人。具体讨论了如何在路径搜索过程中考虑机器人的非完整运动学约束。对于单个机器人，目标是确保任意两个相邻空间之间采样的路径点满足机器人阿克曼模型的最小转弯半径要求，即机器人的运动学状态转换要求。对于多个节点，通过获得路径搜索结果后的轨迹平滑来满足全局运动学约束。在平滑过程中调整轨迹以满足整个路径操作的非完整运动学约束要求。
在定义路径搜索问题时，传统的MAPF求解器定义了不同类型的冲突，并为冲突点添加约束以避免多智能体路径之间的碰撞。然而，这些冲突并不能代表所有的机器人碰撞情况。
本文提出了一种基于非完整约束碰撞搜索树的新算法，该算法结合了离线位置表方法，通过查找存储在查找表中的机器人坐标来获取机器人在地图中占据的空间。这个算法是基于网格地图的原始磁盘传输机器人CBS的变体。本文首先基于网格体冲突树（GBCT）提出了智能体之间碰撞冲突的定义，并为每个单独规划对象执行最优路径优先级搜索，选择碰撞搜索树算法来协调多个规划对象的碰撞冲突。GBCT上的每个节点包含了智能体之间的约束集和满足这些约束的解决方案。使用障碍检查表进行碰撞检测和约束添加。
碰撞检测需要进行机器人空间检查，这可以通过在计算机图形学中离散化机器人的方向向量并将其与平移向量相结合来实现。这允许将占据空间的枚举坐标数据存储在查找表中。令表示围绕体抽象中心轴旋转后的离散方向数。通过将二维障碍物地图与这些离散体空间映射，可以在地图空间中快速识别体空间中占据的网格的具体坐标。通过简化实时几何计算或枚举操作，障碍物检测算法的复杂度可以降低到0（1）
。
■2.2 基于序贯策略的多机器人路径规划
考虑到非完整约束冲突搜索树算法与CBS算法相比，计算时间和完备性都有所降低。在存在障碍物约束的情况下，低层搜索难以加速。但在高层，通过减少可能发生碰撞的机器人数量，从而减少扩展节点的数量并增加搜索空间，这是可行的。一种常见的多智能体优化策略是序贯策略，它将完整的机器人编队划分为小的子类，使每个子类中的机器人与其他子类不发生碰撞，或者可以合并成一个整体并同步移动。
多个非完整约束移动机器人的聚类是基于参考后从低层搜索获得的单机器人路径结果。聚类的目的是减少高层搜索中机器人之间的碰撞，从而加快无碰撞路径结果的搜索。聚类后，根据排序优先级对每个聚类组进行高层搜索。高优先级聚类组被低优先级组视为动态障碍物，在低优先级聚类组执行高层搜索之前，需要添加所有具有现有路径结果的高优先级组。
具体的聚类指标可以基于在CBS算法过程中执行的基于非完整约束的时空A*路径规划，在低层搜索后获得不考虑其他机器人的单机器人路径结果。然后，基于这些单机器人路径结果和相应的时间步长，评估单个路径与其他路径之间的冲突程度，将冲突程度较低的机器人聚类到一个组中。具体的算法过程如下：
ECBS（Focal Search）是一种基于Pearl和Kim 1982年工作的有界次优搜索算法。它保持两个搜索节点列表:OPEN和FOCAL。该算法通过改进次优搜索来加速。在高低层都使用相同的次优因子w进行焦点搜索。低层ECBS为机器人搜索满足CT节点N约束的有界次优路径，使其与其他机器人路径的冲突数最小。由于焦点搜索，其中f(n)是A*算法的代价评估函数f(n) = g(n) + h(n)，代价函数d(n)是当前机器人与路径上其他机器人之间的冲突数。
对于冲突计数，需要在非完整约束移动机器人的搜索中使用改进的碰撞检测，并修改碰撞启发项。每个探索节点必须计算在当前时间区间是否与其他路径结果发生碰撞，统计所有碰撞数，并将其记录为碰撞状态启发项。还需要计算前驱探索节点与当前探索点在时间区间内是否发生碰撞，并将碰撞频率计数作为转换过程碰撞启发项。两种碰撞计算都使用基于网格的碰撞检测算法，并将两个要素组合成代价函数d(n)的估计。根据ECBS算法的证明，在有限的次优因子w范围内，一旦找到解，其成本总和不会超过最优成本总和的w倍。
基于本文的多机器人路径搜索结果，使用基于MPC的轨迹优化方法对多机器人路径搜索结果进行进一步平滑，然后将平滑的轨迹结果部署在多个物理阿克曼机器人上，执行轨迹结果，取得良好的物理验证结果。
本节通过仿真实验验证章节算法，场景为货运码头场景中的多机器人路径规划。为确保在同一组内比较路径长度和时间的有效性，对于具有相同机器人容量的组使用相同的随机数据集作为起点和终点，每个位置的平均随机偏差在5m以内。最终以多机器人路径解决速度和路径特征作为指标。
为验证本章算法相对于原始CL-CBS算法在机器人运动学和搜索效率方面的优势，在模拟的二维码头地图上进行对比实验。进行了两组实验，比较执行序贯策略后多机器人搜索的改进与随机聚类分组和无分组下的改进情况，以及有无改进启发式搜索策略的多机器人搜索算法的性能。
实验结果显示，在12个机器人的路径搜索中，合理的聚类和优先级排序可以使搜索时间比随机聚类算法减少21.9%。这表明当存在大量机器人和高空间交互密度时，合理的聚类算法确实可以减少搜索时间。然而，由于需要计算多个路径之间的耦合关系，聚类分组算法比非聚类算法耗时更多。
本研究使用了具有非完整运动学约束的多移动机器人实验平台。平台的整体功能框架由下位机、上位机和服务器组成。服务器负责通过上位机收集多个机器人的数据，并为多个机器人执行集中式轨迹规划。服务器与多个机器人之间的通信主要通过工业Wi-Fi实现。
上位机使用搭载Ubuntu 18.04操作系统的树莓派4B作为机器人操作系统（ROS）控制器。它主要运行一些复杂的机器人算法模块，包括感知和定位模块、SLAM建图模块、决策规划模块和运动控制模块。它还与底层机器和服务器进行通信。
实验测试时，机器人的最大速度和最大角速度分别设置为0.5m/s和0.6rad/s，定位精度约为3cm。作者将实验重复三次，每个机器人的平均路径规划长度为1.925m，得到如下结果：
本文改进了CL-CBS算法中用于非完整约束机器人的碰撞检测和约束添加的碰撞检测算法，并设计了合理的分组聚类方法。同时将ECBS算法的搜索加速方法应用于CL-CBS算法，取得了良好的算法加速效果。仿真和物理环境实验表明，该方法能够加速非完整约束机器人的多机器人路径规划。在仿真码头测试中，序贯策略搜索算法比原始算法的随机聚类搜索时间减少了21.9%，启发式搜索加速方法在平均搜索时间降低的同时平均规划长度减少了8.7%。
未来可以扩展方法以解决更大规模的非完整约束多机器人搜索问题。同时也可以设计更合理的轨迹优化方法用于控制模块的轨迹跟踪。
HG-CBS Planner: Heuristic Group-based Motion Planning for Multi-robot
这里给大家推荐一门我们最新的课程
