文献综述
机器人的研究越来越多的得到关注和投入，随着计算机技术和人工智能的发展，智能自主移动机器人成为机器人领域的一个重要研究方向和研究热点。移动机器人地图创建是自主移动机器人领域的热点研究问题。本次毕业设计将对多机器人协作探测未知环境中的地图融合和任务分配两个重要内容进行研究。针对地图融合和任务分配中存在的技术难点,旨在提出解决方案,有效提高探测效率。
探测未知环境是移动机器人领域的基础问题,是机器人在未知环境中完成其他任务的必要条件。与单个机器人相比,多机器人系统具有更好的鲁棒性、适应性、灵活性和扩展性,更加适用于探测未知环境, 多机器人系统通过交流协作和分享信息改进了单个机器人的性能，如任务执行效率、健壮性、灵活性和容错性，同时涵盖了分布式决策，编队控制、区域覆盖及其相关应用。多机器人探索拥有比单个机器人明显的优势，可以去做一些单个机器人无法做的事情，在全分布式系统中消除了单点故障。当前的工作集中于地图融合，这是一个挑战性问题。在多机器人系统中共享地图需要高效的协同，地图融合算法产生的全局地图是多机器人系统的重要组成部分。同时在任务分配上也需要较大的优化。目前在地图融合和任务分配方面仍然存在许多问题。地图融合直接决定了多机器系统探测未知环境的准确性,任务分配影响着多机器人系统完成环境探测的效率。
在多移动机器人协作系统项目中有一个很重要的环节就是协作系统环境地图数据库的建立。目前移动机器人工作环境地图表示方式有三种：栅格图、特征图和拓扑图。本次毕业设计将在拓扑图中实现地图创建工作并进行仿真模拟。当多个机器人协作探索环境时，必须合并来自各个机器人的地图，以生成单个全局一致的地图。 当机器人没有共同的参考系或全球定位时，这是一个具有挑战性的问题。 拓扑图简明扼要地描述了环境的可导航性，并且由于在探索过程中易于收集测量数据，因此可以将图的顶点嵌入度量空间中。 使用拓扑图的结构和几何形状来确定具有单个或多个重叠区域的图之间的最佳对应关系。 使用模拟数据和真实数据进行的实验证明算法的有效性。
基于多机器人协作的地图创建按照地图的存储与处理方式的不同可以分为两大类型：集中式和分布式。在集中式中，存在一个中央处理模块，每个机器人分别在自己所在的局部地图中进行定位与地图创建，然后利用无线通信装置将在局部地图中获得的信息传送给中央模块。这种方法通过子地图的匹配，可以充分利用子地图间的冗余信息提高定位与地图创建的精度。但是，当机器人数量增加时中央模块的计算量会显著增大，而且集中式的信息传递需要很大的带宽；系统的可靠性也比较低，一旦中央模块出现故障,整个系统都会陷入瘫痪状态。在分布式中，不存在中央模块，每个机器人都拥有自己的全局地图，在每一时刻机器人把来自其他相邻机器人的信息和自己的观测信息融合到自己的全局地图中，然后以点对点的方式将新的信息传送给其他机器人。每个机器人只能获得与其相邻的机器人的位置信息，不知道整个系统的拓扑结构。这种方法与分布式的信息融合十分相似，可以利用信息滤波器来实现。由于两个不相关信息矩阵的信息融合可以通过两个矩阵的相加而实现，所以利用信息滤波器实现分布式可以避免复杂的计算。
多机器人系统稳定又高效的关键在于系统内的每个机器人个体能否通过交流沟通保持行动的一致，从而没有冲突的协作完成相应的任务。因此，将一系列任务通过特定的算法分配给系统中每一个机器人个体或者机器人子群是保证多机器人系统正常高效运作的关键，这也就是多机器人动态任务分配问题。在多机器人动态任务分配问题中，作为多机器人系统设计与实现中最核心的模块，任务分配的效果直接影响着系统的性能和工作效率。在多机器人系统应用中根据任务情况一般将任务分配分为静态任务分配和动态任务分配，静态任务分配是指当任务执行之前，任务信息对机器人是已知的并保持稳定状态；对于动态任务分配来说，机器人任务分配是一个动态的过程，需要根据任务环境的变化和子群对利益的需求处于不断调整变化的状态。但目前多机器人研究大部分都是针对静态任务分配，对于未知环境下的分布式动态任务只是建立初步模型，分配策略并不完善。而且大多数研究在对动态任务分配结果进行优化时没有从收益的角度出发，很少涉及到多机器人全局最优问题。
动态任务分配也可以称为任务搜索和协调控制任务搜索主要是系统决定如何给每个机器人分配搜索任务才能使搜索过程中消耗能力最少，搜索效果最好。目的是确定具体的合作方式以达到效果最优。主要协调的是路径规划、障碍冲突、死锁消除等。动态任务是指任务信息、环境信息的都会随时产生变化；新任务产生，旧任务删除都是在线完成的；增加或减少机器人数量会改变原有任务的分配结果等。任务分配和分配方法已成为协调机器人团队的重要范例，任务分配是一个过程，其中涉及每个机器人估计执行可用任务所需的效用，并计算任务对机器人的分配，以最大化集体利益。 通常，会重复计算这些匹配项，以使机器人团队可以根据情况的变化进行集体调整。 在这种情况下，运行时间以及最终的机器人到任务匹配的质量都是决定团队效率的重要因素。
通过任务分配研究所要达到的目标主要有两个，首要目标是系统必须按照要求高质量的完成所有分配的任务。第二个目标更为核心，它要求系统在保证完成任务的前提下，充分利用各种资源，以最小的能源消耗实现更为高效的工作效率，同时要求系统中的每个机器人个体都最大化发挥自己的能力。拍卖和基于市场的机制是多机器人系统中分布式任务分配的最流行方法。大多数经典的最佳分配算法最初是由运筹学人员开发的，因此不适用于多机器人任务分配。人们通常希望分散管理，以增强系统对单个故障的容忍度，并缩短实际运行时间。在运营研究人员开发的流行的最佳分配算法中，有一种算法可以方便地分配：Bertsekas著名的最佳AUCTION算法。分散拍卖和招标程序的经济解释得到了许多机器人专家的青睐，在过去的三十年中，在过去的三十年中，通过采用拍卖或类似拍卖的机制，已经开发了许多分散式分配方法。本次毕业设计希望找到一种基于市场的方法，用于解决在多机器人系统中的多机器人任务分配问题，从而找到许多异构机器人对许多异构任务的最佳分配，并对与已存在的方法进行比较研究。
【参考文献】
[1]Yu Shuien,Fu Chunyun,Gostar Amirali K,Hu Minghui. A Review on Map-Merging Methods for Typical Map Types in Multiple-Ground-Robot SLAM Solutions.[J]. Sensors (Basel, Switzerland),2020,20(23).
