基于博弈论的机器人组群系统个体任务分配的算法

　　摘要随着科技水平的不断提升，智能化的机器人组群系统在工业生产、火灾救援等方面的运用愈发广泛，有力的推动了传统行业的发展。而由于机器人组群系统是由一定数量的机器人组成的，每个个体机器人都会分配到各自的任务，通过合理的分工和调配来完成机器人组群系统整体任务，因此，机器人组群系统的工作绩效，就与个体机器人分配任务的水平有直接的关联。本文通过阐述博弈论的基本内涵，对机器人组群系统进行了分析，并提出了机器人组群系统个体任务分配算法，为优化机器人组群系统结构，合理分配个体机器人任务起到了借鉴和参考作用。

　　【关键词】博弈论组群系统机器人

　　机器人组群系统主要是由多种一定数量的个体机器人组成的，通过合理的分工和调配，可以使机器人组群系统达到个体机器人所无法达成的工作目标。而机器人组群系统所具有的优越性，主要是通过合理的对个体任务分配达成的。由于机器人组群系统所处的环境会不断的发生变化，这也就导致了个体机器人的决策方向会发生相应的转变，给任务的分配带来维数灾难，这种高度的动态性和复杂性，为任务分配带来极大的难度的同时，也会导致传统的规划方法无法继续使用。因此，可以利用博弈论的基本原理，将每个个体机器人看做机器人组群系统的一部分，将其融入到环境之中，让个体机器人能根据自身对周围环境变化的理解，以及对其他机器人工作的预测，在一定任务的集合之中挑选出最符合实际情况的任务执行，从而有效的提升机器人组群系统个体任务分配的水平。

　　1博弈论的基本内涵

　　机器人群组主要是由多个结构和功能简单的个体机器人组成的，通过个体机器人的合作，来完成预先设计好的任务。而由于每个机器人都属于一个个体，如何将整体的任务进行合理的分工与分配，让每个机器人都能够发挥出优势，优化机器人群组的组织结构，提高整体的运行绩效，也就成为了机器人群组研究的重点问题。而博弈论主要研究的就是智能设备或机器人之间相互合作和依存的关系，可以将机器人群组中每个个体的竞争与冲突利用形式化的方式进行表达，并通过合理的分配使机器人群组效益最大化，或风险最小化。而由于机器人群组是一个整体的系统，其中每一个个体机器人在进行决策之前都需要从其他个体机器人的角度，对其他个体的行为进行预测，才能得出最合理的决策任务，这也就是在机器人群组中，博弈论应用的基本内容。博弈论主要存在以下三种元素：

　　（1）个体机器人集合，可以将其表示为：

　　（2）假设每个个体机器人i都有一定数量的决策方向可供选择，那么每个个体机器人所构成的纯策略空间可以表示为。其中，在纯策略空间Ai上的一个概率分布，也就是个体机器人i的混合策略。Xim表示为选择λim的概率，可得公式：

　　个体机器人i所能够选择的策略记为，是个体机器人i的一个可选任务计划，也是在博弈的过程中，每个环节个体机器人i所分配到一个任务的概率函数，因此，πi，个体机器人i所能選择的所有策略集合为={πi1，πi2，……，π}。

　　（3）机器人群组中每个个体机器人都会有对应的奖赏函数，记为ri（π），其中π={π1，π2，……，πN}表示了第N个个体机器人的决策局势。个体决策的每一个决策都可以用公式=来表示，假设π||Pi=（π1，π2，……，πi-1，Pi，πi+1，……，πN）在决策局势当中，个体机器人将决策πi转变为Pi，其他个体机器人不发生变化，也就可以得到新的局势：π||P||πi，经过计算可以得出，π是一个重要平衡点。

　　在博弈论中，主要可以根据个体机器人对任所提出的协议进行强制性分析，如果协议的强制性较高，在个体机器人之间达成协议后就不能轻易的更改，而如果强制较低，也就进入到了非合作博弈中来，每个个体机器人互相独立，不形成机器人群组，也就不会形成相应的协议。

　　2机器人组群系统分析

　　机器人的群组系统具有以下几种特点：

　　（1）机器人组群系统是由多种个体机器人所组成的，这些机器既有可能是同构机器人，还有可能是异构机器人。可以用集合表示为A=（a1，a2，……，aN）。

　　（2）机器人组群系统会呈现在一定的环境状态之中，这种环境状态会随着时间的变化而变化。在某一时段t内，机器人组群系统的状态可以表示为st'∈s'。

　　（3）机器人组群系统所处的环境状态是可观测的，个体机器人通过利用自身所携带的各种通信、感应设备可以直观的观测到机器人组群系统所处的环境。利用公式表述为

　　。

　　（4）个体机器人可以通过进行联合任务的方式，改变机器人组群系统所处的环境状态。假设机器人组群系统的任务合集为B，Bi也就是个体机器人i的任务合集，因此，

　　。个体机器人为了改变整个机器人组群系统的外部环境，会通过观测来选择一个恰当的任务bi∈Bi，通过执行该任务来达到影响外部环境的目的。而从宏观的角度来看，机器人组群系统中的每个个体机器人可以通过联合任务来改变自身所处的环境状态。

　　（5）由于机器人组群系统是一种智能化的系统，其中每一个个体机器人带有一定的学识，包括对于整个系统流程的掌握、周围环境、其他个体机器人的工作和预测、对自身任务的和决策等，这也就体现出了个体机器人的任务和决策会随着与外界环境的不断流通而发生变化。

　　（6）个体机器人具有自我决策的功能，自我决策功能是个体机器人通过对外界环境、其他个体及机器人的任务及趋势预测等，从而对自身任务进行合理的决策和规划，由于个体机器人具有决策功能，这也就使得机器人组群系统的工作绩效水平会有极大的提高。

　　（7）个体机器人的决策并不是一成不变的，随着机器人工作的不断开展，会随着外部环境的变化，或是所产生的奖惩来判断自己的决策是否合理，通过不断的更新决策观念，可以保证个体机器人的决策方向大体正确，并且具有较高的绩效水平，这从本质上而言也是一种反思和学习的过程。

　　（8）机器人组群系统中的目标众多，每个个体机器人在不同的工作阶段，都会产生不同的工作目标，同时，机器人组群系统整体又存在一个宏观的工作目标。机器人组群系统的工作目标主要有以下几种特点：

　　首先，机器人组群系统的工作目标具有一致性的特点，无论每个个体机器人的工作目标如何变动，其整体的工作目标依然具有一致性的特点。一个个体机器人在完成目标的同时，还会刺激其他个体机器人的工作，使其目标能够更快的达成，双方不具备冲突。

　　其次，虽然个体机器人在工作目标上具有一致性，但在资源的分配上具有一定的冲突，每个个体机器人都需要利用资源才能完成工作，如果资源没有得到合理的分配，就会导致个体机器人工作产生冲突，这也就需要在机器人组群系统的设计中，注重对资源的合理分配，从而减少个体机器人之间因为资源分配而产生的冲突。

　　3机器人组群系统个体任务分配算法

　　3.1机器人组群系统个体任务的分配

　　随着机器人组群系统工作和外部环境的不断变化，其中的个体机器人之间的交流与互动都会发生相应的转变。因此，在个体机器人的任务决策上，需要采用动态决策的方法，通过合理的分析外部环境和其他个体机器人工作的预判，来选择最合理的决策方向，从而达到工作效率和效果最大化的目的。在机器人组群系统个体任务分配算法中，通过与博弈论的内容相结合，可以将每一个个体机器人都看做博弈体系内的一部分，并与其他的个体机器人形成博弈局势，机器人组群系统中的个体任务分配，就是在博弈局势中按照宏观任务目标进行设计的任务决策思路，在机器人组群系统的个体任务分配上，可以用博弈公式来表示：

　　其中，N代表了整个机器人组群系统中个体机器人的总数，Si代表了每个个体机器人i所有可能处于的状态的合集，Bi代表了每个个体机器人i可能执行或接受的任务的合集，Qi代表了每个个体机器人i在观测期间内，执行联合任务的过程中所获得的效用，也就是个体机器人i所获得的奖赏函数。Q则代表了整个机器人组群系统在进行联合任务的过程中所获得的整体效用。

　　从本质上而言，机器人组群系统的个体任务分配过程，也就是统筹考虑多方面因素，来寻求一个最合理的任务分配策略的过程。由于机器人组群系统的工作目标具有一致性的特点，并且个体机器人i执行联合任务的过程中所获得的效用Qi与整个机器人组群系统在进行联合任务的过程中所获得的整体效用Q是呈现出单调递增态势的，这样一来一旦个体机器人i的效用Qi最大化，整个机器人组群系统的效用Q也能够达到最大化，因此，要注重合理的分配，来使得个体机器人i的效用达到最大化，从而促使整个机器人组群系统的运行绩效得以最大化的提升。

　　如以机器人火灾救援为例，在火灾救援中，机器人组群系统为了最高效的完成火灾救援任务，会主要从两个方面着手：首先，机器人组群系统要严格的遵守火灾紧急程度，通过先救援火势较大，并且随着火势的蔓延会有较大风险的地方，其次，要设置奖励值和惩罚值。由于每一处火灾的燃烧时间都有限，只有在燃烧结束之前对火灾进行扑救，才能最大限度的挽回火灾损失，因此，对于火灾而言，要保证在燃烧时间内尽快进行扑救，如果在火灾燃烧结束之前还没有将其扑灭，则需要为个体机器人给出惩罚值。火灾救援任务一方面要注重对火灾的扑救工作，另一方面要有足够高的效率，在最短时间内进行扑救，将二者整合考虑，赋予相应的奖励值和惩罚值，火灾救援质量就可以用奖励值減去惩罚值来直观的标识，差值越高则证明火灾救援工作越成功。

　　而对于整体而言，由于火灾救援工作是一项系统性的工作，并非扑灭几处火源就可以解决，而一些较大型的火源，个体机器人很难扑灭，因此，为了保证整个机器人组群系统的运行绩效最大化，经常会出现一些个体机器人放弃正在扑救的紧急程度较低的火源，转而去扑救大型火源的现象，这也就体现出了机器人组群系统的工作目标具有一致性的特点。

　　3.2博弈论视角下的机器人组群系统个体任务分配步骤

　　博弈论视角下的机器人组群系统个体任务分配步骤关键任务就是设置合理的函数，使得整个机器人组群系统的函数与个体机器人的函数呈现出单调递增的状态。而想要设计这种单调递增函数，就要按照以下几个步骤进行，层层选择最优的设置策略，从而保证整个机器人组群系统的工作绩效最大化。

　　（1）要对整个机器人组群系统的工作环境进行检测。工作环境对于机器人组群系统的工作状态有直接的影响，需要从复杂的工作环境中提取出与个体机器人任务分配的参数相关的向量，并将向量加入到分配参数公式中来。

　　（2）要评价机器人组群系统及个体机器人在执行任务时的效用值，并挑选出一个某时间段t上的一个任务bit作为参照时间点。

　　（3）要在这一时间点内，对机器人组群系统及个体机器人的状态进行观测，得到结论Si（t+1），并从中得到奖赏函数。

　　（4）要在这一时间点内，对机器人组群系统及个体机器人的任务效用值进行更新，提取出最新的数据。

　　（5）要对以上步骤进行重复，不断的更新新数据，直到整个工作流程结束。

　　4结语

　　博弈论的理论思想在机器人群组系统中的应用，主要体现在机器人群组系统的整体性上，其中每一个个体机器人都是机器人群组系统的重要组成部分，互相之间存在着直接的影响，据个体机器人对任所提出的协议进行强制性分析，如果协议的强制性较高，在个体机器人之间达成协议后就不能轻易的更改，而如果强制较低，也就进入到了非合作博弈中来，每个个体机器人互相独立，不形成机器人群组，也就不会形成相应的协议。同时，通过制订奖励值和惩罚值，让每个个体机器人都能够遵循奖励值最优化的处理方法，可以有效的提升机器人组群系统的整体效用。机器人组群系统个体任务分配算法既要采取动态决策的方法，针对机器人群组系统的外部环境变化，选择合理的决策方向，要基于宏观的任务目标，制定奖励值和惩罚值，保证个体机器人的任务分配能最大限度的提升奖励值与惩罚值的差值，从而提升机器人群组的整体工作效果。另外，在个体任务分配的函数设计上，要通过选取合适的时间点，对整个工作流程的任务效用值数据不断更新和提取，从而实现机器人群组系统的个体任务优化分配。

　　　参考文献 

　　[1]徐心和.从计算机博弈到机器人足球——人工智能长期而持续的挑战[J].机器人技术与应用，2010（01）：10-13. 

　　[2]刘小梅，田彦涛，杨茂.基于博弈论的多机器人任务分配算法[J].吉林大学学报（信息科学版），2010，28（03）：256-263. 

　　[3]柳长安，王静，刘春阳.基于合作4人博弈的足球机器人协作防守模型研究[J].系统仿真学报，2009，21（01）：132-134. 

　　作者简介 ：王韩（2001-），男，高中生。主要研究方向为计算机信息技术。 衡水市第二中学 河北省衡水市 053000