個體機器人局部路徑規劃的人工力矩方法

徐 望 寶， 陳 雪 波， 趙 杰

(1.大連理工大學 電子信息與電氣工程學部，遼寧 大連 116024；2.遼寧科技大學 電子與信息工程學院，遼寧 鞍山114051；3.哈爾濱工業大學 機器人技術與系統國家重點實驗室，黑龍江 哈爾濱150001)

0 引 言

二維障礙平面中個體自主移動機器人的局部路徑規劃問題，是機器人學中的一個重要問題.其目的就是要求一個對環境無任何先驗知識的機器人，僅依靠其傳感器的實時探測和運動過程中積累的環境知識，規劃出一條從起點位置到目標位置的無碰較優路徑，或證明不存在這樣的路徑.

針對上述問題，目前人們已提出了較多的解決方法，其中比較重要的有“沿墻走”方法或“Bug”方法[1～3]、人工勢場法[4～6]等.“Bug”方法的基本原理是:機器人總試圖直接向著目標點運動；在遇到障礙時，才沿著障礙往前走直到確定已繞過了障礙.“Bug”方法有直觀、簡單、在一定條件下能保證收斂的優點；缺點是未曾考慮運動路徑的長度，即路徑優化問題.人工勢場法的基本原理是:機器人活動在一個人工力場中，其中目標對機器人有一個吸引力，障礙對機器人有一個排斥力；在合力作用下，機器人沿使合力減小的方向運動.人工勢場法有實時性強、計算簡單、實現容易等優點；缺點除了未曾考慮路徑優化問題外，還存在一個比較難以解決的“局部極小點”問題[2、6].

在滿足約束的條件下，機器人的運動路徑越短越好.所以在局部路徑規劃問題中，也應考慮路徑優化問題，即利用現有的環境知識，得到一條盡可能短的運動路徑.基于公路圖的方法，如可視圖方法[7]、切 線 圖 方 法[8]、Voronoi圖 方 法[9、10]等，是注重路徑優化的方法.這類方法的基本原理是:首先，機器人要得到一個由可行路徑組成的公路圖，該圖必包含機器人當前位置與目標間的最短可行路徑；然后，運用某種技術如Dijkstra算法或圖理論[9]，機器人從該公路圖中選出最短可行路徑并沿該路徑運動.這類方法的主要優點是常能得到最優可行路徑；缺點是在局部路徑規劃問題中，由于環境知識不斷改變，需要經常重新計算公路圖及最短可行路徑，計算量很大，難以在局部路徑規劃問題中使用.

本文首先將公路圖方法中的有關概念進行推廣，提出廣義可行路徑和最優路徑代表點(Powr)等概念.最優路徑代表點，除在優化路徑時，有與最短廣義可行路徑相同的效果外，還有存儲量小，不需要像公路圖方法一樣考慮機器人的半徑與安全距離[8]，也不需要對環境做預處理等優點.然后將文獻[11、12]提出的用于多機器人隊形控制的人工力矩方法進行推廣，設計在通常情況下會努力使機器人基本運動方向線(PMDline)指向Powr的新吸引矩函數和總努力使機器人的PMDline背向相應危墻代表點的新排斥矩函數.基于上述兩種人工力矩，設計機器人運動控制器.當機器人與目標間的線段被障礙阻斷時，該控制器會使機器人沿PMDline以最大步幅運動，從而即使面臨復雜的障礙，機器人也不會停止運動，即不會被陷住.所以基于人工力矩規劃機器人路徑不會產生類似“局部極小點”的問題.

本文還給出最優路徑代表點的求解方法、個體機器人局部路徑規劃的基本步驟及可達性證明.

1 系統模型與相關定義

本文僅討論二維平面中個體機器人的局部路徑規劃問題，其中工作環境中分布有靜態的多邊形障礙；機器人對環境無任何先驗知識，要求僅依靠傳感器的實時探測和運動過程中積累的環境知識來規劃一條能安全到達目標的路徑；到達目標后，機器人還要盡可能地具有給定的位姿.

在討論問題的解決方法前，首先規定文中使用的一些符號和概念，其中一有向線(射線或有向線段)到另一有向線的角，及有向線方向角的定義與文獻[11]相同，即將一有向線繞其端點旋轉到與全局坐標系中橫坐標軸方向相同時所轉的絕對值不大于π的有向角就是該有向線的方向角.設βi、βj分別是有向線li、lj的方向角，函數

那么β＝agl(βi－βj)就是從li到lj的角.

定義Time＝｛tk｜k＝0，1，…｝為一離散時間點集.任意變量X在tk時刻的值用X(k)表示；如果一變量值的時間沒有指定，則為當前時刻；如果X是一條連續曲線段，則｜X｜是它的長度.AB表示以A、B為端點的線段；Sd(A，B)表示以A為起點、B為終點的有向線段，β(A，B)為Sd(A，B)的方向角；Lr(A，B)表示以A為起點、經過B的射線. (W，－A1，…，－An)表示連續曲線W上除A1，…，An外的點； (Lr(A1，A2)，－A1A2)表示Lr(A1，A2)上除A1A2外的所有點.

R表示機器人；SR表示R的最大運動步幅；Ds是一個與機器人的安全相關的正常數.R的模型如圖1所示，其形狀是一個半徑為DR(Ds＞2SR＋2DR)的圓.R的位置(圓心位置)記為PR，坐標記為(xR，yR).像文獻[11、12]中的機器人模型一樣，R有且只有一條以其所在位置為端點的基本運動方向線(PMDline).該PMDline是一條以PR為端點、βR為方向角的射線，主要用來指示R的位姿或主要運動方向.

圖1 相關模型Fig.1 Associated models

R有一個全方位傳感器，其有效半徑為Dv.對于工作空間中的點F，只有當且PRF不經過任何障礙時，R才能探測到F，否則探測不到F.如在圖1中，R在當前時刻只能探測到灰色區域內及其邊界上的點，該區域外的點如A1(A1在初始時刻能被R探測到)、A5就不能被探測到.

目標記為T，其模型為一個靜態的質點，如圖1所示，坐標記為(xT，yT).T有且只有一條以其位置為端點、βT為方向角的PMDline，用來指示其位姿.文中要求R到達目標后盡可能地具有給定的位姿，即要求R到達目標后，盡可能地小.

假設1 在任意時刻，R通過通信等方式，總能知道T的位置及PMDline的方向角.

假設2 任意兩障礙間的最近距離都不小于Ds；R與T間至少存在一條寬度不小于Ds的路徑.

定義1 設Σ是障礙物邊緣線上一段連續的曲線.如果Σ上不含從未被R探測過的點，且對于任意的與Σ在同一個障礙物邊緣曲線上的曲線段Σ＊，Σ＊Σ就意味著Σ＊上至少有一點從未被R探測到，那么稱Σ為知識障礙墻.

如在圖1中，折線段A1A2A3A4就是一條知識障礙墻；而折線段A1A2A3A4A5不是，因為上面有些點，如A5，從來沒有被R探測到.

顯然，知識障礙墻是環境知識積累的結果.R會記下所有的知識障礙墻并及時更新，以方便應用.

定義2 設W是一條以F1、F2為端點的連續曲線，S是所有以F1、F2為端點，上面的點或在W上或無限地靠近W的連續曲線組成的集合.①如果S中存在一個元素W＊，使得集合 (W＊，－F1，－F2)中不含任何知識障礙墻上的點，那么W就是一條以F1、F2為端點的廣義可行路徑.②如果存在一條知識障礙墻Σ，使得S中的每一個元素，都至少與Σ有一個公共點，那么就說W被Σ阻斷.③如果一條射線上面的任何一條線段都沒有被Σ阻斷，那么該射線沒有被Σ阻斷，否則它就被Σ阻斷.

如在圖1中，折線段PRA4T和PRA2A1A3T都是以PR、T為端點的廣義可行路徑；而折線段PRA2A3T就不是，因為它被知識障礙墻A1A2A3A4阻斷.

廣義可行路徑與完全可行路徑密切相關，因為在一條廣義可行路徑的附近一定存在一條完全可行路徑.但由于廣義可行路徑上可能存在障礙點，R的模型具有幾何形狀且R在運動過程中要與障礙保持一定的安全距離，所以廣義可行路徑又不一定完全可行.

定義3 設F是T或知識障礙墻上的一個點，如果PRF位于以PR、T為端點的最短廣義可行路徑上，且F≠T就意味著對任意的滿足A∈ (Lr(PR，F)，－PRF)且｜FA｜＜Ds的點A，集合 (FA，－F)中都不含知識障礙墻的點，那么稱F為最優路徑代表點，記為Powr.

例如，當PRT不被任何知識障礙墻阻斷時，PRT就是以PR、T為端點的最短廣義可行路徑，此時T就是Powr.

概念“最優路徑代表點”含有兩層意思:一是指Powr能夠代表以PR、T為端點的最短／最優廣義可行路徑，因為直接向著Powr運動就會沿著該路徑運動；二是指在所有能代表該路徑的點中，Powr幾乎是最優的，因為它幾乎是所有既位于該路徑上，同時與PR的連線段又不被任何知識障礙墻阻斷的點中，距PR最遠的點.

對于路徑優化，Powr與以PR、T為端點的最短廣義可行路徑的作用完全相同；但顯然Powr需要的存儲量要少得多.同時Powr也不需要像完全可行路徑那樣考慮機器人的大小和安全距離，也不需要預處理環境，計算容易，所以在本文中，R主要是在Powr的引導下向著T運動.

定義4 設G是知識障礙墻Σ上能被R探測且到PR的距離不大于Ds的點，如果存在一個正常數δ，使得對任意的滿足在Σ上且｜AG｜＜δ的點A，都有｜PRA｜＞｜PRG｜，那么稱G為危墻代表點.

顯然，危墻代表點就是對R具有安全威脅的知識障礙墻上的局部最近點.由于僅是局部最近點，同一知識障礙墻上的危墻代表點可能不只一個，如在圖1中的當前時刻，在知識障礙墻 ——折線段A1A2A3A4上就有兩個危墻代表點G1、G2.危墻代表點的主要作用是防止R向其所在的區域靠近，所以同一知識障礙墻上有多個危墻代表點的特點可以防止機器人在避開該墻的一側后，又撞上該墻的另一側.

2 基于人工力矩的機器人運動控制器

人工力矩概念由文獻[11、12]等根據物理學中力的大小與方向共同決定力矩的基本思想而提出，其與人工勢場力的基本區別是:人工力矩的大小不但與機器人和目標、障礙間的遠近等這些在人工力場中通常被定義成吸引力或排斥力的距離有關，還與機器人的PMDline等相關有向線的方向有關，即還與“力的方向”有關.相對于人工勢場力的主要優點是:人工勢場力只能影響機器人的位置，而人工力矩可以根據系統需要，同時影響機器人的位置和PMDline方向或只影響其中的一個，從而為設計帶來了更多的便利.

例如，本文設計的用于路徑規劃的吸引矩和排斥矩，其中吸引矩常在R的PMDline指向Powr時取得最大值，即通常只影響R的PMDline；排斥矩則總在R的PMDline背離相應危墻代表點時取得最大值，即僅影響R的PMDline.基于上述兩種人工力矩函數設計的用于個體機器人路徑規劃的運動控制器，使R在大部分情況下，一方面沿合力矩增大的方向調整PMDline方向，另一方面則沿PMDline以最大步幅運動.即使在復雜的環境中，R也不會停止運動，即不會被陷住.所以基于人工力矩規劃機器人路徑，不會產生類似人工勢場法中的“局部極小點”問題.

吸引矩與排斥矩函數具體設計如下.設當前時刻為tk，δθ為遠小于π／2的正常數，函數

則Powr對R的吸引矩Ma(k)設計如下:

(1)如果Powr不是目標T或到PR的距離不小于Ds，則

其中βRP(k)是Sd(PR，Powr)的方向角.λa是一常數，本文的取值方法是:如果tk時刻有一危墻代表點G，使得Sd(PR，Powr)到Sd(PR，G)的角的絕對值小于π／2，則λa＝0.5；否則λa＝0.8.按上述方法取λa的理由是:如果Sd(PR，Powr)到Sd(PR，G)的角的絕對值小于π／2，則向著Powr運動就有向著G運動的趨勢，在此情況下吸引矩太大會使R的PMDline在吸引矩的作用下向障礙物方向偏轉太多，從而使R的運動在障礙物前產生振蕩.否則吸引矩大可以加快R趨向Powr的速度.

(2)如果Powr是目標T且到PR的距離小于Ds，則

設G是tk時刻的一個危墻代表點，βGR(k)是Sd(G，PR)的方向角，DGR＝｜Sd(G，PR)｜，λp＝，則G對R的排斥矩Mp(k)設計為

基于人工力矩的機器人運動控制器設計為

其中有關符號的意義和計算方法如下:

(1)(S(k)S(k))T是R在 時 間 段

xy(tktk＋1]內沿其 PMDline的運動量.計算方法是:如果Powr是T且到PR的距離小于Ds，則(Sx(k)Sy(k))T＝ (0 0)T；否則R將以最大步幅沿PMDline方向運動，即

(2)(Δβ(k)Δx(k)Δy(k))T是能增加

1R1R1RR吸引矩的變化量，是吸引矩的梯度方向.設函數

則據式(3)、(4)得

①如果Powr不是目標T或到PR的距離不小于Ds，則

②如果Powr是目標T且到PR的距離小于Ds，則

(3)當R沒有危墻代表點時，∑Δ2βR(k)＝0.否則∑Δ2βR(k)是所有危墻代表點排斥矩梯度方向的和.設Δ2βR(k)是危墻代表點G對R排斥矩的梯度方向，則由式(5)得

從式(6)～(12)可以看出，基于人工力矩的運動控制器，使得R的運動速度，不會因為吸引矩和排斥矩的相互抵消而降低，因為排斥矩不影響機器人的運動速度.這一特點，不僅使得R不至于陷在某一局部極值點而不能自拔，即在人工力矩法中，不會出現類似“局部極小點”的問題；同時也增加了機器人的平均運動速度，從而加快了收斂速度.

將本文的人工力矩函數和運動控制器與文獻[11、12]中相應的人工力矩函數和運動控制器相比可以發現，本文的人工力矩函數和運動控制器要簡單得多，原理也更易懂.

盡管運動控制器(6)有許多優點，但如果存在一個危墻代表點G，滿足

那么直接運用該運動控制器，則R就有可能不趨近Powr.

R不趨近Powr的原因，是因為不等式(13)意味著R的 PMDline到Sd(PR，Powr)的角與到Sd(G，PR)的角的符號相反，如圖2所示，因此相應吸引矩與排斥矩的作用就可能相互抵消，R就可能繼續沿原來PMDline的方向運動；如果R原來的PMDline不指向甚或背向Powr，那么在此情況下，R的運動就會不趨近Powr，或雖然趨近，但速度緩慢.

圖2 R的PMDline背向PowrFig.2 R′s PMDline opposite to the Powr

改進方法就是在運用如式(6)所述的運動控制器前，先檢查所有的危墻代表點，判斷式(13)是否成立.如果都不成立，則直接運用；否則先令βR(k)＝β(PR，Powr)，即令R的 PMDline指向Powr，然后再運用前述控制器.經過上述改進后發現，在當Sd(PR，Powr)不被知識障礙墻阻斷時，基于人工力矩的運動控制器總能使R逐漸趨近Powr.

3 最優路徑代表點求解及局部路徑規劃的基本步驟

首先探討Powr的求解方法，因為如果不求得Powr，則基于人工力矩的運動控制器就無法進行，路徑優化也無從談起.為了方便論述Powr的求解，下面給出兩個新概念.

定義5 設F是廣義可行路徑上的一個點，A是知識障礙墻Σ上的一個點.(1)如果 (Lr(F，A)，－FA)∩Σ＝且Lr(F，A)不被Σ阻斷，那么稱Lr(F，A)為從F到Σ的單向切線，A為切點.(2)當 (Lr(F，A)，－FA)∩Σ不為空時，設A＊為其中距A最近的點.如果AA＊與Σ的一部分能形成一條將F和T分開的閉合曲線，那么Lr(F，A)為從F到Σ的閉合切線，A為切點，A＊為閉合點.

如在圖3中，Lr(PR，A4)是從PR到Σ1的單向切線，A4為切點；Lr(PR，A1)是從PR到Σ1的閉合切 線，A1為 切 點、F1為 閉 合 點；Lr(A1，A2)和Lr(A2，A3)則分別是從A1、A2到Σ1的閉合切線.

為了簡化Powr的求解，在運動過程中，R還會按照下述規則在環境中設置人工障礙線:(1)當PRT同時被知識障礙墻Σ1、Σ2阻斷時，設A1、A2分別為PRT與Σ1、Σ2的交點，那么A1A2將被設置為一條人工障礙線；(2)當PRT僅被Σ1阻斷時，設A1為從PR到Σ1的單向或閉合切線的切點.如果PRA1被Σ2阻斷，那么設A2為PRA1與Σ2交點中，距A1最近的點，則A1A2將被設置為一條人工障礙線.

圖3 單向切線、閉合切線與人工障礙線Fig.3 Single－direction tangents，closed tangents and artificial obstacle segments

如在圖3中，V1V2就是R設置的人工障礙線.設置人工障礙線的主要根據是“沿墻走”方法中盡量不讓機器人往回走的原則.因為如果A1A2是當前時刻設置的人工障礙線，則根據設置方法知，A1A2在當前時刻不能被R探測，但由于A1、A2都在知識障礙墻上，所以A1A2在過去一定可以被R探測到.上述分析說明了R從曾經距A1A2較近的位置運動到了現在距A1A2較遠的位置.所以把A1A2設置成人工障礙線，防止R向A1A2運動就可以防止R往回走，從而在一定程度上可以保證全局收斂性.

雖然通常情況下，人工障礙線被當作知識障礙墻的一部分處理，但如果人工障礙線的設置導致形成一條能將R、T分開的閉合知識障礙墻，則該墻上的所有人工障礙線都會被撤除.

結論1 如果R在當前時刻不能設置人工障礙線，那么，(1)PRT最多被一條知識障礙墻阻斷；(2)設PRT被知識障礙墻Σ阻斷，A1為從PR到Σ的單向或閉合切線的切點，那么PRA1不會被任何知識障礙墻阻斷.

結論2 如果PRT被知識障礙墻Σ阻斷且從PR到Σ有一條閉合切線，那么該閉合切線的切點為Powr.

結論3 當PRT被知識障礙墻Σ阻斷，從PR到Σ有兩條單向切線時，設兩單向切線的切點分別是A1、Q1，那么根據下面算法1可以得到一條記為WA1的路徑PRA1A2…AnT.

算法1 (求路徑WA1)

Step 1 令Ai＝A1，A0＝PR.

Step 2 如果AiT沒有被Σ阻斷，那么停止運算，Ai、T為WA1上的最后兩個節點；否則轉Step 3.

Step 3 如果R有一條從Ai到Σ的閉合切線，則Ai＋1就是該閉合切線的切點；令Ai＝Ai＋1，然后返回Step 2.否則轉Step 4.

Step 4 如果Ai＝A1，那么A2就是從A1到Σ滿足如下條件單向切線的切點:該切線與Lr(PR，Q1)沒有交點.否則Ai＋1就是從Ai到Σ滿足如下條件單向切線的切點:該切線與Lr(Ai－2，Ai－1)沒有交點.令Ai＝Ai＋1，然后返回Step 2.

結論4 當PRT被知識障礙墻Σ阻斷且從PR到Σ沒有閉合切線時，則(1)R有兩條從PR到Σ的單向切線；(2)設兩條單向切線的切點分別是A1、Q1，那么如果WA1、WQ1都是廣義可行路徑，則其中有一條必是以PR、T為端點的最短廣義可行路徑；Powr必是A1、Q1中的一個.

綜合前面的討論，得到了一個計算Powr的算法，即算法2.

算法2 (計算Powr的近似算法)

Step 1 如果PRT未被知識障礙墻阻斷，那么T就是Powr；否則轉Step 2.

Step 2 設PRT被知識障礙墻Σ阻斷.如果從PR到Σ有一條閉合切線，則該閉合切線的切點為Powr；否則轉Step3.

Step 3 計算出從PR到Σ的兩條單向切線的切點，設分別是A1、Q1.

Step 4 運用算法1，分別得到WA1、WQ1；然后計算出｜WA1｜、｜WQ1｜.

Step 5 如果｜WA1｜＜｜WQ1｜，則A1是Powr；否則Q1是Powr.

據算法2得到的Powr不一定位于以PR、T為端點的最短廣義可行路徑上，原因是WA1、WQ1不一定是以PR、T為端點的廣義可行路徑，不一定滿足結論3的條件，所以算法2只是一個近似算法.但據算法2得到的解，對路徑仍有顯著的優化效果.

算法2在最壞情況下的計算量，就是要分別得到WA1、WQ1.設知識障礙墻中邊數最多知識障礙墻的節點數為m，則根據算法1知:最多經過m步的計算，就可以得到WA1／WQ1；所以算法2的時間復雜度為O(2m).

綜合算法2和前面關于機器人運動控制器的討論，得到了算法3.

算法3 (個體機器人局部路徑的規劃)

Step 1 給定系統參數值；對R、T及環境初始化；令tk＝t0.

Step 2 判斷當前時刻能否設置人工障礙線.如果能夠，則設置好人工障礙線.

Step 3 調用算法2，得到Powr；同時得到所有危墻代表點.

Step 4 對每一個危墻代表點，判斷式(13)是否成立；一旦式(13)成立，即令βR(k)＝β(PR，Powr).

Step 5 在基于人工力矩運動控制器的控制下，R運動一步到達下個時刻的位置.

Step 6 如果R還沒有到達T，則更新知識障礙墻集，然后轉Step 2.如此循環，直到到達T，結束程序.

定理1 如果運用算法3規劃個體機器人的路徑，那么在本文所給條件下，R能最終到達T，即系統具有可達性.

證明 根據算法3和前面的討論，可以得到如下結論:如果tk時刻沒有探測到新的障礙點，沒有也不能設置人工障礙線，那么在不考慮那些不能阻斷PR(k－1)T與PR(k)T的知識障礙墻的條件下，以PR(k)、T為端點的最短廣義可行路徑一定比以PR(k－1)、T為端點的最短廣義可行路徑短.得到上述結論的理由是R會逐漸靠近Powr，從而在環境沒有變化的情況下，相應的最短廣義可行路徑會縮短.

根據上述結論可以推出，在最壞情況下:當所有可能被探測到的障礙點全都被探測，所有的知識障礙墻都通過人工障礙線連成了一條，那么環境就不可能再變化，以PR、T為端點的最短廣義可行路徑就會逐漸縮短并最終為零，即R能最終到達T，所以系統具有可達性.證畢.

4 仿真結果與分析

下面給出一個比較典型的仿真，以證明本文所給方法的可行性與有效性.在該仿真中，系統參數值如表1所示；R不具備任何先驗的環境信息，要求它僅依靠傳感器的實時探測和運動過程中積累的環境知識，運用本文所提方法來規劃出一條到達目標T的路徑.

表1 參數值Tab.1 Values of parameters

仿真結果如圖4所示，其中圖4(a)、(b)分別顯示了R在運動79步和147步后的狀態.從圖4可以看出，R在障礙物前的運動像“沿墻走”方法一樣光滑；但顯然又不是簡單的“沿墻走”.如當R在M點時，發現如果繼續近似沿1號障礙的墻走，有可能要走更長的路徑，就轉向墻的另一端運動.如此調整顯然極大地縮短了R的運動路徑.同時從圖4可以看出，R安全地通過了2號與3號障礙間等狹窄通道，準確地到達了距障礙很近的目標，在整個運動過程中沒有出現被陷住的現象.而上述結果，是人工勢場法難以得到的，所以人工力矩法相對于人工勢場法有顯著的優勢.

圖4 復雜環境中個體機器人的路徑規劃Fig.4 Path planning of single robot in a complicated environment

5 結 語

利用當前全部環境知識而得到的最優路徑代表點，不但可以幫助機器人優化路徑和最終到達目標，且有存儲量小，不需要預處理環境等優點.最優路徑代表點的近似計算方法，雖然不一定總能得到精確解，但卻有時間復雜度低、具有良好優化效果的特點.基于人工力矩的運動控制器，繼承了人工勢場法的實時性強、計算容易等優點，而使機器人不會在復雜環境中被陷住，且能控制機器人準確地到達距障礙很近的目標.

下一步將研究更一般環境中，最優路徑代表點的計算方法及如何運用本文所提方法解決多機器人的避碰和路徑規劃等問題.

[1]GE S S，LAI X，MAMUM A A.Boundary following and globally convergent path using instant goals[J].IEEE Transactions on Systems，Man，and Cybernetics，Part B:Cybernetics，2005，35(2):240－254

[2]ZHU Yi， ZHANG Tao，SONG Jing－yan. An improved wall following method for escaping from local minimum in artificial potential field based path planning [C]／／ Proceedings of Joint 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference.Shanghai:IEEE Press，2009:6017－6022

[3]NG J，BR UNL T.Performance comparison of bug navigation algorithms [J].Journal of Intelligent and Robotic Systems，2007，50(1):73－84

[4]RIMON E， KODITSCHEK D E. Exact robot navigation using artificial potential functions [J].IEEE Transactions on Robotics and Automation，1992，8(5):501－518

[5]GE S S，CUI Y J.New potential functions for mobile robot path planning [J].IEEE Transactions on Robotics and Automation，2000，16(5):615－620

[6]KIM Dong－hun.Escaping route method for a trap situation in local path planning [J].International Journal of Control，Automation，and Systems，2009，7(3):495－500

[7]HUANG H P，CHUNG S Y.Dynamic visibility graph for path planning[C]／／Proceedings of IEEE／RSJ International Conference on Intelligent Robots and Systems.Sendal:IEEE Press，2004:2813－2818

[8]LIU Y H，ARIMOTO S.Proposal of tangent graph and extended tangent graph for path planning of mobile robots [C]／／ Proceedings of IEEE International Conference on Robotics and Automation.Sacramento:IEEE Press，1991:312－317

[9]TAKAHASHI O， SCHILLING R J. Motion planning in a plane using generalized Voronoi diagrams [J].IEEE Transactions on Robotics and Automation，1989，5(2):143－150

[10]SUD A，ANDERSEN E，CURTIS S，etal.Realtime path planning in dynamic virtual environments using multiagent navigation graphs [J].IEEE Transactions on Visualization and Computer Graphics，2008，14(3):526－538

[11]XU Wang－bao，CHEN Xue－bo.Artificial moment method for swarm－robot formation control [J].Science in China Series F:Information Science，2008，51(10):1521－1531

[12]徐望寶，陳雪波.一種基于人工力矩的動態隊形控制方法[J].控制理論與應用，2009，26(11):1232－1238