飛行器於二次曲面之最佳路徑

Optimal Chasing and Path Planning Algorithms for Aircrafts in Quadric Surface

詹景裕(Gene-Eu Jan) ； 洪必松(Bi-Sung Hung) ； 蘇健民(Chien-Min Su) ； 林豐裕(Feng-Yu Lin)

《航空太空及民航學刊.系列B》 39卷2期 (2007/10) Pp. 115-122

https://doi.org/10.6124/JAAA.200710_39(2).09

摘要

本文提出新的方法解決二次曲面中單組、多組及即時追截路徑規劃問題，藉由有限空間中轉換?二次曲面的觀念，利用高維幾何迷宮式搜尋法則計算有限空間中各個方塊的到達時間，並運用二次曲面的資料結構，最後達到最佳路徑規劃之目的。本文所提出之單組最佳路徑規劃演算法，其時間與空間複雜度均?O(N)；多組最佳路徑規劃演算法中，?了避免碰撞的發生，則加入飛行器領域的觀念，以space-marking method標示各飛行器之飛行器領域，藉使均能以安全距離相互通過，其時間複雜度?O(qN)；即時追截演算法，假設目標物與追截體的速度均?固定值，先利用前置量線性預估目標物的未來行進路徑，找出追截體可能追截到目標物的路徑，再依據追截體與目標物速度比算出追截體實際的追截路徑，其時間複雜度則?O(N^2 α)，其中N?有限空間中之方塊數，q?飛行器的數目，α?追截體與目標物之速度比。

關鍵字

二次曲面 ； 路徑規劃 ； 飛行器領域 ； 追截

並列摘要

This paper presents some novel methods to solve optimal chasing and path planning problems for aircraft motion in the quadric surface. The optimal path searching algorithm in the quadric surface with O(N) of time and space complexities is based on the higher geometry maze router, where N is the number of voxels in the volume. Furthermore, the proposed algorithm is extended to the optimal path searching for multiple pairs based on the concept of the aircraft domain and space-marking method to avoid collision and the chasing system in the quadric surface with the time complexities of O(qN) and O(N^2 α), respectively, where q is the number of the aircrafts and α is the relative speed ratio of the chaser to target. For the chasing system, it is assumed that the chaser and target have different constant speeds and the chaser should be faster than the target to catch up. In addition, it is useful to foresee the beforehand path of the target if the chaser can detect its current position.

並列關鍵字

Aircraft domain ； Chasing ； Path planning ； Quadric surface