移動機器人嵌入式系統(tǒng)設計與路徑規(guī)劃算法研究

1、移動機器人嵌入式系統(tǒng)設計與路徑規(guī)劃算法研究 中國海洋大學碩士學位論文移動機器人嵌入式系統(tǒng)設計與路徑規(guī)劃算法研究姓名:朱曉榮申請學位級別:碩士專業(yè):信號與信息處理指導教師:周東輝20040701杉動機鞘人嵌入式系統(tǒng)設計與婚靜規(guī)劃算法甜究移動機器人嵌入式系統(tǒng)設計與路徑規(guī)劃算法研究摘要隨著社會的發(fā)展,工業(yè)機器人產(chǎn)量逐年增加,但根據(jù)最新預測,到世紀,家用機器人將成為機器人制造業(yè)的主力機種。工業(yè)機器人主要用于以工廠為代表的第二產(chǎn)業(yè),而家用機器人則主要用于第三產(chǎn)業(yè)的服務業(yè),在普通家庭中蘊藏著巨大的潛在市場。本文對家用移動機器人嵌入式智能規(guī)劃系統(tǒng)進行了深入研究,在智能算法和硬件設計兩方面取得了具有實際應用價

2、值的結論,實現(xiàn)了家用移動機器人的自主行走、實時避障、自動尋找充電器充電、不重復走遍整個房問地面等功能。為了實現(xiàn)上述目標,本文采用了以下路徑規(guī)劃策略和控制算法。工作環(huán)境的不確定性例如室內物體擺放的位置不同要求家用移動機器人具有對環(huán)境的白適應能力。遺傳規(guī)劃算法具有在事先不需要知道解的規(guī)模、類型和結構復雜性等情況下,解的屬性可以根據(jù)問題的需要由求解過程來確定,而且基因編碼長度動態(tài)可變,這些優(yōu)點使得遺傳規(guī)劃算法特別適合用于家用移動機器人在未知環(huán)境下的路徑規(guī)劃。另外一方面,它的內核占用的空問少,易于用硬件實現(xiàn)。因此本文采用遺傳規(guī)劃算法來實現(xiàn)家用移動機器人的實時避障,采用交叉自律行走的模式實現(xiàn)路徑不重復地

3、走遍整個房問地面。另外,為了實現(xiàn)移動機器人的實時避障功能,不僅要求硬件系統(tǒng)具有較強的數(shù)據(jù)處理能力,而且應該具有軟件可移植性和硬件可擴展性?；谶@些要求,本文采用了處理速度較快的可編程門陣列來實現(xiàn)算法,采用位單片機來實現(xiàn)對外圍電路的控制、自動模式與人工控制模式的轉換以及電機驅動等。并且該單片機具有強大的語音處理能力,可以很方便的進行語音識別,用語音來控制機器人的行為。在詳細闡述遺傳規(guī)劃算法在機器人自適應行為進化過程的基礎上,本文討論了該算法在上實現(xiàn)的幾個亟待解決的重要問題,包括個體的寄存器存儲方法、最優(yōu)化隨機數(shù)在硬件上的獲得途徑、交叉操作的實現(xiàn)、以及有效的內存管理方法等。軟件仿真和實驗結果表明,

4、利用上述方法實現(xiàn)的機器人具有較快的白適應迸畫的能力,能夠首先沿著墻壁走一圈,然后交叉自律行走,能夠自動避障,并且能通過遙控操作或語音識別進行自動行走模式和人工控制模式的轉換,當檢測到電壓不足時,能夠自動尋找充電器充電。,單片機,避障關鍵詞:家用移動機器人,遺傳規(guī)劃算法,梏動機器人嵌入式系統(tǒng)漩計路徑規(guī)劃算法研究?., ?“. ,. ,., , ., ?.,. . ., . , .,“”. . .】 , ., ,.移動機器人嵌入式系統(tǒng)吐汁,路子州劃算法研究、 ,.,. . .,.移動機器人戰(zhàn)八系統(tǒng)潢汁與路徑規(guī)劃算法研究概述.課題背景工業(yè)機器人自問世以來很快在世界范圍內得以廣泛應用。目前,工業(yè)機器人

5、產(chǎn)量逐年增加,但據(jù)最新預測,到世紀,家用機器人將成為機器人制造業(yè)的主力機種。工業(yè)機器人主要用于以工廠為代表的第二產(chǎn)業(yè),而家用機器人則主要用于第三產(chǎn)業(yè)的服務業(yè),在普通家庭中蘊藏著巨大的潛在市場。但是,這種家用機器人目前尚無已完善的實例,其定義有各種說法,其技術亦各有千秋。如果要說有共同認識的話,那就是一致認為家用機器人是“在家庭中為個人服務的機器人”。在一般家庭中普及機器人的設想源于兩個出發(fā)點。其一是以年輕人為中心的家庭成員的價值觀的變化,即從“以工作為中一”轉變?yōu)椤耙宰晕覟橹行摹?追求生活的高質量,追求家務勞動的省力化,實現(xiàn)家庭自動化。這就需要借助于家用機器人的服務。其二是整個社會的老齡化。隨

6、著出生率的下降,人類將呈現(xiàn)出長壽化,形成老年人多、年輕人少的社會。從社會福利的角度考慮,需要對許多老人配以家庭助手。但因工資、勞動條件等因素的影響,加之前述年輕人價值觀的變化,在供不應求的勞動力市場上很難找到自然人作為家庭助手,故需家用機器人來補充勞動力市場。家用機器入的開發(fā)犒是今后一個時期機器人的一個重要發(fā)展方向。日本和美國都在加緊研制能夠廣泛用于家庭中的家用機器人,這種機器人除了能夠給家庭帶來娛樂外,還能夠幫助家庭干一些家務,家用機器人的發(fā)展趨勢將是智能化和多功能化。這種機器人運用最先進的電腦技術和通訊技術,能夠與正在上班的人取得正常聯(lián)系,家用機器人能夠根據(jù)主人的意圖完成做飯、打掃衛(wèi)生、收

7、發(fā)電子郵件等許多工作。一些家用機器人還將能夠取代保姆的作用,這些機器人在未來將能夠替代人類的大量家庭勞動、為人類的生活帶來極大的方便和樂趣。國外專家預測,在世紀,家用娛樂型機器人將大量投放市場,其消費勢頭將會超過彩電、電腦和汽車的消費,家用機器人產(chǎn)業(yè)將會成為世紀最有誘惑力的市場之一,特別是能夠用于娛樂方面的家用機器人玩具將更受廣大家庭消費者的歡迎。而在家用機器人中,家用移動機器人占很大一部分比例。家用移動機器人研究概況本二菱重工開發(fā)出種能照顧老人、能看門的家用機器人。這臺取名“我之丸”的人形機器人身高,頭頂設有魚眼照相機,根據(jù)所攝圖像,用各種傳感器一邊測量對象及障礙物的距離,一邊使車輪式的腳在

8、室內繞道行走。它備有充電功能,如果電池電力不足,能自行充電。它能識別多達個人的容貌,掌握約萬個單詞的移動機器人嵌入式系統(tǒng)鹽汁與路杼規(guī)劃算注研究簡單會話。能用內置的無線定位器功能,經(jīng)常連接通信網(wǎng)絡,同外出的對方保持聯(lián)絡及遙控操作。例如,外出的人可用手機了解家中的狀態(tài),若有大的聲響,它能通知預先指定的聯(lián)絡對象,起到“看門作用”;又如發(fā)現(xiàn)獨立生活的高齡老人有異常,它能立即通知遠方的家屬,起到“看護作用”;還能設置提醒服藥的時間以及傳遞健康信息管理等功能。本田公司出品的版機器人能用聲音控制,它有一個憨態(tài)可掬的傻瓜外形,每小時可以行走千米千米。它的身高厘米,重約多千克,體格相當于小學生。的頭部配備了兩部

9、照相機,可以測量與用戶及周圍物體之間的距離,并推算用戶及物體所在的方向與移動,簡單地說,這是一個能自覺地跟著主人走動的機器人。除了可以做“隨從”之外,還有“認人”的本領,它能從拍攝的圖像中抽取人與物體的輪廓進行識別,據(jù)說最多能認個人,同時能區(qū)分一些簡單的姿勢并做出回應。年日本橫濱機器人大展上展示的不僅具各以上的特點,還大大增進了行進速度,搭載了不少全新技術。日本機器人開發(fā)公司近日推出一種可以通過聲音和手機遠程遙控的家用人形機器人,這是世界上首次被推向市場的家用步行機器人。 據(jù)日本讀賣新聞日報道,這種機器人的名字叫“”,身高厘米,體重.斤,可放在手提包里攜帶,腳上穿著落地時可減少沖擊力的機器人鞋

10、子。它有個內置發(fā)動機,可以自己掌握平衡,用兩腳步行和跳舞,能做出指令要求的各種動作。人可以用聲音或手機進行遠程操作,還能通過手機看到機器人臉部照相機拍下的圖片。公司介紹說,可以與小孩一起玩耍,成為他們的好伙伴,還可以和老人對話,讓他們開心姆悶兒排解寂寞。此外,機器人的主人還可以把它單獨放在家里看家。兩腳步行機器人在吐界上第一一次推向市場,預示著機器人開始由產(chǎn)業(yè)使用向個人使用的轉變。由中科院沈陽自動化研究所與中科院自動化研究所聯(lián)合研制成功的一種新型特計劃驗種機器入?基于復合機構的非結構環(huán)境移動機器人,目前通過國家收。專家組認為這一機器人具有很強的環(huán)境適應能力,能在多種復雜、多變、惡劣的環(huán)境下完成

11、運行操作。長期以來,采用何種移動機構和移動方式,一直是移動機器人的關鍵技術之一。這一課題組借鑒以往的輪式、腿式、履帶或滑板式等單一驅動方式,采用了先進的輪一腿履帶等多種復合型裝置。這些驅動裝置自由組合、分西作,既可充分利用單一驅動方式在特定環(huán)境下的某種優(yōu)勢,又可集中發(fā)揮各種仂調裝置在復雜多變環(huán)境下的綜合效力。這種機器人自重不到公斤,長.米、寬.米、高 米,履帶移動速度每分鐘米,膠輪移動速度可達每分鐘米。整機采用了“多傳感器信息融合”新技術。為了彌補機器人探測“盲區(qū)”,在機器人的四周裝有超聲波傳感器和紅外線傳感器,用以搜集機器人各個方向的障礙物信息;同時還裝有確定目標方位的視覺傳感器,用來檢測機

12、器人位置的電予羅盤等。在基于神經(jīng)網(wǎng)絡與模糊算法的自主控制狀態(tài)下,機器人具有自動回避障礙、尋找目標、上樓梯、跨越障礙等功能,馴使而對多種結構的復雜環(huán)境,也能應付自如,迅速做出判斷,根據(jù)不同的地面狀況自移動機器凡嗽入,系統(tǒng)設計與鴨行慨劃算法研究動切換移動方式。據(jù)了解,這種特種機器人技術集機械、電子、新材判、傳感器、計算機、智能控制與網(wǎng)絡通信等多門科學于體,是最具基礎性、戰(zhàn)略性和前瞻性的高新技術。專家認為,這種機器人具有極強的環(huán)境適應能力,將為中國在太空、海洋等未知環(huán)境下的探測勘察工作提供技術保障。.移動機器人路徑規(guī)劃概述移動機器人路徑規(guī)劃是機器人學的一個最基本也是最復雜的問題,它被描述成:給定一個

13、移動機器人所處的環(huán)境環(huán)境可以通過移動機器人視覺系統(tǒng)或者別的途徑獲得,個起始點和一個期望的終止點,移動機器人蹄徑規(guī)劃就是根據(jù)一定的任務要求尋求一條連接起始點到終止點且能避開環(huán)境中障礙物的移動機器人的運動軌跡,即最優(yōu)或次優(yōu)有效路徑.路徑規(guī)劃是移動機器人導航中最重要的任務之一。目前,移動機器人的路徑規(guī)劃算法主要有兩種類型:一種是基于環(huán)境先驗完全信息的路徑規(guī)劃;另一種是基于傳感器信息的不確定環(huán)境的路徑規(guī)劃。完整的先驗信息只適用于靜態(tài)環(huán)境,在情況下,路徑是離線規(guī)劃的。在環(huán)境不確定的情況下,路徑必須在線規(guī)劃,其中還包含在線避障算法。近年來,國內外學者對存在固定障礙的路徑進行了大量研究,提出了一些算法。其中

14、比較成功的方法主要有勢場法和柵格法。.首先提出了人工勢在年和年加以改進,提出了一種人工輔助全局場法,后來由.路徑規(guī)劃法,并進行了性能分析。用柵格法表示格予環(huán)境模型中存在障礙物的可能性的方法起源于美國大學。以后,.雖用柵格表刁一環(huán)境,但是,在更新值上與刪方法不同。在每一次的超聲傳感器讀值時,只需要很少的計算,只影響一個柵格的值,該柵格就是距離超聲頭為讀值的柵格,它在傳感器的軸上。用勢場法決策出虛擬力場去控制移動機器人行駛。通過】陷阱區(qū)域; 在相近障礙物的實驗研究,發(fā)現(xiàn)了勢場法存在四方面問題:之間不能發(fā)現(xiàn)路徑;在障礙物前振蕩;在狹窄通道中擺動。.提出了一種矢量場矩形法,仍采用柵格表示環(huán)境,還采用了

15、兩極數(shù)據(jù)減少技術和信息的三個級別表示,由算法的輸出信息控制移動機器人的速度大小和方向,呈現(xiàn)出良好的性能。但是該方法存在環(huán)境分辨率高與環(huán)境信息存儲量大的矛盾,因此,在實用上受到一定限制。針列圭見劃區(qū)域中障礙物形狀和分布復雜的情況,為了得到滿意的路徑,并且滿足實酬性的要求,后來征柵格法的基礎上,采用基于案例的學習方法來解決移動機器人的路徑規(guī)劃?；诎咐膶W習方法依靠過玄的經(jīng)驗迸彳:二學習及題求解。一個新案例可以通過修改庫中與當前情況相似的的案例來獲得?；诎咐膶W習是增量式的,學習的成功率隨著案例的增加而提高,案例的匹配過程也是案例庫的擴充過程?？坝诎咐膶W習重視的是如何組織和管璀一個案例庫,在需

16、要進行攤璀吲如何快速的從案例庫中找到合適的匹配案例,以及是否擴充案例庫。移動機器人嵌入武系統(tǒng)醴汁與路徑規(guī)劃算法硼究在基于多傳感器融合的導航研究中,模糊邏輯和神經(jīng)網(wǎng)絡是采用得比較多的兩種方法。這兩種方法的共同點在于易于表達某些難以精確描述的規(guī)則,但也存在著各自的缺點:模糊邏輯的運算量隨規(guī)則數(shù)量的增加而成幾何級數(shù)增長,因而在模糊規(guī)則較多時難以付諸實施;神經(jīng)網(wǎng)絡系統(tǒng)受學習樣本的影響很大,選擇代表性強的樣本集是一件分困難的事情,而讓樣本集覆蓋整個樣本空間是不現(xiàn)實的,因而樣本設計就成為神經(jīng)網(wǎng)絡應用的一個豐要問題。由于模糊邏輯和神經(jīng)網(wǎng)絡各自的缺陷,在實際應用中,均未能取得完全滿意的效果。避障控制是導航任務

17、的基本內容之一,后來又出現(xiàn)了將模糊邏輯、神經(jīng)網(wǎng)絡和傳感器融合技術結合起來,用于移動機器人的避障控制研究。利用多個非攝像類的超聲波和紅外線傳感器探測環(huán)境信息,采用多傳感器融合技術對傳感器信息進行處理,研究了模糊聚類和神經(jīng)網(wǎng)絡系統(tǒng)在移動機器人系統(tǒng)中的避障控制能力。利用遺傳算法, .等人設計了一種移動機器人進化規(guī)劃系統(tǒng),在該系統(tǒng)中,路徑由一個個節(jié)點組成,節(jié)點由矛坐標和位表示路徑通暢與否的狀態(tài)來表示,基因與路徑相對應,目標函數(shù)由三個部分組成:路徑長度、光滑度和距離障礙物程度,根據(jù)實際情況規(guī)定了八種遺傳操作。利用改進的進化編程,并精減遺傳操作,得到了很好的效果:并且可以滿足不同的優(yōu)化準則,得到次優(yōu)路徑和

18、更好效率,適應各種情況變化,具有良好的魯棒性。目前,遺傳規(guī)劃算法的研究非?；钴S,研究范圍也涉及到神經(jīng)網(wǎng)絡、專家系統(tǒng)、圖象處理等多個領域,在移動智能機器人研究領域,隨著社會的進步和技術的發(fā)展,越來越需要機器人能夠在沒有人工干預的條件下自適應于環(huán)境和完成所給任務。遺傳算法在這一領域已經(jīng)得到了廣泛地應用并取得了很好的成效。而與相比,雖然提出較晚,理論也較新,但它具有所不具備的優(yōu)點,如:由于許多工程問題可以歸結為對特定輸入產(chǎn)生特定輸出的計算機程序,而算法的個體表示的就是這些計算機程序,它能夠很好的層次化地描述所要解決的問題;而且算法在交叉過程中是任意選擇交叉點,所以它的基因編碼長度是動態(tài)可變的,這就使

19、得基因所描述的系統(tǒng)狀態(tài)可以更好地適應環(huán)境的變化;此外,對于算法的應用,事先不需要知道解的規(guī)模、類型和結構復雜性等,解的這些屬性可以根據(jù)問題的需要由求解過程來確定。這些優(yōu)點使得算法能夠很好地應用于機器人自適應行為的演化巾。 ., .他們把遺傳規(guī)劃算法用于.,機器人的避障行為中,機器人采用 微控制器,實驗結果表明該機器人有良好的進化行為,能夠實時的避開障礙物。本文是采用遺傳規(guī)劃算法來實現(xiàn)避障的,所以下面將詳細闡述一下該算法。.逮傳規(guī)劃算法概述遺傳規(guī)劃;,簡稱算法是由教授提出用于計算機程序的優(yōu)化設計及自動生成的一種算法,其實質是用義的層次化計算機程序描述問題。它的基本思想和遺傳算法 ,簡稱相類似,通

20、過隨機移動機器人戰(zhàn)八。戈系統(tǒng)設計與路徑規(guī)劃算法研究產(chǎn)生初始群體,然后對群體進行自然選擇、交叉變異,最終優(yōu)勝劣汰,自動生成性能較好的計算機程序。算法基于具有描述問題層次化、編碼長度動態(tài)可變等特點,它被廣泛地應用于人工智能、機器學習、符號處理等方面。算法使用分層結構的表達方式來表示解空間,它的葉結點是問題的原始變量,中日結點則是組合這些原始變量的函數(shù),這種結構很類似于語言中的表數(shù)據(jù)結構。算法的個體染色體表示的是許多計算機程序的組合,根據(jù)程序表達含義和組合位置的不同,可以分為函數(shù)集和終止符集,其中函數(shù)集包括運算符號、數(shù)學函數(shù)、條件表達式等等;終止符集包括變量如描述系統(tǒng)的輸入變量、狀態(tài)變量、常數(shù)、無參

21、函數(shù)等等。函數(shù)集和終止符集必須滿足兩個條件:充分性利閉合性。因為算法中問題的解是函數(shù)集和終止符集的組合,所以要求預先設定的函數(shù)集和終止符集的組合空間中包含所給問題的解;同時,函數(shù)集和終止符集的組合必須滿足閉合性,即任意函數(shù)所帶參量和任意終止符的類型必須一致,這樣才能保證遺傳變換的正常進行。和遺傳過程一樣,算法的一般遺傳過程也包括選擇、交叉、變異。結構如圖所示:彪手予.眾幽捌形結構遺傳過程結構圖?墮型型塑壘堅塵:;墨塹堡生蘭墮堡型型曼鯊塑壅根據(jù)基因的結構形式不同,遺傳規(guī)劃算法可以分為樹形結構、線性結構、圖形結構和其他結構形式的。線性結構能交叉操作如圖所示。魚呈量哥.盤了.圈;網(wǎng)圈、一圈孟圈沁護琴

22、零 圜尹辯圓圈圈圈匭圈圓圈圖線形結構遺傳過程結構圖需要說明的是:選擇、交叉、變異操作是個體依次循環(huán)進行的.也就是說下一代群體中包括部分的選擇操作的個體,部分的交叉操作的個體和少部分的變異操作的個體;而不是像的遺傳操作那樣群體依次循環(huán)進行,這樣可以使得更大幾率保證好個體保留下來;由于算法的交叉操作是兩個個體分別隨機選取交叉點,交叉點以下的子個體長度可以不同,個體的編碼長度是動態(tài)可變的,所以即使兩個相同的個體,也只有當交叉點相同時才不會發(fā)生變化,因此算法的個體經(jīng)遺傳操作后不具有同一性,到不會使整個群體趨向最優(yōu);同樣由于算法的交叉操作使得個體編碼長度動態(tài)可變,所以算法不像算法那樣會陷入“早熟”,變異

23、操作的作用也就相應地減弱了;算法的個體就是函數(shù)集和終符集組成的語義樹,所以對個體染色體用符號型編碼表示成樹型結構,能夠很好地體現(xiàn)這種組合關系,而且能很方便地進行遺傳操作。個體的表示。根據(jù)個體的特點.用二叉樹的樹型結構和袖點結構來表示個體和個體的節(jié)點。每一二叉樹都是由很多節(jié)點串起來的,可以通過訪問其根節(jié)點來訪問整個叉樹。適應度函數(shù)的選擇。常用的適應度有:原始適應度、標準適應度、歸一化適應度。原始適應度是問題的自然表達,很多簡單問題如螞蟻覓食問題就可以直接用尋覓到的食物數(shù)量作為原始適應度;標準適應度是原始適應度的又一描述,它總是表現(xiàn)為適應度值越小越好:歸一化適應度是將標準適應度進行歸一化處理。如何

24、選擇合適的適應度函數(shù),還需具體問題具體分析。隨機產(chǎn)生初始群體的方法。采用從下到上的結合法,即根據(jù)函數(shù)所帶變量的個數(shù),對終止符進行隨機組合,然后組合后的于樹又作為一個變量,再次和別的變量包括其他子樹和終止符進行組合,這樣一直組合直到達到設定的樹結構深度。綜上所述,可以看出,與相比,雖然提出較晚,理論也較新,但它具有所不具備的優(yōu)點,如:由于許多工程問題可以歸結為對特定輸入產(chǎn)生特定輸出的計算機程序,而算法的個體表示的就是這些計算機程序,它能夠很好的層次化地描述所要解決的問題;而且算法在交叉過程中是任意選擇交叉點,所以它的基因編碼躍度是動態(tài)可變的,這就使得基因所描述的系統(tǒng)狀態(tài)可以更好的適應環(huán)境的變化;

25、此外,對于算法的應用,事先不需要知道解的規(guī)模、類型和結構復雜性等,解的這些屬性可以根據(jù)問題的需要由求解過程來確定。這些優(yōu)點使得算法能夠很好的用于機器人自適應行為的演化中。遺傳規(guī)劃中個體大小“爆炸”現(xiàn)象及其對策在遺傳規(guī)劃中存在著熟知的所謂“規(guī)模爆炸”問題,亦即作為程序個體表示的文法樹的大小,包括它的深度和廣度,在進化過程中不斷地增大,而與此同時作為解的群體卻沒有任何改進。這一現(xiàn)象為許多研究者所發(fā)現(xiàn)。對于大多數(shù)的應用問題來講,樹不能太大,否則很難將它翻譯為一個有意義的結果;同時,正如許多文獻所指出的那樣, “爆炸”現(xiàn)象常常伴隨著優(yōu)化講程變慢的表現(xiàn)。.內含子的作用與危害在程序樹規(guī)模變大問題中,可以觀

26、察到一個十分有趣的現(xiàn)象,這就是“內含子”大量產(chǎn)生的問題,也可稱之為“冗余”問題,圖,是兩個冗余的程序樹的簡單例子。在圖中,因為第一個變量的值為,所以“與”運算的結果恒為,而不管第二個變量的值是什么。因此,如果有一個子樹以節(jié)點為頂點的匱,那么它對程序樹所代表的整個程序的最終結果沒有任何影響。圖中,實際計算結果是,類似的現(xiàn)象在符號回歸問題的求解過程中是非常普遍的。為了壓縮這種冗余的語句,不得不對最后的結果使用自動編輯器來消除這種現(xiàn)象。但是,這僅僅是在最后步所作的工作,對于在進化過程中怎樣減少該現(xiàn)象并沒有提供幫助。內含子是一個遺傳學術語,指生物染色體上的某些不表達為蛋白質的基因片段,它們只足提供了有

27、意義的基因外顯廠之問的問隙,文獻首先將內含了的概念引入遺傳算法中,在一個串中的某些基因座上放置與適應值計算無關的等位基因,移動機器、嵌入式系統(tǒng)設汁與蹄仟規(guī)劃筒法研究或干脆認為這些位置是空的。引入內含子的意義在于,進行交叉操作時,當交叉點的位置落在內含了時,不會破壞已有的有意義的串,因此能有效地保護現(xiàn)有的模式。圖 冗余程序樹圖冗余程序樹模仿遺傳算法的串表示,引入了線形表示的程序個體,而不是用通常的樹狀表示,并且在遺傳規(guī)劃中引進了內含子的概念,亦即“對任何適應值函數(shù),都不影響所在程序的表現(xiàn)的程序塊”。在實例中發(fā)現(xiàn),進行了交叉操作以后,有相當?shù)膫€體的適應值下降了,同時有相當?shù)膫€體的適應值保持不變。經(jīng)

28、過分析得知,很多個體通過增加它所包含的內含子的個數(shù)來保護自己不受交叉操作破壞作用的影響而保持適應值基本不變。的分析是基于他的程序個體的線形表示的,不完全適用于通用的遺傳規(guī)劃。對于如何在程序樹中引入內含子的概念以及做出相應的分析,仍是一個有爭議的問題。一個比較自然的定義是稱個體樹中的某個節(jié)點是內含子,如果該個體的適應值與頂點在這個節(jié)點的子樹無關。顯然,如果一個節(jié)點是內含子,則以它為頂點的了樹中的任何節(jié)點都是內含子。由于動態(tài)樹狀表示的復雜性,對之進行理論分析是十分網(wǎng)難的這也是遺傳規(guī)劃理論研究中的主要困難所在,現(xiàn)有的結果也是很初步的。如前所述,內含于的出現(xiàn)與存在,在保護個體不受交叉操作的破壞方面是有

29、益的,似是一個程序中有過多的內含予會造成程序樹過度膨脹,影響運算效率,同時也使得剝程序意義的解釋變得同難。已經(jīng)有多種方法來處理這種程序樹的大小“爆炸”的問題,其中最簡單的方法是在遺傳規(guī)劃的運行過程中,限制樹的大小,比如。這種方法的問題是群體的多樣性得不到保證。為了保證備捌的最火深度限制為在群體中有足夠的遺傳物質,只好使用很大的群體規(guī)模,必然大大增加計算量。更移動機器、嵌入式系統(tǒng)世汁與蹄杼覘劃算法硼究重要的是,在多數(shù)應用剛題中,事先根本不可能確定應當如何選擇樹的大小才能解決問題。取得太大,沒有意義,而取得太,有可能得不到正確的解。.消除冗余性的方法普遍的方法是引入類似于優(yōu)化問題中“罰函數(shù)”項的簡

30、約壓力項,對于。個最小化問題,這就相當于將一個與樹的大小有關的項加到原始的適應值函數(shù)上以產(chǎn)生新的適應值函數(shù),剮這里表示一個個體,為的原始適應值,給出了的樹狀表示的復雜度,如樹的深度,節(jié)點的個數(shù)等,為簡約壓力因子,為新的適應值函數(shù).這種方法的困難在于如何權衡簡約壓力因子的大小。如果太小,則對于減少內含子數(shù)目的效果并不理想;而太大,遺傳規(guī)劃傾向于選擇短的解,即使短解的原始適應值較差,這就會導致收斂到錯誤的解。由于事先無法估計最優(yōu)解的規(guī)模,的確定當然是以自適應選擇為佳,亦即在進化過程中自動地調整的大小。在實踐中發(fā)現(xiàn),上述方法有其適用的具體問題。但如何找出問題的特征以便事先就能判斷使用哪一種方法更合適

31、,仍是一一個沒有解決的問題。.論文結構家用移動機器人的開發(fā)將是今舌一個時期機器人的個重要發(fā)展方向,這種機器人除了能夠給家庭帶來娛樂外,還能夠幫助家庭干一些家務,家庭機器人的發(fā)展趨勢:悔是智能化和多功能化。家用移動機器人的關鍵技術是嵌入式智能規(guī)劃系統(tǒng)。規(guī)劃系統(tǒng)包括傳感器及其信息融合、機器人的定位定向和自主規(guī)劃及其硬件實現(xiàn)等。本課題研究的主要內容有家用移動機器人路徑規(guī)劃算法?遺傳規(guī)劃算法、傳感器及信息融合技術以及基于嵌入式芯片的智能規(guī)劃硬件系統(tǒng)的設計實現(xiàn)。本課題交現(xiàn)的基本功能有遇障礙可自動回避、可沿障礙邊界移動、自學習進化算澎、實現(xiàn)行走慕本無重復路徑以盡快的走遍整個房聞地麗;多種傳感器檢測周圍一作

32、環(huán)境,全過程安全可靠,操作自動化:當檢測到電壓不足時,可以自動尋找充電器進行充電,充電一次工作分鐘:可以進行語音識別署遙控操作來切換機器人的行走模式?自辛彳丁走和人工控制行走模式。第 章,遺傳規(guī)劃用于機器人避障的實現(xiàn)。首先說明了本文移動機器人采片的.【徑規(guī)劃算法;然后詳細刳述了遺傳規(guī)劃算法用于機器人避障的實現(xiàn),包括個體的表示、遺傳操作、適應度函數(shù)以及算法進化的詳細過程。仿真結果表明,該遺傳規(guī)移動機器人嵌入式系統(tǒng)吐與路徑規(guī)劃算法研究劃算法學習的速度較快.有較高的處理速度,提高了移動機器人的避障實時特性簡化了系統(tǒng)設計。這一章是本文的重點。第二章,家用移動機器人智能控制系統(tǒng)的硬件設計。根據(jù)算法實現(xiàn)地

33、經(jīng)濟性和簡單可行性以及硬件的可擴展性,選取可編程門陣到芯片作為遺傳算法實現(xiàn)的載體;選用位單片機作為智能控制芯片,以控制電機以及外圍電路。這是本文的另一重點。第章,詳細闡述了遺傳規(guī)劃算法在硬件上實現(xiàn)的幾個重要問題及解決方法,包括個體的寄存器存儲方法、最優(yōu)化隨機數(shù)在硬件上的獲得途徑、交叉操作的實現(xiàn)、以及有效的內存管理方法等。第四章,淪文總結。概括本論文研究的主要內容,并說明了本課題研究的重點內容和方向。鴉功機器幾嵌入式系統(tǒng)慢汁與鴨行況劃貫:研究遺傳規(guī)劃算法用于機器人避障的實現(xiàn)本文所采用的路徑規(guī)劃算法本課題要實現(xiàn)的基本指標有:自學習進化算法實現(xiàn)逞障礙可自動回避;行走基本無重復路徑以盡快的走遍整個面積

34、;多個傳感器檢測周圍工作環(huán)境,全過程安全可靠,操作自動化;當檢測到電壓不足時,可以自動尋找充電器進行充電,充電一次可工作分鐘;可以進行語音識別和遙控操作來切換機器人的行走模式?自主行走和人工控制模式。根據(jù)要實現(xiàn)的基本指標,使機器人采用交叉獨立自律行走的模式。圖為交叉行走模式不意圖。首先,通過測距傳感器檢測房間的墻壁,控制機器人沿墻角行走。在沿墻角行走時,當檢測到標志時,確認走遍周邊墻角使機器人返回原位。周邊墻角走完后,轉向房間中部行走,從房間一側行至對側后,轉動。返回,如此反復行走,如前方有障礙物則返回。這種往復行走在交叉。的縱橫兩個方向進行,即可將仝竄走遍。外走緘向往葭行走行盤瓤盜橫向往復行

35、走圖交叉行走模式圖移動機器凡嵌入式系統(tǒng)設計與踹桿覘劃骨限研究為了實現(xiàn)以上這些動作,需按以下的基本規(guī)則進行控制。第,障礙物回避規(guī)則。根據(jù)算法硬件實現(xiàn)的可行性、方便性和經(jīng)濟性,用遺傳規(guī)劃算法來實現(xiàn)機器人的避障行為。在吸塵機器人周圍設置六個紅外線測距傳感囂,把這些傳感器的數(shù)值輸入到智能控制器里,利【;遺傳規(guī)劃算法得到機器人的兩輪電機的速度,從而控制行走電動機的動作。這樣,目使遇到各種各樣材質和形狀的障礙物,也不會沖撞,保證吸塵機器人高效準確地在墻角環(huán)行和在房問中部往復行走。笫二,姿勢控制規(guī)則。首先,通過測距傳感器檢測房間的墻壁,控制機器人沿墻角行走一周。然后縱橫兩方向往復行走,通過旋轉傳感器進行控制

36、,使機器人保持直行,前方遇到障礙物進行。的轉向控制。但只用這種控制在有地毯的房間或地面不太平的房間,保持直行有困難。比如地毯的毛有一定的傾向,機器人即使向前直行,由于傾斜毛的影響,也會使本體改變前進方向。因此使用可檢測萬向輪方向的橫向傳感器,根據(jù)此傳感器的信息可知道橫向偏移,從而修正控制機器人保持直行。由于本機器人是自動操作,通常用戶是不在旁邊的。如運轉中出現(xiàn)故障,不僅不能作,還可能發(fā)生不安全情況。因此需要采取一些措施來避免出現(xiàn)這些問題,在本機上設置檢測本機至地面距離的高度傳感器,工作前預先檢測前方的地面高度,如遇到臺階等物體,可使機器人回避。設置報警傳感器,在車輪遇到障礙物產(chǎn)生渭夠,當孩子不

37、注意壓碰本機等,在機器人工作難以繼續(xù)進行時,使機器人停止運轉。系統(tǒng)的構成整個系統(tǒng)的構成如圖所示,外部傳感器得到的信息經(jīng)過單片機處理后得到距離數(shù)據(jù)傳給控制器,由固化在的算法來處理這些數(shù)據(jù),從而得到機器人的動作信息,以驅動機器人動作。動作評價適應度計算移動機器人與傳感控制器憊度器單片機?一距離等信息記憶與處理圖系統(tǒng)整體框圖移動機器凡嵌入式系統(tǒng)設十與蹄櫛賤臂璉研究.實驗環(huán)境如圖所求,機器人為二輪小車,采用芯片作為微控制器,同時采用存儲器用于存儲的電路配置信息。片運動控制芯片可實現(xiàn)機器人左、右輪速度伺服控制,電機為自帶光電編碼盤和減速器的直流電機,單片機為臺灣凌陽公司的位單片機,傳感器是分布在小車周圍

38、的六個紅外接近傳感器,能檢測的距離大約為如圖。圖 二輪小車移動機器人嵌入式系統(tǒng)畦汁與路徑規(guī)劃算法研究圖 紅外接近傳感器分布圖.機器人運動模型圖所示為三輪機構原理圖。它是由獨立驅動的兩個后輪和小腳輪構成的輔助輪組合而成。設轉向角為中、點的坐標為,、車體相對于坐標軸的偏斜角為,、。為兩輪的速度,那么車體的運動可用表達式來表示:,淞圖小車機構原理倒.遺傳規(guī)劃算法和機器代碼在第一一章已經(jīng)講述過,等人利用遺傳規(guī)劃算法來進化機器人的行為得移動機器人嵌八式系統(tǒng)設計與路徑舭劃算注研究到很好的效果,本文是在他們研究方法的基礎上,提出三點改進:一是個體是用一組位的寄存器組來存放;二是算法在上實現(xiàn)的,而不是在單片機

39、上來實現(xiàn);三是群體的初始化時,隨機數(shù)獲得的方法不一樣。通過這三點改進,機器人進化的速度加快,而且遇到障礙物時自動避障的靈敏度提高了。遺傳規(guī)劃是用于計算機程序的優(yōu)化設計及自動生成的一種算法,其實質是用義的層次化計算機程序描述問題。它的基本思想和遺傳算法相類似,通過隨機產(chǎn)生初始群體,然后對群體進行自然選擇、交叉變異,最終優(yōu)勝劣汰,自動生成性能較好的計算機程序。算法基于具有描述問題層次化、編碼長度動態(tài)可變等特點,它被廣泛地應用于人工智能、機器學習、符合處理等方面。許多工程問題可以歸結為對特定輸入產(chǎn)生特定輸出的計算機程序,而算法的個體表示的就是這些計算機程序,它能夠很好的層次化地描述所要解決的問題;而

40、且算法在交叉過程中是任意選擇交叉點,所以它的基因編碼長度是動態(tài)可變的,這就使得基因所描述的系統(tǒng)狀態(tài)可以更好的適應環(huán)境的變化;此外,對于算法的應用,事先不需要知道解的規(guī)模、類型和結構復雜性等,解的這些屬性可以根據(jù)問題的需要由求解過程來確定。這些優(yōu)點使得算法能夠很好的用于機器人自適應行為的演化中。所渭路徑規(guī)劃就是在給定的障礙環(huán)境結構下,機器人從初始點出發(fā),能夠避開障礙物而到達目標點。這包含兩層意思,一是如何避障,二是避開障礙物后向哪個方向走才能最優(yōu)的到達目標點?；谏鲜鲞z傳規(guī)劃算法的優(yōu)點,本文首先利用該算法實現(xiàn)避障,然后根據(jù)交叉獨立行走的模式走遍整個房間的面積。.個體的表示在本系統(tǒng)中,采用線性基因

41、的形式,并把構成群體的個體以二進制代碼的形式進行存儲。這就使得系統(tǒng)的執(zhí)行速度提高了很多倍,同時節(jié)省了存儲空間,內核只需要的存儲空間。這些特性可以使算法運行在低端處理器上如一塊芯片進行理想的實時控制,從而達到了能進行獨立的控制,而不需要構成主從式結構。這里采用的進化算法是一種高級的,即每個個體都是由不同長度的位的指令序列集類似標準語言函數(shù)的機器代碼序列組成的。每條位的指令代表簡單的算術操作如“”或者“”,可以包招最大長度為位的常數(shù),它的結構如圖,它包括四部分:頭部分、返同部分、函數(shù)體和緩沖區(qū)。頭部分存放常量和個體初始化的內容,不能對這部分代碼進行交叉或變異操作;返回部分使系統(tǒng)在函數(shù)調.后返回到主

42、進程中;函數(shù)體是由代表個體的實際程序組成的,遺傳操作存這哩發(fā)牛;在每個個體的末尾都保留了一部分緩沖區(qū)空間,這保證了個體的長度是叮以變化的,為交叉操作提供了空間。移動機器凡嵌入式系統(tǒng)設計與路徑蜘劃算法研究.一?斗?十斗竺五裂圖個體的結構.遺傳操作在本系統(tǒng)中,利用兩點字符串交叉,節(jié)點是基本的交叉單位,可以在節(jié)點的一側或兩側進行交叉操作,但不能在節(jié)點內部,圖例示了本文中采用的交叉方法。變異發(fā)生在節(jié)點內部,變異算子保證變異后的指令在有效的指令集范圍內。所有的遺傳操作都要保證進化中的封閉性。在該實驗中,采用的是低級機器代碼指令,函數(shù)集由算術操作、,移位操作、和邏輯操作,和組成的。恕引創(chuàng) ,譽尚忑只圖 交

43、叉操作移動機器人嵌入,系統(tǒng)醴計與路徑艦劃算法研究.適應度函數(shù)在本文中,每個個體都是由簡單的指令集程序行組成的,這些指令表示了變量、輸入和輸出參數(shù)之間的關系。輸入是六個紅外接近傳感器的距離值,運行后的結果輸出是兩輪驅動電機的速度, 用函數(shù)可以表示為:,:,。,。,。,其中,?是外界傳感器的數(shù)值,。,:是兩輪驅動電機的速度。但為了更好的表達個體進化與外界環(huán)境的關系,我們把上述函數(shù)表示成下式:., ,:,個體根據(jù)適應度函數(shù)值的大小來調節(jié)參數(shù),從而使個體能更好的適應環(huán)境。適應值函數(shù)的大小表示了個體的優(yōu)劣,它由“懲”和“罰”兩部分組成。對函數(shù)值有負貢獻的部分,即“罰”,它是所有紅外傳感器數(shù)值的和。越接近

44、一個物體,“罰”的值越大,為了防止機器人原定不動或打轉,給適應度函數(shù)值一個正的部分,即“獎”,機器人走得越快,“獎”值就越大。,的取值范圍為?,值越大越接近物體。、。取值為?,是個體執(zhí)行的結果,為左右輪的速度。根據(jù)以上原則,適應度函數(shù)值可表示為:,一、一,一。.進化算法在本系統(tǒng)中,進化訓練中選用的參數(shù)如表所示表函數(shù)集: ,“獎”減去“罰”的部分適應度函數(shù):群體規(guī)模:%交叉率:%變異率:聯(lián)賽選擇選擇:移動機器人嵌入武系統(tǒng)醯計與路徑規(guī)劃算法研究圖控制結構圖控制結構框圖如圖所示,算法具體的實現(xiàn)步驟如下從群體中任意選擇個個體;對聯(lián)賽選擇中的個個體,都做如下幾步:從外界讀入六個傳感器的數(shù)值,并把這些值傳

45、給該個體。執(zhí)行個體得到兩輪驅動電機的速度。把電機速度傳給機器人。休眠等待機器人的動作結果。再次讀入傳感器的數(shù)值并計算適應度函數(shù)的值。根據(jù)適應度函數(shù)的值,用最好的兩個個體的子代來代替最差的兩個個體。對子代進行交叉和變異。轉到步驟,重復以上步驟,直到選出最優(yōu)的個體。算法實現(xiàn)的流程如圖。.該算法的仿真結果開始時行為是雜亂無章的。在頭幾分釗,內,機器人不斷的垮物體碰撞,但隨著時間的推移,碰撞次數(shù)越來越少,第一個智能行為經(jīng)常表現(xiàn)為遇到障礙物時向后退,然后逐漸的學會拐彎以避開障礙物。移動機器人嵌入式系統(tǒng)世計與路徑規(guī)劃算法訓究移動機器人嵌入式系統(tǒng)設計與路徑規(guī)劃算法研究進化過程中個體適應度值和性能的變化可以從

46、圖,中看出,在進化中的第代內,平均適應度值和最好個體的適應度值都得到提高圖和。從圖可以看出,從第代開始,最好的個體的適應度函數(shù)值就達到了進化后最后個體的適應度函數(shù)值,但是波動很大。雖然在每代中最好的個體都保留下來,但在訓練中相同的個體卻表現(xiàn)為不同的適應度函數(shù)值,這是由于適應度的取值依賴于其性能即表現(xiàn)結果,而不是控制程序結構本身。從圖可以看出,在代內,是穩(wěn)定增加的,但平均碰撞次數(shù)平均采樣數(shù)卻沒有明顯的變化,這說明了隨著進化的進行,達到了避障的效果。圖每代最好個體的適應度值圖每代平均適應度值圖采樣數(shù)和碰撞次數(shù)的變化結果討論由以上討論可以看出,該遺傳規(guī)劃算法學習的速度較快,有較高的處理速度、較低的內

47、存需求,提高了移動機器人的避障實時特性、簡化了系統(tǒng)設計。堡墊絲堡壘堂壘壅至墮堡墮堡塑型生燮一一?移動機器人智能控制系統(tǒng)的硬件設計一?算法的硬件實現(xiàn)甫隸奎翥柔魯霪磊孥裂蔞霉言裳警罌凳金譬鏨耋唑莖哭擎鬈并瑟螽皇篆墓翥鬈霹器八日眵哭州雌早;蘭耄糞銎鑾焉萋譬獬南翥譬篡塞焱,。嬲磊鬻翼豁一是容量足夠大,能容得下算法的實現(xiàn);二是處理謎度快,便一是硬件具有“擴展性、軟件具有可移植性、可集成。劉。篙鬈篡乎蠢翟麓戮襄囂差囂禚籌器瑟瓣篙篙未簸鼗蓑算/算善安現(xiàn)的載體:選用位單片機作為智能控制心片,吼控市氈屯“隊刪。路。幽為整個硬件系統(tǒng)的連接框圖。實現(xiàn)算法六個紅外接近傳感器電機驅動電路紅外接收裝置霍爾元件檢測語言錄放

48、電路單片機輪予轉數(shù)用來計算速度語言識別控制遙控電路電路圖整個硬件系統(tǒng)框圖?堡塑璺堡壘莖墨竺堡。蘭墮堡塑型墨鯊窒?現(xiàn)場可編程門陣列.可編程邏輯器件當今社會是數(shù)字化的社會,是數(shù)字集成電路廣泛應用的社會。數(shù)字集成電路在小斷的進行更新?lián)Q代。由早期的電子管、晶體管、小中規(guī)模的集成電路、發(fā)展到大規(guī)模和超大規(guī)模的集成電路,幾萬門以上,還有許多具有特定功能的專用集成電路。而隨著微電子技術的發(fā)展,設計與制造集成電路的任務已經(jīng)不完全由半導體商來獨立承擔。系統(tǒng)設計師們更希望能按照自己的意愿設計出符合自己要求的專用集成電路芯片即,且希望設計周期盡可能的短,希望在實驗室里就能完成芯片設計工作,并且可以立即投入使用。就出

49、現(xiàn)了可編程邏輯器件?？删幊踢壿嬈骷芡瓿扇魏螖?shù)字器件的功能,上至高性能,下至簡單的電路,都可以用來實現(xiàn)。如同一張白紙或是一堆積木,工程師可以通過傳統(tǒng)的原理圖輸入法,或是波形輸入及硬件描述語言一般為語言或語言自由的設計一個數(shù)字系統(tǒng)。通過軟件仿真,我們可以事先驗證設計的正確性。在完成以后,還可以利用的在線修改能力,隨時修改設計而不必改動硬件電路。使用來開發(fā)數(shù)字電路,可以大大縮短設計時間,減少面積,提高系統(tǒng)的可靠性。的這些優(yōu)點使得技術在年代以后得到飛速的發(fā)展,同時也大大推動了軟件和硬件描述語言的進步。一現(xiàn)場可編程門陣列和目前使用較多的器件為 。不同的,一家對自己的產(chǎn)品分類和叫法不盡相同。通常是按照結

50、構的不同來劃分和的。采用的是基于乘積項的結構。而是采用的查找表? 結構。查找表簡稱為,本質上就是一個,目前的中多使用輸入的,所以每個可以看成一個有位地址線的.的。當用戶通過語言或其他方式描述廠一個邏輯電路以后,開發(fā)軟件會自動計算邏輯電路的所有可能的結果,并把結果實現(xiàn)寫入,這樣,每輸入一個信號進行邏輯運算就相當于輸入一個地址進行疊表,然后把查找的結果輸出。這種基于工藝的器件,掉電后,其上的所有數(shù)據(jù)就會丟失。因而需要一個外部的器件一般為一個或者同過機的并口,在上電時寫數(shù)據(jù)到器件中,之后器件才能執(zhí)行各種操作。因而不便于加密,中的數(shù)據(jù)容易破改,不利于數(shù)據(jù)的保密,對保密性要求較高的場合不適用。移力機器幾

51、嵌八,系統(tǒng)設計瞎衽帆劃算法研究. 系列器件本實驗選用的是公司生產(chǎn)的 系列芯;。,型號為:這里考慮到以后拶展設計的需要,選用一個門數(shù)較多的芯片?？膳渲眠壿嬒盗行酒瑑炔坑蓧K,輸入輸出塊和高效分層的通用布線通道部分構成。每個包括個,每個又由兩個,兩個觸發(fā)器和相關邏輯構成。般把看成是最小的單元。采用.伏的低電壓供電。采用新的先進的./.的工藝技術制造。具有高于器件的性能。和系列器件相似。集成度低于系列器件兩者的集成范圍較少有重疊,比器件密度要高。有個和與器件一樣容量的塊。不具有類似的差分輸入輸出標準。系列器件具有較高的集成度,因而拓寬了它的應用范圍;內部大量的短的可連線保證了快速的布局布線時間。全局時鐘布線資源:有個專用的全局低斜率的時鐘緩沖器。他們有專用的輸腳,其中個位于中上部,另外個位于中下部。有附加的公共資源,這些資源是用來分配低斜率/高扇出控制信號的,如附加的時鐘、時鐘使能、三態(tài)控制和復位?？刂菩盘栐谄骷鹊姆峙湓趦燃纯赏瓿?。在片時鐘分配: