連豊力Lian, Feng-Li臺灣大學:電機工程學研究所周執中Chou, Chih-ChungChih-ChungChou2010-07-012018-07-062010-07-012018-07-062009U0001-0501200911472900http://ntur.lib.ntu.edu.tw//handle/246246/188098為完成行動式機器人的自動導航，基於動態窗格演算法(DWA)，這篇論文提出一名為DWA*之反應式演算法來達成高速、平順、且不受局部極小值問題影響的導航。原始的DWA方法只利用了少部份之環境資訊來在機器人的運動空間中搜尋適當之指令，因此，機器人易於走進局部極小值地區而無法脫出此複雜的環境.為能避開局部極小值地區，DWA*運用了區域分析技術來過濾不適當的動作指令，並使用A*搜尋演算法進行預測式驗證，藉此決定一組最佳動作指令，其可引導機器人於數步之後得到最佳的結果。最後，這篇論文分別展示了使用聲納測距器及使用雷射測距器的機器人之模擬與實驗結果，由此可顯出DWA*比起原始的DWA有著更為優越的表現。Based on the dynamic window approach (DWA) for robot navigation, this thesis presents a local reactive method, called DWA*, for mobile robots to achieve high-speed, smooth, and local-minima-free navigation. The original DWA utilizes only a small part of environmental information to search for a proper motion command in the robot’s motion space. Hence, the robot can be easily driven into local-minima area and trapped in complex environment. In order to escape from the local-minima area, DWA* applies region analysis technique to filter improper commands, and uses the A* search algorithm with the look-ahead verification to determine the optimal command which can lead the robot to the best consequence after a designated number of steps. In this thesis, extensive simulation and experimental studies using sonar-based or laser-based mobile robot are presented to illustrate the excellent performance of using the DWA* compared with that of using the original DWA.摘要 IBSTRACT IIONTENTS IVIST OF FIGURES VIHAPTER 1 1NTRODUCTION 1.1 Motivation 1.2 Problem Formulation 2.3 Contribution of the Thesis 3.4 Organization of the Thesis 4HAPTER 2 5ELATED WORKS 5.1 Development of Global Path Planning Methods 5.2 Development of Local Reactive Methods 7.3 Hybrid Methods 9.4 Search Problem Formulation 10HAPTER 3 18YNAMIC WINDOW APPROACH 18.1 Procedure of DWA 18HAPTER 4 22ODIFIED ALGORITHM DWA* 22.1 Procedure of DWA* 22.2 Interval Analysis 24.3 Region Detection 26.4 Set of Situations 29.5 In-Region DWA 31.6 Look-Ahead Verification 33.7 Implementation on Laser-Based Mobile Robots 35.8 Implementation on Sonar-Based Mobile Robots 36HAPTER 5 40IMULATION RESULTS 40.1 Simulation Platform 40.2 Simulation Results for Laser-Based Robot 41.3 Simulation Results for Sonar-Based Robot 50HAPTER 6 56XPERIMENTAL RESULTS 56.1 Experimental Results for Laser-Based Robot 56.2 Experimental Results for Sonar-Based Robot 62HAPTER 7 67ISCUSSION 67PPENDIX 70.1 A* Optimality 70.2 Door Detection 71EFERENCES 731039134 bytesapplication/pdfen-US動態窗格演算法局部反應式演算法速度空間方法預測式驗證Dynamic window approachlocal reactive methodvelocity space approachlook-ahead verificationthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/188098/1/ntu-98-R95921129-1.pdf