多机器人协同导航技术综述
期刊：无人系统技术 （综合影响因子 2.018）
第一作者：张辰
Content
多机器人协同定位技术
概率估计方法
将每个机器人的位置视为概率分布，通过对机器人的位置进行优化估计
-
滤波类方法：扩展卡尔曼滤波（EKF）、无迹卡尔曼滤波（UKF）、容积卡尔曼滤波（CKF）、粒子滤波（PF）、信息滤波（IF）。
- EKF、UKF、CKF 是针对基于高斯假设的非线性系统状态估计问题提出的方法，是在卡尔曼滤波框架下，通过对系统非线性的不同处理实现状态估计。在多机器人系统中，非线性卡尔曼滤波框架包括以下 4 个步骤：（1）系统建模：分析系统运动模型，构建运动方程和观测方程。（2）时间更新：依据前一时刻的最佳状态估计值，结合机器人线速度、角速度等运动信息，在运动方程中进行一步预测，计算当前时刻机器人的预测位置，并对预测协方差进行一步预测。（3）量测更新：根据机器人外部感知获取的当前时刻相对数据，结合时间更新过程得到的当前时刻预测位置，对机器人位置进行最优估计，并计算当前时刻的估计协方差。（4）循环（2）、（3）步，递归地进行最优估计。
- PF 方法抛弃高斯假设，基于蒙特卡洛思想，通过大量的随机采样点对非线性模型和非高斯分布进行模拟。需要的粒子数量巨大，计算负担较重。
-
最大后验概率方法：通过最大化后验概率的状态位置作为机器人位置的最佳估计，来求解多机器人定位问题。机器人 \(i\) 通过本地测量获取自身线速度与角速度，组成向量 \(u = [v, \omega]^T\)，通过外感测量获取相对于机器人 \(j\) 的相对距离和角度数据 \(z = [d, \theta]^T\) ，通过迭代方法求解使后验概率函数 \(P(x|u, z)\) 取得最大值的 \(x^*\)，即为机器人位姿的估计。
-
极大似然估计：通过最大化似然函数的状态位姿作为机器人位姿的估计。通过机器人之间的
相对观测结果和机器人本地测量数据构建似然函数 \(P(z|x)\)，通过求解使似然函数取得最大值的 \(x^*\) ，作为机器人位姿的估计。
优化方法
通过建立约束方程和目标函数，通过优化求解目标函数极值，来计算各机器人的位姿。
-
滚动时域估计（Moving Horizon Estimation，MHE）方法：通过建立固定时间域长度的优化计算窗口，使用时间窗开始时刻的多机器人位姿数据组成系统状态向量、时间窗内各时刻的状态噪声序列和到达代价函数，构建性能指标函数。通过最小化性能指标函数，估计时间窗结束时刻的各机器人的位姿数据
-
梯度下降法：测量每个机器人与邻居机器人的局部距离信息或相对方位信息，通过每个机器人的位姿估计值计算对应的相对距离或相对方位，构造测量值与估计值的均方差目标函数，通过梯度下降法求解。
地图匹配方法
常用于无人机导航，提前建立地图，在无人机飞行过程中将感知信息与地图匹配
- 在空地异构机器人协同定位中，地图匹配成为联系空地不同视角的桥梁：将无人机俯拍视角与地面机器人平视全景视角进行匹配，可以实现二者的协同定位。
多机器人路径规划技术
耦合式方法
将多机器人视为一个整体，将各机器人的所有自由度整合成一个多自由度空间，对其进行搜索和规划，计算和搜索的复杂度将会呈指数增长
在耦合方法中，许多单机器人路径规划的经典方法被扩展到多机器人路径规划中。
-
人工势场法：通过在机器人的运行空间中构建势能场，目标点对机器人产生引力，障碍物对机器人以及机器人之间产生斥力，通过合力引导机器人走向目标点。在复杂环境中容易出现合力为零情况，陷入“死锁”状态，因此研究者提出了多种改进方法，通过加入偏向力使机器人跳出“死锁”状态。
-
概率类规划方法：通过随机采样的方法，在复杂环境中规划路径，计算量小且速度较快，具备概率完备性。常见的概率类方法有概率路线图法（Probabilistic Roadmap，PRM）、快速搜索随机树（Rapid-exploration Random Tree，RRT）
解耦式方法
首先对各机器人进行单独的路径规划（使用经典的面向单机器人的路径规划方法），再通过协调算法将发生冲突的机器人路径进行调整。
路径协调方法
-
M*算法：以经典的 A*算法作为底层路径规划器，在规划过程中若发现两机器人碰撞，则局部增加搜索空间的维数，以协调机器人之间的运动。复杂度较低，动态性较好，但是难以获得全局最优解，容易陷入局部极小值或者陷入“死锁”状态。
-
基于冲突的搜索算法（Conflict Based Search，CBS）：采用两级算法结构，底层使用 A*算法对单机器人进行路径规划搜索，在顶层建立基于单个机器人的时间、位置约束的二叉约束树。当多机器人之间的路径产生冲突时，对树执行节点搜索，实现冲突调节。
-
基于保留区域的方法：根据运动方向计算未来几个时间步内机器人将要到达的栅格位置，称为保留区域。当两机器人保留区域重叠，则形成多机器人冲突描述，交由中央模块进行任务分配和协调。
多机器人任务分配技术
基于行为的分配方法
通过找到一个具有最大效用的机器人-任务对，将任务分配给机器人。
典型的基于行为的任务分配方法包括 ALLIANCE 方法、本地资格广播（Broadcast of LocalEligibility，BIE）方法等。在运行过程中，各机器人定期进行任务重新分配的规划，每个机器人向其他机器人传播它对每个任务的效用值，每个机器人中执行贪婪策略，选择自身效用最高的为高优先级任务。
在效用值传播过程中，借助通信的传播方法对于通信的要求较高，研究人员提出了相对观测的分散计算方式：通过维持包含“默许”和“耐心”的离散效能评估方法。当某机器人正在执行一项任务时，其自身对于该任务的默许值逐渐增加，其他机器人对于该任务的耐心程度下降。
市场机制方法
多机器人系统在某种协议基础上通过机器人之间的相互协商、谈判来完成任务分配。
- 基于合同网协议的方法（最经典）。基于市场拍卖模型，主要包括任务发布、任务投标和任务分配三个阶段。适合于在任务和机器人状态可知的中小规模异构机器人中进行分布式问题的协作求解。
群体智能方法
通过对鸟群、蚁群、蜂群等生物群体系统的行为进行研究和模拟，仿照自然界生物体的自组织行为
- 蚁群算法（最典型）：机器人从完成某任务转移到下一个任务过程中，根据完成任务的代价，在两任务之间的路径上留下不同浓度的信息素。通过信息素累加和蒸发因子作用，更新路径上的信息素浓度。信息素浓度影响任务转移概率函数的值，机器人根据转移概率函数选择下一步将要执行的任务。
人机共融的多机器人任务分配方法
将人这一因素加入到多机器人任务分配过程中，但人仍在任务分配回环以外，通过指令或任务下达的方式对多机器人任务分配形成干预。
-
Local and nonlocal human-to-robot task allocation in fiber-wireless multi-robot networks (2018, IEEE Systems Journal): 提出了一种基于距离、剩余能量、机器人的能力和可用性的异构机器人选择算法，通过建立任务请求-任务应答-代价评估-择优分配-故障实时监测，在网络协议层集成本地和非本地任务分配，解决如何有效地将给定的人工任务分配给合适的机器人、如何低成本求解任务分配和非本地任务分配的问题。
-
Collaborative human-robot hierarchical task execution with an activationspreading architecture (2019, The 11th International Conference
on Social Robotics): 研究了基于层次任务计划的人机协同任务执行问题，将人-机器人协同任务以树状结构表示，并针对重叠和非重叠子任务的冲突进行了不同处理，提高了人-机器人团队中任务的动态分配能力和不同环境条件下的机会式任务执行能力。 -
Adaptive risk-based replanning for human-aware multi-robot task allocation with local perception (2019, RAL): 提出了一种在多机器人任务分配环境下的基于风险的自适应重新规划策略，基于社会风险和人类运动预测不确定性的变化，实时动态的调整任务分配，以处理局部感知的局限性和不可预测的人类行为。