Comments:

The overview focuses on the three essential challenges of multi-robot collaborative navigation——collaborative localization，path planning and task assignment, and explains technologies of them in detail respectively. The logic of the whole essay is very clear and we can see that different from reviews, the overview includes just a few critical thinking points and doesn’t explain the critical thinking points in depth.

Reading Notes:

多机器人协同导航技术综述

Overview of Multi-robot Collaborative Navigation Technology

［引用格式］张辰，周乐来，李贻斌. 多机器人协同导航技术综述［J］. 无人系统技术，2020，3（2）：1-8.

• Some of the Specialized Vocabulary:

RFID无线射频识别（radio frequency identification devices）

Robustness鲁棒性（控制系统在一定的参数摄动下，维持其某些性能与品质稳定的特性）

滚 动 时 域 估 计（Moving Horizon Estimation，MHE）

SLAM (Simultaneous Localization and Mapping),也称为CML (Concurrent Mapping and Localization) 同步/并行定位与建图

1. 三个关键问题：协同定位、路径规划和任务分配

1、多机器人协同定位技术

定位信息的获取是实现协同定位的基础。

     方式：绝对式（本地测量） & 相对式（外感测量）

（以下为上面信息的引用论文，可供学习参考）

［1］ 顾大强，郑文钢. 多移动机器人协同搬运技术综述［J］. 智能系统学报，2019，14（1）：20-27.

［2］ 韩廷睿. 基于图拉普拉斯的分布式编队控制与分布式定位［D］. 杭州：浙江大学，2017.

多机器人协同定位

根据结构分为：主从式&并行式

（高精度导航传感器）主节点        相同的传感设备，相互校正

（低成本低精度）从节点（校正）     去中心化，更好的鲁棒性

简单成本低，依赖高               拓扑、融合算法复杂，状态相关性问题

［3］ Kim Y G，Kwak J H，Hong D H，et al. Localization strategy based on multi-robot collaboration for indoor service robot applications［C］. International Conference on Ubiquitous Robots & Ambient Intelligence. IEEE，2013.

1.1）概率估计方法：将每个机器人的位置视为概率分布，通过对机器人的位置进行优化估计，获得各机器人的准确定位。

①滤波类方法：（通过前一时刻各机器人的位姿估计当前时刻各机器人的位姿）

• 扩展卡尔曼滤波（EKF）（线性化近似→线性误差→算法发散）、无迹卡尔曼滤波（UKF）（一定数量采样点，逼近概率分布）、容积卡尔曼滤波（CKF）（三阶球面径向准测，容积积分近似高斯加权积分，容积点逼近非线性系统的概率分布）

——基于高斯假设的非线性系统状态估计问题提出的方法；卡尔曼滤波框架下，通过对系统非线性的不同处理实现状态估计

非线性卡尔曼滤波框架：

（1）系统建模（运动方程和观测方程）；

（2）时间更新（根据最佳状态估计值，预测位置、协方差）

（3）量测更新（外部感知当前时刻相对数据+预测位置→最优估计）

（4）循环（2）、（3）步，递归地进行最优估计

• 粒子滤波（PF）（抛弃高斯假设，基于蒙特卡洛法思想，大量的随机采样点对非线性模型和非高斯分布进行模拟）、信息滤波（IF）

［4］ Cao Y J，David S，Andreas Z. Collaborative localization and tracking with minimal infrastructure ［J］. arXiv： Signal Processing，2019.

［5］ Lyu Y，Pan Q，Lv J. Unscented transformation-based multi-robot collaborative self-localization and distributed target tracking［J］. Applied Sciences，2019，9（5）.

［6］ Chenchana B，Labbani-Igbida O，Renault S，et al. Range-based collaborative MSCKF localization ［C］. 2018 25th International Conference on Mechatronics and Machine Vision in Practice，2018.

［7］ 毛玲，李振波，陈佳品. 基于相对定位的多移动微机器人协作定位方法［J］. 传感器与微系统，2018（8）：46-48.

［8］ Hage J A，Najjar M E B E，Pomorski D. Fault tolerant collaborative localization for multi-robot system ［C］. Mediterranean Conference on Control & Automation Med.

IEEE，2016.

②最大后验概率估计法：通过最大化后验概率的状态位置作为机器人位置的最佳估计，来求解多机器人定位问题。

［9］ Nerurkar E D，Roumeliotis S I，Martinelli A. Distributed maximum a posteriori estimation for multi-robot cooperative localization ［C］. 2009 IEEE International Conference on Robotics and Automation，2009.

③极大似然估计法：通过最大化似然函数的状态位姿作为机器人位姿的估计。

［10］ 卢虎，蒋小强，闵欢. 具有通信约束的分布式SOR多智能体轨迹估计算法［J］. 航空学报，2019，40（10）：171-183.

1.2）优化方法（通过建立约束方程和目标函数，通过优化求解目标函数极值，来计算各机器人的位姿）

①滚动时域估计（Moving Horizon Estimation，MHE）——动态滚动式的最优估计方法。（实时性和动态性，算法对于计算能力要求较高）

［11］ 杨建，罗涛，魏世乐，等. 基于MHE的多UUV协同定位方法［J］. 舰船科学技术，2017，39（12）：81-85.

②梯度下降法——测量邻居机器人的局部距离或相对方位，通过位姿估计值计算相对距离或相对方位。构造测量值与估计值的均方差目标函数。通过梯度下降法求解目标函数的最小值，获得机器人位置的最佳估计。

（图中锚点机器人用于确定多机器人团队的全局坐标）

［12］ 魏明珠，谢晓梅，严鹏，等. 月面多机器人的分布式协同定位算法研究［J］. 载人航天，2019（5）：594-599.

1.3）地图匹配方法：与提前建立的地图进行匹配，以确定当前的位置。

（空地异构机器人协同定位：俯拍视角+平视全景视角；SLAM，特征点匹配）

［13］ Zhang J， Liu R， Yin K， et al. Intelligent collaborative localization among air-ground robots for industrial environment perception［J］. IEEE Transactions on Industrial Electronics，2019，66：9673-9681.

2、多机器人路径规划技术

多机器人路径规划问题特点：机器人团队存在更多约束（队形、先后顺序）；机器人团队内部存在规划冲突问题。

2.1）耦合式路径规划方法：将多机器人视为一个整体，将各机器人的所有自由度整合成一个多自由度空间，对其进行搜索和规划。（可在全局范围内进行优化搜索，但机器人数目较多时非常复杂）

• 人工势场法（引力、斥力）——机器人路径规划问题的经典方法；但是在复杂环境中容易出现合力为零情况，陷入“死锁”状态——加入偏向力使机器人跳出“死锁”状态。

［14］ Ferreira B M，Matos A C，Cruz N A，et al. A centralized approach to the coordination of marine robots［M］. Proceedings of the 11th Portuguese Conference on Automatic Control. Springer International Publishing，2015.

［15］ Solovey K，Salzman O，Halperin D. Finding a needle in an exponential haystack：discrete RRT for exploration of implicit roadmaps in multi-robot motion planning［J］. International Journal of Robotics Research，2016，35：501-513.

• 概率类规划方法： 通过随机采样的方法，在复杂环境中规划路径，计算量小且速度较快，具备概率完备性，尤其适合高维系统。

概 率 路 线 图 法（Probabilistic Roadmap，PRM）；

快速搜索随机树（Rapid-exploration Random Tree，RRT）（将 m 个目标位置组合成 m 维空间内的路径规划目标点，建立随机路线图或生成随机扩展树，建立起始点与目标点的连接线路）

2.2）解耦式路径规划方法：对每个机器人进行独立的路径规划，之后再通过协调方法对多个独立路径进行协调和修改，以解决冲突问题。（复杂度较低，动态性较好，但难以获得全局最优解，容易陷入局部极小值或者陷入“死锁”状态）

路径协调方法：

1. 针对短生命周期的路径规划方法：

• M*算法——使用亚维展开框架，以经典的A*算法作为底层路径规划器，若发现碰撞，则局部增加搜索空间的维数，以协调机器人之间的运动。

［16］ Wagner G，Choset H. Subdimensional expansion for multirobot path planning［J］. Artificial Intelligence，2015，219：1-24.

• 基于冲突的搜索算法（Conflict Based Search，CBS）——两级算法结构：底层使用A*算法，顶层建立基于单个机器人的时间、位置约束的二叉约束树。当多机器人之间的路径产生冲突时，对树执行节点搜索。

［17］ Sharon G，Stern R，Felner A，et al. Conflict-based search for optimal multi-agent pathfinding［J］. Artificial Intelligence，2015，219：40-66.

• 基于保留区域的方法——根据运动方向计算未来几个时间步内机器人将要到达的栅格位置，称为保留区域，重叠则形成冲突描述，交由中央模块进行任务分配和协调。

［18］ Kim D G，Hirayama K，Park G K. Collision avoidance in multiple-ship situations by distributed local search［J］. Journal of Advanced Computational Intelligence and Intelligent Informatics，2014，18：839-848.

［19］曹其新，黄先群，朱笑笑，等. 基于保留区域的分布式多机器人路径规划［J］. 华中科技大学学报（自然科学版），2018，46（12）：71-76.

1. 长生命周期的路径规划概念：面向变化的多目标点，到达某一目标点后会再次获得新的目标点任务，规划过程长期运行。

［20］ Ma H，Li J，Kumar T K S，et al. Lifelong multi-agent path finding for online pickup and delivery tasks［C］. International Conference on Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems，2017.

3、多机器人任务分配技术

任务分配问题是组合优化问题，目标是找到机器人和任务之间的最佳匹配，实现完成任务耗时最少，机器人整体移动路径长度最短，机器人团队总体能量消耗最低等优化目标，最大限度地提高团队的整体效能。

3.1）基于行为的分配方法：ALLIANCE 方法、本地资格广播（Broadcast of Local Eligibility，BIE）方法等。（实时性、容错性和鲁棒性好，只能求得局部最优解）

向其他机器人传播本机器人对每个任务的效用值，执行贪婪策略，选择自身效用最高的为高优先级任务。

（通信要求较高→提出相对观测的分散计算方式——通过维持“默许”和“耐心”的离散效能评估方法）

［21］ Gerkey B P. Multi-robot task allocation： analyzing the complexity and optimality of key architectures［C］. 2003 IEEE International Conference on Robotics and Automation. IEEE，2003.

3.2）市场机制方法：协商思想，某种协议为基础。（适合于在任务和机器人状态可知的中小规模异构机器人中进行分布式问题的协作求解，能够实现全局最优任务分配）

• 典型分配方法：基于合同网协议的方法——基于市场拍卖模型，主要包括任务发布、任务投标和任务分配三个阶段。

建立能力集和任务集→评价→投标信息→投标收益

［22］ Gautham P，Thomas M，Sonya A，et al. A distributed task allocation algorithm for a multi-robot system in healthcare facilities［J］. Journal of Intelligent & Robotic Systems，2015，80（1）：33-58.

［23］ Huang Y，Zhang Y，Xiao H. Multi-robot system task allocation mechanism for smart factory ［C］. 2019 IEEE 8th Joint International Information Technology and Artificial Intelligence Conference. IEEE，2019.

3.3）群体智能方法：仿照自然界生物体的自组织行为，没有中央控制单元，相互作用的简单独立自主个体，涌现方法。

• 典型代表：蚁群算法——根据代价，在两任务之间的路径上留下不同浓度的信息素。通过信息素累加和蒸发因子作用，更新路径上的信息素浓度。信息素浓度影响任务转移概率函数的值，机器人根据转移概率函数选择下一步将要执行的任务。

［24］ 刘瑞轩，张永林. 基于改进蚁群算法的多自主式水下机器人任务分配［J］. 中国舰船研究，2018，13（6）：109-114.

3.4）人机共融的多机器人任务分配方法：

• 人在闭环的人-多异构机器人协作模式
• 人仍在任务分配回环以外（通过指令或任务下达的方式对多机器人任务分配形成干预）：

基于距离、剩余能量、机器人的能力和可用性的异构机器人选择算法；

［25］ Chowdhury M，Maier M. Local and nonlocal human-to-robot task allocation in fiber-wireless multi-robot networks［J］. Systems Journal，2018，12（3）：2250-2260.

人-机器人协同任务以树状结构表示，处理重叠/非重叠子任务的冲突；

［26］ Anima B A，Blankenburg J，Zagainova M，et al. Collaborative human-robot hierarchical task execution with an activation spreading architecture［C］. The 11th International Conference on Social Robotics，2019.

基于风险的自适应重新规划策略；

［27］ Talebpour Z，Martinoli A. Adaptive risk-based replanning for human-aware multi-robot task allocation with local perception［J］. 2019. IEEE Robotics and Automation Letters，2019，4：3790-3797.

4、未来挑战：

（1）如何实现更加高效可靠的多机器人通信、更加简洁的系统结构、更加智能的协调策略。

（2）大规模多机器人协同。

（3）如何将人这一要素引入多机器人协同导航过程中，实现真正的人在回环内的协同控制。