摘  要： 在RoboCup環(huán)境下,針對(duì)多機(jī)器人的路徑規(guī)劃和任務(wù)分配,將LPN-DE方法和組合拍賣(mài)法有效結(jié)合,綜合考慮多機(jī)器人的避障、路徑規(guī)劃和角色分配，提出了完整的實(shí)現(xiàn)方法和動(dòng)態(tài)模型，并在RoboCup中型組機(jī)器人上驗(yàn)證了該方法的實(shí)用性和有效性。
　　關(guān)鍵詞： LPN-DE； 適應(yīng)度； 組合拍賣(mài); 路徑規(guī)劃

　　隨著RoboCup競(jìng)技活動(dòng)的穩(wěn)定快速發(fā)展，機(jī)器人對(duì)外部世界的感知和反饋都發(fā)生了深刻的變化。目前，基于聲學(xué)傳感的機(jī)器人基本過(guò)時(shí)，利用全景視覺(jué)攝像和智能規(guī)劃的技術(shù)成為主流。
　　在全景攝像機(jī)(Full View Camera)的支持下，機(jī)器人能夠完成球、球門(mén)、立柱、帶有不同色標(biāo)的雙方機(jī)器人、球場(chǎng)白線及綠色地面的自主識(shí)別，從而建立起反映球場(chǎng)環(huán)境的圖像空間，通過(guò)相關(guān)的處理技術(shù)，為機(jī)器人的路徑規(guī)劃提供條件。
　　由于RoboCup環(huán)境的高度動(dòng)態(tài)性，機(jī)器人的障礙不再是一些靜態(tài)的物體，而是位置不斷變化的對(duì)方和己方機(jī)器人，機(jī)器人的目標(biāo)也是運(yùn)動(dòng)著的。最初的辦法是每隔一段時(shí)間采樣一次環(huán)境信息，再利用靜態(tài)的處理方法得出每一次采樣下的規(guī)劃路徑，它沒(méi)有考慮到動(dòng)態(tài)變化，而且存在重復(fù)性，結(jié)果自然不理想，更不能實(shí)現(xiàn)多機(jī)器人間的協(xié)作與配合。因此,要求把目標(biāo)和障礙物的動(dòng)態(tài)信息同機(jī)器人自身的運(yùn)動(dòng)、位置狀態(tài)結(jié)合起來(lái)，對(duì)障礙物和目標(biāo)的運(yùn)動(dòng)狀態(tài)進(jìn)行預(yù)先的估計(jì)，從而規(guī)劃出更合理的路徑。
　　路徑規(guī)劃是機(jī)器人正確運(yùn)動(dòng)的基礎(chǔ)，但目前的RoboCup已是多機(jī)器人的團(tuán)隊(duì)運(yùn)動(dòng)，由之而來(lái)的是多機(jī)器人的體系結(jié)構(gòu)、任務(wù)分配、自主定位、協(xié)調(diào)通信等一系列問(wèn)題。其中最主要的就是任務(wù)分配和通信問(wèn)題，只有建立在多機(jī)器人的任務(wù)分配和通信的基礎(chǔ)之上，才能完成多機(jī)器人之間的協(xié)作，并規(guī)劃出一條能夠到達(dá)目標(biāo)的合理路徑。
1 相關(guān)研究
　　對(duì)于多機(jī)器人系統(tǒng),路徑規(guī)劃就是通過(guò)獲取全場(chǎng)信息,決定機(jī)器人間的角色任務(wù)分配,在規(guī)劃方案的整合下,計(jì)算出一條能夠快速到達(dá)目標(biāo)的合理路徑。參考文獻(xiàn)[1]利用基于采樣和概率的蒙特卡羅（Monlt Carlo）方法解決機(jī)器人的自主定位問(wèn)題,結(jié)合球場(chǎng)三角、白線和中圈定位方法，提高了定位效率和成功率，為路徑規(guī)劃提供了全場(chǎng)物體的運(yùn)動(dòng)和位置信息。Konolige在參考文獻(xiàn)[2]中提出了線性規(guī)劃導(dǎo)航梯度方法LPN(Linear Programming Navigation gradient method)，主要解決靜態(tài)環(huán)境下的路徑規(guī)劃問(wèn)題，它的構(gòu)想是諸多相關(guān)文獻(xiàn)包括本文解決問(wèn)題的理論基礎(chǔ)。由于沒(méi)有考慮到動(dòng)態(tài)環(huán)境，因此參考文獻(xiàn)[3]提出了動(dòng)態(tài)環(huán)境下的LPN方法LPN-DE(LPN for Dynamic Environment)，建立了新的動(dòng)態(tài)模型，基本解決了動(dòng)態(tài)環(huán)境下的避障和到達(dá)問(wèn)題；但對(duì)于靜止和速度線上的避障問(wèn)題，該模型存在缺陷，參考文獻(xiàn)[4]針對(duì)此缺陷，提出了改進(jìn)的動(dòng)態(tài)模型，較好地完善了單機(jī)器人的動(dòng)態(tài)避障和路徑規(guī)劃方法。
　　解決了單機(jī)器人的路徑規(guī)劃問(wèn)題后，就涉及到機(jī)器人間的任務(wù)分配和協(xié)作問(wèn)題。參考文獻(xiàn)[5]提出了用單物品拍賣(mài)的方法來(lái)分配任務(wù)，參與拍賣(mài)的機(jī)器人出價(jià)的依據(jù)就是機(jī)器人目前的位置和到目標(biāo)的距離，但它有可能得不到最優(yōu)路徑^[6]。參考文獻(xiàn)[7]提出了基于適應(yīng)度的任務(wù)分配方法，概括了分配的四個(gè)基本目標(biāo)，并制定了響應(yīng)的四個(gè)選擇策略，在此基礎(chǔ)上建立了任務(wù)和機(jī)器人的通用適應(yīng)度模型。這是一個(gè)較好的任務(wù)和機(jī)器人間的適應(yīng)度量化模型。
　　本文在LPN-DE理論的基礎(chǔ)上，利用子任務(wù)和機(jī)器人的適應(yīng)度作為角色分配的組合拍賣(mài)條件，提出了完整和可行的解決動(dòng)態(tài)多機(jī)器人的路徑規(guī)劃方案，并在真實(shí)的機(jī)器人環(huán)境中進(jìn)行驗(yàn)證和改進(jìn)。
2 動(dòng)態(tài)環(huán)境下線性規(guī)劃導(dǎo)航梯度方法（LPN-DE）
　　在全景攝像機(jī)的的圖像空間內(nèi)，本方法將全景圖像柵格化為10 cm×10 cm的實(shí)景離散空間(已解決圖像畸變)，如圖1所示。為了規(guī)劃出一條高效可達(dá)的路徑，必須使：(1)機(jī)器人避免同對(duì)方或己方機(jī)器人碰撞；(2)追蹤目標(biāo)球的路徑最短。所以采樣圖像空間，并用LPN方法為每一個(gè)采樣?xùn)鸥褓x值，這種賦值方法即為導(dǎo)航函數(shù)。沿著導(dǎo)航函數(shù)梯度下降的方向就可以得到一條如圖1的路徑。

　　對(duì)于環(huán)境中的任意一個(gè)柵格，在此定義2個(gè)函數(shù)：
　　A：鄰接耗費(fèi)函數(shù)。代表柵格與障礙物的距離遠(yuǎn)近。
　　I：本質(zhì)耗費(fèi)函數(shù)。代表相鄰柵格間的距離。
　　從機(jī)器人到目標(biāo)球的一條路徑為一組有序采樣點(diǎn)集：P_n={p_n,p_n-1,…,p₀}，路徑的耗費(fèi)函數(shù)由其上每一點(diǎn)的A和I組成。耗費(fèi)函數(shù)F可表示為：
　　

　　機(jī)器人的導(dǎo)航函數(shù)表示為從n點(diǎn)出發(fā)到目標(biāo)點(diǎn)的最小路徑耗費(fèi)的耗費(fèi)值：
　　
　　式中，P_k^j是j條從p_n開(kāi)始到達(dá)目標(biāo)點(diǎn)的路徑，m是兩點(diǎn)間存在路徑的數(shù)量。
　　顯然，即使采樣空間很小，計(jì)算空間中每一點(diǎn)的導(dǎo)航函數(shù)都是很大的計(jì)算量。而LPN方法可以大大簡(jiǎn)化這一過(guò)程。LPN方法更新過(guò)程如圖2所示主要有如下三步：

　　(1) 開(kāi)始時(shí)，為目標(biāo)點(diǎn)賦0值，其余點(diǎn)賦無(wú)窮大值。
　　(2) 把目標(biāo)點(diǎn)放入鏈表中。
　　(3) 循環(huán)更新鏈表中的每一點(diǎn)，擴(kuò)展它的8相鄰點(diǎn)，并刪除該點(diǎn)。
　　如圖3中更新點(diǎn)p的操作：對(duì)p的任一鄰點(diǎn)q，它的耗費(fèi)值為p點(diǎn)的值加上p到q的鄰接耗費(fèi)再加上q的本質(zhì)耗費(fèi)。若q的值比原值小，則把q放入鏈表。圖中右下角q的值為20+10+10=40，大于原值30，故不能把該點(diǎn)的值放入鏈表。LPN方法規(guī)劃路徑如圖3所示。LPN方法可算出每一個(gè)采樣點(diǎn)到目標(biāo)點(diǎn)的最小耗費(fèi)路徑。圖1所示的2條路徑即為L(zhǎng)PN方法的更新結(jié)果，但只有其中一條是合理的，原因是沒(méi)有考慮到障礙物的動(dòng)態(tài)速度。

　　考慮障礙物的動(dòng)態(tài)信息，必須建立障礙物的動(dòng)態(tài)信息模型。參考文獻(xiàn)[3]首創(chuàng)了F動(dòng)態(tài)函數(shù)模型：
　　
式中，α(p)為采樣點(diǎn)與障礙物速度方向的夾角，‖v‖是障礙物速度的模，d(p)是二者間距離，如圖4所示。當(dāng)α(p)或‖v‖為0時(shí)，即機(jī)器人在障礙物速度線上或障礙物靜止時(shí)規(guī)劃不出有效的路徑。參考文獻(xiàn)[4]提出了改進(jìn)的F動(dòng)態(tài)函數(shù)模型：
　　

　　該模型既保留了前者的動(dòng)態(tài)影響特性，又較好地解決了存在的問(wèn)題，只需要根據(jù)場(chǎng)地要求和機(jī)器人的特性調(diào)整、a、b參數(shù)的值即可。基于此F函數(shù)，提出了新的障礙物動(dòng)態(tài)模型：
   

    其中，C是障礙物點(diǎn)的本質(zhì)耗費(fèi)，為較大值；ε為略小于1的常數(shù)，以免在F為零時(shí)規(guī)劃出的路徑經(jīng)過(guò)障礙物，出現(xiàn)比賽中常見(jiàn)的雙方機(jī)器人的長(zhǎng)時(shí)間原地糾纏和抵觸。圖5為本模型在動(dòng)態(tài)障礙下的路徑仿真，圖6為本模型在靜態(tài)和動(dòng)態(tài)混合障礙下的路徑仿真。由圖可以看出，機(jī)器人能較好地避開(kāi)了動(dòng)、靜態(tài)的障礙，找到目標(biāo)球。

3 多機(jī)器人的適應(yīng)度組合拍賣(mài)模型
3.1 多機(jī)器人適應(yīng)度模型
　　LPN-DE方法很好地解決了單機(jī)器人的動(dòng)態(tài)路徑規(guī)劃問(wèn)題，但在多機(jī)器人的環(huán)境下帶來(lái)了很多問(wèn)題，從理論分析和作者的參賽經(jīng)驗(yàn):在發(fā)現(xiàn)了球之后，眾多機(jī)器人都會(huì)追趕而去，在球的周?chē)鷣y作一團(tuán)，出現(xiàn)很多不可預(yù)測(cè)的情況，拿球的效率很低。因此必須讓機(jī)器人有所分工和協(xié)作，才能更好地適應(yīng)多機(jī)器人的環(huán)境。
　　為了解決多機(jī)器人任務(wù)分配的準(zhǔn)則，本文提出了適應(yīng)度的概念。適應(yīng)度是指機(jī)器人對(duì)當(dāng)前各任務(wù)的適應(yīng)程度和完成能力。在這個(gè)準(zhǔn)則約束下，把機(jī)器人的任務(wù)分為4個(gè)等級(jí)：
　　(1)射門(mén)：機(jī)器人拿到球之后，將球射入對(duì)方球門(mén)。
　　(2)追球：機(jī)器人發(fā)現(xiàn)球之后，向球運(yùn)動(dòng)，并拿到球。
　　(3)攔截：攔截對(duì)方射門(mén)或追球的機(jī)器人。
　　(4)回防：機(jī)器人沒(méi)有發(fā)現(xiàn)球后，主動(dòng)回撤己方區(qū)域防守。
　　其中，各等級(jí)的標(biāo)號(hào)就是它們的優(yōu)先級(jí)。同時(shí)，根據(jù)機(jī)器人的當(dāng)前狀態(tài)因素，為機(jī)器人建立了一個(gè)適應(yīng)度模型，包含如下參數(shù)：
　　(1)機(jī)器人當(dāng)前任務(wù)標(biāo)號(hào)As：參數(shù)為變量，取值由機(jī)器人當(dāng)前選擇的任務(wù)確定。
　　(2)機(jī)器人當(dāng)前功能狀態(tài)St：參數(shù)為變量，如果機(jī)器人具備執(zhí)行任務(wù)i的能力，則S_t(i)的值為1，否則取0。
　　根據(jù)當(dāng)前的任務(wù)特點(diǎn)和機(jī)器人狀態(tài)之間的匹配，利用拍賣(mài)的方法進(jìn)行任務(wù)分配，并根據(jù)球場(chǎng)的變化適時(shí)調(diào)整機(jī)器人的角色，從而最終完成拿球和射門(mén)的任務(wù)。
3.2 基于適應(yīng)度的組合拍賣(mài)方法
　　多件物品組合拍賣(mài)問(wèn)題(Multi-unit Combinatorial Auctions)可描述為：設(shè)M表示為拍賣(mài)物品的集合，用M={1,2,…,m}表示,每種物品數(shù)量表示為U={u₁,u₂,…,u_m}，競(jìng)標(biāo)集合B={B₁,…,B_n}，若P_j是此競(jìng)標(biāo)的一個(gè)出價(jià)，S_j是一個(gè)物品集合。則一個(gè)競(jìng)標(biāo)就是一個(gè)二元組B_j=j,P_j>，將每一個(gè)競(jìng)標(biāo)j注為勝利(x_j=1)或失敗(x_j=0)，滿(mǎn)足以下約束：
　　

　　投標(biāo)者之間必須滿(mǎn)足：
　　(1)中標(biāo)者之間不存在物品上的沖突;
　　(2)中標(biāo)者所帶來(lái)的收益最大。
　　針對(duì)適應(yīng)度模型的4個(gè)等級(jí)，以機(jī)器人和目標(biāo)球之間的距離為拍賣(mài)的競(jìng)標(biāo)出價(jià)，具體的拍賣(mài)策略是：
　　(1)若某個(gè)機(jī)器人處于“射門(mén)”狀態(tài)，則不再執(zhí)行其他任務(wù)，其余機(jī)器人皆需配合它的動(dòng)作，執(zhí)行“攔截”任務(wù)。
　　(2)若無(wú)機(jī)器人處于“射門(mén)”狀態(tài)，則距離目標(biāo)球最近的機(jī)器人執(zhí)行“追球”任務(wù)，其余機(jī)器人執(zhí)行“攔截”任務(wù)，并根據(jù)球場(chǎng)狀態(tài)適時(shí)調(diào)整機(jī)器人執(zhí)行任務(wù)的角色。
　　(3)若機(jī)器人都沒(méi)有發(fā)現(xiàn)球，則首先旋轉(zhuǎn)360°，若仍然沒(méi)有發(fā)現(xiàn)，則距離己方區(qū)域最近的兩個(gè)機(jī)器人執(zhí)行“回防”任務(wù)。
　　(4)拍賣(mài)是基于協(xié)商主義的，多機(jī)器人系統(tǒng)在設(shè)定的協(xié)議基礎(chǔ)上通過(guò)機(jī)器人間的協(xié)商、談判來(lái)完成任務(wù)分配，本文的協(xié)議就是機(jī)器人對(duì)任務(wù)的適應(yīng)度。
4 基于適應(yīng)度拍賣(mài)的多機(jī)器人實(shí)驗(yàn)
　　本文采用的是RoboCup中型組4:4平臺(tái)，球場(chǎng)環(huán)境尺寸為12m×8m。為了驗(yàn)證LPN-DE和適應(yīng)度拍賣(mài)方法的有效性，截取了開(kāi)球后的某個(gè)典型狀態(tài)，此時(shí)機(jī)器人都發(fā)現(xiàn)了球，通過(guò)LPN-DE方法的計(jì)算，每個(gè)機(jī)器人規(guī)劃出了自己的追球路徑，如圖7所示。在LPN-DE方法的基礎(chǔ)上，利用適應(yīng)度拍賣(mài)的方法對(duì)四級(jí)任務(wù)分配給多機(jī)器人，規(guī)劃出的路徑如圖8所示。

　　多機(jī)器人系統(tǒng)所存在的問(wèn)題就是讓機(jī)器人能夠相互配合，優(yōu)化協(xié)同解決問(wèn)題，而不是各自單獨(dú)按照同樣的方式運(yùn)動(dòng)。從圖8可以看出，在距離球最近的那個(gè)機(jī)器人追球后，其余的機(jī)器人執(zhí)行的是攔截任務(wù)，拿到球的概率提高了。

　　在RoboCup動(dòng)態(tài)環(huán)境下的多機(jī)器人協(xié)同問(wèn)題實(shí)時(shí)性高、運(yùn)算量大、系統(tǒng)復(fù)雜，需要整合環(huán)境信息，己方、對(duì)方機(jī)器人狀態(tài)等諸多靜態(tài)和動(dòng)態(tài)信息。本文把諸多文獻(xiàn)中解決各個(gè)子問(wèn)題的方法結(jié)合起來(lái)，利用LPN-DE方法計(jì)算出單機(jī)器人的最優(yōu)路徑，再將任務(wù)分解為4個(gè)等級(jí)，根據(jù)LPN-DE的結(jié)果即可算出機(jī)器人對(duì)各等級(jí)的適應(yīng)度，在此基礎(chǔ)上，用組合拍賣(mài)的方法進(jìn)行任務(wù)分配，得到每個(gè)機(jī)器人的最佳角色。此綜合規(guī)劃方法已應(yīng)用于蘇州大學(xué)RoboCup中型組“騎士”隊(duì)中，取得了較好的效果。

參考文獻(xiàn)
[1] 劉松國(guó)，朱世強(qiáng).移動(dòng)機(jī)器人的蒙特卡羅自主定位算法研究. 機(jī)電工程, 2005.
[2] KONOLIGE K. A gradient method for realtime robot control.IEEE International Conference on Intelligent Robots and Systems, 2000.
[3] FARINELI A, IOCCHI L. Planning trajectories in dynamic  environments using a gradient method. Proc. the International RoboCup Symposium,Padua,Italy, 2003.
[4] 王建中，尹義龍.基于動(dòng)態(tài)信息模型的LPN路徑規(guī)劃方法.計(jì)算機(jī)工程, 2006(9).
[5] GERKEY B P, MATARIC M J.Sold!:auction methods for multirobot coordinational. IEEE Transactions on Robotics and Automation, 2002.
[6] BERHAULT M, HUANG H. Robot exploration with combinatorial auctions.Georgia Instiute of Technology,2003.
[7] 董煬斌,蔣靜坪.基于適應(yīng)度的多機(jī)器人任務(wù)分配策略. 浙江大學(xué)學(xué)報(bào)(工學(xué)版), 2007(2).