本論文規劃了一套自走車的導航機制，包括地圖資訊計算模組，循找路徑模組及動態控制模組，由自走車上的PDA負責整個導航系統的動作，包括路徑規劃，閃避障礙物，轉換指令等工作，再由做為馬達控制器的單晶片控制器將PDA的指令轉換為馬達的控制訊號，由模組間的互相合作以整合地圖資訊並規劃路徑，使自走車能順利地找到一條由起點通往終點的路徑，另外也可使用教導式路徑規劃預先設計路徑點之間路徑使自走車能結合自動循徑及使用者教導以依照使用者的規劃來行進，並改良了轉向的機制使得旋轉半徑減小，準確度也更加提昇，也輔以實驗的結果以印證理論的正確性。另外無線網路系統應用於自走車上使得自走車的控制能在數千公里遠的一端來進行，而使用PDA取代傳統的電腦則可使自走車的重量大幅減少，增加使得自走車在移動時更加靈活。

In this thesis, we introduced a navigation mechanism for an autonomous mobile robot. The mechanism is composed of a map information analyzing module, a path finding module, and a dynamic control module. The navigation is handled by a personal digital assistant (PDA) on the mobile robot. This PDA-based system is in charge of the tasks including path planning, obstacle avoiding, and command transformation. The navigation system will first find a path and translate it into commands of a motor controller. Then, a single chip computer, the motor controller, will translate the commands into electronic signals to actually control the motor. The path can also be generated by a guiding system, which uses another PDA to actually guide the mobile robot. The learned path will navigate the robot later autonomously. Applying the wireless LAN module to the mobile robot system makes the users capable of controlling the robot far from thousands miles away. And replacing the personal computer on the mobile robot with a light-weighted PDA also greatly reduces the load of the robot, and makes the navigation more agile.

目 錄
中文摘要 I
Abstract II
誌 謝 III
目 錄 IV
表 目 錄 VII
圖 目 錄 VIII

第一章　序論 1
　　1.1 研究背景與動機 1
　　1.2 研究目的 1
　　1.3 相關研究回顧與討論 3
　　1.4 研究成果與貢獻 4
　　1.5 章節簡介 5

第二章　自走車相關軟硬體 6
　　2.1 自走車相關硬體介紹 6
　　2.2 自走車軟體架構簡介 7
　　2.3 自走車控制系統架構 9

第三章　自走車導航策略 11
　　3.1 自走車導航環境分類 12
　　3.2 自走車之導航基本策略 12
　　3.3 導航地圖表示方法 14
　　3.4 導航路徑規劃介紹 18
　　　　3.4.1 全域路徑規劃 19
　　　　3.4.2 區域路徑規劃 24
　　3.5 區域路徑規劃方法 24
　　　　3.5.1 距離轉換法 24
　　　　3.5.2 路徑轉換法 29
　　　　3.5.3 路徑最佳化 30
　　3.6 教導式路徑規劃 33

　　4.1 自走車轉向機制 36
　　　　4.1.1 自走車轉向計算公式 37
　　4.2 馬達控制器介紹 40
　　4.3 馬達控制器的溝通介面 42
　　　　4.3.1 序列通訊介面 42
　　　　4.3.2 指令格式介紹 45
　　4.5 指令與座標的轉換 50

第五章　自走車運動實驗 53
　　5.1 實驗環境及流程介紹 53
　　5.2 轉向角度測試 54
　　5.3 前進距離測試 60
　　5.4 可能誤差因素討論 63
　　　　5.4.1 滑動的誤差 63
　　　　5.4.2 馬達及電池的誤差 63
　　　　5.4.3 其他因素誤差 64
　　5.5 實際地圖路徑規劃實驗 66

第六章　結果與討論 70
　　6.1 己完成結果 70
　　6.2 結論 71
　　6.3 未來研究方向 73

參考文獻 2
自 述 74


表 目 錄
表2.1 自走車硬體設備表 6
表3.1 自走車導航環境 12
表3.2 地圖圖元表示法 18
表3.3 節點關係表 22
表4.1 DB9型RS232接腳定義圖 43
表4.2 DB9型RS232接腳定義圖 44
表4.3 指令格式對照表 46
表4.4 無線傳輸裝置比較 49
表5.1 左轉100步實驗數據 55
表5.2 左轉200步實驗數據 56
表5.3 右轉100步實驗數據 57
表5.4 右轉200步實驗數據 59
表5.5 前進1000步實驗數據61
表5.6 前進500步實驗數據 62


圖 目 錄
圖2.1 自走車行進示意圖 7
圖2.2 自走車軟體執行程序圖 8
圖2.3 自走車軟體執行程序內部模組 9
圖2.4 自走車控制系統架構圖 11
圖2.5 自走車系統內部模組 11
圖3.1 本文採取之導航基本策略 14
圖3.2 格點地圖示意圖 17
圖3.3 常見的環境資訊地圖 19
圖3.4 各點間距離 22
圖3.5 地圖數值示意圖 25
圖3.6 實際數值地圖 27
圖3.7 有障礙物的數值地圖 28
圖3.8 實際地圖(a) 28
圖3.9 實際地圖(b) 29
圖3.10 實際地圖(c) 29
圖3.11 路徑最佳化示意圖 32
圖3.12 路徑最佳化實際模擬結果 32
圖3.13 路徑最佳化流程圖 33
圖3.14 教導式路徑規劃示意圖 34
圖3.15 教導式路徑規劃流程圖 35
圖4.1 四輪式轉向模型向參數圖 37
圖4.2 二輪式轉向模型向參數圖 39
圖4.3 旋轉角度示意圖 40
圖4.4 DB25型RS232接腳圖 43
圖4.5 DB9型RS232接腳圖 44
圖4.6 RS232傳輸示意圖 45
圖4.7 自走車訊息傳送架構圖 48
圖4.8 自走車行進方向 51
圖5.1 左轉100步實驗結果長條圖 55
圖5.2 左轉200步實驗結果長條圖 56
圖5.3 右轉100步實驗結果長條圖 58
圖5.4 右轉200步實驗結果長條圖 58
圖5.5 前進1000步實驗結果長條圖 61
圖5.6 前進500步實驗結果長條圖 62
圖5.7 前進誤差示意圖 64
圖5.8 實際地圖所規劃路徑 66
圖5.9 實際地圖導航實驗結果 68

[1] T.Y. Li and C.C. Chang, Path Planning with Incremental Roadmap Update for Large Environments, IEEE International Conference on Robotics and Automation, May 2001.

[2] H. Van Brussel, H. Xu, and J. Vandorpe, Exact dynamic map building for a mobile robot using geometrical primitives produced by a 2D range finder, Proceeding of IEEE International Conference on Robotics and Automation, vol.1, 901-908, April 1996.

[3] 林懋瑜，無人式自走車導航與避障系統之研究，國立成功大學工程科學系碩士論文，2001.

[4] 曾華瑋，自走式機器人在部分未知環境的路徑規劃與避障，國立成功大學工程科學系碩士論文，1999.

[5] S.J. Russell, P.Norvig, Artificial Intelligence: A Modern Approach, Prentice-Hall, Inc., p.93, 1995.

[6] 梁朝琪，事件驅動式多代理者自走車導航系統，國立成功大學工程科學系碩士論文，2000.

[7] D. Langer, J.K. Rosenblatt and M. Hebert, An integrated system for autonomous off-road navigation, Proceeding of IEEE International Conference on Robotics and Automation, vol.1, 414-419, May 1994.

[8] A. Sankaranarayanan, A new algorithm for robot curve-following amidst unknown obstacles, and a generalization of maze-searching, Proceeding of IEEE International Conference on Robotics and Automation, vol.3, 2487-2494, May 1992.

[9] L. Kichul, K. Hyuntae, P. Mignon, and R. Kangyuel, Obstacle avoidance navigation using a local path planning method, Proceeding of the 35th Conference on Decision and Control, 1996.

[10] A. Stentz, Optimal and efficient path planning for partially-known environments, Proceeding of IEEE International Conference on Robotics and Automation, vol.4, 3310-3317, May 1994.

[11] A. Ollero, A. Reina, and J. Gonzalez, Map building for a mobile robot equipped with a 2D laser rangefinder, Proceeding of IEEE International Conference on Robotics and Automation, vol.3, 1904-1909, May 1994.

[12] K.Sundaraj, D.D. Aulignac, E.Mazer, A New Algorithm for computing Minimum Distance, IEEE International Conference on Intelligent Robots and Systems. 2000.

[13] T. Fraichard, J.M. Ahuactzin, Smooth Path Planning for Cars, IEEE International Conference on Robotics and Automation. 2001.

[14] P. Evangelos, P. Ioannis, Planning and Obstacle Avoidance for Mobile Robots, IEEE International Conference on Robotics & Automation, 2001.

[15] O. Khatib, Real-time Obstacle Avoidance for Manipulators and Mobile Robots, IEEE International Conference on Robotics and Automation, vol.1, 500-505, 1985.

[16] R. Brooks, Solving the Find-Path Problem by Good Representation of Free Space, IEEE Transactions on Systems Man, and Cybernetics, Vol. SMC-13, No.3, March/April 1983.

[17] D. Keirsey, E. Koch, J. McKisson, A. Meystel, and J. Mitchell, Algorithm of Navigation for a Mobile Robot, IEEE International Conference on Robotics, 574-583, March, 1984.

[18] A. Yahja, A. Stentz, S. Singh, and B.L. Brumitt, Framed-Quadtree Path Planning for Mobile Robots Operation in Sparse Environments, IEEE Conference on Robotics and Automation, May 1998.

[19] A. Suluh, T. Sugar, M. McBeath, Spatial Navigation Principles: Application to Mobile Robots, IEEE International Conference on Robotics and Automation, May 2001.