遺傳算法與機器人路徑規(guī)劃摘要：機器人的路徑規(guī)劃是機器人學(xué)的一個重要研究領(lǐng)域，是人工智能和機器人學(xué)的一個結(jié)合點。對于移動機器人而言，在其工作時要求按一定的規(guī)則，例如時間最優(yōu)，在工作空間中尋找到一條最優(yōu)的路徑運動。機器人路徑規(guī)劃可以建模成在一定的約束條件下，機器人在工作過程中能夠避開障礙物從初始位置行走到目標(biāo)位置的路徑優(yōu)化過程。遺傳算法是一種應(yīng)用較多的路徑規(guī)劃方法，利用地圖中的信息進(jìn)行路徑規(guī)劃，實際應(yīng)用中效率比較高。關(guān)鍵詞：路徑規(guī)劃；移動機器人；避障；遺傳算法GeneticAlgorithmandRobotPathPlanningAbstract:Robotpathplanningresearchisaveryimportantareaofrobotics,itisalsoacombinepointofartificialintelligenceandrobotics.Forthemobilerobot,itneedtobeworkedbycertainrulers（e.gtimeoptimal），andfindabestmovementpathinworkspace.Robotpathplanningcanbemodeledthatinthecourseofrobotsabletoavoidtheobstaclesfromtheinitialpositiontothetargetlocation,anditruquiretoworkunderertainconstraints.Geneticalgorithmusedinpathplanningisverycommon,whenplanningthepath,itusetheinformationofmap,andhavehigheficientinactual.Keywords:Pathplanning,mobilerobot,avoidtheobstacles,geneticalgorithm 路徑規(guī)劃1.1機器人路徑規(guī)劃分類（1）根據(jù)機器人對環(huán)境信息掌握的程度和障礙物的不同，移動機器人的路徑規(guī)劃基本上可分為以下幾類：1，已知環(huán)境下的對靜態(tài)障礙物的路徑規(guī)劃；2，未知環(huán)境下的對靜態(tài)障礙物的路徑規(guī)劃；3，已知環(huán)境下對動態(tài)障礙物的路徑規(guī)劃；4，未知環(huán)境下的對動態(tài)障礙物的路徑規(guī)劃。（2）也可根據(jù)對環(huán)境信息掌握的程度不同將移動機器人路徑規(guī)劃分為兩種類型：1，基于環(huán)境先驗完全信息的全局路徑規(guī)劃；2，基于傳感器信息的局部路徑規(guī)劃。（第二種中的環(huán)境是未知或部分未知的，即障礙物的尺寸、形狀和位置等信息必須通過傳感器獲取。）1.2路徑規(guī)劃步驟無論機器人路徑規(guī)劃屬于哪種類別，采用何種規(guī)劃算法，基本上都要遵循以下步驟：1,建立環(huán)境模型，即將現(xiàn)實世界的問題進(jìn)行抽象后建立相關(guān)的模型；2,路徑搜索方法，即尋找合乎條件的路徑的算法。路徑規(guī)劃方法1.3.1傳統(tǒng)路徑規(guī)劃方法（1）自由空間法（freespaceapproach）基于簡化問題的思想,采用“結(jié)構(gòu)空間”來描述機器人及其周圍的環(huán)境。這種方法將機器人縮小成點,將其周圍的障礙物及邊界按比例相應(yīng)地擴大,使機器人點能夠在障礙物空間中移動到任意一點,而不與障礙物及邊界發(fā)生碰撞。（2）圖搜索法采用預(yù)先定義的幾何形狀構(gòu)造自由空間，并將其表示為連通圖，然后通過搜索連通圖進(jìn)行路徑規(guī)劃。這種方法比較靈活，改變初始位置和目標(biāo)位置不會重構(gòu)連通圖，但是障礙物比較多時，算法會比較復(fù)雜，且不一定能找到最短路徑。（3）人工勢場法（artificialpotentialfield）既是把機器人工作環(huán)境模擬成一種力場。目標(biāo)點對機器人產(chǎn)生引力，障礙物對機器人產(chǎn)生斥力，通過求合力來求控制機器人的運動。1.3.2智能路徑規(guī)劃方法（1）基于模糊邏輯算法（fuzzylogicalgorithm）的機器人路徑規(guī)劃此方法基于傳感器的實時信息，參考人的的經(jīng)驗，通過查表獲得規(guī)劃信息，實現(xiàn)局部路徑規(guī)劃。通過把約束和目標(biāo)模糊化，利用隸屬度函數(shù)尋找使各種條件達(dá)到滿意的程度，在模糊意義下求解最優(yōu)解。（2）基于神經(jīng)網(wǎng)絡(luò)（NN）的機器人路徑規(guī)劃主要是基于神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)構(gòu)造出來能量函數(shù)，根據(jù)路徑點與障礙物位置的關(guān)系，選取動態(tài)運動方程，規(guī)劃出最短路徑。（3）基于遺傳算法（GA）的機器人路徑規(guī)劃遺傳算法運算進(jìn)化代數(shù)眾多，占據(jù)較大的存儲空間和運算時間，本身所存在的一些缺陷(如解的早熟現(xiàn)象、局部尋優(yōu)能力差等)，保證不了對路徑規(guī)劃的計算效率和可靠性的要求。為提高路徑規(guī)劃問題的求解質(zhì)量和求解效率，研究者在其基礎(chǔ)上進(jìn)行改進(jìn)。機器人路徑規(guī)劃算法的方法很多，除了上面介紹的常見的路徑規(guī)劃方法外，還有基于蟻群算法的路徑規(guī)劃，基于微粒群算法的路徑規(guī)劃，結(jié)合模擬退火算法的遺傳算法等。前面對路徑規(guī)劃的方法做了整體的介紹，下面則要講解的具體的算法：遺傳算法在路徑規(guī)劃中的應(yīng)用。2基于遺傳算法的機器人路徑規(guī)劃2.1遺傳算法相關(guān)知識遺傳算法(GA)由美國Miehigan大學(xué)的JohnHolland等在20世紀(jì)60年代末期到70年代初期研究形成的一個較完整的理論方法，從試圖解釋自然系統(tǒng)中生物的復(fù)雜適應(yīng)過程入手，模擬生物進(jìn)化的機制來構(gòu)造人工系統(tǒng)的模型。遺傳算法包括三個基本操作：選擇，交叉和變異。2.2路徑規(guī)劃的具體步驟利用遺傳算法進(jìn)行路徑規(guī)劃時，一般包含：環(huán)境建模，編碼，群體初始化，確定適應(yīng)度函數(shù)（fitnessfunction），遺傳操作。2.2.1環(huán)境建模所謂建模是指建立合理的數(shù)學(xué)模型來描述機器人的工作環(huán)境.本次涉及的機器人工作環(huán)境都是障礙物已知的二維空間。本文中遺傳算法應(yīng)用的環(huán)境都是基于下面條件考慮的：（1）機器人被看做是一個點；（2）障礙物的尺寸都向外擴展半個機器人半徑。如圖2.1所示圖2.1路徑規(guī)劃環(huán)境模型圖Fig.2.1Pathplanningenvironmentmodeldiagram2.2.2編碼在機器人的工作環(huán)境圖中可以看到，機器人的運動軌跡由若干直線段構(gòu)成，每段直線段是機器人運動的基本單位。機器人到達(dá)目標(biāo)點的整個路徑可表示成：其中Li是第i段直線段的矢量表示，它的兩個端點分別可以表示為Pi和Pi+1,符號“+”表示矢量的運算?？梢砸設(shè)表示原點，于是于是整個機器人的運動路徑可以表示為如下的路點矢量集合：設(shè)Pi的坐標(biāo)點可以表示為（xi，yi），那么在算法實現(xiàn)時，路徑就可以以坐標(biāo)點形式儲存。這樣就完成了對染色體的編碼，所有的路徑T是可能的一個滿足條件路徑。2.2.3群體初始化群體初始化往往是隨即產(chǎn)生的，這里所講的兩種遺傳算法都是隨即生產(chǎn)從出發(fā)點到目標(biāo)點的任意一條可行路徑集合作為初始群體。例如在第一個遺傳算法應(yīng)用中采用均勻分布的方法進(jìn)行群體初始化。2.2.4適應(yīng)度函數(shù)規(guī)劃出路徑的優(yōu)劣程度要有一個評價的標(biāo)準(zhǔn)。適應(yīng)度函數(shù)就是為了評價這個優(yōu)劣程度。在這個適應(yīng)度函數(shù)中以路徑長度和障礙物作為評價指標(biāo)，并使所求解向指標(biāo)漸小的方向進(jìn)化。該函數(shù)的構(gòu)造如下：(1)在函數(shù)中a1，a2是權(quán)重系數(shù)，分別強化了不同指標(biāo)的重要性。第一項表示路徑的總長度，第二項是障礙物的排斥函數(shù)。(2)M是障礙物的個數(shù)，βi是第i段直線與第j個障礙物的排斥度。定義為：(3)共3項分別對應(yīng):①直線段與障礙物相交時;②直線段距離障礙物do≤ds；③直線段遠(yuǎn)離障礙物do>ds。其中γ為使直線段不與障礙物相交所要移動的最短距離，do為直線段到障礙物的距離，稱ds為安全距離,當(dāng)do≥ds后,算法將不再試圖使路徑進(jìn)一步遠(yuǎn)離障礙物,稱該線段和障礙物無排斥。給出適應(yīng)度函數(shù)后，在后面的運行過程中，算法試圖使適應(yīng)度函數(shù)最小化并認(rèn)為使得該函數(shù)取得較小值的解為較優(yōu)解。2.2.5遺傳操作交叉算子交叉操作對兩個對象操作，對對象進(jìn)行隨即分割，然后重組得到兩個新的個體。交叉根據(jù)分割點的數(shù)量分為單點交叉和多點交叉，單點交叉是多點交叉的一種特殊形式?；镜牟僮魅缦聢D2.2所示：圖2.2多點交叉操作Fig.2.2Multi-pointcrossoveroperation在圖中，父染色體被隨機四個分割點分為五部分，標(biāo)有箭頭的部分互換。這樣完成交叉操作后產(chǎn)生兩條子染色體基本的交叉操作產(chǎn)生的子代染色體的長度可能不等，結(jié)果是，對應(yīng)的適應(yīng)度函數(shù)也發(fā)生變化。對交叉算子的改進(jìn)是使為了獲得更低函數(shù)值的適應(yīng)度函數(shù)。前面已經(jīng)給出路徑的表達(dá)式。這里給出一個線段的相交函數(shù)：（4）0表示第i段直線與所有的障礙物不相交，1表示第i段直線與障礙物相交。并定義如下路段與障礙物相交狀態(tài)變化函數(shù)：（5）gi可能的取值為：1，0，-1。為1時第i+1點前段直線與障礙物不相交后一段相交，-1的時候相反，為0的時候說明前后段的情況相同。這里選擇分割點的原則是：選擇gi為1時對應(yīng)的變化點作為1號父個體的第一分割點，選擇緊隨該點之后使得gi為-1的點作為第2分割點。對于2號父個體，選擇過程恰好相反，選擇gi為-1時對應(yīng)的變化點作為2號父個體的第一分割點，選擇緊隨該點之后使得gi為1的變化點作為第2分割點。更多的分割點同理可得。除此之外還要考慮交叉點數(shù)的選取，前面的交叉操作會使最后的染色體很短，所以后續(xù)的操作要設(shè)定染色體的長度，設(shè)定標(biāo)準(zhǔn)如下。（6）變異算子變異過程中，個體中的分量以很小的概率或步長產(chǎn)生轉(zhuǎn)移。對于給定路徑，該操作對路徑上的各路點pi以一定的概率改變其坐標(biāo)。標(biāo)準(zhǔn)變異對地圖中的信息并沒有加以利用，變異是隨機的搜索，常常導(dǎo)致路徑劣化。而改進(jìn)型變異算子優(yōu)先選取和障礙物相交的線段的端點進(jìn)行變異，同時限制變異所得的路點坐標(biāo)在障礙物之外，并且使變異所得的路點新坐標(biāo)滿足：（7）通過這樣的約束條件保證了每次變異對路徑優(yōu)化的非負(fù)效果。插入算子該算子在其所作用路徑上增加路點?？紤]路徑上某一直線段與障礙物相交，并且有端點坐標(biāo)Pi處于障礙物外部空間。于是通過在Pi與Pi+1之間插入合適的端點，一定可以得到不與障礙物相交。同理，對于Pi+1處于障礙物外部空間時，一定可以有不與障礙物相交。對于Pi與Pi+1均位于障礙物內(nèi)部的情況，該算子將隨機生成坐標(biāo)值，滿足位于所有障礙物的外部空間。刪除算子該算子在所操作路徑上記錄所有位于障礙物內(nèi)部空間的路點，隨機選擇其中之一并予以刪除。對于不和障礙物相交的路徑，該算子則在其全體路點中隨機選擇刪除點。3仿真結(jié)果與總結(jié)3.1仿真結(jié)果圖3.1算法輸出結(jié)果1Fig.3.1Algorithmoutput1其代價函數(shù)值為109.9561，路徑全長109.9561.圖3.2算法輸出結(jié)果2Fig.3.2Algorithmoutput2其代價函數(shù)值為80.0835，路徑全長80.0835.圖3.3算法輸出結(jié)果3Fig.3.3Algorithmoutput3其代價函數(shù)值為76.1412，路徑全長76.1412.在上面三個仿真圖中，適應(yīng)度函數(shù)的值和路徑值是一樣的。上面的仿真的群體規(guī)模都是100，進(jìn)化50次，染色體變異概率0.3，權(quán)重系數(shù)a1，a2分別是1，1000。算法比較表1成功率對比Tab.1Successratecomparison地圖1地圖2地圖3算法157410算法272590算法31009992表2平均代價對比Tab.2Averagepricecomparison地圖1地圖2地圖3算法1113.234282.5809NA算法2111.324281.1283NA算法3109.617882.647878.2485表3標(biāo)準(zhǔn)差對比Tab.3Standarddeviationcomparison地圖1地圖2地圖3算法14.14711.4494NA算法27.56031.4548NA算法35.67213.183710.6819上述的實驗數(shù)據(jù)證明了本文所提出的改進(jìn)型遺傳算法的有效性。在3幅不同的地圖上都達(dá)到了90%以上的算法成功率，并且相對其它算法有明顯提高。隨著地圖的不同，各算法的成功率均出現(xiàn)不同程度波動，但改進(jìn)型遺傳算法波動幅度最小，保持了較好的穩(wěn)定性，體現(xiàn)出良好的地圖適應(yīng)能力