移動(dòng)機(jī)器人完全遍歷系統(tǒng)研究_圖文

1、東南大學(xué)碩士學(xué)位論文移動(dòng)機(jī)器人完全遍歷系統(tǒng)研究姓名:劉奎申請(qǐng)學(xué)位級(jí)別:碩士專業(yè):機(jī)械電子工程指導(dǎo)教師:張赤斌20060306 3.2路徑規(guī)劃的分類路徑規(guī)劃的分類方式隨著標(biāo)準(zhǔn)的不同有很多分類方法。按移動(dòng)目標(biāo)主要有兩種路徑規(guī)劃,一種是傳統(tǒng)的點(diǎn)到點(diǎn)的路徑規(guī)劃,另一種就是完全遍歷路徑規(guī)劃。點(diǎn)到點(diǎn)的路徑規(guī)劃是一種從始點(diǎn)到終點(diǎn)的運(yùn)動(dòng)策略,它要求尋找一條從始點(diǎn)到終點(diǎn)的最優(yōu)(如代價(jià)最小、路徑最短、時(shí)間最少并且合理的路徑,使移動(dòng)機(jī)器人能夠在工作空間順利地通行而不碰到任何障礙物。完全遍歷路徑規(guī)劃是一種在二維工作空間中特殊的路徑規(guī)劃,指在滿足某種性能指標(biāo)最優(yōu)或準(zhǔn)優(yōu)的前提下,尋找一條在設(shè)定區(qū)域內(nèi)從始點(diǎn)到終點(diǎn)且經(jīng)過所有

2、可達(dá)點(diǎn)的連續(xù)路徑。圖3-1(a為傳統(tǒng)的點(diǎn)到點(diǎn)的路徑規(guī)劃,此路徑是一條從起點(diǎn)sN終點(diǎn)G的最短的避碰的路徑。(b為完全遍歷路徑規(guī)劃,此路徑是一條遍歷環(huán)境空間中所有可達(dá)點(diǎn)的路徑。 (a點(diǎn)到點(diǎn)路徑規(guī)劃(b完全遍歷路徑規(guī)劃圖31傳統(tǒng)路徑規(guī)劃和完全遍歷路徑規(guī)劃比較根據(jù)對(duì)環(huán)境信息掌握的程度和空間描述形式將機(jī)器人路徑規(guī)劃分成三類:基于環(huán)境先驗(yàn)完全信息的全局路徑規(guī)劃、基于傳感器信息的局部路徑規(guī)劃和混合型方法。全局規(guī)劃方法依照己獲取的環(huán)境信息,給機(jī)器人規(guī)劃出一條運(yùn)動(dòng)路徑。全局路徑的精確度取決于獲取環(huán)境信息的準(zhǔn)確程度。全局方法通常以尋找最優(yōu)解,但需要預(yù)先知道環(huán)境準(zhǔn)確的信息,并且計(jì)算量通常很大。局部規(guī)劃方法側(cè)重考慮機(jī)

3、器人當(dāng)前局部環(huán)境信息,通過多種傳感器獲取位置或部分未知的環(huán)境信息,即障礙物的尺寸、形狀和位置等信息,使機(jī)器人具有良好的避碰能力。和全局規(guī)劃方法相比,更具實(shí)時(shí)性和實(shí)用性。缺陷是僅依靠局部信息,有時(shí)會(huì)產(chǎn)生局部極點(diǎn),無法保證機(jī)器人能順利地到達(dá)目標(biāo)點(diǎn)。混合型方法結(jié)合全局和局部方法的優(yōu)點(diǎn),將全局規(guī)劃的“粗”路徑作為局部規(guī)劃的子目標(biāo),特別在復(fù)雜環(huán)境中此方法經(jīng)常被使用?？偟膩碚f,全局路徑規(guī)劃基于環(huán)境模型,環(huán)境的全部信息已知;局部路徑規(guī)劃基于傳感器的信息,環(huán)境信息全部未知或部分未知。局部路徑規(guī)劃和全局路徑規(guī)劃并沒有本質(zhì)區(qū)別。前者只是把全局路徑規(guī)劃的環(huán)境考慮得更復(fù)雜一些,即環(huán)境是動(dòng)態(tài)的。很多適用于全局路徑規(guī)劃的

4、方法經(jīng)過改進(jìn)都可以用于局部路徑規(guī)劃;而適用于局部路徑規(guī)劃的方法都可以適用于全局路徑規(guī)劃。3.3幾種典型路徑規(guī)劃移動(dòng)機(jī)器人路徑規(guī)劃研究起始于20世紀(jì)70年代,目前對(duì)這一問題的研究仍十分活躍,許多學(xué)者做了大量的工作,提出了許多成熟的路徑規(guī)劃算法。根據(jù)空間描述形式的不同,從全局路徑規(guī)劃和局部路徑規(guī)劃來劃分國內(nèi)外路徑規(guī)劃方法較為清晰。全局的路徑規(guī)劃有基于構(gòu)型空間的幾何法和基于狀態(tài)空間的拓?fù)浞?前者主要有單元分解法(柵格法、可視圖法、 在完全遍歷過程中,常常遇到“死基點(diǎn)”情況,首先,通過環(huán)境電子地圖找到最近的未遍歷區(qū)域。通過尋找具體方法是:首先,查找遍歷矩陣搜索未遍歷矩形區(qū)域;接著,計(jì)算當(dāng)前區(qū)域到所有未

5、遍歷區(qū)域的距離(空間距離,找到晟近的未遍歷區(qū)域,作為下一目標(biāo)區(qū)域:最后,利用反向梯度法找到最近未遍歷區(qū)域的路徑。如圖310所示,從基點(diǎn)1區(qū)域開始遍歷,依次遍歷了基點(diǎn)2、4、5、6、7、8、9基點(diǎn)所在矩形區(qū)域。遍歷完基點(diǎn)9所在的區(qū)域后,用搜索規(guī)則找下一目標(biāo)基點(diǎn)時(shí)發(fā)現(xiàn)基點(diǎn)9為“死基點(diǎn)”;接著,就在未遍歷區(qū)域(基點(diǎn)12、13所在區(qū)域中尋找最近的未遍歷區(qū)域,經(jīng)過計(jì)算,基點(diǎn)12距離基點(diǎn)9最近,即基點(diǎn)12就是下一目標(biāo)基點(diǎn)。于是,就用反向梯度法求得基點(diǎn)9N基點(diǎn)12的最短路徑(基點(diǎn)9一基點(diǎn)8(10一基點(diǎn)7(11一基點(diǎn)12。 0bstaclt鬻56蕊謠8甲10塞9黧j456怒2345.,。,8l23./5678

6、_/,一3蕊邋89100】船麟34鶼憋黲9100bstacle圖39反向梯度法求最短路徑圖3-10完全遍歷中的反向梯度法全局路徑規(guī)劃完成所有基點(diǎn)的遍歷,而局部路徑規(guī)劃要完成某基點(diǎn)所在區(qū)域的局部遍歷。在全局路徑規(guī)劃層每搜索到一未遍歷基點(diǎn),就要完成該矩形區(qū)域的局部遍歷。全局路徑規(guī)劃和局部路徑規(guī)劃交錯(cuò)進(jìn)行,最終實(shí)現(xiàn)環(huán)境完全遍歷。在局部路徑規(guī)劃中,移動(dòng)機(jī)器人完成局部區(qū)域遍歷運(yùn)動(dòng)。這個(gè)過程分為三個(gè)部分:尋找局部區(qū)域遍歷起始點(diǎn),局部區(qū)域遍歷和回到局部區(qū)域基點(diǎn)。(1局部遍歷模式在全局路徑規(guī)劃中,采用單元分解法的思想,在單元間建立交錯(cuò)網(wǎng)路。在交錯(cuò)網(wǎng)絡(luò)上實(shí)現(xiàn)對(duì)基點(diǎn)的遍歷。在局部層要完成對(duì)局部矩形區(qū)域的遍歷,由于

7、局部區(qū)域是連通的,很容易使用模板法實(shí)現(xiàn)遍歷。算法規(guī)定局部遍歷路徑規(guī)劃三種基本遍歷運(yùn)動(dòng)模式(如圖311:螺旋式,弓形式(橫和弓形式(豎。遍歷運(yùn)動(dòng)模式由環(huán)境的形狀決定,而環(huán)境的形狀通過環(huán)境學(xué)習(xí)得到。前種模式針對(duì)矩形區(qū)域中沒有障礙物的情況,后兩種模式適應(yīng)于矩形區(qū)域中存在障礙物的情況。弓形式(橫和弓形式(豎其實(shí)是同一種遍歷模式,只是遍歷直線行走的方向不同,前者是橫著行走,后者是豎著行走。這三種基本的遍歷模式由5個(gè)基本模板組成,如圖312所示,算法中定義了5種基本模板:(a前進(jìn)模板,(b右轉(zhuǎn)模板,(c左轉(zhuǎn)模板,(d后退右轉(zhuǎn)模板,(e后退左轉(zhuǎn)模板。 東南大學(xué)碩士學(xué)位論文 圖3-20完全遍歷路徑規(guī)劃經(jīng)過大量

8、地圖的仿真表明,該遍歷算法的覆蓋率達(dá)到9096以上,有的甚至達(dá)到95%以上,而且重復(fù)率在lO%以下。對(duì)于不同的地圖覆蓋率和重復(fù)率是不同的,不過對(duì)大多數(shù)地圖而言,該算法是高效的、實(shí)用的,具有很強(qiáng)的適應(yīng)性。由于算法只關(guān)注基點(diǎn)的信息,而基點(diǎn)是有限的,這樣就大大減少了計(jì)算量。而完全遍歷過程是機(jī)器人自主完成的,具有很高的智能。遍歷過程中很少有遺漏區(qū)域,在障礙物附近區(qū)域仍有重復(fù)的情況,這是無法避免的。但這比以往的遍歷算法有了大大的改善。對(duì)于特別復(fù)雜的環(huán)境該算法在局部區(qū)域的遍歷算法有待進(jìn)一步改進(jìn),同時(shí)如何更合理的進(jìn)行矩形化建模將是下一步要研究的課題。該完全遍歷算法特點(diǎn)是系統(tǒng)要處理的信息量很少,機(jī)器人實(shí)時(shí)性控制更強(qiáng)。特別是提出了基點(diǎn)這一重要概念,使得在未知環(huán)境中實(shí)現(xiàn)完全遍歷更有效、更方便。3.8本章小結(jié)路徑規(guī)劃是移動(dòng)機(jī)器人導(dǎo)航中最重要的任務(wù)之一。本章從路徑規(guī)劃研究內(nèi)容、分類方法入手,分別討論了幾種常見的路徑規(guī)劃方法,如人工勢(shì)場(chǎng)法,模糊邏輯法,遺傳算法,神經(jīng)網(wǎng)絡(luò)法等。相對(duì)于點(diǎn)對(duì)點(diǎn)的路徑規(guī)劃方法,完全遍歷路徑規(guī)劃是一個(gè)全