臺灣博碩士論文加值系統

本文利用機動車輛移動的觀念與可表示高低起伏地形之方塊式(voxel base)資料結構，來求出機動車輛(mobile vehicles)於三維空間中之二次曲面上的最佳行進路徑之搜尋演算法；為了確保選擇的機動車輛預置目標點與雷達站之間可互相通視(light of sight)，提出以方塊式之資料結構為基礎的兩點間通視演算法。論文中以東部某地區為實例，建構此區域之三維電子地圖資料庫(database of three-dimensional electronic map)，再應用多方向性迷宮三維網格圖最短路徑演算法，配合兩點間之通視演算法及各種機動車輛移動時所需考量的限制條件之權重，於該自由空間中計算之總成本，進而求得機動車輛之最佳行進路徑。另外，本文整合三維電子地圖資料庫與全球衛星定位系統，建構三維電子地圖上之即時導航系統以提昇機動車輛調度管理之效率。


關鍵字：方塊式資料結構，多方向性迷宮(最短路徑)搜尋演算法，全球衛星定位系統，通視，網格圖，機動車輛

A novel path-planning method for mobile vehicles or stations among obstacles of arbitrary shape is presented. This method includes three parts. In the first part, a linear-interpolation scheme is introduced to create a database of three-dimensional electronic map based on a military map. In the second part, a Euclidean geometry scheme is applied to determine the light of sight that defines the relation of any pair of voxels. The last part, a higher geometry maze routing algorithm is introduced to conduct an optimal path-planning method in the workspace. The obtained optimal path is collision free path with minimum total cost. Comparing with other research based on vector data structure, this paper adopts a novel voxel-based data structure to complete the optimal path-planning for mobile vehicles. In addition, the Global Positioning System is applied to the database of three-dimensional electronic map for real-time navigation as well.

Keyword：Global Positioning System, higher geometry maze routing algorithm, light of sight, mobile vehicles, raster map, voxel-based data structure

第一章 緒論 1
第二章 三維電子地圖資料庫之建置 5
2.1 方塊式結構三維電子地圖資料庫之建構 6
2.2 原始資料之細分化 7
2.3 自由空間之定義 8
2.3.1可通行之道路 9
2.3.2 其他限制條件 10
第三章 通視(LIGHT OF SIGHT)演算法 11
3.1通視理論推導與演算法 12
3.2 範例 14
3.2.1 不可通視之範例 14
3.2.2 可通視之範例 15
第四章 機動車輛最佳行進路徑選擇 16
4.1 單組最短路徑搜尋 16
4.1.1 演算法 16
4.1.2範例 16
4.2多組最佳行進路徑搜尋 16
4.2.1 演算法 17
4.2.2 範例 18
第五章 三維電子地圖與全球衛星定位系統之整合與應用 20
5.1 全球衛星定位系統簡介 20
5.2 座標轉換 22
5.3 三維電子地圖上整合全球衛星定位系統之即時導航系統 24
第六章 結論與建議 29

[1] Ki-Yin Chang, Gene Eu Jan, and Ian Parberry, “A Method for Searching Optimal Routes with Collision Avoidance on Raster Charts,” The Journal of Navigation, Vol. 56, No. 3, 2003, pp. 371-384.
[2] S. N. Gewali and Ioannis G. Tollis, “Path Planning in the Presence of Vertical Obstacles,” IEEE Transactions on Robotics and Automation, Vol. 6, No. 3, pp. 331-341, June 1990.
[3] Gene Eu Jan, Ming-Bo Lin and Yung-Yuan Chen, “Computerized Shortest Path Searching for Vessels,” Journal of Marine Science and Technology, Vol. 5, No. 1, June 1997, pp. 95-99.
[4] Gene Eu Jan, and Ki-Yin Chang, “An Improved Lee’s Algorithm on Electronic Maps,” 2002 International Computer Symposium, National Dong Hwa Univ., Hualien, Taiwan, pp. 776- 786, Dec. 2002.
[5] Gene Eu Jan, Ki-Yin Chang and Jazz Wu, “The Planning of a 3D Shortest Path on a Volume,” Trans. on AASRC, Vol. 35, No. 2, 2003, pp. 197-202.
[6] E. D. Kaplan, “Understanding GPS: Principle and Application,” Artech House, London, 1996.
[7] C. Y. Lee, “An Algorithm for Path Connections and Its Applications,” IRE Trans. on Electron. Computer, Vol. EC-10, pp. 346- 365, Sept. 1961.
[8] Y. L. Lin, Y. C. Hsu and F. S. Tsai, “Hybrid Routing,” IEEE Trans. on CAD, pp. 151-157, Feb. 1990.
[9] K. Mikami and K. Tabuchi, “A Computer Program for Optimal Routing of Printed Circuit Connections,” IFIPS Proc., Vol., H47, pp. 1475-1478, 1968.
[10] B. W. Parkinson, “ History and Operation of NAVSTAR, The Global Positioning System,” IEEE Transcation on Aerospace and Electronic Systems, Vol. 30, No 4, pp. 1143~1162, Oct., 1994.
[11] J. L. Dí-az-de León S. and J. H. Sossa A., “Automatic Path Planning for a Mobile Robot Among Obstacles of Arbitrary Shape,” IEEE Trans. On Systems, Man. And Cybernetics, Vol. 28, No. 3, June 1998.
[12] O. Takahashi and R. J. Schilling “Motion Planning in a Plane Using Generalized Voronoi Diagrams,” IEEE Transactions on Robotics and Automation, Vol. 5, No. 2, pp. 143-150, 1989.
[13] 史習平，”汽車導航系統DIY”，交通部運輸研究所，1997。
[14] 何志宏、張邵卿、許文達，”利用DGPS差分式全球衛星定位系統建立最短行車導引控制系統之研究”，運輸計劃季刊，23卷4期，民國83年12月。
[15] 安守中， ”GPS全球衛星定位系統入門”， 全華科技出版社，2002。
[16] 林宏正，”GPS的應用及未來的發展”，新電子科技，第一百五十八期，pp. 188-192，1999。
[17] 林志鴻、陳春益、林育俐、曾志強，”委外校車路線規劃問題之研究”，運輸計劃季刊，31卷2期，民國91年6月。
[18] 周天穎，”地理資訊系統理論與實務”，儒林圖書出版社，民國92年02月。
[19] 洪必松，”三度空間與二次曲面之最短路徑規劃及動態追截”，國立台灣海洋大學資訊科學研究所碩士論文，民國九十一年七月。
[20] 洪瓊萍，”當GIS遇到GPS”，新電子科技，第一百五十八期，pp. 185-187，1999。
[21] 施保旭，”地理資訊系統”，儒林圖書有限公司，2001年11月第三版二刷。
[22] 曾清涼、儲慶美，”GPS衛星測量原理與應用”，成功大學衛星資訊研究中心，1999。
[23] 黃晟中，”結合GPS與行動通訊系統之無線電定位技術研究”，國立台灣海洋大學導航與通訊研究所碩士論文，民國九十一年十二月。
[24] 黃華尉，”TWD97與TWD67二度TM座標轉換之研究”，成功大學測量工程學系，民國90年。
[25] 詹亨文，”整合GSM於全球衛星定位系統之多功用應用程式介面設計”，逢甲大學電子工程所，民國91年8月。
[26] 詹景裕、張啟隱、汪一帆，”網格圖上任意形狀機器人之最短路徑規劃”，九十一年度年會暨精密機械製造研討會，Taiwan, Nov. 2002, pp. 120~130.
[27] 詹景裕、張啟隱、汪一帆，”網格圖上可旋轉的任意形狀機器人之最短路徑規劃”，九十一年度年會暨精密機械製造研討會，Taiwan, Nov. 2002, pp. 131~140.
[28] 劉佳峰，”結合 GPS 與 GIS 技術建立之汽車導航系統”，中央大學資訊管理研究所，民國85年6月。
[29] 鄭昆霖，”在PDA上整合GPS與GIS之導航系統”，逢甲大學資訊工程所，民國91年6月。
[30] 謝權信，”智慧型e化車輛導航系統研究”，中華大學機械與航太工程研究所，民國91年6月。
[31] http://www.iot.gov.tw/chinese/lib/transinfo/index.htm，交通部運輸研究所統計資料。
[32] http://www.btc.com.tw/big-5/2-11-gps_gprs.htm，英群企業產品介紹資料。