吳文臻

摘要：松散型合作群機(jī)器人系統(tǒng)在現(xiàn)階段煤礦輔助機(jī)器人作業(yè)中具有廣泛應(yīng)用前景。但松散型合作群機(jī)器人系統(tǒng)的任務(wù)分配過(guò)程未向劃分過(guò)程進(jìn)行反饋，導(dǎo)致任務(wù)劃分與分配過(guò)程高效性與合理性不足。針對(duì)該問(wèn)題，提出一種基于改進(jìn)型魯賓斯坦協(xié)商策略的煤礦井下群機(jī)器人高效任務(wù)分配算法。根據(jù)群機(jī)器人系統(tǒng)任務(wù)劃分與分配過(guò)程的多方博弈特點(diǎn)，將魯賓斯坦協(xié)商策略由雙方博弈向多方共同博弈方向延伸，提出多方協(xié)商博弈的“出價(jià)?討價(jià)?還價(jià)”規(guī)則。從機(jī)器人個(gè)體執(zhí)行能力與任務(wù)執(zhí)行情況差異的角度出發(fā)，提出基于機(jī)器人個(gè)體單位時(shí)間任務(wù)完成量的折扣因子計(jì)算方法，以及基于各分配周期任務(wù)執(zhí)行情況的任務(wù)完成狀態(tài)反饋參數(shù)模型，以實(shí)現(xiàn)任務(wù)的動(dòng)態(tài)劃分與分配。通過(guò)3組機(jī)器人合作執(zhí)行煤礦礦區(qū)的整體監(jiān)測(cè)任務(wù)，對(duì)算法性能開展實(shí)驗(yàn)驗(yàn)證，結(jié)果表明：①算法3（采用改進(jìn)型魯賓斯坦協(xié)商策略）的任務(wù)劃分與分配效率較算法1（將每組無(wú)人機(jī)數(shù)量與運(yùn)行速度乘積的比例直接作為3組無(wú)人機(jī)任務(wù)劃分與分配的標(biāo)準(zhǔn)）、算法2（使用多方共同協(xié)商的魯賓斯坦協(xié)商策略，但不考慮任務(wù)完成狀態(tài)反饋參數(shù)）分別提升了30.10%，18.29%。②基于算法3的3組無(wú)人機(jī)執(zhí)行任務(wù)的平均最大時(shí)間差為42 s，較算法1、算法2分別優(yōu)化了77.66%，65.29%，這是由于算法3通過(guò)引入任務(wù)完成狀態(tài)反饋參數(shù)，及時(shí)對(duì)任務(wù)參與方的任務(wù)執(zhí)行過(guò)程進(jìn)行評(píng)估，將任務(wù)的分配和執(zhí)行過(guò)程向任務(wù)的劃分階段進(jìn)行反饋，使任務(wù)的劃分與分配更加準(zhǔn)確。

關(guān)鍵詞：煤礦井下群機(jī)器人；松散型合作群機(jī)器人；魯賓斯坦協(xié)商策略；任務(wù)劃分與分配；折扣因子；狀態(tài)反饋

中圖分類號(hào)： TD67??? 文獻(xiàn)標(biāo)志碼： A

Efficient task assignment algorithm for coal mine underground group robots

WU Wenzhen1，2

（1. CCTEG China Coal Research Institute ， Beijing 100013， China；2. State Key Laboratory ofHigh Efficient Mining and Clean Utilization of Coal Resources， Beijing 100013， China）

Abstract： The loose cooperative group robot system has broad application prospects in the current coal mine auxiliary robot operation. However， the task assignment process of the loose cooperative group robot system did not provide feedback to the division process， resulting in insufficient efficiency and rationality of the task division and assignment process. To address this issue， an efficient task assignment algorithm for coal mine underground group robots based on an improved Rubinstein negotiation strategy is proposed. Based on the multi-party game features of task division and assignment in group robot systems， the Rubinstein negotiation strategy is extended from a bipartite game to a multi-party joint game. A "bid-bargain-counteroffer" rule for multi-party negotiation games is proposed. From the perspective of the difference between the execution capability and task execution status of individual robots， a discount factor calculation method based on the task completion quantity per unittime of robot individuals is proposed. A task completion status feedback parameter model based on the task execution status of each assignment cycle is also proposed to achieve dynamic task division and assignment. By collaborating with three groups of robots to perform overall monitoring tasks in coal mining areas， experimental verification is conducted on the performance of the algorithm. The results show the following points.① Algorithm 3 uses an improved Rubinstein negotiation strategy. Algorithm 1 directly uses the ratio of the number of unmanned aerial vehicles in each group multiplied by their running speed as the standard for task division and assignment in three groups of unmanned aerial vehicles. Algorithm 2 uses the Rubinstein negotiation strategy of multi-party negotiation without considering the feedback parameters of task completion status. Algorithm 3 has a higher efficiency in task division and assignment than Algorithm 1 and Algorithm 2 by 30.10% and 18.29% respectively.② The average maximum time difference for the three groups of unmanned aerial vehicles based on Algorithm 3 to execute tasks is 42 seconds. It is 77.66% and 65.29% optimized compared to Algorithm 1 and Algorithm 2， respectively. This is because Algorithm 3 introduces task completion status feedback parameters to timely evaluate the task execution process of the task participants. Algorithm 3 provides feedback on the task assignment and execution process to the task division stages， making the task division and assignment more accurate.

Key words： coal mine underground group robots; loose cooperative group robots; Rubinstein negotiation strategy; task division and assignment; discount factor; state feedback

0 引言

機(jī)器人在煤炭行業(yè)的應(yīng)用研究是煤礦智能化技術(shù)創(chuàng)新的關(guān)鍵方向。作為機(jī)器人的核心組成部分，移動(dòng)機(jī)器人已逐漸滲透到“采、掘、機(jī)、運(yùn)、通”等煤礦生產(chǎn)的各個(gè)環(huán)節(jié)[1]。尤其是在面對(duì)如礦井采空區(qū)沉降監(jiān)測(cè)、井下大面積危險(xiǎn)區(qū)域監(jiān)測(cè)等可并行完成的任務(wù)時(shí)，由多個(gè)具備簡(jiǎn)單結(jié)構(gòu)與功能的同構(gòu)機(jī)器人單元組成的群機(jī)器人系統(tǒng)可在任務(wù)執(zhí)行效率方面展現(xiàn)出巨大優(yōu)勢(shì)[2]。在群機(jī)器人系統(tǒng)中，機(jī)器人單元之間的合作方式分為緊密型和松散型2種。緊密型合作方式主要基于行為技術(shù)、虛擬向量場(chǎng)技術(shù)實(shí)現(xiàn)機(jī)器人單元的高度協(xié)調(diào)運(yùn)作，需要實(shí)時(shí)預(yù)知與優(yōu)化多種因素，因此主要應(yīng)用于機(jī)器人編隊(duì)保持或合作搬運(yùn)等強(qiáng)實(shí)時(shí)協(xié)作場(chǎng)景；松散型合作方式主要基于不同類型任務(wù)分配策略，在每個(gè)任務(wù)執(zhí)行周期初始階段實(shí)現(xiàn)機(jī)器人單元的任務(wù)分配，由于其對(duì)機(jī)器人單元實(shí)時(shí)性配合要求低，更適用于礦山救援、環(huán)境探測(cè)、災(zāi)害監(jiān)測(cè)等任務(wù)中的未知區(qū)域探索和地圖構(gòu)建等場(chǎng)景[3-5]。因此，松散型合作群機(jī)器人系統(tǒng)在現(xiàn)階段煤礦輔助機(jī)器人作業(yè)中有廣泛應(yīng)用前景。

松散型合作群機(jī)器人系統(tǒng)中，任務(wù)被劃分為多個(gè)子任務(wù)，并分配至群機(jī)器人系統(tǒng)中的機(jī)器人單元分別執(zhí)行。任務(wù)劃分是以機(jī)器人單元的預(yù)定義任務(wù)執(zhí)行成本為基礎(chǔ)。在任務(wù)分配完成后，機(jī)器人單元自身任務(wù)執(zhí)行能力是任務(wù)執(zhí)行效果最大的影響因素[6]。由于松散型合作方式關(guān)注的重點(diǎn)是任務(wù)分配問(wèn)題，其任務(wù)劃分過(guò)程被假定為已經(jīng)在協(xié)作技術(shù)框架外完成，所以松散型合作的主要缺點(diǎn)是任務(wù)分配過(guò)程與任務(wù)劃分過(guò)程不是一體化，任務(wù)分配過(guò)程不會(huì)向任務(wù)劃分過(guò)程進(jìn)行反饋，導(dǎo)致任務(wù)分配過(guò)程中遇到的錯(cuò)誤不能被及時(shí)修正[7-8]，進(jìn)而導(dǎo)致任務(wù)的整體執(zhí)行周期過(guò)長(zhǎng)，即任務(wù)執(zhí)行高效性不足，同時(shí)任務(wù)執(zhí)行過(guò)程中機(jī)器人個(gè)體的空閑率過(guò)高，即任務(wù)分配合理性不足。例如松散型合作方式中運(yùn)用最廣泛的任務(wù)分配算法——合同網(wǎng)算法中，每個(gè)機(jī)器人單元會(huì)根據(jù)預(yù)定義的成本和收入函數(shù)來(lái)計(jì)算每個(gè)任務(wù)的預(yù)期收益和損失，然而機(jī)器人單元的偏好和限制等因素只在任務(wù)分配階段被考慮，并沒(méi)有在任務(wù)劃分階段考慮，導(dǎo)致任務(wù)分配的合理性不足[9]。

魯賓斯坦協(xié)商策略是博弈論方面的合作博弈模型，沒(méi)有第三方強(qiáng)制結(jié)束機(jī)制與任何附加基礎(chǔ)，最終分配結(jié)果完全由博弈參與方自身因素決定，可兼顧所有博弈參與方最大利益[10]。魯賓斯坦協(xié)商策略主要用于解決雙方合作之前對(duì)總?cè)蝿?wù)量的分配問(wèn)題，用完全信息動(dòng)態(tài)博弈方法模擬基本的、無(wú)限期的完全信息討價(jià)還價(jià)過(guò)程，并據(jù)此將整個(gè)博弈建立為完全信息輪流“出價(jià)?討價(jià)?還價(jià)”模型[11]。

針對(duì)群機(jī)器人系統(tǒng)在任務(wù)劃分與分配過(guò)程中高效性與合理性不足的問(wèn)題，本文將魯賓斯坦協(xié)商策略與群機(jī)器人系統(tǒng)松散型合作方式的任務(wù)劃分與分配相融合，提出煤礦井下群機(jī)器人高效任務(wù)分配算法。首先，將魯賓斯坦協(xié)商策略由雙方博弈向多方共同博弈方向延伸；然后，基于機(jī)器人個(gè)體的不同執(zhí)行能力及當(dāng)前任務(wù)的執(zhí)行情況，融入表示任務(wù)完成狀態(tài)的反饋參數(shù)，構(gòu)建折扣因子計(jì)算模型，最終實(shí)現(xiàn)任務(wù)的動(dòng)態(tài)劃分與分配；最后，通過(guò)3組機(jī)器人共同合作執(zhí)行煤礦礦區(qū)整體監(jiān)測(cè)任務(wù)，對(duì)算法的任務(wù)劃分與分配策略進(jìn)行驗(yàn)證，并對(duì)算法的高效性與合理性展開實(shí)驗(yàn)驗(yàn)證。

1 魯賓斯坦協(xié)商策略基本理論

在魯賓斯坦協(xié)商策略中，根據(jù)輪流“出價(jià)?討價(jià)?還價(jià)”模型，參與協(xié)商博弈的雙方輪流提出希望得到的份額。博弈從發(fā)起者開始，得到報(bào)價(jià)的一方可選擇接受報(bào)價(jià)，即最終達(dá)成協(xié)議，也可選擇拒絕報(bào)價(jià)，并向?qū)Ψ教岢鲂碌膱?bào)價(jià)。博弈過(guò)程會(huì)一直持續(xù)下去，直到博弈雙方最終達(dá)成協(xié)議。該博弈過(guò)程參與方的出價(jià)方式都是加密的，每個(gè)參與方都不會(huì)掌握對(duì)方準(zhǔn)確的出價(jià)方式，且通過(guò)運(yùn)用魯賓斯坦協(xié)商策略能夠保證參與博弈的雙方最終達(dá)成協(xié)議[12-13]。

1.1 折扣因子

在魯賓斯坦協(xié)商策略模型中，參與雙方都有一個(gè)與其自身特征相匹配的折扣因子，折扣因子越小，通過(guò)博弈最終所得任務(wù)份額越少。折扣因子為參與方的加密信息，對(duì)方無(wú)法得到該信息。假設(shè)總?cè)蝿?wù)量為1，參與雙方首次提出的任務(wù)份額均接近總?cè)蝿?wù)量（一般取總?cè)蝿?wù)量的99%），且提出的任務(wù)份額隨博弈輪數(shù)的增加逐漸減小。隨著博弈的進(jìn)行，提出報(bào)價(jià)的參與方新要求的任務(wù)份額 K 與上一輪要求任務(wù)份額 L 之間關(guān)系為[14-15]

K =δL??????? （1）

式中δ為折扣因子，0<δ＜1。

將協(xié)商發(fā)起者和響應(yīng)者的折扣因子分別記為δ1和δ2，首次提出的任務(wù)份額分別記為p和q，協(xié)商過(guò)程如圖1所示。發(fā)起者先出價(jià)p，響應(yīng)者可以接受或拒絕1-p的份額。如果響應(yīng)者接受，則博弈結(jié)束，博弈結(jié)果按發(fā)起者提出的方案執(zhí)行；如果響應(yīng)者拒絕，則響應(yīng)者出價(jià)（還價(jià)）q，發(fā)起者可以接受或拒絕 1- q 的份額；如果發(fā)起者接受，則博弈結(jié)束，博弈結(jié)果按響應(yīng)者提出的方案執(zhí)行；如果發(fā)起者拒絕，發(fā)起者再出價(jià)δ1p；如此持續(xù)進(jìn)行下去，直到參與博弈的某一方出價(jià)被另一方接受為止。因此這是一個(gè)無(wú)限期完全信息博弈，發(fā)起者在輪數(shù)1，3，5，…出價(jià)，響應(yīng)者在輪數(shù)2，4，6，…出價(jià)。

1.2 博弈平衡

魯賓斯坦協(xié)商策略的博弈過(guò)程長(zhǎng)度不確定，通過(guò)運(yùn)用有限階段逆向歸納法可獲取博弈平衡點(diǎn)[16]。假設(shè)在第i（i≥3）輪博弈時(shí)參與人1出價(jià)M，參與人2在得到份額為1- M后達(dá)成協(xié)議。當(dāng)?shù)趇輪博弈時(shí)的 M 等價(jià)于第i-1輪博弈時(shí)的δ1 M，參與人2在第 i-1輪博弈時(shí)得到1-δ1 M。同理，當(dāng)?shù)趇-1輪博弈時(shí)的1-δ1 M等價(jià)于第i-2輪博弈時(shí)的δ2（1-δ1 M），參與人1在第i-2輪博弈時(shí)得到1-δ2（1-δ1 M），如圖2所示，因此可得博弈結(jié)束時(shí)參與人1理論上能夠得到的份額，即理論博弈平衡點(diǎn) M。

由于參與雙方出價(jià)策略具有保密性，博弈過(guò)程中雙方無(wú)法通過(guò)理論博弈平衡點(diǎn)判斷博弈是否結(jié)束，所以只能通過(guò)參與博弈的某一方判斷對(duì)方的剩余報(bào)價(jià)是否大于自身在下一輪博弈中準(zhǔn)備提出的報(bào)價(jià)，如果大于自身準(zhǔn)備提出的報(bào)價(jià)，則博弈結(jié)束，否則進(jìn)行下一輪的博弈[17-18]。

2 基于改進(jìn)型魯賓斯坦協(xié)商策略的群機(jī)器人任務(wù)劃分與分配算法

群機(jī)器人任務(wù)劃分與分配問(wèn)題可看作多方合作博弈的過(guò)程。根據(jù)群機(jī)器人系統(tǒng)的工作特點(diǎn)，遵循魯賓斯坦協(xié)商策略中提出的輪流“出價(jià)?討價(jià)?還價(jià)”思想，將魯賓斯坦協(xié)商策略參與方的數(shù)量由限定的雙方協(xié)商向多方共同協(xié)商的方向進(jìn)行拓展延伸，通過(guò)對(duì)任務(wù)完成的狀態(tài)進(jìn)行實(shí)時(shí)反饋，使群機(jī)器人在任務(wù)劃分與分配過(guò)程中體現(xiàn)出高效性和合理性[19]。

2.1 多方共同協(xié)商博弈過(guò)程

基于改進(jìn)型魯賓斯坦協(xié)商策略的群機(jī)器人任務(wù)采用“循環(huán)出價(jià)，末位決定”原則進(jìn)行博弈。在n個(gè)參與方共同博弈的過(guò)程中，由前n-1個(gè)參與方分別提出希望得到的份額，第n個(gè)參與方選擇接受或拒絕，如果選擇接受，則博弈結(jié)束，博弈結(jié)果按照前n-1個(gè)參與方提出的份額進(jìn)行劃分與分配；如果選擇拒絕，則第n個(gè)參與方與前n-2個(gè)參與方再分別提出希望得到的份額，第n-1個(gè)參與方選擇接受或拒絕，如果選擇接受，則博弈結(jié)束，博弈結(jié)果按前n-2個(gè)參與方與第 n個(gè)參與方提出的份額進(jìn)行劃分與分配；如果選擇拒絕，則前n-3個(gè)與后2個(gè)參與方再分別提出希望得到的份額，第n-2個(gè)參與方選擇接受或拒絕；依此類推，直到最終任務(wù)劃分與分配份額被所有參與方接受為止[20]。

以3方共同協(xié)商博弈為例（圖3），將協(xié)商參與方的折扣因子分別記為δ1，δ2，δ3，首次提出的任務(wù)份額分別記為 X，Y，Z。第1輪博弈由參與方 A 和參與方 B 先出價(jià)，參與方 C 可以接受或拒絕。如果參與方 C 接受，則博弈結(jié)束，博弈結(jié)果按照參與方 A 和參與方 B 提出的方案執(zhí)行；如果參與方 C 拒絕，第2輪博弈開始，參與方 C 和參與方 A 共同出價(jià)（還價(jià)），參與方 B 可以接受或拒絕；如果參與方 B 接受，則博弈結(jié)束，博弈結(jié)果按參與方 C 和參與方 A 提出的方案執(zhí)行；如果參與方 B 拒絕，第3輪博弈開始，參與方 B 和參與方 C再出價(jià)；如此一直進(jìn)行下去，直到出價(jià)被3個(gè)參與方都接受為止。

2.2 折扣因子計(jì)算模型

折扣因子δ表示任務(wù)參與方對(duì)任務(wù)的執(zhí)行能力，是根據(jù)各參與方的自身特征來(lái)確定的加密參數(shù)，對(duì)任務(wù)最終的分配比例起著決定性作用。折扣因子的影響因素有諸多方面，每個(gè)影響因素的變化對(duì)折扣因子造成的影響程度差別很大。根據(jù)任務(wù)的不同，將影響因素分為主要部分和次要部分，這里只考慮對(duì)任務(wù)劃分有較大影響的主要部分。

如果影響因素大小與單位時(shí)間內(nèi)完成的任務(wù)量成正比，則隨著影響因素?cái)?shù)值增大，單位時(shí)間內(nèi)完成的任務(wù)量變化趨勢(shì)為遞增（如果影響因素大小與單位時(shí)間內(nèi)完成任務(wù)量成反比，則取影響因素的倒數(shù)作為其數(shù)值）。任取多個(gè)對(duì)數(shù)型、指數(shù)型及比例型3種典型遞增模式的影響因素進(jìn)行分析，如圖4所示。首先給出影響因素?cái)?shù)值x與單位時(shí)間完成的任務(wù)量f 之間的關(guān)系，可知隨著不同影響因素?cái)?shù)值的增大，單位時(shí)間內(nèi)完成任務(wù)量的遞增趨勢(shì)差別較大。完成單位任務(wù)量所需時(shí)間為t，則t和f 之間的關(guān)系為 t =1/ f ，則基于x與f 之間的變化關(guān)系，可得影響因素?cái)?shù)值x與t 的關(guān)系，當(dāng)x一定時(shí)，t越大表示任務(wù)完成效率越低。

基于x與t 的變化關(guān)系，用折扣因子δ表示1- t，即表示影響因素對(duì)任務(wù)的影響能力，可得影響因素?cái)?shù)值x與其折扣因子δ的關(guān)系，如圖5所示?？煽闯鲭S著影響因素?cái)?shù)值增大，如果單位時(shí)間內(nèi)完成任務(wù)量增大的幅度越大，即折扣因子增長(zhǎng)越快，則該影響因素對(duì)任務(wù)的影響能力就越大，意味著該影響因素越影響因素?cái)?shù)值x與折扣因子δ間的關(guān)系為

式中r為影響因素的權(quán)重系數(shù)，0＜r≤1，r 越大，單位時(shí)間完成的任務(wù)量越多，折扣因子越大，即越重要。

以指數(shù)型、對(duì)數(shù)型及比例型3種典型增長(zhǎng)曲線為例，對(duì)影響因素?cái)?shù)值x與折扣因子δ之間的關(guān)系進(jìn)行驗(yàn)證，結(jié)果如圖6所示。首先取3種影響因素?cái)?shù)值x與單位時(shí)間完成任務(wù)量f 的數(shù)據(jù)，分別滿足上述3種典型類型變化趨勢(shì)，如圖6（a）所示。根據(jù)影響因素?cái)?shù)值x、完成單位任務(wù)量所需時(shí)間t及折扣因子δ之間的轉(zhuǎn)換關(guān)系，可得影響因素?cái)?shù)值x與其折扣因子δ關(guān)系，如圖6（b）所示?？煽闯鲭S著影響因素?cái)?shù)值增大，指數(shù)型增長(zhǎng)模式在單位時(shí)間內(nèi)完成任務(wù)量增大幅度最大，折扣因子增長(zhǎng)最快，即該影響因素重要性最大，比例型增長(zhǎng)次之，對(duì)數(shù)型增長(zhǎng)最小。

分別為3種影響因素選取合適權(quán)重系數(shù)，代入式（3）進(jìn)行驗(yàn)證，其中指數(shù)型增長(zhǎng)的權(quán)重系數(shù) r1=0：078，對(duì)數(shù)型增長(zhǎng) r2=0：009，比例型增長(zhǎng) r3=0：025，將所得的計(jì)算結(jié)果與圖6（b）中理論結(jié)果進(jìn)行對(duì)比，結(jié)果如圖7所示?？煽闯稣劭垡蜃佑?jì)算結(jié)果與理論結(jié)果之間的誤差在0.02范圍內(nèi)，所以在權(quán)重系數(shù)選擇恰當(dāng)?shù)那疤嵯?，式?）可對(duì)影響因素與折扣因子間的關(guān)系進(jìn)行較好描述。

由于影響因素之間是耦合的，針對(duì)多個(gè)影響因素對(duì)折扣因子產(chǎn)生的影響，影響因素?cái)?shù)值x與折扣因子δ的關(guān)系為

式中：k為任務(wù)完成狀態(tài)反饋參數(shù)；m為影響因素總數(shù)；xj為第j 個(gè)影響因素?cái)?shù)值；rj為第j 個(gè)影響因素的權(quán)重系數(shù)。

在折扣因子中引入任務(wù)完成狀態(tài)反饋參數(shù)k，對(duì)上一個(gè)分配周期任務(wù)執(zhí)行情況進(jìn)行評(píng)估，根據(jù)評(píng)估結(jié)果對(duì)任務(wù)劃分與分配情況進(jìn)行調(diào)整，使群機(jī)器人系統(tǒng)最大限度地發(fā)揮自身任務(wù)執(zhí)行能力，進(jìn)而高效完成任務(wù)。任務(wù)完成狀態(tài)反饋參數(shù)k為

式中：W為任務(wù)執(zhí)行度參數(shù)，表示在上一個(gè)分配周期中完成的任務(wù)量與分配總?cè)蝿?wù)量比值；Waverage為平均任務(wù)執(zhí)行度參數(shù)，表示上一個(gè)分配周期中所有任務(wù)參與方任務(wù)執(zhí)行度參數(shù)的算術(shù)平均數(shù)。

第1個(gè)分配周期（任務(wù)劃分的初始階段）進(jìn)行任務(wù)劃分與分配時(shí)k =1。

2.3 多方協(xié)商平衡

改進(jìn)型魯賓斯坦協(xié)商策略的最大特點(diǎn)是任務(wù)劃分與分配由原來(lái)的雙方進(jìn)行博弈改進(jìn)為多方博弈。由于最終的博弈平衡需要滿足所有參與方的需求份額，所以其博弈過(guò)程更為復(fù)雜，持續(xù)時(shí)間更長(zhǎng)。

改進(jìn)型魯賓斯坦協(xié)商策略基于有限階段逆向歸納法尋找多方博弈的理論協(xié)商博弈平衡點(diǎn)：n個(gè)參與方進(jìn)行博弈，每個(gè)參與方的折扣因子分別為δ1?δn，博弈過(guò)程如圖8所示。在第i（i≥n）輪博弈時(shí)編號(hào)為1?n-1的參與方分別出價(jià)M1?Mn-1，編號(hào)為n的參與方得到剩余份額s0后達(dá)成協(xié)議。因?yàn)榈趇輪博弈時(shí)的 M1等價(jià)于第i-1輪博弈時(shí)的δ1 M1，參與方n在第i-1輪博弈時(shí)最多得到sn；因?yàn)榈趇-1輪博弈時(shí)的M2等價(jià)于第i-2輪博弈時(shí)的δ2 M2，參與方1在第i-2輪博弈時(shí)至少得到 s1；因?yàn)榈?i-2輪博弈時(shí)的 M3等價(jià)于第 i-3輪博弈時(shí)的δ3 M3，參與方2在第i-3輪博弈時(shí)至少得到 s2；依次類推，在第i-n+1輪博弈時(shí)的sn等價(jià)于第i-n輪博弈時(shí)的δnsn，參與方n-1在第i-n輪博弈至少得到sn-1。

根據(jù)第i輪博弈時(shí)各參與方所得份額等價(jià)于第i一 n輪博弈時(shí)所得的份額，可得

該方程組的未知數(shù)分別為參與人1?n 的所得份額M1?Mn，求解該方程組即可得出參與人1?n 通過(guò)改進(jìn)型魯賓斯坦協(xié)商策略進(jìn)行博弈后所得的理論協(xié)商博弈平衡點(diǎn)。

3 實(shí)驗(yàn)驗(yàn)證

以工業(yè)級(jí)四旋翼無(wú)人機(jī)組共同完成某煤礦礦區(qū)整體監(jiān)測(cè)任務(wù)作為實(shí)驗(yàn)背景，對(duì)基于改進(jìn)型魯賓斯坦協(xié)商策略的群機(jī)器人任務(wù)劃分與分配算法的高效性與合理性進(jìn)行驗(yàn)證。工業(yè)級(jí)四旋翼無(wú)人機(jī)外形與視角如圖9所示，技術(shù)參數(shù)見表1。在任務(wù)執(zhí)行過(guò)程中，當(dāng)完成任務(wù)劃分與分配后，運(yùn)用Web+GIS技術(shù)自動(dòng)生成和優(yōu)化作業(yè)航線。運(yùn)用電子圍欄與飛行控制系統(tǒng)相配合的方式規(guī)劃作業(yè)區(qū)域和禁飛區(qū)域，其中任務(wù)區(qū)域的總面積為3.498 m2。無(wú)人機(jī)群依據(jù)規(guī)劃航線自主飛行，實(shí)現(xiàn)任務(wù)區(qū)域遍歷[21-22]。

實(shí)驗(yàn)準(zhǔn)備階段，將13架無(wú)人機(jī)分為3組，每一組作為一個(gè)參與方參與任務(wù)劃分與分配過(guò)程的博弈。對(duì)每組無(wú)人機(jī)的最大運(yùn)動(dòng)速度進(jìn)行限制，使無(wú)人機(jī)的飛行能力實(shí)現(xiàn)差異化。3組無(wú)人機(jī)的個(gè)數(shù)與飛行速度見表2。

3.1 第1個(gè)分配周期的任務(wù)比例分配

進(jìn)行任務(wù)區(qū)域劃分前需確定3組無(wú)人機(jī)的初始折扣因子。主要影響因素有每組無(wú)人機(jī)數(shù)量和運(yùn)行速度，取無(wú)人機(jī)數(shù)量權(quán)重系數(shù)r1=0：95，機(jī)器人運(yùn)行速度權(quán)重系數(shù) r2=0：85，任務(wù)完成狀態(tài)反饋參數(shù) k =1。根據(jù)式（4）可得3組無(wú)人機(jī)的初始折扣因子分別為δ1=0：9823，δ2=0：9765，δ3=0：9655。設(shè)每一次任務(wù)劃分與分配周期為120 s，總?cè)蝿?wù)份額為1，在明確任務(wù)區(qū)域的總面積和3組無(wú)人機(jī)的折扣因子后，根據(jù)式（6）可得3組無(wú)人機(jī)的理論協(xié)商博弈平衡點(diǎn)，分別為0.3635，0.3256，0.3109。

根據(jù)3組無(wú)人機(jī)的參數(shù)，運(yùn)用改進(jìn)型魯賓斯坦協(xié)商策略對(duì)任務(wù)份額進(jìn)行劃分，博弈過(guò)程如圖10所示。博弈共進(jìn)行了47輪，在第1輪博弈中，第1組和第2組無(wú)人機(jī)的初始出價(jià)（期望份額）為0.49，則第3組無(wú)人機(jī)得到的初始份額為0.02，小于其在第2輪博弈中準(zhǔn)備提出的報(bào)價(jià)0.49，則3組無(wú)人機(jī)進(jìn)入第2輪的博弈。依此類推，第2組無(wú)人機(jī)得到的報(bào)價(jià)為0.3360，大于其在下一輪博弈中準(zhǔn)備提出的報(bào)價(jià)0.3351，則博弈過(guò)程結(jié)束，3組無(wú)人機(jī)得到博弈的平衡。在第1個(gè)分配周期的初始階段，3組無(wú)人機(jī)分配的任務(wù)份額分別為0.3748，0.3360，0.2892，與理論協(xié)商博弈平衡點(diǎn)相比，誤差份額保持在0.05范圍內(nèi)。誤差產(chǎn)生的原因是，通過(guò)式（6）只需要經(jīng)過(guò)1步計(jì)算即可得出理論博弈平衡點(diǎn)，但實(shí)際平衡點(diǎn)需要通過(guò)多步協(xié)商博弈獲取，每一步計(jì)算產(chǎn)生的誤差均會(huì)得到累計(jì)。

由于任務(wù)執(zhí)行過(guò)程中受風(fēng)速、任務(wù)區(qū)域輪廓等因素影響，第1個(gè)分配周期中每組無(wú)人機(jī)對(duì)分配所得任務(wù)的完成情況有較大差別。第1個(gè)分配周期結(jié)束后任務(wù)區(qū)域的剩余面積，即第2個(gè)分配周期任務(wù)區(qū)域總面積為3.303 km2。

根據(jù)式（5）計(jì)算第1個(gè)分配周期的任務(wù)完成狀態(tài)反饋參數(shù)，對(duì)3組無(wú)人機(jī)的任務(wù)執(zhí)行情況進(jìn)行評(píng)估，根據(jù)評(píng)估情況對(duì)折扣因子進(jìn)行適應(yīng)性調(diào)整。第1個(gè)分配周期中3組無(wú)人機(jī)對(duì)任務(wù)的完成情況與狀態(tài)反饋參數(shù)見表3。將k代入式（4），可得3組無(wú)人機(jī)的折扣因子：δ1=0：9859，δ2=0：9762，δ3=0：9538。

3.2 剩余分配周期的任務(wù)比例分配

在第2個(gè)分配周期的初始階段，根據(jù)第2個(gè)分配周期的任務(wù)區(qū)域面積和3組無(wú)人機(jī)的折扣因子，運(yùn)用改進(jìn)型魯賓斯坦協(xié)商策略對(duì)任務(wù)區(qū)域進(jìn)行新一輪的劃分與分配，在進(jìn)行了44輪博弈后得到協(xié)商博弈平衡，3組無(wú)人機(jī)獲得的任務(wù)份額分別為0.4022，0.3449，0.2529。

3組無(wú)人機(jī)共同執(zhí)行礦區(qū)整體監(jiān)測(cè)任務(wù)共經(jīng)歷15個(gè)分配周期。每組無(wú)人機(jī)在不同分配周期的任務(wù)完成情況如圖11所示。受外界（如地形、氣候等不可抗拒因素）影響，同一組無(wú)人機(jī)在不同分配周期完成的任務(wù)量相差較大，除第15個(gè)分配周期外，第1組無(wú)人機(jī)在單個(gè)分配周期完成任務(wù)量 task_1變化范圍為0.0714～0.1258 km2，第2組無(wú)人機(jī)在單個(gè)分配周期完成任務(wù)量 task_2的變化范圍為0.0524～0.1008 km2，第3組無(wú)人機(jī)在單個(gè)分配周期完成任務(wù)量 task_3的變化范圍為0.0412～0.0829 km2。

在每個(gè)分配周期初始階段，通過(guò)分析上個(gè)分配周期中每組無(wú)人機(jī)任務(wù)執(zhí)行情況，即每組無(wú)人機(jī)的執(zhí)行水平與任務(wù)總體執(zhí)行水平之間的關(guān)系，確定任務(wù)完成狀態(tài)反饋參數(shù)k。通過(guò)式（4）對(duì)折扣因子δ進(jìn)行調(diào)整，進(jìn)而通過(guò)改進(jìn)型魯賓斯坦協(xié)商策略對(duì)每個(gè)任務(wù)分配周期的任務(wù)劃分比例p進(jìn)行調(diào)整。任務(wù)執(zhí)行過(guò)程中，在任務(wù)比例劃分階段，3組無(wú)人機(jī)在不同分配周期的反饋參數(shù)k、折扣因子δ、劃分比例 h 的變化情況如圖12所示。可看出劃分比例 h 的變化趨勢(shì)與任務(wù)完成狀態(tài)反饋參數(shù)k的變化趨勢(shì)基本相符，即在前一個(gè)分配周期中任務(wù)執(zhí)行水平較高的無(wú)人機(jī)組，在下一周期中所分配的任務(wù)量會(huì)隨之增大，相反地，任務(wù)執(zhí)行水平較低的無(wú)人機(jī)組在下一周期中分配的任務(wù)量隨之降低，實(shí)現(xiàn)了執(zhí)行能力的最大化。

不同分配周期的博弈輪數(shù)如圖13所示，可看出運(yùn)用改進(jìn)型魯賓斯坦協(xié)商策略，每個(gè)分配周期的博弈輪數(shù)保持在40～50之間，穩(wěn)定地解決了區(qū)域遍歷任務(wù)過(guò)程中的任務(wù)劃分分配問(wèn)題。

3.3 不同任務(wù)劃分與分配算法高效性與合理性對(duì)比實(shí)驗(yàn)

為了比較算法在任務(wù)劃分與分配方面的高效性，分別運(yùn)用3種不同的任務(wù)劃分與分配算法進(jìn)行煤礦礦區(qū)整體監(jiān)測(cè)任務(wù)實(shí)驗(yàn)，實(shí)驗(yàn)中設(shè)置相同的無(wú)人機(jī)數(shù)量、運(yùn)行速度及任務(wù)區(qū)域面積。每種任務(wù)劃分與分配算法分別進(jìn)行3次實(shí)驗(yàn)，取3次實(shí)驗(yàn)經(jīng)歷的平均時(shí)間作為參考。

算法1通過(guò)計(jì)算每組無(wú)人機(jī)數(shù)量與運(yùn)行速度的乘積，將乘積的比例直接作為3組無(wú)人機(jī)任務(wù)劃分與分配的標(biāo)準(zhǔn)，即每組無(wú)人機(jī)分配的任務(wù)份額分別為0.4412，0.3330，0.2258；算法2使用多方共同協(xié)商的魯賓斯坦協(xié)商策略，但不考慮任務(wù)完成狀態(tài)反饋參數(shù)k，任務(wù)的分配和執(zhí)行過(guò)程不會(huì)向任務(wù)劃分過(guò)程進(jìn)行反饋，3組無(wú)人機(jī)分配的任務(wù)份額始終為0.3748，0.3360，0.2892；算法3采用改進(jìn)型魯賓斯坦協(xié)商策略，實(shí)現(xiàn)任務(wù)的動(dòng)態(tài)劃分與分配。由于無(wú)人機(jī)續(xù)航能力弱的缺點(diǎn)不可避免，無(wú)人機(jī)電池更換時(shí)間不在實(shí)驗(yàn)計(jì)時(shí)范圍內(nèi)。

通過(guò)對(duì)總體任務(wù)執(zhí)行過(guò)程進(jìn)行計(jì)時(shí)，實(shí)現(xiàn)對(duì)3種不同任務(wù)劃分與分配算法高效性的對(duì)比?；?種算法的任務(wù)執(zhí)行過(guò)程所經(jīng)歷的時(shí)間見表4?？煽闯鏊惴?的任務(wù)劃分與分配效率較算法1、算法2分別提升了30.10%，18.29%。

通過(guò)對(duì)每組無(wú)人機(jī)的任務(wù)執(zhí)行過(guò)程進(jìn)行計(jì)時(shí)，實(shí)現(xiàn)對(duì)3種不同的任務(wù)劃分與分配算法合理性的對(duì)比。每組無(wú)人機(jī)的平均任務(wù)執(zhí)行時(shí)間見表5?？煽闯龌谒惴?的3組無(wú)人機(jī)執(zhí)行任務(wù)的平均最大時(shí)間差為188 s，即無(wú)人機(jī)組在執(zhí)行完任務(wù)之后平均有188 s 的等待時(shí)間，這段時(shí)間內(nèi)部分無(wú)人機(jī)組處于空閑狀態(tài)，而部分無(wú)人機(jī)一直處于任務(wù)執(zhí)行狀態(tài)；同理，基于算法2的3組無(wú)人機(jī)執(zhí)行任務(wù)的平均最大時(shí)間差為121 s，這是由于算法2運(yùn)用了多方共同協(xié)商的魯賓斯坦協(xié)商策略，該策略通過(guò)折扣因子優(yōu)化了影響因素（無(wú)人機(jī)數(shù)量和運(yùn)行速度）與任務(wù)劃分與分配結(jié)果之間的關(guān)系，避免了影響因素隨著其數(shù)值增大導(dǎo)致的冗余問(wèn)題；基于算法3的3組無(wú)人機(jī)執(zhí)行任務(wù)的平均最大時(shí)間差為42 s，較算法1、算法2分別優(yōu)化了77.66%，65.29%，這是由于算法3通過(guò)引入任務(wù)完成狀態(tài)反饋參數(shù)k，及時(shí)對(duì)任務(wù)參與方的任務(wù)執(zhí)行過(guò)程進(jìn)行評(píng)估，將任務(wù)的分配和執(zhí)行過(guò)程向任務(wù)的劃分階段進(jìn)行反饋，使任務(wù)的劃分與分配更加準(zhǔn)確。

由實(shí)驗(yàn)結(jié)果可知，運(yùn)用改進(jìn)型魯賓斯坦協(xié)商策略對(duì)任務(wù)進(jìn)行劃分與分配，能夠最大化地發(fā)揮群機(jī)器人的任務(wù)執(zhí)行能力，體現(xiàn)了改進(jìn)型魯賓斯坦協(xié)商策略在任務(wù)劃分與分配方面的高效性和合理性優(yōu)勢(shì)。

4 結(jié)論

1）將魯賓斯坦協(xié)商策略中的雙方博弈向多方共同博弈的方向拓展延伸；以對(duì)任務(wù)最終分配起決定性作用的影響因素為研究對(duì)象，提出了折扣因子計(jì)算方法，根據(jù)該方法能夠量化參與方對(duì)任務(wù)的執(zhí)行能力；在折扣因子中引入任務(wù)完成狀態(tài)反饋參數(shù)，通過(guò)評(píng)估對(duì)所分配任務(wù)的執(zhí)行程度，對(duì)任務(wù)劃分與分配情況進(jìn)行調(diào)整。

2）基于3組無(wú)人機(jī)合作開展煤礦礦區(qū)監(jiān)測(cè)任務(wù)實(shí)驗(yàn)，對(duì)算法的高效性與合理性進(jìn)行了驗(yàn)證。驗(yàn)證結(jié)果表明：算法3的任務(wù)劃分與分配效率較算法1、算法2分別提升了30.10%，18.29%；基于算法3的 3組無(wú)人機(jī)執(zhí)行任務(wù)的平均最大時(shí)間差為42 s，較算法1、算法2分別優(yōu)化了77.66%與65.29%。

參考文獻(xiàn)（References）：

[1] 張鵬.智能礦山機(jī)器人協(xié)同管控[J].工礦自動(dòng)化，2021，47（增刊2）：43-44.

ZHANG Peng. Collaborative control of robots in intelligent mine[J]. Industry and Mine Automation，2021，47（S2）：43-44.

[2] 王宏，宋智瀛，賈瑞清.基于模塊化異構(gòu)多機(jī)器人的煤礦災(zāi)害處置系統(tǒng)[J].煤炭科學(xué)技術(shù)，2011，39（10）：93-95，111.

WANG Hong， SONG Zhiying，JIA Ruiqing. Mine disaster control system based on module heteromerous multi robot[J]. Coal Science and Technology，2011，39（10）：93-95，111.

[3] GAUTHAM D，THOMAS M，SONYA C，et al. A distributed task allocation algorithm for a multi-robot system in healthcare facilities[J]. Journal of Intelligent & Robotic Systems，2015，80（1）：33-58.

[4] 彭凡彬，楊俊杰，葉波.改進(jìn)蟻群算法的變電站群機(jī)器人路徑規(guī)劃研究[J].儀表技術(shù)，2018（3）：9-13，35.

PENG Fanbin，YANG Junjie，YE Bo. Research on robot path planning of substation group based on improved ant colony algorithm[J]. Instrumentation Technology，2018（3）：9-13，35.

[5] 王偉嘉，鄭雅婷，林國(guó)政，等.集群機(jī)器人研究綜述[J].機(jī)器人，2020，42（2）：232-256.

WANG Weijia，ZHENG Yating，LIN Guozheng，et al. Swarm robotics：a review[J]. Robot，2020，42（2）：232-256.

[6] XIAO Renbin，WU Husheng，HU Liang，et al. A swarm intelligence labour division approach to solving complex area? coverage? problems? of swarm? robots[J]. International Journal of Bio-Inspired Computation，2020，15（4）：224-238.

[7] 邱靖廷.基于群體智能的多機(jī)器人任務(wù)分配[D].哈爾濱：哈爾濱工程大學(xué)，2020.

QIU Jingting. Multi-robot task assignment based on group intelligence[D]. Harbin： Harbin Engineering University，2020.

[8] YEUNG W L. Efficiency of task allocation based on contract net protocol with audience restriction in a manufacturing control application[J]. International Journal of Computer Integrated Manufacturing，2018，31（10）：1005-1017.

[9] 梁志偉，吳海健. RoboCup標(biāo)準(zhǔn)平臺(tái)組中基于改進(jìn)合同網(wǎng)協(xié)議的任務(wù)分配算法[J].計(jì)算機(jī)工程與科學(xué)，2022，44（1）：176-183.

LIANG Zhiwei， WU Haijian. A task allocation algorithm based on the improved contract network protocol in RoboCup standard platform league[J]. Computer Engineering & Science，2022，44（1）：176-183.

[10] 黃柳強(qiáng)，秦麗娟，商云龍.電力市場(chǎng)雙邊協(xié)商交易模型設(shè)計(jì)研究[J].廣西電力，2021，44（2）：14-19.

HUANG Liuqiang， QIN Lijuan， SHANG Yunlong. Research on a design of bilateral negotiation and transaction model in electricity market[J]. Guangxi Electric Power，2021，44（2）：14-19.

[11] 馬金龍. 基于博弈論的國(guó)際工程承包合同糾紛研究[D].北京：北京交通大學(xué)，2020.

MA Jinlong. Research on the disputes of international engineering contracts based on game theory[D]. Beijing：Beijing Jiaotong University，2020.

[12] 羅震環(huán).基于VCG和魯賓斯坦模型的數(shù)據(jù)定價(jià)方法研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2021.

LUO Zhenhuan. Research on data pricing methods based on VCG and rubinstein models[D]. Harbin：Harbin Institute of Technology，2021.

[13] JAEHWI S， HOUNG S. Bargaining model-based coverage area subdivision of multiple UAVs in remote sensing[J]. Journal of Biosystems Engineering，2021，45（3）：133-144.

[14] 張夢(mèng)穎，王蒙一，王曉東，等.基于改進(jìn)合同網(wǎng)的無(wú)人機(jī)群協(xié)同實(shí)時(shí)任務(wù)分配問(wèn)題研究[J].航空兵器，2019，26（4）：38-46.

ZHANG? Mengying， WANG? Mengyi，WANGXiaodong，et al. Cooperative real-time task assignment of UAV group based on improved contract net [J]. Aero Weaponry，2019，26（4）：38-46.

[15] 馬洪寬.博弈論[M].上海：同濟(jì)大學(xué)出版社，2015：78-91.

MA Hongkuan. Game theory[M]. Shanghai：Tongji University Press，2015：78-91.

[16] 王磊.動(dòng)態(tài)合作博弈中解的策略穩(wěn)定性[D].青島：青島大學(xué)，2016.

WANG Lei. Strategic stability of solutions in dynamic cooperative games[D]. Qingdao：Qingdao University，2016.

[17] 郭超，熊偉，劉呈祥.合同網(wǎng)協(xié)議改進(jìn)研究現(xiàn)狀與展望[J].裝備學(xué)院學(xué)報(bào)，2016，27（6）：82-89.

GUO Chao，XIONG Wei，LIU Chengxiang. Prospects and current researches on improvement of contract net protocol[J]. Journal of Equipment Academy，2016，27（6）：82-89.

[18] SZCZERBA R J，GALKOWSKI P，GLICKSTEIN I S， et al. Robust algorithm for real-time route planning[J].IEEE Transactions on Aerospace and Electronic Systems，2000，36（3）：869-878.

[19] 劉剛，王瑛，張發(fā)，等.合同網(wǎng)協(xié)議協(xié)商機(jī)制收斂性與收斂速率分析[J].控制與決策，2014，29（6）：1027-1034.

LIU Gang， WANG Ying， ZHANG Fa， et al. Convergence and convergent rate analysis of contract net protocol negotiation mechanism[J]. Control and Decision，2014，29（6）：1027-1034.

[20] 李娟，張昆玉.基于改進(jìn)合同網(wǎng)算法的異構(gòu)多AUV協(xié)同任務(wù)分配[J].水下無(wú)人系統(tǒng)學(xué)報(bào)，2017，25（6）：418-423.

LI Juan，ZHANG Kunyu. Heterogeneous multi-AUV cooperative task allocation based on improved contract net algorithm[J]. Journal of Unmanned Undersea Systems，2017，25（6）：418-423.

[21] 吳江，趙世鈺，周銳，等.基于面向服務(wù)的多無(wú)人機(jī)輔助決策仿真集成方法[J].系統(tǒng)仿真學(xué)報(bào)，2012，24（12）：2525-2529.

WU Jiang，ZHAO Shiyu，ZHOU Rui，et al. Simulation integration of decision aiding based on service-oriented for multiple UAVs[J]. Journal of System Simulation，2012，24（12）：2525-2529.

[22] CHEN Kaiwen，REICHARD G，AKANMU A，et al. Geo-registering UAV-captured close-range images to GIS-based? spatial? model? for? building? facade inspections[J]. Automation in Construction，2021，122（1）. DOI：10.1016/j.autcon.2020.103503.