遺傳算法與機(jī)器人路徑規(guī)劃

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