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

1、遺傳算法與機器人路徑規(guī)劃摘要:機器人的路徑規(guī)劃是機器人學(xué)的一個重要研究領(lǐng)域,是人工智能和機器人學(xué)的一個結(jié)合點。對于移動機器人而言,在其工作時要求按一定的規(guī)則,例如時間最優(yōu),在工作空間中尋找到一條最優(yōu)的路徑運動。機器人路徑規(guī)劃可以建模成在一定的約束條件下,機器人在工作過程中能夠避開障礙物從初始位置行走到目標(biāo)位置的路徑優(yōu)化過程。遺傳算法是一種應(yīng)用較多的路徑規(guī)劃方法,利用地圖中的信息進行路徑規(guī)劃,實際應(yīng)用中效率比較高。關(guān)鍵詞:路徑規(guī)劃;移動機器人;避障;遺傳算法Genetic Algorithm and Robot Path PlanningAbstract: Robot path planning

2、 research is a very important area of robotics, it is also a combine point of artificial intelligence and robotics. For the mobile robot, it need to be worked by certain rulers(e.g time optimal,and find a best movement path in work space. Robot path planning can be modeled that in the course of robo

3、ts able to avoid the obstacles from the initial position to the target location,and it ruquire to work under ertain constraints. Genetic algorithm used in path planning is very common, when planning the path ,it use the information of map ,and have high eficient in actual.Key words: Path planning,mo

4、bile robot, avoid the obstacles, genetic algorithm1路徑規(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)境是未知或部分未知的,即障礙物的尺寸、形狀和位置等信息必須

5、通過傳感器獲取。1.2路徑規(guī)劃步驟無論機器人路徑規(guī)劃屬于哪種類別,采用何種規(guī)劃算法,基本上都要遵循以下步驟:1, 建立環(huán)境模型,即將現(xiàn)實世界的問題進行抽象后建立相關(guān)的模型;2, 路徑搜索方法,即尋找合乎條件的路徑的算法。1.3路徑規(guī)劃方法1.3.1傳統(tǒng)路徑規(guī)劃方法(1自由空間法(free space approach基于簡化問題的思想, 采用“結(jié)構(gòu)空間” 來描述機器人及其周圍的環(huán)境。這種方法將機器人縮小成點,將其周圍的障礙物及邊界按比例相應(yīng)地擴大,使機器人點能夠在障礙物空間中移動到任意一點,而不與障礙物及邊界發(fā)生碰撞。(2圖搜索法采用預(yù)先定義的幾何形狀構(gòu)造自由空間,并將其表示為連通圖,然后通過

6、搜索連通圖進行路徑規(guī)劃。這種方法比較靈活,改變初始位置和目標(biāo)位置不會重構(gòu)連通圖,但是障礙物比較多時,算法會比較復(fù)雜,且不一定能找到最短路徑。(3人工勢場法(artificial potential field既是把機器人工作環(huán)境模擬成一種力場。目標(biāo)點對機器人產(chǎn)生引力,障礙物對機器人產(chǎn)生斥力,通過求合力來求控制機器人的運動。1.3.2 智能路徑規(guī)劃方法(1基于模糊邏輯算法(fuzzy logic algorithm的機器人路徑規(guī)劃此方法基于傳感器的實時信息,參考人的的經(jīng)驗,通過查表獲得規(guī)劃信息,實現(xiàn)局部路徑規(guī)劃。通過把約束和目標(biāo)模糊化,利用隸屬度函數(shù)尋找使各種條件達(dá)到滿意的程度,在模糊意義下求解

7、最優(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ī)劃遺傳算法運算進化代數(shù)眾多,占據(jù)較大的存儲空間和運算時間,本身所存在的一些缺陷(如解的早熟現(xiàn)象、局部尋優(yōu)能力差等,保證不了對路徑規(guī)劃的計算效率和可靠性的要求。為提高路徑規(guī)劃問題的求解質(zhì)量和求解效率,研究者在其基礎(chǔ)上進行改進。機器人路徑規(guī)劃算法的方法很多,除了上面介紹的常見的路徑規(guī)劃方法外,還有基于蟻群算法的路徑規(guī)劃,基于微粒群算法的路徑規(guī)劃,結(jié)合模擬退火算法的遺傳算法等。前面對路徑規(guī)劃的方法做了整體的介紹,下面

8、則要講解的具體的算法:遺傳算法在路徑規(guī)劃中的應(yīng)用。2基于遺傳算法的機器人路徑規(guī)劃2.1遺傳算法相關(guān)知識遺傳算法(GA由美國Miehigan大學(xué)的JohnHolland等在20世紀(jì)60年代末期到70年代初期研究形成的一個較完整的理論方法,從試圖解釋自然系統(tǒng)中生物的復(fù)雜適應(yīng)過程入手,模擬生物進化的機制來構(gòu)造人工系統(tǒng)的模型。遺傳算法包括三個基本操作:選擇,交叉和變異。2.2路徑規(guī)劃的具體步驟利用遺傳算法進行路徑規(guī)劃時,一般包含:環(huán)境建模,編碼,群體初始化,確定適應(yīng)度函數(shù)(fitness function,遺傳操作。2.2.1環(huán)境建模所謂建模是指建立合理的數(shù)學(xué)模型來描述機器人的工作環(huán)境.本次涉及的機器

9、人工作環(huán)境都是障礙物已知的二維空間。本文中遺傳算法應(yīng)用的環(huán)境都是基于下面條件考慮的:(1機器人被看做是一個點;(2障礙物的尺寸都向外擴展半個機器人半徑。如圖2.1所示 圖2.1 路徑規(guī)劃環(huán)境模型圖Fig.2.1 Path planning environment model diagram2.2.2編碼在機器人的工作環(huán)境圖中可以看到,機器人的運動軌跡由若干直線段構(gòu)成,每段直線段是機器人運動的基本單位。機器人到達(dá)目標(biāo)點的整個路徑可表示成:其中L i 是第i 段直線段的矢量表示,它的兩個端點分別可以表示為Pi 和Pi+1,符號“+”表示矢量的運算?？梢砸設(shè) 表示原點,于是于是整個機器人的運動路徑可

10、以表示為如下的路點矢量集合:設(shè)Pi 的坐標(biāo)點可以表示為(xi ,yi ,那么在算法實現(xiàn)時,路徑就可以以坐標(biāo)點形式儲存。這樣就完成了對染色體的編碼,所有的路徑T 是可能的一個滿足條件路徑。2.2.3 群體初始化群體初始化往往是隨即產(chǎn)生的,這里所講的兩種遺傳算法都是隨即生產(chǎn)從出發(fā)點到目標(biāo)點的任意一條可行路徑集合作為初始群體。例如在第一個遺傳算法應(yīng)用中采用均勻分布的方法進行群體初始化。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)漸小的方向進化。該函數(shù)的構(gòu)造如下:(1在函數(shù)中a1,a

11、2是權(quán)重系數(shù),分別強化了不同指標(biāo)的重要性。第一項表示路徑的總長度,第二項是障礙物的排斥函數(shù)。 (2M 是障礙物的個數(shù),i 是第i 段直線與第j 個障礙物的排斥度。定義為:121.-+=n l l l T i i i OP l -=+1n OPOP T =21,-=-=+=112111(N i i N i i K a a T F =M j ij i 0(3共3 項分別對應(yīng):直線段與障礙物相交時;直線段距離障礙物d o d s ; 直線段遠(yuǎn)離障礙物 d o > ds 。其中為使直線段不與障礙物相交所要移動的最短距離,d o 為直線段到障礙物的距離,稱d s 為安全距離,當(dāng) d o d s 后

12、,算法將不再試圖使路徑進一步遠(yuǎn)離障礙物,稱該線段和障礙物無排斥。給出適應(yīng)度函數(shù)后,在后面的運行過程中,算法試圖使適應(yīng)度函數(shù)最小化并認(rèn)為使得該函數(shù)取得較小值的解為較優(yōu)解。2.2.5 遺傳操作交叉算子交叉操作對兩個對象操作,對對象進行隨即分割,然后重組得到兩個新的個體。交叉根據(jù)分割點的數(shù)量分為單點交叉和多點交叉,單點交叉是多點交叉的一種特殊形式?；镜牟僮魅缦聢D2.2所示: 圖2.2 多點交叉操作Fig.2.2 Multi-point crossover operation在圖中,父染色體被隨機四個分割點分為五部分,標(biāo)有箭頭的部分互換。這樣完成交叉操作后產(chǎn)生兩條子染色體基本的交叉操作產(chǎn)生的子代染色

13、體的長度可能不等,結(jié)果是,對應(yīng)的適應(yīng)度函數(shù)也發(fā)生變化。對交叉算子的改進是使為了獲得更低函數(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號父個體, 選擇過程恰好相反,

14、 選擇 gi 為 -1時對應(yīng)的變化點作為2號父個體的第一分割點, 選擇緊隨該點之后使得gi 為1的變化點作為第 2 分割點。更多的分割點同理可得。除此之外還要考慮交叉點數(shù)的選取,前面的交叉操作會使最后的染色體很短,所以后續(xù)的操作要設(shè)定染色體的長度,設(shè)定標(biāo)準(zhǔn)如下。 (6 +-+=02(12s o o s s ij d d d d d (=10i l f (ii i l f l f g -=+135(3520205526421N clen clen clen clen crossnm <<<<= 變異算子變異過程中,個體中的分量以很小的概率或步長產(chǎn)生轉(zhuǎn)移。 對于給定路徑,

15、該操作對路徑上的各路點pi 以一定的概率改變其坐標(biāo)。標(biāo)準(zhǔn)變異對地圖中的信息并沒有加以利用,變異是隨機的搜索,常常導(dǎo)致路徑劣化。而改進型變異算子優(yōu)先選取和障礙物相交的線段的端點進行變異,同時限制變異所得的路點坐標(biāo)在障礙物之外, 并且使變異所得的路點新坐標(biāo)滿足:new i i new i OP l -=+111-=i i new i OP OP l new (7(i i new i new i l f l f l f l f +-11 通過這樣的約束條件保證了每次變異對路徑優(yōu)化的非負(fù)效果。 插入算子該算子在其所作用路徑上增加路點?？紤]路徑上某一直線段與障礙物相交,并且有端點坐標(biāo)Pi 處于障礙物外部

16、空間。于是通過在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.1 Algorithm output 1其代價函數(shù)值為 109.9561,路徑全長 109.9561.i i i OP

17、OP l -=+1P new i 1+newi i new i OP OP l 111+-=P newi 1+圖 3.2 算法輸出結(jié)果 2 Fig.3.2 Algorithm output 2 其代價函數(shù)值為 80.0835，路徑全長 80.0835. 圖 3.3 算法輸出結(jié)果 3 Fig.3.3 Algorithm output 3 其代價函數(shù)值為 76.1412，路徑全長 76.1412. 在上面三個仿真圖中，適應(yīng)度函數(shù)的值和路徑值是一樣的。上面的仿真的群體規(guī)模都是 100，進化 50 次，染色體變異概率 0.3，權(quán)重系數(shù) a1，a2 分別是 1，1000。 算法比較 表 1 成功率對比

18、Tab.1 地圖 1 算法 1 算法 2 算法 3 57 72 100 Success rate comparison 地圖 2 41 59 99 地圖 3 0 0 92 -6- 表 2 平均代價對比 Tab.2 地圖 1 算法 1 算法 2 算法 3 113.2342 111.3242 109.6178 Average price comparison 地圖 2 82.5809 81.1283 82.6478 地圖 3 NA NA 78.2485 表 3 標(biāo)準(zhǔn)差對比 Tab.3 算法 1 算法 2 算法 3 Standard deviation comparison 地圖 2 1.4494 1.4548 3.1837 地圖 3 NA NA 10.6819 地圖 1 4.1471 7.5603 5.6721 上述的實驗數(shù)據(jù)證明了本文所提出的改進型遺傳算法的有效性。在 3 幅不同的地圖上都達(dá)到了 90% 以上的算法成功率，并且相對其它算法有明顯提高。隨著地圖的不同，各算法的成功率均出現(xiàn)不同程度波 動，但改進型遺傳算法波動幅度最小，保持了較好的穩(wěn)定性，體現(xiàn)出良好的地圖適應(yīng)