赵慧潮 石朝侠

（南京理工大学计算机科学与工程学院 南京 210094）

基于市场法的多机器人协作未知环境探索∗

赵慧潮 石朝侠

（南京理工大学计算机科学与工程学院 南京 210094）

多任务分配是多机器人未知环境协作探索的关键问题。传统市场法由于追求单体机器人最优化，从而牺牲了整体最优化，而基于蚁群算法的多任务分配方法虽然实现了整体最优化，但是不适合在未知环境探索中使用。论文在市场法的基础上提出了一种改进方法，该方法将机器人到任务点所经过路径上的排斥素的多少作为拍卖获胜的条件。该方法提高了多机器人系统完成环境探索的效率。通过实验验证该算法的有效性。

多机器人；协作探索；市场法；排斥素

1 引言

利用多机器人协作探索未知环境与单个机器人系统相比具有信息冗余、柔韧性、并行性等特点，但是在未知环境下也面临多任务分配、有线通信和信息融合等挑战。多机器人技术广泛应用于战场侦察［1］、星球探测［2］、灾难救援等领域。

多机器人系统探索未知环境的关键则是如何更加有效地分配任务点，兼顾单个机器人和多机器人系统的整体效率［3］，减少任务目标重复探索、区域重复等问题，因此探索策略必须具备可靠性、鲁棒性和高效性［4］。

目前广泛应用在多机器人协作探索未知环境中的方法主要包括：蚁群算法［5］、神经网络算法［6］、粒子群算法［7］、市场拍卖方法［8］和组合分配方法等等。现在比较主流的方法为市场法、组合分配方法。市场法模拟拍卖行业制度，各机器人在每执行完一次探索以后，根据剩余目标任务的完成时间、能源消耗等指标进行投标、相互竞价，通过拍卖机制将任务分配到具体的机器人［9］。市场法可以实现单个机器人的高效率，但是经常会陷入局部最优无法实现多机器人系统整体的最优化。文献［10］在市场拍卖方法的基础上结合旅行商［11］解决方案和最短路径算法［12］，提高了任务分配效率。文献［13］利用市场拍卖方法获得目标点，在向目标点运动的过程中预测下一个目标点，从而节省目标分配时间。基于组合分配的优化方法主要是对矩阵的运算，在任务数量均匀分布的情况下能够表现出比较良好的实验效果，当任务点大量集中于某个区域的时候，探索效率较差。

2 市场法

在人类长期的市场经济行为中，商家和个人通过货物贸易实现个人利益的最大化。简单来说就是实现资源的最优化利用，这一点和多机器人任务分配十分相似，多机器人任务分配是为了以最合理优化的方法将多任务分配到单个机器人，实现多机器人系统的整体最优化。模仿人类社会的拍卖行为，提出了基于拍卖方法的任务分配方式［14］。拍卖法是市场法的主要表现形式，具体步骤如下：

1）机器人将自己探测到的任务点以广播的方式发布拍卖信息，该机器人被称为拍卖机器人。拍卖信息主要是任务点的位置信息。收到信息的机器人判断自己是否可以到达任务点，如果可以到达就参与投标。参与投标的机器人被称为竞标机器人。

2）每个竞标机器人根据收到的拍卖信息计算到达任务点的耗时、路程和效益，从而得到自己的投标值。将投标信息以广播的方式发送出去。

3）拍卖机器人将收到的所有竞标机器人的投标信息进行排序比较，从而确定最终赢得拍卖的机器人。

基于市场法的多任务分配方法可以有效地适用于动态环境全局信息不确定的环境中［15］。同时市场法任务分配对于机器人数量的变化具有很好的适应性［16］，使得多机器人系统规模扩大变得更加容易。市场法可以实现每个机器人的局部最优化，但是局部最优化并不代表整体最优化。

3 基于排斥素的市场法

传统市场法由于追求单体机器人最优化从而牺牲了整体最优化，而基于蚁群算法的多任务分配方法实现了整体最优化但是不适合在未知环境探索中使用。传统市场法中机器人选择任务点主要是基于到达任务点的距离作为判断标准，这样就没有考虑其他机器人的探索情况。相对于吸引信息素，排斥素更加适合于多机器人协作完成未知环境的探索，在未知环境探索中排斥素能够更加直接有效。利用排斥素作为判断标准，利用了之前机器人的探测信息，可以很好地考虑到机器人之前的探索情况，避免机器人过于集中在同于区域。

3.1 相关假设

本文研究采用市场算法实现动态多任务的分布式分配，对多机器人系统特性、任务特点和环境特征有如下假设：

1）机器人具有诚实性，当遇到相同情况机器人执行的动作都是一样的，不具有随机性；

2）机器人具有自私性，机器人所做的一切行为都是为了实现自身利益最大化；

3）机器人是理性的，机器人所执行的一切动作都是在允许的范围内的；

4）任何机器人之间都可以进行广播或者点播方式进行通信，但是通信的可靠性并不能得到保证；

5）多机器人系统中机器人的数量可以增减；

6）多机器人系统中每个机器人之间的关系是完全分布式的，不存在“领导者”和“跟随者”的关系；

7）待分配的任务是简单任务，不可以进行分解，每个任务都可以由单个机器人完成不需要协作完成；

8）任务是动态出现的。

3.2 排斥素的计算

假设节点nodei为任务点，则称节点nodei为任务点taski。在竞争蚁群算法中利用Dijkstra最短路径算法计算机器人robotk当前所在路口nodeo到任务点taski的最短路径，最短路径所经过的边的集合为PAT={n odeo，…，nodei} 。假设机器人robotk从节点nodei1到任务点taskin的最短路径为 nodei1，nodei2，nodei3，nodei4，…，nodein。则从节点node到任务点task的排斥素为i1in

其中：节点nodeit

与节点nodeit+1为相邻节点，且nodeit、nodeit+1之间的通路为itit+1；Phekitit+1表示相邻节点nodeit到nodeit+1的排斥素。

假设节点nodei与节点nodej相邻，则机器人robotk从节点nodei到节点nodej的排斥素的计算表达式为

其中：Nj表示节点nodej的相邻节点的集合，t∈Nj表示节点nodeit为节点nodej的相邻节点；Phe(ij)表示边ij自身的排斥素；表示节点nodej其他各分支上排斥素和；μij为调整对Phek

ij影响大小的参数。

假设从节点i到节点 j至少需要经l条边，称节点i到节点 j的距离为lij，则 μij的计算表达式为

其中：sumr表示该路口有几个机器人路口经过；maxl表示路口到当前机器人所在路口允许的最多路口个数，maxl的计算公式如下

其中：Vk表示地图中已经探索过的路口个数，maxl的大小由Vk所决定。距离机器人越远的路口对机器人选择运动方向的影响越小，式（2）是一个递归公式，如果对该公式不加限制地一直进行递归会严重影响该算法的效率，本文提出了maxl这个概念，将距离超过maxl的路口的影响全部视为0，这样就会减少递归次数，提高算法的效率。

3.3 任务分配过程

3.3.1 任务点分配

本文采用拍卖法实现任务点分配，拍卖过程中会出现两个角色“拍卖方”和“竞拍方”，发现任务点的机器人被称为“拍卖方”，可能完成该任务的机器人被称为“竞拍方”。多机器人系统中在不同的时刻每个机器人都有扮演不同角色的可能性，但是每个机器人同一时刻最多只能扮演其中一种角色。“拍卖方”将待分配的任务分配给最合理的“竞拍方”来完成该任务；“竞拍方”基于自身能力和所处环境位置对被拍卖的任务进行投标，由“拍卖方”机器人做出决定，从众多“竞拍方”中选择最优的“拍卖方”将任务分配给它。任务点的分配主要包括四个步骤，分别为任务发布、投标计算、合同授权以及合同建立。

1）任务发布

当“拍卖方”发现有任务没有被分配，将该任务的相关信息利用广播的方式发送给可能对该任务做出拍卖响应的机器人。如图1所示，任务相关信息主要包括任务位置和最晚投标时间等等。

图1 任务发布

2）投标计算

接收到“拍卖方”发送的任务信息后，机器人判断该任务点是否在自己的地图范围内，如果机器人可以找到到达该任务点路径，就计算到达任务点的路径上的排斥素。如果机器人可以到达该任务，就将信息排斥素作为“投标价格”，利用点对点的通信方式将“投标价格”发送给拍卖方，“投标价格”的内容主要有机器人自身的信息和到达任务点的排斥素。如图2所示。

图2 投标计算

3）合同授权

“拍卖方”将任务信息广播出去后就进入等待投标阶段，当收到“竞拍方”发来的关于此次拍卖的投标，将该投标信息保存下来。当投标时间结束，“拍卖方”停止接收其他机器人的投标，“拍卖方”对所收到的所有投标进行排序，选择排斥素最少的“竞拍方”作为此次拍卖的获胜方，并向其发送竞拍胜利建立合同的信息。如图3所示。

图3 合同授权

4）合同建立

如图4所示，获得本次拍卖的“竞拍方”向“拍卖方”发送合同确认信息，与“拍卖方”建立合同关系，将该任务加入到自己的任务表序列中，保证该机器人执行该任务。在合同建立的过程中，如果“竞拍方”发现自身情况发生改变不适合执行该合同，就需要向“拍卖方”发送合同取消信息，此时“拍卖方”重新进入合同授权阶段，重新选择“拍卖方”作为任务的执行者向其授权合同。

图4 合同建立

该分配方法虽然解决了分布式多机器人系统的任务分配问题，但是由于该方法对网络通信十分依赖，如果在任务分配的过程中出现通信中断或者丢包等情况，可能直接导致任务分配失败，甚至可能导致多机器人系统整体出现奔溃。

为了防止系统奔溃的情况出现，如果在规定时间内没有将任务拍卖出去就取消本次任务拍卖，避免由于通信等问题导致系统出现奔溃，在下次任务拍卖过程中再次对该任务进行拍卖。

3.3.2 任务点再分配

机器人通过拍卖获得完成任务点的“合同”，但是随着时间的迁移，机器人的状态发生改变，有些任务可能不再适合自己去完成，此时就需要对这些已经经过一次拍卖的任务进行再次拍卖分配。任务点再分配的过程和3.3.1小节的分配过程基本相似，区别主要集中在任务发布过程中。机器人每完成一个任务后，计算自己的任务表序列中排斥素最高的任务点对其进行“拍卖”，如果该任务点被成功“拍卖”出去，则从自己的任务表中将该任务点删除。

4 实验对比

本文以南京理工大学校园地图作为实验的模拟环境，在此基础上进行仿真实验。如图5为部分实验环境，实验范围为1100m×1300m，机器人运行速度为5m/s。将本文提出的方法与市场法、组合拍卖方法进行比较，得出该方法的优劣性。本文在不同的机器人数量的情况，分别针对算法的搜索完成时间、搜索路径以及重复率进行比较。在实验过程中，随机选取20组机器人的初始位置，排除初始位置的选取不同对实验结果造成干扰。同时每组初始位置重复十次实验过程，排除实验过程中可能存在的一些不可预知的偶然性因素对实验结果造成误差干扰。

图5 实验环境

4.1 探索未知环境完成时间对比

从图6可知，在机器人数量相同的情况下，相较于传统市场法和组合分配算法本文提出的基于排斥素市场法的探索完成时间相对较短，比其他两种方法完成时间减少了8%。同时还可以发现随着机器人数量的增加，多机器人系统完成未知环境探索的时间也在逐渐下降，但是当机器人的个数增加到一定数量以后，多机器人系统探索完成时间并不会持续下降，而是在一定的时间范围内波动。由此可以得出多机器人探索未知环境并不是机器人的数量越多探索时间就一定会越短。

图6 在不同机器人数量的情况下，各算法的完成时间

4.2 探索未知环境重复率对比

从图7可知，在机器人数量相同的情况下，本文提出的算法在降低地图重复率方面有显著效果。基于排斥素市场法将探索未知环境的重复率降低了23%。同时可以看到无论采用何种算法随着机器人数量的增加，虽然地图重复率存在偶然的轻微下降，但是总体都是呈上升趋势。

4.3 探索未知环境行驶路径对比

从图8可知，在机器人数量相同的情况下，本文提出的算法在降低完成路径方面略有改进并没有取得较显著的效果。

图7 在不同机器人数量的情况下，各算法的重复率

图8 在不同机器人数量的情况下，各算法的完成路径

5 结语

根据仿真实验结果分析可知，在机器人数量相同的情况下本文提出的算法可以在更短时间和更低重复率的情况下完成未知环境的探索。但是该算法也存在一些不足的地方。诸如无法有效降低多机器人系统的探索路径长度，无法解决未知环境探索效率随着机器人的数量增加一直持续提高存在性能瓶颈。

［1］Hougen D F，Benjaafar S，Bonney J C，et al.A miniature robotic system for reconnaissance and surveillance［C］//IEEE International Conference on Robotics&Automation，2000：501-507.

［2］Apostolopoulos D S，Pedersen L，Shamah B N，et al.Robotic Antarctic Meteorite Search：Outcomes［C］//Proceedings-IEEE International Conference on Robotics and Automation，2001：4174-4179 vol.4.

［3］王姝莉.基于多机器人协调的搜集与围捕问题的研究［D］.北京：中国科学院自动化研究所，2003.WANG Shuli.Research on the Multi-Robot System Cooperation Based on Foraging and Pursuit Game［D］.Beijing：Instltute of Automation，Chinese Academy of Sclences，2003.

［4］张飞，陈卫东，席裕庚.多机器人协作探索的改进市场法［J］.控制与决策，2005，20（5）：516-520.ZHANG Fei，CHEN Weidong，XI Yugeng.Improved market-based approach to collaborative multi-robot exploration［J］.Control and Decision，2005，20（5）：516-520.

［5］Dorigo M，Bonabeau E，Theraulaz G.Ant algorithms and stigmergy［J］.Future Generation Computer Systems，2000，16（8）：851-871.

［6］Colby M，Chung J J，Tumer K.Implicit adaptive multi-robot coordination in dynamic environments［C］//Ieee/rsj International Conference on Intelligent Robots and Systems.IEEE，2015.

［7］Cai Y，Yang S X.An improved PSO-based approach with dynamic parameter tuning for cooperative multi-robot target searching in complex unknown environments［J］.

［8］Vig L，Adams J A.Market-Based Multi-robot Coalition Formation［M］.Springer Japan，2006.

［9］陈建平.多机器人系统中的机器人合作问题研究［D］.广州：广东工业大学，2011.CHEN Jianping.Research on the Multi-Robot System Cooperation Based on Foraging and Pursuit Game［D］.Guangzhou：Guangdong University of Technology，2011.

［10］rk，Sava&#，Kuzucuo&#，Lu A E.Optimal bid valuation using path finding for multi-robot task allocation［J］.Journal of Intelligent Manufacturing，2015，26（5）：1049-1062.

［11］Michail O，Spirakis P G.Traveling salesman problems in temporal graphs☆，☆☆［J］.Theoretical Computer Science，2016，634：1-23.

［12］Yue Y.An Efficient Implementation of Shortest Path Algorithm Based on Dijkstra Algorithm［J］.Journal of Wuhan Technical University of Surveying&Mapping，1999.

［13］Wei C，Hindriks K V，Jonker C M.Dynamic task allocation for multi-robot search and retrieval tasks［J］.Applied Intelligence，2016：1-19.

［14］金涬，石纯一.拍卖方法引入多Agent系统［J］.计算机科学，2003，30（8）：104-107.JIN Xing，SHI Chunyi.The Auction and its Application in Multi-Agent System［J］.Computer Science，2003，30（8）：104-107.

［15］吕洪莉.面向多目标优化的多AUVs群体协同任务分配［D］.哈尔滨：哈尔滨工程大学，2012.LV Hongli.Task Allocation of Multi-AUV System Based on Multi-objective Optimization［D］.Harbin：Harbin Engineering University，2012.

［16］崔一鸣.多机器人协作的关键技术研究［D］.南京：南京理工大学，2008.CUI Yiming.Key Technology of multi-robot collaboration［D］.Nanjing：Nanjing University of Science and Technology，2008.

Unknown Environment Exploration of Multi-robot Based on Market

ZHAO Huichao SHI Chaoxia
（School of Computer Science and Engineering，Nanjing University of Science&Technology，Nanjing 210094）

Multi-task assignment is a key problem in multi-robot's collaborative exploration of unknown environment.Traditional market methods sacrifice the overall optimization because of the pursuit of single-robot's optimization.However，the method basing on the partition exploration can achieve the overall optimization，which is not suitable for exploration in the unknown environment.This paper put forward a market approach based on improved the traditional market approach，this method took the number of rejection pheromones in the path through the robot as the condition of winning the auction.The method improves the efficiency of the multi-robot system to complete the environment exploration.What's more，the effectiveness of the algorithm has been verified by experiments.

multi-robot，cooperative exploration，market-based，rejection of pheromone

TP242.6

10.3969/j.issn.1672-9722.2017.11.001

Class Number TP242.6

2017年5月10日，

2017年6月17日

国家自然科学基金项目“基于XX环境搜索面上研究”（编号：61371040）资助。

赵慧潮，男，硕士研究生，研究方向：多机器人协同和未知环境探索。石朝侠，男，博士，副教授，研究方向：

移动机器人自主导航、多机器人协同。