三維電子地圖上機動車輛最佳路徑規劃與GPS之整合應用

The Optimal Path-Planning for Mobile Vehicles with GPS on 3-D Electronic Maps

張啟隱(Ki-Yin Chang) ； 詹景裕(Gene-Eu Jan) ； 羅文泉(Lsword Lou) ； 尹治平(Zhi-Ping Yin)

《航空太空及民航學刊.系列B》 38卷1期 (2006/04) Pp. 63-70

https://doi.org/10.6124/JAAA.200604_38(1).08

摘要

本文利用機動車輛移動的觀念與可表示高低起伏地形之方塊式(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.

並列關鍵字

Global positioning system ； Higher geometry maze routing algorithm ； Light of sight ； Mobile vehicles ； Raster map ； Voxel-based data structure