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

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

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

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

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

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

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

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

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

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

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

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

參考文獻
[1] 劉松國，朱世強.移動機器人的蒙特卡羅自主定位算法研究. 機電工程, 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] 王建中，尹義龍.基于動態(tài)信息模型的LPN路徑規(guī)劃方法.計算機工程, 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] 董煬斌,蔣靜坪.基于適應度的多機器人任務分配策略. 浙江大學學報(工學版), 2007(2).