【文章內(nèi)容簡介】 機器人就能夠?qū)崿F(xiàn)自主導航。通過對各種算法的分析和比較，本文選擇重點研究利用遺傳算法和人工勢場法對機器人進行路徑規(guī)劃。 作為現(xiàn)實環(huán)境中駐留的智能體，機器人與外界環(huán)境交互需要解決基本的三個問題：我在哪里?應該去哪里?如何到達那里?對于此類問題的研究稱為導航技術，而最后一個問題涉及機器人的路徑規(guī)劃，它是導航研究的一個重要環(huán)節(jié)和課題。所謂路徑規(guī)劃，可以描述為在有障礙物的工作環(huán)境中，如何為機器人尋找一條從起點到目標點的最優(yōu)或次優(yōu)路徑，使機器人在運動過程中能安全、無碰撞地繞過所有的障礙物，到達目標點。路徑的性能指標有距離、時間、能量、安全等。與單機器人相比，多機器人的路徑規(guī)劃不僅要求每一個機器人各自尋找一條上述的路徑，還要求機器人沿該路徑行走時避免與其它機器人發(fā)生碰撞，從而對機器人之間路徑的規(guī)劃和協(xié)凋提出了更高的要求。因此，多機器人路徑規(guī)劃具有如下特點：復雜性：動態(tài)時變環(huán)境下的規(guī)劃非常復雜且計算量龐大；隨機性：復雜環(huán)境下的不確定因素使得環(huán)境充滿隨機性；多約束：機器人存在形狀、速度、加速度等約束；多目標：多個機器人均需路徑最短、安全無碰，在同一環(huán)境下會產(chǎn)生沖突。根據(jù)機器人對環(huán)境信息了解的程度不同，路徑規(guī)劃可分為兩種類型：(1)環(huán)境信息己知的離線全局路徑規(guī)劃；(2)環(huán)境信息全部未知或部分未知，通過傳感器對機器人的工作環(huán)境進行探測，以獲取障礙物位置、形狀和尺寸等信息的在線局部路徑規(guī)劃。目前，關于環(huán)境信息完全已知的全局路徑規(guī)劃方法比較多，由于是離線靜態(tài)規(guī)劃方法，通?？梢缘玫阶顑?yōu)路徑。這類方法主要有：可視圖法、自由空間法以及柵格法等。但當機器人在環(huán)境信息完全未知或局部未知的環(huán)境下工作時，就無法使用這些離線方法了。因此，需要使用基于傳感器信息的局部路徑規(guī)劃方法。這類方法通常有：人工勢場法、VFII、D宰法等。局部路徑規(guī)劃利用傳感器提供的環(huán)境信息來進行規(guī)劃，常用的傳感器包括有聲吶、超聲波傳感器、激光測距儀和視覺傳感器等。路經(jīng)規(guī)劃是機器人完成任務的安全保障，也是機器人實現(xiàn)智能化的關鍵技術，是機器人智能化程度的重要標志。在當前機器人硬件系統(tǒng)精度短期內(nèi)無法提高的情況下，對于路徑規(guī)劃算法的研究顯得尤為重要。3 多機器人系統(tǒng)體系結構 多機器人群體體系結構群體體系結構一般分為集中式（Centralized）和分散式（Decentralized）兩種，而分散式結構又可進一步分為分層式（Hierarchical）和分布式（Distributed）兩種（）。群體體系結構的選擇受機器人本身、任務、工作環(huán)境的狀況等諸多因素影響，因此應當綜合分析這些因素，確定系統(tǒng)的規(guī)模及系統(tǒng)機器人間恰當?shù)南嗷リP系，從而選擇合適的結構，充分發(fā)揮其優(yōu)越性。多機器人協(xié)作的體系結構可以歸結為兩個問題：由誰來做出決策并協(xié)調(diào)大家；用什么方法來做決策，得到每個機器人每個運動周期的指令。 (a)集中式結構 (b)分層式結構 (c)分布式結構 多機器人群體體系結構圖(1) 集中式結構(a)所示，它有一個主控機器人，主控機器人運行各種規(guī)劃算法，對其控制下的機器人進行任務分配、相互調(diào)度和動作選擇。在這種體系結構中，受控機器人之間不存在通訊，本身只是一個執(zhí)行體，沒有自己選擇動作和進行相互協(xié)調(diào)的能力。集中式結構的優(yōu)點是理論背景清晰，實現(xiàn)起來較為直觀。它的缺點在于容錯性、適應性和靈活性差，對主控機器人的要求高，當某一個機器人出現(xiàn)問題，特別是主控機器人出現(xiàn)問題時，會導致整個系統(tǒng)的癱瘓。(2) 分布式結構(c)所示，這種結構不存在主控機器人，各機器人之間是平等的，均能通過通訊進行交流、自主地進行決策。相對于集中式結構，分布式結構具有故障冗余、并行運行和可伸縮性等諸多優(yōu)點。但是這種系統(tǒng)的整體性以及協(xié)調(diào)性較差，容易雜亂無章，當各個機器人過分強調(diào)自己任務的重要性時，將會過多地占用系統(tǒng)資源，使得整個系統(tǒng)的效率低下。(3) 分層式結構(b)所示，它是介于集中式結構和分布式結構之間的一種結構，是一種混合型結構。分層式結構有一個主控機器人，同時受控機器人之間也存在著通訊。主控機器人在掌握全局信息及同受控機器人交流的基礎上對任務進行分配，同時協(xié)調(diào)任務執(zhí)行過程中出現(xiàn)的沖突等問題，但不具體地控制受控機器人的運動。各受控機器人掌握著局部環(huán)境信息及所需要的系統(tǒng)信息，執(zhí)行任務時結合著主控機器人的命令及周圍環(huán)境情況自主進行運動規(guī)劃。 典型的機器人個體體系結構 機器人個體控制體系結構是指機器人系統(tǒng)內(nèi)部硬件和軟件的組成結構、功能分配、管理方式，是確定一個機器人系統(tǒng)的智能結構和邏輯上的計算結構。多機器人控制系統(tǒng)(MRCS：Multirobot Cooperative System)由多個機器人組成，機器人控制系統(tǒng)是機器人的核心部分，同時也決定了MRCS中機器人的協(xié)作能力。機器人本身需要具有自主性，對環(huán)境的交互性、協(xié)作性、可通訊性，以及自適應性、實時性等特性?？梢哉f系統(tǒng)性能直接取決于個體機器人性能的好壞。個體機器人的控制結構不同，其采用的控制方法也各不相同。移動機器人從誕生到發(fā)展至今，出現(xiàn)的頗具特色的個體控制結構有慎思式結構、反應式、分層遞階式、以及混合式結構。 慎思式結構慎思式結構，又稱為傳統(tǒng)結構，是通過傳感系統(tǒng)獲得的描述環(huán)境的符號信息，建立環(huán)境模型，然后結合要實現(xiàn)的目標，進行規(guī)劃任務，再由執(zhí)行機構來控制電機轉(zhuǎn)動，從而實現(xiàn)個體機器人對環(huán)境的響應。慎思式體系結構是一種縱向結構，它遵循一條從感知、建模、規(guī)劃、任務執(zhí)行到電機控制的串行控制路線，典型的結構是智能機器人Shakey。慎思式結構適合已知環(huán)境下的任務明確、目標給定的系統(tǒng)，其控制過程都預先規(guī)定，是一個顯式的符號模型，系統(tǒng)的智能在于規(guī)劃者或程序員，而不是執(zhí)行任務的系統(tǒng)。慎思式結構的缺點很明顯：(1)體積大。機器人存儲符號信息量與它內(nèi)部狀態(tài)的大小相當，系統(tǒng)越復雜，體積越大。(2)建模困難。規(guī)劃和世界模型的建立是一個非常困難的過程，而且計劃的開環(huán)執(zhí)行無法適應環(huán)境的不確定性和不可預知性。 慎思式結構圖 Schema的一種“純粹”的行為（behaviors）控制系統(tǒng)，它遵循“感知—動作”的規(guī)則，在AI（Agent Intelligent）領域也被稱為行為主義?；谛袨榈目刂扑枷氩煌趥鹘y(tǒng)人工智能的功能分解方法，它采用動作分解或行為分解的方法。 反應式結構反應式結構采用自下而上的構造系統(tǒng)方式。它不包含世界模型，也不使用復雜的符號推理，系統(tǒng)的功能由一些基本、簡單的行為完成，在得到傳感器的輸入后，有能力不經(jīng)過復雜的推理而立即對環(huán)境做出反應，是一種構造工作于開放式環(huán)境中機器人的有效工具。它建立了機器人傳感器與執(zhí)行器的直接聯(lián)系，通過行為的響應實現(xiàn)控制，從而提高了系統(tǒng)的快速反應能力。各種行為在融合時通過權重的大小來體現(xiàn)機器人的不同側(cè)重點（像以協(xié)作為主還是以競爭為主），權重有不同的調(diào)整規(guī)則。Brooks提出的包容式結構(Subsumption Architecture）可以看作反應式結構的一個特例，它的行為權重只有0和1，而且每次只有一種行為的權重為1，其余行為權重抑制為0。反應式結構的優(yōu)點是采用模塊化設計，對于不同的任務要求及環(huán)境需求易于重構，而且響應快速，適合于動態(tài)、開放的環(huán)境。其缺點是不能勝任傳感器數(shù)據(jù)的復雜分析、推理，而且由于知識的不足，不能完成認知水平的任務。 分層遞階式體系結構分層遞階式體系結構，美國學者Saridis很早就提出了一個關于智能控制系統(tǒng)的三級分層遞階式體系結構[33]，其分層原則是隨著控制精度的增加而智能減少。 分層遞階式結構 該結構是以問題的分解、規(guī)劃為基礎，每一層都有一個統(tǒng)一的問題表達方式，往往上層模型比下層具有更高的抽象層次，處理更為復雜的問題。當某層收到上層下發(fā)的任務后，要根據(jù)本層的世界模型，將該任務表達為本層問題，同時將該問題分解為下一層可解決的子問題序列，并將其作為任務繼續(xù)下發(fā)給下層。這樣，一個總?cè)蝿战?jīng)層層分解直到最底層——一般為執(zhí)行機構的驅(qū)動層。從這一過程可以看出，其任務分解與規(guī)劃基本是離線的過程，其傳感器的作用是為離線規(guī)劃提供世界模型，這種模型是靜態(tài)的，重新規(guī)劃發(fā)生在上層下達新任務及下層報告某子任務無法完成時。而無論在何種情況下，所有已有的分解及規(guī)劃結果都將被舍棄，而代之以新的規(guī)劃結果。因此，我們只有兩種途徑處理動態(tài)環(huán)境的問題，一是建立可以表達這種動態(tài)環(huán)境的世界模型，這樣就可以事先對環(huán)境的變化反應，做出合理的規(guī)劃，但是很難建立動態(tài)環(huán)境的有效模型。因而，在高度動態(tài)環(huán)境中，只能通過傳感器等感知環(huán)境的變化。如果環(huán)境的變化導致某層任務的失敗，該失敗將被上報給上層，同時環(huán)境的變化將被感知并引起世界模型的變化，上層或重新規(guī)劃或?qū)⑷蝿帐⌒畔⒗^續(xù)上報，直到某一合適的功能層重新規(guī)劃為止。因此，任何環(huán)境變化都有可能導致重新規(guī)劃的發(fā)生，而且可能在多個層次上發(fā)生。如果這種重新規(guī)劃的頻率過高，將大大降低任務的完成效率，減弱機器人的反應能力。這種結構的優(yōu)點在于，系統(tǒng)的功能及層次分明，易于實現(xiàn)；缺點是由于該結構采用串行處理使得對外部時間的反應時間變長，任何環(huán)境的變化都有可能導致重新規(guī)劃的發(fā)生，對外部的反應時間較長，從而降低了任務完成的效率。 混合式結構傳統(tǒng)的體系結構缺乏實用性和必要的靈活性，而包容式結構和反應式結構都是針對移動機器人而提出的，提高了系統(tǒng)的響應速度，在一些實際應用中產(chǎn)生了良好的效果；慎思式和分層遞階式智能程度較高，但是無法對環(huán)境的變化做出快速的反應。隨著機器人控制體系結構研究的深入開展，許多研究人員將多種體系結構有機地結合起來，實現(xiàn)多種體系結構的優(yōu)勢互補，形成了更加魯棒的混合式體系結構。這種結構通過對控制體系結構進行合理的分層，將包容式結構，反應式控制結構與上層規(guī)劃，推理有機地結合在一起。目前開展的體系結構研究工作很多圍繞著混合式體系結構進行，混合式結構能夠快速響應環(huán)境信息，但其智能程度較低。典型的結構有蔡自興提出的基于功能/行為集成的自主式移動機器人進化控制體系結構[34]，趙憶文提出的由系統(tǒng)監(jiān)控管理層、行為模塊層和運動行為層構成的基于行為的分層遞階控制結構[5]，Conell提出了基于包容式結構的包括符號層、包容層和伺服控制層的SSS結構。4 人工勢場法 人工勢場法原理 在物理學中研究的問題往往都要涉及到一定空間區(qū)域內(nèi)的物理量，而各個物理量之間又相互存在一定的關系或影響。通常，我們將這個空間區(qū)域稱之為“場，比如力場、電場以及磁場等具有類似特征。在上述一些的所謂“場中間，用來描述其特征屬性物理量往往是以空間位置(坐標)為變量的函數(shù)。力場中的引力場就是通過兩物體間的距離來衡量計算其間引力的大小，電場、磁場中力的大小也都與其參照源的相對距離有關。類似于場的概念，Khatib引入了人工勢場的概念。人工勢場法的基本思想是：把機器人在環(huán)境中的運動視為在一種抽象的人造受力場中運動，即在環(huán)境中建立目標點引力場和障礙物斥力場共同作用的人工勢場，搜索勢函數(shù)的下降方向來尋找無碰路徑。具體方法是首先在機器人的運動空間中創(chuàng)建一個勢場。該勢場由兩部分組成，一個是引力場，目標點對機器人產(chǎn)生引力，方向指向目標點另一個是斥力場，障礙物對機器人產(chǎn)生斥力，方向指向遠離障礙物的方向。整個勢場是其引力部分和斥力部分的疊加。根據(jù)引力和斥力的合力來控制機器人的運動。機器人就沿著合成的勢場力方向，繞開障礙物，向目標點運動。人工勢場如圖4—1所示。 人工勢場法模型圖從避障考慮，引力勢場作用的范圍較大,而斥力場只是作用在局部范圍內(nèi)，距障礙較遠的區(qū)域不受障礙斥力場的影響。因而，這種方法也稱為局部方法。 傳統(tǒng)的勢場函數(shù) 勢場是對一機器人運行環(huán)境的人為抽象描述，障礙物Obstacle及目標點Goal按某種規(guī)則(勢函數(shù))產(chǎn)生一定的勢場，機器人Robot在勢場中具有一定的勢能勢函數(shù)是根據(jù)實際情況人為設定的，所以勢函數(shù)的形式不是固定不變的，往往是根據(jù)需要設定。勢函數(shù)分為斥力勢函數(shù)和引力勢函數(shù)。我們下面介紹一種傳統(tǒng)的勢場函數(shù)。 (1)斥力勢函數(shù)在勢場中，由障礙物產(chǎn)生的勢場對機器人產(chǎn)生斥力，并且距離越近，斥力越大，即機器人與障礙物越近，機器人具有的勢能越大，反之越小。這種勢場和電磁場類似，與距離成反比，所以斥力勢函數(shù)可以表示為： （）式中：Kr為斥力勢場常量；X為機器人位置向量；Xobs為障礙物位置向量；p(X，Xobs)=｜XXobs｜為機器人與障礙物的最短距離；為斥力勢場的作用范圍。當機器人與障礙物的距離大于時，斥力勢場對機器人的運動不再有影響。斥力的方向背離障礙物。當→0時，→∞，即當機器人與障礙物相碰時，受到的斥力為無窮大。為了避免機器人與障礙物相碰，可以設一個最小安全距離，當→時，→∞機器人受到的可以表示為： (2)引力勢函數(shù)目標的引力勢函數(shù)Uatt同樣也基于距離的概念。目標對機器人起吸引作用，距離越遠，吸引作用越大，即機器人距目標越遠，所具有的勢能就越大；反之就越小。當距離為零時，機器人的勢能為零，此時機器人到達目標。這種勢場和重力場類似。引力勢函數(shù)可取為： () 式中：Ka為引力勢場常量；為目標位置向量；為機器人與目標的距離。相應的引力為，引力的方向指向目標點。所以機器人所受的勢場和力分別為； () （） 傳統(tǒng)的人工勢場法存在的問題 采用人工勢場法，當環(huán)境變得復雜之后，機器人可能找不到一條可以使之無碰撞到達目標點的路徑，原因是傳統(tǒng)勢場法還存在一定的問題。問題一：目標點不可到達 當目標點位置與障礙物位置很近時，機器人在引力場的作用下往目標運動時也同時向障礙物靠近，機器人在受到引力向目標運動的同時還受到來自障礙物的斥力作用，如果此時斥力大于引力，那么總的勢場力在目標點附近就不是全局最小，機器人將不能到達目標點。大量的實驗表明，局部極小往往發(fā)生在離障礙物比較近的地方。問題二：陷入局部極小值點 在