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

1、遺傳算法與機(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ī)器人在工作過(guò)程中能夠避開(kāi)障礙物從初始位置行走到目標(biāo)位置的路徑優(yōu)化過(guò)程。遺傳算法是一種應(yīng)用較多的路徑規(guī)劃方法,利用地圖中的信息進(jìn)行路徑規(guī)劃,實(shí)際應(yīng)用中效率比較高。關(guān)鍵詞:路徑規(guī)劃;移動(dòng)機(jī)器人;避障;遺傳算法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機(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)境是未知或部分未知的,即障礙物的尺寸、形狀和位置等信息必須

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

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

7、于神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)構(gòu)造出來(lái)能量函數(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ī)劃問(wèn)題的求解質(zhì)量和求解效率,研究者在其基礎(chǔ)上進(jìn)行改進(jìn)。機(jī)器人路徑規(guī)劃算法的方法很多,除了上面介紹的常見(jiàn)的路徑規(guī)劃方法外,還有基于蟻群算法的路徑規(guī)劃,基于微粒群算法的路徑規(guī)劃,結(jié)合模擬退火算法的遺傳算法等。前面對(duì)路徑規(guī)劃的方法做了整體的介紹,下面則要講解的具體的算法:遺傳算法在路徑規(guī)劃中的應(yīng)用。2基

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

9、條件考慮的:(1機(jī)器人被看做是一個(gè)點(diǎn);(2障礙物的尺寸都向外擴(kuò)展半個(gè)機(jī)器人半徑。如圖2.1所示 圖2.1 路徑規(guī)劃環(huán)境模型圖在機(jī)器人的工作環(huán)境圖中可以看到,機(jī)器人的運(yùn)動(dòng)軌跡由若干直線段構(gòu)成,每段直線段是機(jī)器人運(yùn)動(dòng)的基本單位。機(jī)器人到達(dá)目標(biāo)點(diǎn)的整個(gè)路徑可表示成:其中L i 是第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è)滿足條件

10、路徑。群體初始化往往是隨即產(chǎn)生的,這里所講的兩種遺傳算法都是隨即生產(chǎn)從出發(fā)點(diǎn)到目標(biāo)點(diǎn)的任意一條可行路徑集合作為初始群體。例如在第一個(gè)遺傳算法應(yīng)用中采用均勻分布的方法進(jìn)行群體初始化。規(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ù)。 (2M 是障礙物的個(gè)數(shù),i 是第i 段直線與第j 個(gè)障礙物的排斥度。定義為:121.-+=n l l l T i i i OP l

11、 -=+1n OPOP T =21,-=-=+=112111(N i i N i i K a a T F =M j ij i 0(3共3 項(xiàng)分別對(duì)應(yīng):直線段與障礙物相交時(shí);直線段距離障礙物d o d s ; 直線段遠(yuǎn)離障礙物 d o > ds 。其中為使直線段不與障礙物相交所要移動(dòng)的最短距離,d o 為直線段到障礙物的距離,稱d s 為安全距離,當(dāng) d o d s 后,算法將不再試圖使路徑進(jìn)一步遠(yuǎn)離障礙物,稱該線段和障礙物無(wú)排斥。給出適應(yīng)度函數(shù)后,在后面的運(yùn)行過(guò)程中,算法試圖使適應(yīng)度函數(shù)最小化并認(rèn)為使得該函數(shù)取得較小值的解為較優(yōu)解。交叉算子交叉操作對(duì)兩個(gè)對(duì)象操作,對(duì)對(duì)象進(jìn)行隨即分割,然后

12、重組得到兩個(gè)新的個(gè)體。交叉根據(jù)分割點(diǎn)的數(shù)量分為單點(diǎn)交叉和多點(diǎn)交叉,單點(diǎn)交叉是多點(diǎn)交叉的一種特殊形式?；镜牟僮魅缦聢D2.2所示: 圖2.2 多點(diǎn)交叉操作在圖中,父染色體被隨機(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。為

13、1時(shí)第i+1點(diǎn)前段直線與障礙物不相交后一段相交,-1的時(shí)候相反,為0的時(shí)候說(shuō)明前后段的情況相同。這里選擇分割點(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è)體, 選擇過(guò)程恰好相反, 選擇 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 +-+=02(12s o o s s ij d d

14、d d d (=10i l f (ii i l f l f g -=+135(3520205526421N clen clen clen clen crossnm <<<<= 變異算子變異過(guò)程中,個(gè)體中的分量以很小的概率或步長(zhǎng)產(chǎn)生轉(zhuǎn)移。 對(duì)于給定路徑, 該操作對(duì)路徑上的各路點(diǎn)pi 以一定的概率改變其坐標(biāo)。標(biāo)準(zhǔn)變異對(duì)地圖中的信息并沒(méi)有加以利用,變異是隨機(jī)的搜索,常常導(dǎo)致路徑劣化。而改進(jìn)型變異算子優(yōu)先選取和障礙物相交的線段的端點(diǎn)進(jìn)行變異,同時(shí)限制變異所得的路點(diǎn)坐標(biāo)在障礙物之外, 并且使變異所得的路點(diǎn)新坐標(biāo)滿足:new i i new i OP l -=+111-=i i n

15、ew i OP OP l new (7(i i new i new i l f l f l f l f +-11 通過(guò)這樣的約束條件保證了每次變異對(duì)路徑優(yōu)化的非負(fù)效果。 插入算子該算子在其所作用路徑上增加路點(diǎn)?？紤]路徑上某一直線段與障礙物相交,并且有端點(diǎn)坐標(biāo)Pi 處于障礙物外部空間。于是通過(guò)在Pi 與Pi+1之間插入合適的端點(diǎn) ,一定可以得到不與障礙物相交。同理,對(duì)于Pi+1處于障礙物外部空間時(shí),一定可以有 不與障礙物相交。對(duì)于Pi 與Pi+1均位于障礙物內(nèi)部的情況,該算子將隨機(jī)生成坐標(biāo)值,滿足 位于所有障礙物的外部空間。 刪除算子該算子在所操作路徑上記錄所有位于障礙物內(nèi)部空間的路點(diǎn),隨機(jī)選擇

16、其中之一并予以刪除。對(duì)于不和障礙物相交的路徑,該算子則在其全體路點(diǎn)中隨機(jī)選擇刪除點(diǎn)。 3 仿真結(jié)果與總結(jié)3.1 仿真結(jié)果 圖3.1 算法輸出結(jié)果1其代價(jià)函數(shù)值為 109.9561,路徑全長(zhǎng) 109.9561.i i i OP OP l -=+1P new i 1+newi i new i OP OP l 111+-=P newi 1+表 2 平均代價(jià)對(duì)比 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.

17、2485 表 3 標(biāo)準(zhǔn)差對(duì)比 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í)驗(yàn)數(shù)據(jù)證明了本文所提出的改進(jìn)型遺傳算法的有效性。在 3 幅不同的地圖上都達(dá)到了 90% 以上的算法成功率，并且相對(duì)其它算法有明顯提高。隨著地圖的不同，各算法的成功率均出現(xiàn)不同程度波 動(dòng)，但改進(jìn)型遺傳算法波動(dòng)幅度最小，保持了較好的穩(wěn)定性，體現(xiàn)出良好的地圖適應(yīng)能力。 3.2 總結(jié) 本文講述了遺傳算法如何規(guī)劃路徑的過(guò)程。這

18、種遺傳算法能使機(jī)器人在復(fù)雜的環(huán)境中優(yōu)化出一條合適 的路徑。本文中的遺傳算法基于坐標(biāo)值對(duì)染色體編碼，很好的利用了地圖中的信息，提高了算法的收斂速 度。但是這種算法的不足之處是參數(shù)不能隨工作過(guò)程而自動(dòng)調(diào)整，這是有待改進(jìn)的地方。 致謝 感謝陳萬(wàn)米老師的指導(dǎo)，在此表示感謝！ 參考文獻(xiàn)： 1 2 3 4 Ayala-Ramirez V,Perez-Garcia A,Montecillo-Puente F J,et al. Path planning using genetic algorithms for mini-robotic tasksC.Hague Netherlands: IEEE SMC'200