資源描述：
《移動機器人避障路徑規(guī)劃算法的研究.pdf》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、機器人技術(shù)中文核心期刊《微計算機信息》(嵌入式與SOC)2008年第24卷第2-2期文章編號:1008-0570(2008)02-2-0212-02移動機器人避障路徑規(guī)劃算法的研究Path-planningAlgorithmResearchofRobots(南京工業(yè)大學(xué))張帆周慶敏ZHANGFANZHOUQINGMIN摘要:避障路徑規(guī)劃問題是在障礙物環(huán)境中,在滿足與障礙物不相碰撞的前提條件下,規(guī)劃一條從起點到達終點的路徑。在此過程中,往往符合條件的路徑不止一條,如何在其中找到最短路徑則是我們關(guān)心的問題。本文以構(gòu)建障礙物模型為基礎(chǔ),將路徑規(guī)劃問題轉(zhuǎn)化為求解一條經(jīng)過起點和終點的最短
2、路徑,并在此基礎(chǔ)上構(gòu)建了算法程序。通過計算機仿真表明該方法具備良好的路徑規(guī)劃能力。關(guān)鍵詞:路徑規(guī)劃;機器人;避障中圖分類號:TP391文獻標(biāo)識碼:AAbstract:Avoidanceobstaclepathplanningproblemisthatinobstacleenvironment,fromstartpointtodestinationpoint,researchacollisionfreepath.Thiskindofpathmaybeplenty,butthispaperfocusestofindtheshortestlengthofpath.Aprogramfo
3、rsearch-ingtheshortestlengthofpathispresented.Computersimulationexperimentshowsthat,themethodhasgoodpathplanningability.技Keywords:pathplanning,robots,avoidanceobstacle術(shù)表示為Distance(v[i],v[j])(簡記為d[i][j])。定義cost[Obj_point]1引言[Obj_point]為圖G的可視圖矩陣,cost[i][j]=d([i][j])。創(chuàng)路徑規(guī)劃是移動機器人導(dǎo)航的最基本環(huán)節(jié)之一,機器人路3
4、構(gòu)造可視圖矩陣徑規(guī)劃是針對某個特定的問題狀態(tài)出發(fā),尋求一系列行為動作,新并建立一個操作集合,該集合具有時間上的序列關(guān)系直到目標(biāo)頂點與頂點之間有兩類關(guān)系,一類是同一障礙物的頂點間狀態(tài)為止。路徑規(guī)劃的核心算法就是最短路徑算法,它是計算機關(guān)系,一類是不同障礙物的頂點間關(guān)系。這兩類關(guān)系都可以通科學(xué)與地理信息科學(xué)等領(lǐng)域研究的熱點。最短路徑算法有很多,過判斷由頂點v[i],v[j]構(gòu)成的路徑與障礙物多邊形Object[k](k=包括圖論基本方法、啟發(fā)式搜索方法、動態(tài)規(guī)劃方法、神經(jīng)網(wǎng)絡(luò)1,2,3?)是否相交來解決。方法等。路徑規(guī)劃是移動機器人導(dǎo)航技術(shù)中不可缺少的重要組下面分兩種情況計算cos
5、t.成部分,它反映了機器人在運動過程中與周圍環(huán)境的交互能力,1)頂點v[i]v[j]∈Object[k](k=1,2,3?),計算邊Distance(v[i],v是移動機器人完成任務(wù)的基礎(chǔ)和安全保障。本文的研究目的在[j])可按下式計算(采用偽代碼表示)于從有障礙物的環(huán)境中,從起始點到目標(biāo)點之間規(guī)劃出一條與if(v[i],v[j]是同一障礙物的頂點){環(huán)境障礙物無碰的最短路徑。構(gòu)造出可視圖,在可視圖的基礎(chǔ)if(v[i],v[j]是相鄰頂點)上規(guī)劃出從起始點至目標(biāo)點的最短避障路徑。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])=∞//∞用計算機中能表示的最大數(shù)代替2基本定義}定義2.1設(shè)vi=(xi,yi)(i=1,2,?,m),v1=vm+1是平面R2上2)若頂點v[i]∈Object[k],v[j]∈Object[s](k≠s),則計算過程相構(gòu)成某多邊形Pi的m個頂點,如果對任意i,j(i≠j),i,j=1,2,對復(fù)雜。倘若i,j兩點間無障礙物,可按(1)式計算,否則就要判?,m,線段vivi+1與vjvj+1或是相鄰且相交于一端點或不相斷v[i],v[j]兩點構(gòu)成的路徑v(i,j)與障礙物多邊形頂點v[a],v[a+1]交,
7、則稱多邊形Pi為簡單多邊形。簡單多邊形集合記為P=組成的邊界v(a,a+1)是否相交,根據(jù)相交結(jié)果來計算Distance(vi,{Pi
8、i=1,2,?K},K為簡單多邊形的個數(shù);簡單多邊形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)有無交點,可以計算由v(i
