移動(dòng)機(jī)器人避障路徑規(guī)劃算法的研究.pdf

《移動(dòng)機(jī)器人避障路徑規(guī)劃算法的研究.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、機(jī)器人技術(shù)中文核心期刊《微計(jì)算機(jī)信息》(嵌入式與SOC)2008年第24卷第2-2期文章編號(hào):1008-0570(2008)02-2-0212-02移動(dòng)機(jī)器人避障路徑規(guī)劃算法的研究Path-planningAlgorithmResearchofRobots(南京工業(yè)大學(xué))張帆周慶敏ZHANGFANZHOUQINGMIN摘要:避障路徑規(guī)劃問(wèn)題是在障礙物環(huán)境中,在滿足與障礙物不相碰撞的前提條件下,規(guī)劃一條從起點(diǎn)到達(dá)終點(diǎn)的路徑。在此過(guò)程中,往往符合條件的路徑不止一條,如何在其中找到最短路徑則是我們關(guān)心的問(wèn)題。本文以構(gòu)建障礙物模型為基礎(chǔ),將路徑規(guī)劃問(wèn)題轉(zhuǎn)化為求解一條經(jīng)過(guò)起點(diǎn)和終點(diǎn)的最短

2、路徑,并在此基礎(chǔ)上構(gòu)建了算法程序。通過(guò)計(jì)算機(jī)仿真表明該方法具備良好的路徑規(guī)劃能力。關(guān)鍵詞:路徑規(guī)劃;機(jī)器人;避障中圖分類(lèi)號(hào):TP391文獻(xiàn)標(biāo)識(shí)碼:AAbstract:Avoidanceobstaclepathplanningproblemisthatinobstacleenvironment,fromstartpointtodestinationpoint,researchacollisionfreepath.Thiskindofpathmaybeplenty,butthispaperfocusestofindtheshortestlengthofpath.Aprogramfo

3、rsearch-ingtheshortestlengthofpathispresented.Computersimulationexperimentshowsthat,themethodhasgoodpathplanningability.技Keywords:pathplanning,robots,avoidanceobstacle術(shù)表示為Distance(v[i],v[j])(簡(jiǎn)記為d[i][j])。定義cost[Obj_point]1引言[Obj_point]為圖G的可視圖矩陣,cost[i][j]=d([i][j])。創(chuàng)路徑規(guī)劃是移動(dòng)機(jī)器人導(dǎo)航的最基本環(huán)節(jié)之一,機(jī)器人路3

4、構(gòu)造可視圖矩陣徑規(guī)劃是針對(duì)某個(gè)特定的問(wèn)題狀態(tài)出發(fā),尋求一系列行為動(dòng)作,新并建立一個(gè)操作集合,該集合具有時(shí)間上的序列關(guān)系直到目標(biāo)頂點(diǎn)與頂點(diǎn)之間有兩類(lèi)關(guān)系,一類(lèi)是同一障礙物的頂點(diǎn)間狀態(tài)為止。路徑規(guī)劃的核心算法就是最短路徑算法,它是計(jì)算機(jī)關(guān)系,一類(lèi)是不同障礙物的頂點(diǎn)間關(guān)系。這兩類(lèi)關(guān)系都可以通科學(xué)與地理信息科學(xué)等領(lǐng)域研究的熱點(diǎn)。最短路徑算法有很多,過(guò)判斷由頂點(diǎn)v[i],v[j]構(gòu)成的路徑與障礙物多邊形Object[k](k=包括圖論基本方法、啟發(fā)式搜索方法、動(dòng)態(tài)規(guī)劃方法、神經(jīng)網(wǎng)絡(luò)1,2,3?)是否相交來(lái)解決。方法等。路徑規(guī)劃是移動(dòng)機(jī)器人導(dǎo)航技術(shù)中不可缺少的重要組下面分兩種情況計(jì)算cos

5、t.成部分,它反映了機(jī)器人在運(yùn)動(dòng)過(guò)程中與周?chē)h(huán)境的交互能力,1)頂點(diǎn)v[i]v[j]∈Object[k](k=1,2,3?),計(jì)算邊Distance(v[i],v是移動(dòng)機(jī)器人完成任務(wù)的基礎(chǔ)和安全保障。本文的研究目的在[j])可按下式計(jì)算(采用偽代碼表示)于從有障礙物的環(huán)境中,從起始點(diǎn)到目標(biāo)點(diǎn)之間規(guī)劃出一條與if(v[i],v[j]是同一障礙物的頂點(diǎn)){環(huán)境障礙物無(wú)碰的最短路徑。構(gòu)造出可視圖,在可視圖的基礎(chǔ)if(v[i],v[j]是相鄰頂點(diǎn))上規(guī)劃出從起始點(diǎn)至目標(biāo)點(diǎn)的最短避障路徑。Distance(v[i],v[j])=sqrt((v[i].x-v[j].x)2+(v[i].y-

6、v[j].y)2)(1)elseDistance(v[i],v[j])=∞//∞用計(jì)算機(jī)中能表示的最大數(shù)代替2基本定義}定義2.1設(shè)vi=(xi,yi)(i=1,2,?,m),v1=vm+1是平面R2上2)若頂點(diǎn)v[i]∈Object[k],v[j]∈Object[s](k≠s),則計(jì)算過(guò)程相構(gòu)成某多邊形Pi的m個(gè)頂點(diǎn),如果對(duì)任意i,j(i≠j),i,j=1,2,對(duì)復(fù)雜。倘若i,j兩點(diǎn)間無(wú)障礙物,可按(1)式計(jì)算,否則就要判?,m,線段vivi+1與vjvj+1或是相鄰且相交于一端點(diǎn)或不相斷v[i],v[j]兩點(diǎn)構(gòu)成的路徑v(i,j)與障礙物多邊形頂點(diǎn)v[a],v[a+1]交,

7、則稱(chēng)多邊形Pi為簡(jiǎn)單多邊形。簡(jiǎn)單多邊形集合記為P=組成的邊界v(a,a+1)是否相交,根據(jù)相交結(jié)果來(lái)計(jì)算Distance(vi,{Pi

8、i=1,2,?K},K為簡(jiǎn)單多邊形的個(gè)數(shù);簡(jiǎn)單多邊形Pi可表vj)的值。這里v[a],v[a+1]∈Object[l](l=1,2,?,a=1,2,?)。倘若相示為Pi={vj

9、j=1,2,?,m}。交,則將相應(yīng)值置為∞。定義2.2障礙物多邊形用Object[i]表示,i=1,2,3?且當(dāng)且判斷路徑v(i,j)和邊界v(a,a+1)有無(wú)交點(diǎn),可以計(jì)算由v(i