工業界為了提高產能﹑提昇品質和加強競爭力，在成本的許可下往往會採用自動化來替代人工作業，尤其在全自動化無人工廠內同時使用多個搬運車或機器人的場合很多，當很多機器人同時應用在同一個作業系統時，就產生了碰撞問題，因此有許多人致力於機器人的路徑規劃研究，但在多個機器人避碰研究領域上，通常只會考慮多個機器人的協調避碰路徑，而很少探討在多個機器人之間做最有效率的運動軌跡規劃，導致於在多個機器人整體應用效率不高，實用性亦不大。因此本研究提出一個有效率的方法來解決多個自走式機器人的碰撞問題並改善其效率。本論文的架構，為了探討多個自走式機器人在時間上的避碰規劃，分成單一和多個自走式機器人路徑規劃兩步驟進行探討；首先配合使用迪傑斯托(Dijkstra)演算法，考慮每一部自走式機器人的最短避碰路徑，找出介於起點到終點位置間的最短路徑；接著將各個自走式機器人路徑加進來，建構一軌跡資料結構，探討彼此間的路徑協調。本研究中，為廣泛應用在各種有障礙顧慮環境下，考慮將障礙物輪廓以多邊形來表示，且障礙物的資料是在進行自走式機器人避碰檢測前已先行確定。最後將以電腦模擬來驗證此法的可行性，計算各個自走式機器人行程減少及總體程序節省的時間，同時規劃出以最佳時間為目標的路徑程序組，以提高工廠自動化的效率與競爭力。

In this thesis we proposed an efficient method to solve the traffic coordination on multiple AGVs path planning task. Firstly the shortest route of each AGV between starting and terminal point without collision is solved by proposed Dijkstra algorithm.
For coordinating all the AGV in the traffic route model, the efficient and detail data structure algorithm is proposed and discussed. The data structure is called Linking-Occupation-Table (LOT), which records the identified number, specification, route information and collision prediction of each AGV. And then, the LOT of each AGV is built and prepared for the followed simulation processes as verification. The LOT can also be noted as AGV route traffic controller command file.
After computer simulation by using Simple++, the optimal time schedule of each AGVs'' route is thus obtained and verified. The current research proposes and demonstrates an efficient method in the field of multiple AGV traffic coordination and time scheduling planning task, it can be applied to increase production competition of the factory automation.

目錄
中文摘要I
英文文摘要Ⅱ
目錄Ⅳ
圖目錄Ⅵ
表目錄Ⅸ
第一章 前言1
1.1 機器人與自動化1
1.2 研究動機3
1.3 文獻回顧4
1.3.1 集中法在多個機器人避碰研究方面4
1.3.2 解耦法在多個機器人避碰研究方面:5
1.4 論文架構6
第二章 相關基本理論8
2.1 架構空間8
2.2 網格分割法9
2.3 迪傑斯托(Dijkstra)理論10
2.4 連結工作表12
第三章 避碰模型建立13
3.1 建構環境相關資訊13
3.2 產生所有可能路徑13
3.3 最短路徑搜尋16
3.4 避碰模型建立流程圖19
第四章 協調軌跡規劃24
4.1 建構車輛相關資訊24
4.2 資料結構建立24
4.3 碰撞情形26
4.4 判斷碰撞的方法27
4.4.1判斷對撞的方法28
4.4.2判斷追撞的方法28
4.5 軌跡協調演算法29
4.6 動態模擬31
4.7 軌跡協調流程圖31
第五章 範例與討論39
5.1 整合架構圖39
5.2 範例一41
5.3 討論49
5.4 範例二56
第六章 結論與展望61
6.1 結論61
6.2 展望62
參考文獻63
圖目錄
圖2.1 以架構空間來表示移動距離體與其他物體間之關係8
圖2.2 由10*10=100個點集合所組成的網格空間9
圖2.3 連結工作表資料結構12
圖3.1 依序將可通行點重新排列並賦予名稱14
圖3.2 扣除障礙特徵點後所有可通行路面15
圖3.3 可通行路線及每個節點間的距離17
圖3.4 避碰模型流程圖19
圖3.5 3D工作環境和車輛初始條件示意圖20
圖3.6 AutoCAD下2D工作環境建構圖和放大圖20
圖3.7 所有可通行路線21
圖3.8 黑色車路線圖21
圖3.9 紅色車路線圖21
圖3.10 綠色車路線圖22
圖3.11 藍色車路線圖22
圖3.12 無人搬運車路徑圖22
圖4.1 線段連結工作表資料結構25
圖4.2 節點連結工作表資料結構25
圖4.3 AGV#1 通過節點時間圖25
圖4.4 線段連結工作表26
圖4.5 節點連結工作表26
圖4.6 碰撞情況一27
圖4.7 碰撞情況二27
圖4.8 碰撞情況三27
圖4.9 碰撞情況四27
圖4.10 軌跡協調流程圖32
圖4.11 三輛車路線圖33
圖4.12 線段和節點連結工作表34
圖4.13 t = 0s時模擬情形37
圖4.14 t = 100s時模擬情形37
圖4.15 t = 150s時模擬情形38
圖4.16 t = 431s時模擬情形38
圖5.1 協調多台無人搬運車演算法之架構圖40
圖5.2 實驗室3D環境示意圖41
圖5.3 實驗室2D環境建構圖42
圖5.4 實驗室所有避碰路線圖42
圖5.5 AGV#1路線圖43
圖5.6 AGV#2路線圖43
圖5.7 AGV#3路線圖43
圖5.8 AGV#4路線圖43
圖5.9 AGV#5路線圖43
圖5.10 總合路線圖43
圖5.11 路徑程序圖44
圖5.12 t = 0s時模擬情形46
圖5.13 t = 55.5s時模擬情形46
圖5.14 t = 79.8s時模擬情形47
圖5.15 t = 142.7s時模擬情形47
圖5.16 t = 309s時模擬情形48
圖5.17 交通示意圖56
圖5.18 t = 0s時鳥瞰圖57
圖5.19 t = 5s時鳥瞰圖58
圖5.20 t = 10s時鳥瞰圖58
圖5.19 t = 15s時鳥瞰圖59
圖5.20 t = 20.65s時鳥瞰圖59
表目錄
表3.1 從起點1至終點6的鄰接矩陣18
表3.2 從任意起點至任意終點的軌跡矩陣18
表4.1 三輛車模擬結果36
表5.1 無人搬運車工作條件41
表5.2 paper[18]三輛車模擬之結果50
表5.3 本研究三輛車模擬之結果51
表5.4 paper[18]五輛車模擬之結果51
表5.5 本研究五輛車模擬之結果51
表5.6 AGV#1速度為0.1m/s時模擬結果52
表5.7 AGV#1速度為0.09m/s時模擬結果52
表5.8 AGV#1速度為0.08m/s時模擬結果53
表5.9 AGV#1速度為0.07m/s時模擬結果53
表5.10 AGV#1速度為0.06m/s時模擬結果53
表5.11 AGV#1速度為0.05m/s時模擬結果54
表5.12 AGV#1速度為0.1m/s且停留節點為起點之模擬結果55
表5.13 15m/s（約54km/hr）交通模擬結果57
表5.14 20m/s（約36km/hr）交通模擬結果60
表5.15 10m/s（約72km/hr）交通模擬結果60

參考文獻
[1] J.T. Schwartz, M. Sharir, On the ''piano movers'' problem: III. Coordinating the motion of several independent bodies: The special case of circular bodies moving amidst polygonal obstacles, International Journal of Robotics Research 2 (3) (1983) 46-75.
[2] M. Sharir, S. Sifrony, Coordinated motion planning for two independent robots, in: Proceedings of the Fourth ACM Symposium on Computational Geometry, 1988.
[3] P. Tournassoud, A strategy for obstacle avoidance and its application to multi-robot systems, in: Proceedings of the IEEE International Conference on Robotics and Automation, San Francisco, CA, USA, 1986,pp. 1224-1229.
[4] J. Barraquand, J. -C. Latombe, A Monte-Carlo algorithm for path planning with many degrees of freedom, in: Proceedings of the IEEE International Conference on Robotics and Automation, Cincinnati, OH, USA, 1990. pp. 1712-1717.
[5] J. Barraquand, J. -C. Latombe , Robot motion planning: A distributed representation approach, International Journal of Robotics Research 10 (6) (1991) 628-649.
[6] B.H. Lee and C.S.G. Lee , Collision-free motion planning of two robots, IEEE Trans. Sys. & Cyber. , Vol.SMC-17, No 1, pp.21-32, 1987.
[7] R. A. Basta, R. Mhrotra and M. R. Varanasi , Collision detection for planning collision-free motion of two robot arms,Proc. IEEE Int. Conf. Robot. & Automat. , pp.638-640, 1988.
[8] K. Shin and Z. Bien ,Collision-free trajectory planning for two robot arms,Robotica,Vol.7,pp.205-212,1989.
[9] M. Erdmann, T. Lozano-Perez, On multiple moving objects, in: Proceedings of the IEEE International Conference on Robotics and Automation, San Francisco, CA, USA, 1986, pp. 1419-1424.
[10] S.J. Buckley, Fast motion planning for multiple moving robots, in: Proceedings of the IEEE International Conference on Robotics and Automation, Scottsdale, Arizona, USA, 1989, pp. 322-326.
[11] M.Z. Yannakakis, C.H. Papadimitriou, H.T. Kung, Locking policies: Safety and freedom for deadlock,in: Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979, pp. 286-297.
[12] P.A. O''Donnell, T Lozano-Perez, Deadlock-free and collision-free coordination of two robotic manipulators, in: Proceedings of the IEEE International Conference on Robotics and Automation, Scottsdale, Arizona, USA, 1989, pp. 484-489.
[13] Z. Bien, J. Lee, A minimum-time trajectory planning method for two robots, IEEE Transactions on Robotics and Automation 8 (3) (1992) 414-418.
[14] C. Chang, M.J. Chung, B.H. Lee, Collision avoidance of two robot manipulators by minimum delay time, IEEE Transactions on Systems Man, and Cybernetics 24 (3) (1994) 517-522.
[15] Y.H. Liu, S. Kuroda, T. Naniwa, H. Moborio, S. Arimoto, A practical algorithm for planning collision-free coordinated motion of multiple mobile robots, in: Proceedings of the IEEE International Conference on Robotics and Automation, Scottsdale, Arizona,USA, 1989, pp. 1427-1432.
[16] D.D. Grossman, Traffic control of multiple robot vehicles, IEEE Journal of Robotics and Automation 4 (5) (1988) 491-497.
[17] S. Kato, S. Nishiyama, J. Takeno, Coordinating mobile robots by applying traffic rules, in: Proceedings of the IEEE IROS ''92,Raleigh, NC, USA, July 1992.
[18] J.-H. Lee, B.H. Lee, M.H. Choi, J.D. Rim. K.-T Joe, H. Park, A real time traffic control scheme for a multiple AGV system, in:Proceedings of the IEEE International Conference on Robotics and Automation, Nagoya, Japan, 1995, pp. 1625-1630.
[19] J. Wang, Operating primitives supporting traffic regulation and control of mobile robots under distributed robotic systems, in: Proceedings of the lEEE International Conference on Robotics and Automation, Wagoya, Japan, 1995, pp. 1613-1618.
[20] J. Wang, S. Premvuti, Distributed traffic regulation and control for multiple autonomous mobile robots operating in discrete space,in: Proceedings of the IEEE International Conference on Robotics and Automation, Nagoya, Japan, 1995, pp. 1619-1624.
[21] A.-H. Cai, T. Fukuda, F Arai, T. Ueyama. A. Sakai, Hierarchical control architecture for cellular robotic system - simulations and experiments, in: Proceedings of the IEEE International Conference on Robotics and Automation, Nagoya, Japan, 1995, pp. 1191-1196.
[22] K. Souccar, K.A. Grupen, Distributed motion control for multiple robotic manipulators, in: Proceedings of the IEEE International Conference on Robotics and Automation, Mineapolis, USA, 1996.
[23] T.Lozano-Perez,and M.A.Wesley,A algoritnm for planning collision free paths among polyhedral obstacles,Commu. Of the ACM, Vol.22, No. 10 ,Oct.1979.
[24] J.Clatombe, Robot motion planning, Kluwer Academic Publishers, USA, Second printing,1991.
[25] J.P. Laumond, P.E.Jacobs, M.Taix, and R.M.Murray, A motion planner for nonholonomic mobile robots, IEEE. Trans Robotics and Automation, vol.10, no.5,Oct.1994,pp.577-593.
[26] O.Takahashi and R.J.Schilling, Motion planning in a plane using Generalized Voronoi Diagrams, IEEE.Trans Robotics and Automation, vol.5, no.2,1989,pp.143-150.
[27] Y.K. Hwang and Narendra Ahuja, A potential Field approach to path planning, IEEE.Trans Robotics and Automation, vol.8, no.1, February.1994,pp.23-32.
[28] J.O. Kim and P.K. Khosla, Real-time obstacle avoidance using harmonic potential functions , IEEE. Trans Robotics and Automation, vol.8, no.3, June.1992,pp.338-349.
[29] E. Rimon and D.E. Koditschek , Exact robot navigation using artificial potential functions, IEEE. Trans Robotics and Automation , vol.8, no.5, October 1992,pp.501-518.
[30] A. Zelinsky , Amobile robot exploration algorithm , IEEE. Trans Robotics and Automation, vol.8, no.6 , December 1992,pp.707-717.
[31] Y.H. Liu and S. Arimoto , Find in the shortest path of a disc among polygonal obstacles using a radius independent graph, IEEE. Trans Robotics and Automat"ion, vol.11, no.5, October 1995,pp.682-691.
[32] Y.H.Liu and S.Arimoto,Path planning using a tangent graph for mobile robots among polygonal and curved obstacles, Int.J.Robotics Research, Vol.11,No. 4, August 1992, pp.376-382.
[33]陳志鏗,鄭惟仁,車輛型機器人路徑規劃與路徑跟隨之研究, 中國機械工程學會第十三屆論文集, pp. 417-424.
[34]鄭璧瑩,劉德進,兼顧能源消耗評估的最佳路線規劃,中國機械工程學會第十四屆論文集, pp. 283-290.
[35]資料結構-使用C語言,蔡明志編著,松崗電腦圖書資料股份有限公司.
[36]林士文,機器手臂與活動障礙物間的避碰分析,交通大學機械研究所碩士論文,指導教授,鄭璧瑩,陳大潘,June 1994,pp. 6-14.