基于博弈論的機器人組群系統(tǒng)個體任務分配的算法

摘 要隨著科技水平的不斷提升，智能化的機器人組群系統(tǒng)在工業(yè)生產(chǎn)、火災救援等方面的運用愈發(fā)廣泛，有力的推動了傳統(tǒng)行業(yè)的發(fā)展。而由于機器人組群系統(tǒng)是由一定數(shù)量的機器人組成的，每個個體機器人都會分配到各自的任務，通過合理的分工和調(diào)配來完成機器人組群系統(tǒng)整體任務，因此，機器人組群系統(tǒng)的工作績效，就與個體機器人分配任務的水平有直接的關聯(lián)。本文通過闡述博弈論的基本內(nèi)涵，對機器人組群系統(tǒng)進行了分析，并提出了機器人組群系統(tǒng)個體任務分配算法，為優(yōu)化機器人組群系統(tǒng)結構，合理分配個體機器人任務起到了借鑒和參考作用。

【關鍵詞】博弈論 組群系統(tǒng) 機器人

機器人組群系統(tǒng)主要是由多種一定數(shù)量的個體機器人組成的，通過合理的分工和調(diào)配，可以使機器人組群系統(tǒng)達到個體機器人所無法達成的工作目標。而機器人組群系統(tǒng)所具有的優(yōu)越性，主要是通過合理的對個體任務分配達成的。由于機器人組群系統(tǒng)所處的環(huán)境會不斷的發(fā)生變化，這也就導致了個體機器人的決策方向會發(fā)生相應的轉變，給任務的分配帶來維數(shù)災難，這種高度的動態(tài)性和復雜性，為任務分配帶來極大的難度的同時，也會導致傳統(tǒng)的規(guī)劃方法無法繼續(xù)使用。因此，可以利用博弈論的基本原理，將每個個體機器人看做機器人組群系統(tǒng)的一部分，將其融入到環(huán)境之中，讓個體機器人能根據(jù)自身對周圍環(huán)境變化的理解，以及對其他機器人工作的預測，在一定任務的集合之中挑選出最符合實際情況的任務執(zhí)行，從而有效的提升機器人組群系統(tǒng)個體任務分配的水平。

1 博弈論的基本內(nèi)涵

機器人群組主要是由多個結構和功能簡單的個體機器人組成的，通過個體機器人的合作，來完成預先設計好的任務。而由于每個機器人都屬于一個個體，如何將整體的任務進行合理的分工與分配，讓每個機器人都能夠發(fā)揮出優(yōu)勢，優(yōu)化機器人群組的組織結構，提高整體的運行績效，也就成為了機器人群組研究的重點問題。而博弈論主要研究的就是智能設備或機器人之間相互合作和依存的關系，可以將機器人群組中每個個體的競爭與沖突利用形式化的方式進行表達，并通過合理的分配使機器人群組效益最大化，或風險最小化。而由于機器人群組是一個整體的系統(tǒng)，其中每一個個體機器人在進行決策之前都需要從其他個體機器人的角度，對其他個體的行為進行預測，才能得出最合理的決策任務，這也就是在機器人群組中，博弈論應用的基本內(nèi)容。博弈論主要存在以下三種元素：

（1）個體機器人集合，可以將其表示為：

（2）假設每個個體機器人i都有一定數(shù)量的決策方向可供選擇，那么每個個體機器人所構成的純策略空間可以表示為。其中，在純策略空間Ai上的一個概率分布，也就是個體機器人i的混合策略。Xim表示為選擇λim的概率，可得公式：

個體機器人i所能夠選擇的策略記為，是個體機器人i的一個可選任務計劃，也是在博弈的過程中，每個環(huán)節(jié)個體機器人i所分配到一個任務的概率函數(shù)，因此，πi，個體機器人i所能選擇的所有策略集合為={πi1，πi2，……，π}。

（3）機器人群組中每個個體機器人都會有對應的獎賞函數(shù)，記為ri（π），其中π={π1，π2，……，πN}表示了第N個個體機器人的決策局勢。個體決策的每一個決策都可以用公式=來表示，假設π||Pi=（π1，π2，……，πi-1，Pi，πi+1，……，πN）在決策局勢當中，個體機器人將決策πi轉變?yōu)镻i，其他個體機器人不發(fā)生變化，也就可以得到新的局勢：π||P||πi，經(jīng)過計算可以得出，π是一個重要平衡點。

在博弈論中，主要可以根據(jù)個體機器人對任所提出的協(xié)議進行強制性分析，如果協(xié)議的強制性較高， 在個體機器人之間達成協(xié)議后就不能輕易的更改，而如果強制較低，也就進入到了非合作博弈中來，每個個體機器人互相獨立，不形成機器人群組，也就不會形成相應的協(xié)議。

2 機器人組群系統(tǒng)分析

機器人的群組系統(tǒng)具有以下幾種特點：

（1）機器人組群系統(tǒng)是由多種個體機器人所組成的，這些機器既有可能是同構機器人，還有可能是異構機器人?？梢杂眉媳硎緸锳=（a1，a2，……，aN）。

（2）機器人組群系統(tǒng)會呈現(xiàn)在一定的環(huán)境狀態(tài)之中，這種環(huán)境狀態(tài)會隨著時間的變化而變化。在某一時段t內(nèi)，機器人組群系統(tǒng)的狀態(tài)可以表示為st'∈s'。

（3）機器人組群系統(tǒng)所處的環(huán)境狀態(tài)是可觀測的，個體機器人通過利用自身所攜帶的各種通信、感應設備可以直觀的觀測到機器人組群系統(tǒng)所處的環(huán)境。利用公式表述為

。

（4）個體機器人可以通過進行聯(lián)合任務的方式，改變機器人組群系統(tǒng)所處的環(huán)境狀態(tài)。假設機器人組群系統(tǒng)的任務合集為B，Bi也就是個體機器人i的任務合集，因此，

。個體機器人為了改變整個機器人組群系統(tǒng)的外部環(huán)境，會通過觀測來選擇一個恰當?shù)娜蝿誦i∈Bi，通過執(zhí)行該任務來達到影響外部環(huán)境的目的。而從宏觀的角度來看，機器人組群系統(tǒng)中的每個個體機器人可以通過聯(lián)合任務來改變自身所處的環(huán)境狀態(tài)。

（5）由于機器人組群系統(tǒng)是一種智能化的系統(tǒng)，其中每一個個體機器人帶有一定的學識，包括對于整個系統(tǒng)流程的掌握、周圍環(huán)境、其他個體機器人的工作和預測、對自身任務的和決策等，這也就體現(xiàn)出了個體機器人的任務和決策會隨著與外界環(huán)境的不斷流通而發(fā)生變化。

（6）個體機器人具有自我決策的功能，自我決策功能是個體機器人通過對外界環(huán)境、其他個體及機器人的任務及趨勢預測等，從而對自身任務進行合理的決策和規(guī)劃，由于個體機器人具有決策功能，這也就使得機器人組群系統(tǒng)的工作績效水平會有極大的提高。

（7）個體機器人的決策并不是一成不變的，隨著機器人工作的不斷開展，會隨著外部環(huán)境的變化，或是所產(chǎn)生的獎懲來判斷自己的決策是否合理，通過不斷的更新決策觀念，可以保證個體機器人的決策方向大體正確，并且具有較高的績效水平，這從本質上而言也是一種反思和學習的過程。

（8）機器人組群系統(tǒng)中的目標眾多，每個個體機器人在不同的工作階段，都會產(chǎn)生不同的工作目標，同時，機器人組群系統(tǒng)整體又存在一個宏觀的工作目標。機器人組群系統(tǒng)的工作目標主要有以下幾種特點：

首先，機器人組群系統(tǒng)的工作目標具有一致性的特點，無論每個個體機器人的工作目標如何變動，其整體的工作目標依然具有一致性的特點。一個個體機器人在完成目標的同時，還會刺激其他個體機器人的工作，使其目標能夠更快的達成，雙方不具備沖突。

其次，雖然個體機器人在工作目標上具有一致性，但在資源的分配上具有一定的沖突，每個個體機器人都需要利用資源才能完成工作，如果資源沒有得到合理的分配，就會導致個體機器人工作產(chǎn)生沖突，這也就需要在機器人組群系統(tǒng)的設計中，注重對資源的合理分配，從而減少個體機器人之間因為資源分配而產(chǎn)生的沖突。

3 機器人組群系統(tǒng)個體任務分配算法

3.1 機器人組群系統(tǒng)個體任務的分配

隨著機器人組群系統(tǒng)工作和外部環(huán)境的不斷變化，其中的個體機器人之間的交流與互動都會發(fā)生相應的轉變。因此，在個體機器人的任務決策上，需要采用動態(tài)決策的方法，通過合理的分析外部環(huán)境和其他個體機器人工作的預判，來選擇最合理的決策方向，從而達到工作效率和效果最大化的目的。在機器人組群系統(tǒng)個體任務分配算法中，通過與博弈論的內(nèi)容相結合，可以將每一個個體機器人都看做博弈體系內(nèi)的一部分，并與其他的個體機器人形成博弈局勢，機器人組群系統(tǒng)中的個體任務分配，就是在博弈局勢中按照宏觀任務目標進行設計的任務決策思路，在機器人組群系統(tǒng)的個體任務分配上，可以用博弈公式來表示：

其中，N代表了整個機器人組群系統(tǒng)中個體機器人的總數(shù)，Si代表了每個個體機器人i所有可能處于的狀態(tài)的合集，Bi代表了每個個體機器人i可能執(zhí)行或接受的任務的合集，Qi代表了每個個體機器人i在觀測期間內(nèi)，執(zhí)行聯(lián)合任務的過程中所獲得的效用，也就是個體機器人i所獲得的獎賞函數(shù)。Q則代表了整個機器人組群系統(tǒng)在進行聯(lián)合任務的過程中所獲得的整體效用。

從本質上而言，機器人組群系統(tǒng)的個體任務分配過程，也就是統(tǒng)籌考慮多方面因素，來尋求一個最合理的任務分配策略的過程。由于機器人組群系統(tǒng)的工作目標具有一致性的特點，并且個體機器人i執(zhí)行聯(lián)合任務的過程中所獲得的效用Qi與整個機器人組群系統(tǒng)在進行聯(lián)合任務的過程中所獲得的整體效用Q是呈現(xiàn)出單調(diào)遞增態(tài)勢的，這樣一來一旦個體機器人i的效用Qi最大化，整個機器人組群系統(tǒng)的效用Q也能夠達到最大化，因此，要注重合理的分配，來使得個體機器人i的效用達到最大化，從而促使整個機器人組群系統(tǒng)的運行績效得以最大化的提升。

如以機器人火災救援為例，在火災救援中，機器人組群系統(tǒng)為了最高效的完成火災救援任務，會主要從兩個方面著手：首先，機器人組群系統(tǒng)要嚴格的遵守火災緊急程度，通過先救援火勢較大，并且隨著火勢的蔓延會有較大風險的地方，其次，要設置獎勵值和懲罰值。由于每一處火災的燃燒時間都有限，只有在燃燒結束之前對火災進行撲救，才能最大限度的挽回火災損失，因此，對于火災而言，要保證在燃燒時間內(nèi)盡快進行撲救，如果在火災燃燒結束之前還沒有將其撲滅，則需要為個體機器人給出懲罰值。火災救援任務一方面要注重對火災的撲救工作，另一方面要有足夠高的效率，在最短時間內(nèi)進行撲救，將二者整合考慮，賦予相應的獎勵值和懲罰值，火災救援質量就可以用獎勵值減去懲罰值來直觀的標識，差值越高則證明火災救援工作越成功。

而對于整體而言，由于火災救援工作是一項系統(tǒng)性的工作，并非撲滅幾處火源就可以解決，而一些較大型的火源，個體機器人很難撲滅，因此，為了保證整個機器人組群系統(tǒng)的運行績效最大化，經(jīng)常會出現(xiàn)一些個體機器人放棄正在撲救的緊急程度較低的火源，轉而去撲救大型火源的現(xiàn)象，這也就體現(xiàn)出了機器人組群系統(tǒng)的工作目標具有一致性的特點。

3.2 博弈論視角下的機器人組群系統(tǒng)個體任務分配步驟

博弈論視角下的機器人組群系統(tǒng)個體任務分配步驟關鍵任務就是設置合理的函數(shù)，使得整個機器人組群系統(tǒng)的函數(shù)與個體機器人的函數(shù)呈現(xiàn)出單調(diào)遞增的狀態(tài)。而想要設計這種單調(diào)遞增函數(shù)，就要按照以下幾個步驟進行，層層選擇最優(yōu)的設置策略，從而保證整個機器人組群系統(tǒng)的工作績效最大化。

（1）要對整個機器人組群系統(tǒng)的工作環(huán)境進行檢測。工作環(huán)境對于機器人組群系統(tǒng)的工作狀態(tài)有直接的影響，需要從復雜的工作環(huán)境中提取出與個體機器人任務分配的參數(shù)相關的向量，并將向量加入到分配參數(shù)公式中來。

（2）要評價機器人組群系統(tǒng)及個體機器人在執(zhí)行任務時的效用值，并挑選出一個某時間段t上的一個任務bit作為參照時間點。

（3）要在這一時間點內(nèi)，對機器人組群系統(tǒng)及個體機器人的狀態(tài)進行觀測，得到結論Si（t+1），并從中得到獎賞函數(shù)。

（4）要在這一時間點內(nèi)，對機器人組群系統(tǒng)及個體機器人的任務效用值進行更新，提取出最新的數(shù)據(jù)。

（5）要對以上步驟進行重復，不斷的更新新數(shù)據(jù)，直到整個工作流程結束。

4 結語

博弈論的理論思想在機器人群組系統(tǒng)中的應用，主要體現(xiàn)在機器人群組系統(tǒng)的整體性上，其中每一個個體機器人都是機器人群組系統(tǒng)的重要組成部分，互相之間存在著直接的影響，據(jù)個體機器人對任所提出的協(xié)議進行強制性分析，如果協(xié)議的強制性較高，在個體機器人之間達成協(xié)議后就不能輕易的更改，而如果強制較低，也就進入到了非合作博弈中來，每個個體機器人互相獨立，不形成機器人群組，也就不會形成相應的協(xié)議。同時，通過制訂獎勵值和懲罰值，讓每個個體機器人都能夠遵循獎勵值最優(yōu)化的處理方法，可以有效的提升機器人組群系統(tǒng)的整體效用。機器人組群系統(tǒng)個體任務分配算法既要采取動態(tài)決策的方法，針對機器人群組系統(tǒng)的外部環(huán)境變化，選擇合理的決策方向，要基于宏觀的任務目標，制定獎勵值和懲罰值，保證個體機器人的任務分配能最大限度的提升獎勵值與懲罰值的差值，從而提升機器人群組的整體工作效果。另外，在個體任務分配的函數(shù)設計上，要通過選取合適的時間點，對整個工作流程的任務效用值數(shù)據(jù)不斷更新和提取，從而實現(xiàn)機器人群組系統(tǒng)的個體任務優(yōu)化分配。

參考文獻

[1]徐心和.從計算機博弈到機器人足球——人工智能長期而持續(xù)的挑戰(zhàn)[J].機器人技術與應用，2010（01）：10-13.

[2]劉小梅，田彥濤，楊茂.基于博弈論的多機器人任務分配算法[J].吉林大學學報（信息科學版），2010，28（03）：256-263.

[3]柳長安，王靜，劉春陽.基于合作4人博弈的足球機器人協(xié)作防守模型研究[J].系統(tǒng)仿真學報，2009，21（01）：132-134.

作者簡介

王韓（2001-），男，高中生。主要研究方向為計算機信息技術。

作者單位

衡水市第二中學 河北省衡水市 053000endprint