多機(jī)器人編隊(duì)避障方法理論基礎(chǔ)概述目錄TOC\o"1-3"\h\u12762多機(jī)器人編隊(duì)避障方法理論基礎(chǔ)概述 1287561.1人工勢(shì)場(chǎng)法 1153841.2BUG算法 4283201.3向量直方圖法 5213111.4搜索類算法 5142581.5其他算法 11324061.5.1神經(jīng)網(wǎng)絡(luò)方法 1129781.5.2模糊邏輯方法 13在機(jī)器人向目標(biāo)點(diǎn)前行過程中，通過傳感器感知障礙物的存在，利用避障算法進(jìn)行處理，指導(dǎo)機(jī)器人的下一步行為，指引其路線的選擇，實(shí)時(shí)更新路線軌跡，繞過障礙物REF_Ref14966\r\h[25]。隨著計(jì)算機(jī)運(yùn)算能力的不斷加強(qiáng)，傳感器精度的升級(jí)以及自動(dòng)化程度的提升，對(duì)避障算法提出了更高的要求，越來越多的需要適應(yīng)性更強(qiáng)的、統(tǒng)一化程度更高的避障算法，以期能解決更為復(fù)雜障礙環(huán)境條件，不同類型機(jī)器人避障的客觀需要。然而至今沒有任何一種避障策略算法能夠解決在多障礙，多地形條件，多維度環(huán)境中機(jī)器人都能進(jìn)行有效地避障這一問題，突破解決統(tǒng)一化程度更高，適應(yīng)性更強(qiáng)的避障算法的問題勢(shì)必會(huì)帶來機(jī)器人領(lǐng)域的一場(chǎng)大的革新。人工勢(shì)場(chǎng)法人工勢(shì)場(chǎng)(Artificialpotentialfields,APF）是由KhatibREF_Ref15156\r\h[26]在上世紀(jì)九十年代年提出的。將一個(gè)物體被放置在一個(gè)力場(chǎng)中，這個(gè)力場(chǎng)是由一個(gè)被定義為目標(biāo)的點(diǎn)的引力和被建模為不可通過的障礙物表面所產(chǎn)生的的斥力所形成的，那么這個(gè)物體就有可能在不與障礙物碰撞的情況下穿過存在障礙的實(shí)驗(yàn)環(huán)境并到達(dá)目標(biāo)點(diǎn)。APF技術(shù)基于目標(biāo)的吸引力和移動(dòng)機(jī)器人運(yùn)行檢測(cè)識(shí)別區(qū)域內(nèi)障礙物的排斥力的矢量和。一般的設(shè)計(jì)是，機(jī)器人在當(dāng)前位置所受目標(biāo)的吸引力隨著距目標(biāo)點(diǎn)位置距離的增加而增加，所受到的排斥力同障礙物表面與機(jī)器人之間的距離成反比。對(duì)于避障區(qū)域內(nèi)每個(gè)點(diǎn)，都可以計(jì)算出在該點(diǎn)機(jī)器人所受到的合力，該合力將指引機(jī)器人下一步行為（如圖3-1所示）。人工勢(shì)場(chǎng)法將地圖中的障礙物產(chǎn)生的斥力場(chǎng)表現(xiàn)為電磁學(xué)上的一個(gè)高峰，而目標(biāo)點(diǎn)產(chǎn)生的引力表現(xiàn)為低谷。在機(jī)器人要進(jìn)行避障的區(qū)域內(nèi)，勢(shì)場(chǎng)會(huì)對(duì)機(jī)器人每個(gè)位置產(chǎn)生指引下一步運(yùn)行的合力，指引著機(jī)器人向目標(biāo)點(diǎn)前行。圖3-1APF原理示意圖如圖3-2所示，三幅圖中，展示了人工勢(shì)場(chǎng)的原理。左圖是障礙環(huán)境，中間兩個(gè)黑塊是障礙物。機(jī)器人要從圖中無障礙地從起始點(diǎn)運(yùn)動(dòng)到目標(biāo)點(diǎn)。在通過人工勢(shì)場(chǎng)法形成勢(shì)場(chǎng)后，建立了中圖所示的模型，最后那幅圖展示了形成勢(shì)場(chǎng)后得到的等勢(shì)位圖，圖中的每條連續(xù)的曲線就表示了同勢(shì)力值大小的位置，可以看到示意機(jī)器人運(yùn)行軌跡的從起點(diǎn)到終點(diǎn)的連線不會(huì)跨過障礙，機(jī)起始點(diǎn)出發(fā)，一路沿著勢(shì)場(chǎng)下降的方向到達(dá)最終的目標(biāo)點(diǎn)REF_Ref17017\r\h[27]。圖3-2勢(shì)場(chǎng)示意圖想象將一個(gè)小球從碗邊放入碗中，小球會(huì)自然地向碗的底部滑落。這就好比一個(gè)勢(shì)場(chǎng)。機(jī)器人正是沿著“碗底”這個(gè)勢(shì)場(chǎng)所指向的那個(gè)方向一直行走。更進(jìn)一步的是，如果碗的壁不是光滑的，有凸起的。那么小球會(huì)在下滑的過程中繞開凸起滑向碗底。類似的，機(jī)器人在人工市場(chǎng)中也會(huì)將障礙物看成是一個(gè)個(gè)的凸起，從而繞過這個(gè)比較高的障礙物向著目標(biāo)行進(jìn)。從一方面來看，在數(shù)學(xué)表達(dá)式上人工勢(shì)場(chǎng)法顯現(xiàn)了出簡(jiǎn)潔、優(yōu)美的亮眼之處，得到了很多人的青睞。且在常規(guī)障礙環(huán)境中，適應(yīng)性良好，得到了極大的應(yīng)用。人工勢(shì)場(chǎng)法也存在著需要解決的問題與瓶頸。人工勢(shì)場(chǎng)法存在局部最優(yōu)點(diǎn)問題：多數(shù)情況下，在應(yīng)用避障算法的時(shí)候并不會(huì)將目標(biāo)點(diǎn)置于障礙物極近的位置。這樣當(dāng)機(jī)器人運(yùn)行到目標(biāo)點(diǎn)位置附近時(shí)，障礙物的斥力會(huì)變小，不能與目標(biāo)點(diǎn)產(chǎn)生的引力抗衡，機(jī)器人受到目標(biāo)點(diǎn)吸引而向目標(biāo)點(diǎn)進(jìn)發(fā)直至到到終點(diǎn)。但在一個(gè)極端情況下，將目標(biāo)點(diǎn)附近放置一個(gè)障礙物，這樣當(dāng)機(jī)器人接近目標(biāo)時(shí)，機(jī)器人在受到目標(biāo)位置引力的同時(shí)還會(huì)受到相近位置的障礙物產(chǎn)生的斥力。會(huì)造成斥力與引力“較勁”的情況，合力變不會(huì)指向目標(biāo)點(diǎn)，機(jī)器人并不會(huì)繼續(xù)向著目標(biāo)位置進(jìn)發(fā)，合勢(shì)場(chǎng)導(dǎo)向產(chǎn)生了錯(cuò)誤，機(jī)器人最終也就無法到達(dá)目標(biāo)點(diǎn)，反而會(huì)被障礙物排斥的更遠(yuǎn)。解決方法上，可以調(diào)整合勢(shì)場(chǎng)函數(shù)，通過建立統(tǒng)一的勢(shì)能函數(shù)來解決這一問題。如在合勢(shì)場(chǎng)函數(shù)中加入零極值點(diǎn)，這樣就可以無論終點(diǎn)位置是否存在障礙物，都會(huì)保證目標(biāo)點(diǎn)的是勢(shì)場(chǎng)零點(diǎn)，是“碗”的最低部。但為了機(jī)器人實(shí)際運(yùn)行算法的時(shí)候進(jìn)行有效率的避障，這種方法勢(shì)必會(huì)增大運(yùn)算量。因而，這種改進(jìn)方法只適用障礙物是規(guī)則的，且數(shù)量上不宜過多。否則算法的計(jì)算量將很大，有時(shí)甚至是無法計(jì)算的。處理函數(shù)中的局部極小值問題的另一種思路是，一旦檢測(cè)到機(jī)器人沒有到達(dá)目標(biāo)位置（即卡住在局部極小值）就給機(jī)器人施加隨機(jī)力，稱為隨機(jī)漫步。例如，如果機(jī)器人被想象成一個(gè)流體或氣體粒子，機(jī)器人將能夠通過機(jī)器人和目標(biāo)位置之間的障礙物。但是，這種方法在遇到狹窄的通道時(shí)就不會(huì)成功，會(huì)導(dǎo)致與障礙發(fā)生碰撞。人工勢(shì)場(chǎng)法還存在一個(gè)致命缺點(diǎn)——零勢(shì)能點(diǎn)。在某些特殊情況下，障礙物形成的斥力與目標(biāo)位置的引力恰抵消，這會(huì)使得使移動(dòng)機(jī)器人陷入局部極小點(diǎn)，機(jī)器人利用合力無法走出極小點(diǎn)，達(dá)不到路徑規(guī)劃的目的。隨著障礙物的數(shù)量增加，產(chǎn)生零勢(shì)能點(diǎn)的可能性也會(huì)隨之增加REF_Ref18101\r\h[28]。因此，解決零勢(shì)能點(diǎn)的問題在復(fù)雜障礙環(huán)境條件下顯得尤為重要。另外在局部雜亂的環(huán)境中，機(jī)器人若遇到不規(guī)則障礙物，例如鋸齒狀障礙物前，由于機(jī)器人可以在無障礙的路徑中獲得更高的速度，可能存在歐氏距離意義上更長(zhǎng)但運(yùn)行時(shí)間更短的路徑，合勢(shì)場(chǎng)會(huì)形成“渦流”現(xiàn)象，機(jī)器人會(huì)在障礙物前震蕩，形成徘徊抖動(dòng)現(xiàn)象。震蕩運(yùn)動(dòng)問題的一種解決方案是將障礙物分組在一起，設(shè)置虛擬障礙物，這些障礙物可能包含狹窄的通道，并且障礙物之間距離足夠近。在一些特殊避障場(chǎng)景下，例如迷宮，人工勢(shì)場(chǎng)法還會(huì)存在陷阱區(qū)域的問題。通過對(duì)人工勢(shì)場(chǎng)法的優(yōu)劣分析，在3.4節(jié)提出A*算法徹底解決這種弊端，并在5.5節(jié)通過仿真實(shí)驗(yàn)加以驗(yàn)證。BUG算法Bug算法是最符合機(jī)器思維的避障算法。其基本思想是，機(jī)器人向著目標(biāo)點(diǎn)直線前行，直到在檢測(cè)到障礙后，原有的直行行不通了，下一步就是圍著檢測(cè)到的障礙物輪廓保持安全距離裕量繞行，從而“繞開”它。為了簡(jiǎn)化運(yùn)算步驟，優(yōu)化軌跡曲線，Bug算法經(jīng)過發(fā)展有著不同的改善版本。最初版的Bug1避障思路是這樣的。機(jī)器人在向著目標(biāo)點(diǎn)直線行進(jìn)過程中遇到障礙物時(shí)，它首先完全地圍繞物體運(yùn)動(dòng)，并在從距目標(biāo)點(diǎn)距離最短的點(diǎn)與障礙物分離（如圖3-3所示）。雖然Bug1算法的效率很低，但通過這樣做卻可以保證機(jī)器人到達(dá)目標(biāo)，這也為后續(xù)的版本地改進(jìn)提供了基礎(chǔ)。優(yōu)化后的Bug2算法中，機(jī)器人在遇到障礙時(shí)雖然也會(huì)跟蹤圍繞著障礙物邊沿運(yùn)行，但它與Bug1算法最大的不同是，其并不會(huì)完全圍繞物體一整周，一旦機(jī)器人發(fā)現(xiàn)可以直線移動(dòng)至目標(biāo)時(shí)，就立即與障礙分離，這樣比起B(yǎng)ug1算法在總行走距離上少了不少（如圖3-3所示）。分析可知，路線的選取長(zhǎng)度較長(zhǎng)是Bug算法得到應(yīng)用的一個(gè)重要的限制因素。機(jī)器人采用該算法避障會(huì)走許多“彎路”，運(yùn)行效率低下。更為關(guān)鍵的是，Bug算法只能用于二維場(chǎng)景，三維環(huán)境下并不適用。當(dāng)遇到特殊形狀的障礙物時(shí)，這種算法往往會(huì)得到錯(cuò)誤的路。圖3-3BUG1算法（左）與改進(jìn)后BUG2算法（右）對(duì)比示意圖向量直方圖法向量直方圖法將機(jī)器人當(dāng)前位置周圍環(huán)境對(duì)機(jī)器人運(yùn)行產(chǎn)生的影響用概率加以描述，并用柱狀圖刻畫影響。向量直方圖法是典型的即走即更新地圖的實(shí)時(shí)性避障算法。向量直方圖法基本過程有兩步，首先刻畫機(jī)器人周圍的環(huán)境，并采用直方圖柵格化轉(zhuǎn)換為極坐標(biāo)向量的形式描述，第二階段依據(jù)通過概率，選擇對(duì)機(jī)器人運(yùn)行影響概率最小的方向前進(jìn)。向量直方圖法難點(diǎn)在于基于機(jī)器人當(dāng)前位置做到生成一個(gè)實(shí)時(shí)的直方圖。該圖會(huì)根據(jù)機(jī)器人所搭載的傳感器所傳來的數(shù)據(jù)來進(jìn)行實(shí)時(shí)的更新。這就對(duì)傳感器硬件和機(jī)器人的運(yùn)算力提出了更高的要求。VFH算法生成的的極坐標(biāo)直方圖如圖3-4所示：圖3-4VFH示意圖REF_Ref22631\r\h[29]如圖3-4所示，橫軸為機(jī)器人當(dāng)前位置探測(cè)到360°方向上的角度范圍，縱坐標(biāo)為機(jī)器人在各方向上通過周邊環(huán)境的概率值。實(shí)際過程中機(jī)器人會(huì)每隔一個(gè)時(shí)間采樣點(diǎn)，生成一幅柱狀概率圖，根據(jù)通過概率選擇通過概率最高的去行進(jìn)。搜索類算法談及避障，機(jī)器人首先要做的事不是如何去“躲避”，而是向哪走。因?yàn)檎系K物的未知性，機(jī)器人“視野”有界性，避障只應(yīng)是機(jī)器人在向目標(biāo)點(diǎn)移動(dòng)過程中遇到障礙后采取的行動(dòng)。無論是人工勢(shì)場(chǎng)法，BUG算法亦或是向量直方圖法均是在機(jī)器人前進(jìn)過程中，先感知障礙物，通過相應(yīng)算法計(jì)算出下一步的位置從而規(guī)劃路徑。另一種思路是，將機(jī)器人從當(dāng)前位置到目標(biāo)位置所有路徑加以預(yù)先探索，從中選取一條運(yùn)行。在小范圍內(nèi)，這種思路具有可行性。一個(gè)直接的想法是，從機(jī)器人當(dāng)前位置與目標(biāo)點(diǎn)建立直線L，機(jī)器人沿著這條直線行走，遇到障礙后再采取避障的策略，如順時(shí)針或逆時(shí)針繞障礙物行走直到重回直線L上，再繼續(xù)向目標(biāo)點(diǎn)行進(jìn)。如此往復(fù)執(zhí)行，勢(shì)必會(huì)到達(dá)“終點(diǎn)”。在不考慮路徑規(guī)劃的情況下這是一種簡(jiǎn)單的且切實(shí)可行的策略。這個(gè)策略明顯存在一個(gè)缺陷，就是“繞”，會(huì)顯著增加機(jī)器人路線長(zhǎng)度。為了解決這一路徑優(yōu)化問題，1968年Hart教授等專家提出了一種用于路徑搜索的啟發(fā)式搜索算法——A*算法REF_Ref24466\r\h[30]。與人工勢(shì)場(chǎng)法最大的不同是，A*解決了障礙“圈套”的問題。要想逃離，躲避障礙圈套的第一步就是要識(shí)別處于路線上所有可能對(duì)機(jī)器人“設(shè)套”的障礙。這就需要機(jī)器人在向目標(biāo)點(diǎn)前行之前遍歷搜索這些障礙物。這其中的方法有很多。為了實(shí)現(xiàn)所謂的搜索，就需要量化地圖，這就需要將路徑量化，即柵格化（如圖3-5所示）。將地圖劃分為一個(gè)個(gè)大小一致的柵格，之后就是搜索了。尋路的工作核心就是去遍歷設(shè)定地圖區(qū)域內(nèi)機(jī)器人下一步或下幾步將要走的或者是可能要去走的地圖，識(shí)別出其中存在的影響向目標(biāo)行進(jìn)的障礙并加以刻畫，緊接著對(duì)可通過的部分進(jìn)行線路規(guī)劃，從而指導(dǎo)機(jī)器人的行進(jìn)。圖3-5柵格地圖示意圖地圖柵格化之后形成一個(gè)個(gè)形狀、大小相同的小室。這些小室的形狀為了方便下一步機(jī)器人行進(jìn)線路的統(tǒng)一化，最好是對(duì)稱圖形。比如可以把要搜尋的區(qū)域劃分成了正方形的格子。這樣一來，還可以方便的把機(jī)器人要進(jìn)行搜索的每個(gè)柵格標(biāo)記成0，1數(shù)組。數(shù)組的每一項(xiàng)代表一個(gè)格子，標(biāo)記為0的柵格被認(rèn)為是下一步機(jī)器人可以走的，可以用來規(guī)劃行進(jìn)路線的，而標(biāo)記為1的柵格就是障礙物所在的柵格，在規(guī)劃?rùn)C(jī)器人線路的時(shí)候加以過濾掉。再下一步的工作就是遍歷地圖，通過不同的算法決定走那些代表著0的格子最合理，最有效。這樣就實(shí)現(xiàn)了優(yōu)化機(jī)器人路徑的過程從而完成路徑規(guī)劃的目的。方便起見，把每個(gè)劃分好的方格的中心點(diǎn)定義為“節(jié)點(diǎn)”（node），這樣每個(gè)單元格都是一個(gè)節(jié)點(diǎn)。邊緣連接相鄰的單元格。障礙物可以被設(shè)置為“空”，這樣機(jī)器人就無法與障礙相遇，復(fù)雜情況下，可以對(duì)不同路況的區(qū)域格子賦以不同的權(quán)重?？梢哉f用于機(jī)器人搜索的地圖是由節(jié)點(diǎn)斷續(xù)組成的?？梢灶A(yù)見，柵格化程度越高，即密化搜索地圖程度也越高，規(guī)劃出的機(jī)器人行進(jìn)路線也就越平滑。當(dāng)然的，生成的數(shù)組量也越大，會(huì)帶來運(yùn)算量和響應(yīng)時(shí)間上的同步提升。因而，根據(jù)不同的障礙環(huán)境，避障要求指標(biāo)的不同，選取不同的密化度尤為重要。從整體響應(yīng)時(shí)間來看，并非一味地的追求高平滑度的行進(jìn)路線就是最優(yōu)的。通過以上分析，研究搜索區(qū)域內(nèi)的路徑規(guī)劃，障礙環(huán)境中機(jī)器人的避障問題其實(shí)就是就是研究遍歷圖的方法。把從圖中的一個(gè)節(jié)點(diǎn)出發(fā)訪問圖中其他所有的節(jié)點(diǎn)的過程稱為遍歷，為了高效，只要是某一節(jié)點(diǎn)被訪問過，當(dāng)然的，它就不必被再次訪問了。所以，遍歷過程需要兩個(gè)“記錄”，或者說是記錄表。一個(gè)用來記錄未被考察的小室，不妨把它稱作OPEN表；一個(gè)用來記錄已經(jīng)考察過的小室，稱為CLOSED表。要明確一點(diǎn)的是，遍歷的過程機(jī)器人事先并不知道終點(diǎn)的位置以及障礙物的位置，他只在自己的搜索框地圖內(nèi)遍歷。這也是搜索遍歷的意義所在。而搜索的方法有多種。從深度與廣度兩種不同優(yōu)先遍歷節(jié)點(diǎn)的方式來分，遍歷搜索圖有深度優(yōu)先遍歷（DepthFirstSearch，DFS）與廣度優(yōu)先遍歷（BreadthFirstSearch，BFS）兩種方式。第一種是“打破砂鍋問到底”的尋訪節(jié)點(diǎn)的方式。機(jī)器人從當(dāng)前位置開始，縱向或橫向選擇一條支路，將其看為是一條沒有岔路的單行路，盡可能不斷地向前推進(jìn)搜索，直至遍歷到了圖的邊界或探尋到障礙節(jié)點(diǎn)就往回退?；赝藭r(shí)，只要再次發(fā)現(xiàn)一條可以繼續(xù)縱深推進(jìn)搜索的下級(jí)支路，則繼續(xù)向前。依次往復(fù)，直至發(fā)現(xiàn)目標(biāo)點(diǎn)或遍歷盡地圖。像這樣以縱深推進(jìn)為優(yōu)先搜索方向，不斷先縱深再回退尋找其他支路的遍歷方式，稱為深度優(yōu)先遍歷（DFS）（如圖3-6所示）。DFS使用“后進(jìn)先出”原則。圖3-6DFS示意圖與之相對(duì)應(yīng)的，還有另一種尋訪方式：在遍歷順序上，將寬度或者說是廣度看成是優(yōu)先搜索的過程就是廣度優(yōu)先搜索算法。具體來講，以機(jī)器人當(dāng)前位置為核心點(diǎn)，首先把它周圍的的幾個(gè)節(jié)點(diǎn)探索完成，接著在以已經(jīng)形成的搜索過的區(qū)域?yàn)楹诵膮^(qū)域，將其相接的更外圍的一圈節(jié)點(diǎn)加以搜索，然后再去搜索距離機(jī)器人起始點(diǎn)起點(diǎn)更遠(yuǎn)一些（間隔兩層）的節(jié)點(diǎn)……這樣不斷擴(kuò)大搜索區(qū)域，直至所有的節(jié)點(diǎn)被遍歷。這種由機(jī)器人起始點(diǎn)為核心節(jié)點(diǎn)，不斷地向外圍擴(kuò)散的遍歷方式就是廣度優(yōu)先搜索算法（BFS）。為了有序的遍歷到每一圈的節(jié)點(diǎn)，需要在執(zhí)行算法的過程中，記錄當(dāng)前被尋訪的節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)的位置，稱之為根節(jié)點(diǎn)。這樣做的好處是，一旦遍歷結(jié)束，搜索到目標(biāo)點(diǎn)后，便可以從目標(biāo)點(diǎn)開始，溯源根節(jié)點(diǎn)逆序找到起點(diǎn)，由此就構(gòu)成了一條路徑（如圖3-7所示）。BFS使用“先進(jìn)先出”原則。圖3-7BFS示意圖在對(duì)節(jié)點(diǎn)數(shù)據(jù)的采集，存儲(chǔ)以及運(yùn)算上，深度優(yōu)先算法與廣度優(yōu)先算法有著顯著的區(qū)別（如圖3-8所示）。廣度優(yōu)先算法新節(jié)點(diǎn)的信息會(huì)頂?shù)糇畛豕?jié)點(diǎn)的信息，所以BFS選取狀態(tài)采用了隊(duì)列的形式，先進(jìn)先出。廣度優(yōu)先算法由于需要不斷記錄上一根節(jié)點(diǎn)的位置信息，數(shù)據(jù)需要加以堆積，采用了類似堆棧的方式。當(dāng)前遍歷的節(jié)點(diǎn)信息在下一遍歷過程中會(huì)立即被提出。圖3-8DFS（左圖）與BFS（右圖）數(shù)據(jù)查詢方式對(duì)比更進(jìn)一步的情況是，如果一些障礙物并不影響機(jī)器人通過，這樣并沒必要刻意去躲避障礙。也就是說，可以將圖形中相鄰節(jié)點(diǎn)之間的移動(dòng)代價(jià)加以賦值。鑒于此，上世紀(jì)六十年代，計(jì)算機(jī)科學(xué)家EdsgerW.Dijkstra設(shè)計(jì)出Dijkstra算法REF_Ref28159\r\h[31]。Dijkstra算法考慮到了當(dāng)前節(jié)點(diǎn)與起始節(jié)點(diǎn)的移動(dòng)代價(jià)。為了實(shí)現(xiàn)易于統(tǒng)計(jì)節(jié)點(diǎn)之間機(jī)器人移動(dòng)的代價(jià)和，采用設(shè)置優(yōu)先隊(duì)列表的方式加以記錄。優(yōu)先隊(duì)列表根據(jù)每個(gè)節(jié)點(diǎn)與機(jī)器人起始節(jié)點(diǎn)的預(yù)估值來進(jìn)行排序。在機(jī)器人避障前加以遍歷地圖，對(duì)遍歷過的每一個(gè)節(jié)點(diǎn)均需計(jì)算其從當(dāng)前位置到起始位置所移動(dòng)的距離代價(jià)，即對(duì)每個(gè)可通過的節(jié)點(diǎn)賦以權(quán)值，最終選取權(quán)重小的節(jié)點(diǎn)規(guī)劃?rùn)C(jī)器人路徑。一步步反復(fù)進(jìn)行，以保證每步的移動(dòng)代價(jià)是最小的?？梢钥闯鲈贒ijkstra算法中，并沒有考慮到下一節(jié)點(diǎn)的選取問題，或者說在搜索方向上存在一定的盲目性。針對(duì)這個(gè)痛點(diǎn)，我們不妨再增加一個(gè)考慮因素，及給定一個(gè)搜索方向，使得每次選取下一個(gè)搜索節(jié)點(diǎn)都具有向目標(biāo)點(diǎn)進(jìn)發(fā)的方向性。這就是貪婪最佳優(yōu)先搜索算法。貪婪最佳優(yōu)先搜索算法在優(yōu)先隊(duì)列表里通過每個(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的預(yù)估值來進(jìn)行排序。在搜索時(shí)間上不難分析出，貪婪最佳優(yōu)先搜索算法遍歷時(shí)間要顯著短于廣度優(yōu)先算法，效率上得以大幅提升。盡管它的路徑不是最優(yōu)和最短的。這也正是貪婪最佳優(yōu)先搜索算法的優(yōu)勢(shì)之處，基于目標(biāo)方向去搜索，摒棄了全圖全域式地完全搜索。在有了搜索時(shí)間上最快的遍歷方式——貪婪最佳優(yōu)先算法和搜索路徑上最短的遍歷方式——Dijkstra算法的基礎(chǔ)上，就可以綜合兩者優(yōu)勢(shì)得到又快，又短的遍歷節(jié)點(diǎn)的算法——A*算法。既考慮當(dāng)前代價(jià)，即為每個(gè)尋訪節(jié)點(diǎn)設(shè)置權(quán)值，不停的計(jì)算每個(gè)節(jié)點(diǎn)到起始節(jié)點(diǎn)的距離，以獲得最短路線，同時(shí)也照顧到搜索方向上的目的性，持續(xù)計(jì)算每個(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)點(diǎn)的距離，從而引導(dǎo)機(jī)器人的搜索隊(duì)列不斷地向目標(biāo)位置逼近，從而搜索更少的節(jié)點(diǎn)，以保證路徑規(guī)劃的最優(yōu)。經(jīng)過以上分析，不難得出A*算法依據(jù)的基本原理公式：（3-1）F(n)表示從機(jī)器人當(dāng)前所在節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)總共需要經(jīng)過的預(yù)估距離。G(n)是機(jī)器人當(dāng)前所在節(jié)點(diǎn)到節(jié)點(diǎn)n的最短距離，H(n)是節(jié)點(diǎn)n到終點(diǎn)的預(yù)估距離。G(n)的計(jì)算只需在搜索隊(duì)列中選取權(quán)值最小的即可得出。而對(duì)于H(n)由于是目標(biāo)節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的距離，這個(gè)值機(jī)器人并不知道，需要加以估計(jì)，預(yù)測(cè)。這里要強(qiáng)調(diào)的是，在計(jì)算H(n)時(shí)，要選取曼哈頓距離來度量其大小。因?yàn)槿绻?jiǎn)單的選取歐氏距離又可能會(huì)途徑障礙，這與機(jī)器人實(shí)際運(yùn)行軌跡不符，會(huì)顯著增加預(yù)估值F(n)。圖3-9不同距離度量方式如圖3-9所示，圖中兩節(jié)點(diǎn)之間通過線段直接連接的綠線是兩節(jié)點(diǎn)之間的歐氏距離。紅線、黃線或藍(lán)線這三條并不直接通過兩節(jié)點(diǎn)之間做直線連接的線表征了曼哈頓距離，用這種方法計(jì)量預(yù)估距離可以避免遍歷地圖是預(yù)估的機(jī)器人行經(jīng)路線“橫跨”障礙物。如圖3-10所示為廣度優(yōu)先搜索算法，貪婪最佳優(yōu)先算法與A*算法的遍歷方式對(duì)比圖。圖3-10三種搜索方式對(duì)比其他算法神經(jīng)網(wǎng)絡(luò)方法神經(jīng)網(wǎng)絡(luò)（NeuralNetworks，NN），是一種模仿生物神經(jīng)元結(jié)構(gòu)和功能的數(shù)學(xué)模型，定義為一種模仿人類行為的能力REF_Ref30426\r\h[32]。模仿了人對(duì)問題的思維過程以及遇到問題解決方法。人工神經(jīng)網(wǎng)絡(luò)方法避障是統(tǒng)計(jì)學(xué)在智能領(lǐng)域的實(shí)際應(yīng)用，它的基本要求是確保系統(tǒng)能夠像人一樣執(zhí)行給定的任務(wù)，依據(jù)輸入與輸出間復(fù)雜的關(guān)系進(jìn)行訓(xùn)練建模。從工程的角度來看，它能夠提供并行計(jì)算的替代品。這一領(lǐng)域的研究是與許多相關(guān)科學(xué)領(lǐng)域結(jié)合而發(fā)展的。神經(jīng)網(wǎng)絡(luò)的基本架構(gòu)如圖3-11所示。圖3-SEQ表\*ARABIC11神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)從圖3-11，可以了解神經(jīng)網(wǎng)絡(luò)的基本操作路線。網(wǎng)絡(luò)層數(shù)因系統(tǒng)而異，一般來說，對(duì)于三層結(jié)構(gòu)，第1層是輸入層，第2層作為隱藏層，在第2層實(shí)現(xiàn)成員函數(shù)，而最后一層是輸出層REF_Ref31614\r\h[33]。應(yīng)用到機(jī)器人領(lǐng)域，神經(jīng)網(wǎng)絡(luò)方法會(huì)把機(jī)器人從起始點(diǎn)到目標(biāo)點(diǎn)所有行經(jīng)路線加以建模，通過對(duì)上一時(shí)刻機(jī)器人的位置，運(yùn)動(dòng)姿態(tài)以及周圍的障礙信息的建模，得出機(jī)器人應(yīng)該進(jìn)行的下一步包括速度，方向在內(nèi)的的運(yùn)動(dòng)姿態(tài)。不斷前行的過程就是不斷建模輸出的過程。這對(duì)機(jī)器人的運(yùn)算能力提出較高的要求。但在硬件設(shè)施不斷升級(jí)換代的今天，這已不成限制因素。神經(jīng)網(wǎng)絡(luò)方法適用領(lǐng)域更廣的避障場(chǎng)景是針對(duì)動(dòng)態(tài)環(huán)境的障礙。動(dòng)態(tài)障礙環(huán)境中，可以建立基于動(dòng)態(tài)神經(jīng)網(wǎng)絡(luò)的避障算法，動(dòng)態(tài)神經(jīng)網(wǎng)絡(luò)在機(jī)器人所處障礙環(huán)境復(fù)雜度高時(shí)優(yōu)勢(shì)會(huì)更為顯著且可以調(diào)整算法的結(jié)構(gòu)層級(jí)，實(shí)時(shí)地改變機(jī)器人當(dāng)前所處障礙環(huán)境狀態(tài)與其下一步進(jìn)行避障動(dòng)作之間的映射關(guān)系，這種方法較其他算法可以顯著減輕機(jī)器人的運(yùn)算壓力REF_