臺灣博碩士論文加值系統

本文以動態規劃方法處理低空飛行載具之路徑規劃問題。我們以飛機作為飛行載具之模型，首先討論飛機在定航速定航向與變航向之飛行模式，藉此求出飛機爬升率與迴轉半徑之限制。其次介紹Dijkstra演算法(Dijkstra’s Algorithm)與動態規劃方法之概念與精神以處理最短路徑之問題，其中Dijkstra演算法為標記修正法(Label Correcting Method)之一種特例。當最短路徑問題對應於確定性有限狀態之問題時，我們可以基於最佳性原理，利用動態規劃方法來處理最短路徑的問題，因此，我們以動態規劃方法處理低空飛行載具之路徑規劃問題。針對低空飛行載具之路徑規劃問題，由於載具以貼地方式飛行，故我們以適合載具的調整策略產生一虛擬地形(virtual terrain)，並在此虛擬地形上對載具作路徑的規劃。在僅考慮爬升率作為載具之飛行限制時，所規劃出的最佳路徑無法滿足飛行載具之轉彎行為，因此我們引入禁止路徑(forbidden path)的概念來描述載具迴轉半徑之限制，使規劃出的最佳路徑更符合載具實際飛行之行為。除此之外，我們亦提出以連續更新(successive update)配合螺旋架構(spiral scheme)的想法加快演算法之計算速度。最後，我們討論在各種不同條件下最佳路徑之模擬結果，並提出未來發展與改善之方向。

In this thesis, the method of dynamic programming is applied to deal with the path-planning problem for low-altitude flying vehicles. The motion of the airplanes is considered to model the behavior of the vehicles. The capability of flight along a straight line with constant velocity is used to deduce the rate-of-climb constraint on the possible paths. The limitations of turning at constant speeds induce the constraint of turning radius on curved paths. These physical constraints are then invoked to obtain possible paths, among which the optimal one is desired. The search of the optimal path can be categorized as the shortest path problem, for which various algorithms can be adopted. One strategy is the so-called Label Correcting Methods, among them the Dijkstra’s algorithm is a special case. On the other hand, since a shortest path problem is equivalent to a deterministic finite-state problem, it can be solved by the method of dynamic programming (DP), which is based on the Principle of Optimality. Due to its flexibility, the DP method can accommodate more complicated scenario in which the stochastic process may be involved. For a given terrain, the flight paths are envisioned to lie on the corresponding virtual terrain, which reflects the low altitude feature of the flight. After discretization of the terrain, the notions of forbidden points and forbidden paths are introduced to realize the rate-of-climb constraint and the constraint of turning radius, respectively. To expedite the algorithm, the concepts of the successive update and the spiral scheme are proposed. The simulation results show that the methodology discussed in the thesis can efficiently provide the optimal paths of a low-altitude flying vehicle under various conditions, which may have potential applications in designing the flight paths for missiles or bombers.

第一章 緒論
1.1 研究動機................................................1
1.2 文獻回顧................................................1
1.3 內容概述與論文架構......................................2
第二章 飛行動力學與飛行限制
2.1 定航向定航速之飛行模式..................................5
2.1.1 水平飛行(level flight)..............................7
2.1.2 爬升(climb).........................................8
2.2 變航向之飛行模式.......................................10
2.2.2 拉起 (pull-up).....................................12
2.2.3 倒飛(pull-down)....................................13
2.2.4 最小迴轉半徑.......................................14
第三章 路徑規劃之演算法
3.1 Dijkstra演算法(Dijkstra’s Algorithm)..................17
3.1.1 Dijkstra演算法理論.................................18
3.1.2 實例...............................................19
3.2 標記修正法(Label Correcting Method)....................22
3.2.1 標記修正法理論.....................................22
3.2.2 標記修正法分類.....................................24
3.3 動態規劃(Dynamic Programming)方法......................25
3.3.1 動態規劃理論.......................................25
3.3.2 實例...............................................28
第四章 低空飛行載具之路徑規劃
4.1 低空飛行載具之路徑規劃基本問題.........................31
4.1.1 虛擬地形(virtual terrain)..........................32
4.1.2 禁止點(forbidden point)與禁止矩陣(forbidden matrix)32
4.1.3 移動(move)與映射(map)..............................33
4.1.4 距離函數(distance function)........................34
4.2 動態規劃演算法.........................................35
4.3 載具彎道飛行限制之路徑規劃問題.........................38
4.3.1 禁止路徑(forbidden path)...........................39
4.3.2 擴增成本張量(extended cost tensor).................40
4.3.3 動態規劃演算法.....................................42
4.4 連續更新(successive update)與螺旋架構(spiral scheme)加速
動態規劃方法...........................................45
4.4.1 連續更新(successive update)........................46
4.4.2 螺旋架構(spiral scheme)............................48
第五章 結果與討論
5.1 虛擬地形之模擬結果.....................................50
5.2 低空飛行載具之路徑規劃.................................53
5.3 爬升率與最小迴轉半徑對最佳路徑之影響...................55
5.3.1 爬升率.............................................55
5.3.2 最小迴轉半徑.......................................57
5.4 連續更新與螺旋架構對演算法計算速度之影響...............60
5.5 距離函數改變對最佳路徑之影響...........................64
第六章 結論

[1] Anderson, J.D. ,”Introduction to Flight” , McGraw-Hill
International,1989
[2] Bertsekas, D.P. ,”Dynamic Programming and Optimal
Control”, Athena Scientific,1995
[3] Dijkstra, E.W. ,”A Note on Two Problems in Connexion with
Graphs”, Numer. Math. ,Vol. 1,pp. 269-271,1959
[4] Dreyfus, S.E. ,and Law, A.M. “The Art and Theory of
Dynamic Programming”, Academic Press Inc. ,1977
[5] Gifford, K.K. ,and Murphy, R.R. ,”Incorporating Terrain
Uncertainties in Autonomous Vehicle Path Planning”, Proc.
IROS 96,pp. 1134-1140, 1996
[6] Houghton, E.L. ,and Carruthers, N.B. ,”Aerodynamics for
Engineering Students”, Edward Arnold,1982
[7] Kermode, A.C. ,”Mechanics of Flight”, Addition Wesley
Longman Limited,1972
[8] Kwok, K.S. ,and Driessen, B.J. ,”Path Planning for Complex
Terrain Navigation Via Dynamic Programming”, Proc. of
American Control Conference, S.D., Cal., pp. 2941-2944,1999
[9] Lam, K.P. ,and Tong, C.W. ,”Connectionist Network for
Dynamic Programming Problems”, IEE Proc.-Comput. Digit.
Tech. ,Vol. 144, No. 3,pp. 163-167,1997
[10] Larson, R.E. ,and Casti, J.L. ,”Principles of Dynamic
Programming─PartⅡ Advanced Theory and applications”,
Marcel Dekker Inc. ,1982
[11] Lewis, F.L. ,and Syrmos, V.L. ,”Optimal Control”, John
Wiley & Sons,1995
[12] Ravindran, A. ,and Phillips, D.T. ,and Solberg, J.J. ,”
Operations Research─Principles and Practice”, John Wiley
& Sons,1987
[13] Seckel, E. ,”Stability and Control of Airplanes and
Helicopters”, Academic Press Inc. ,1964
[14] Gerald, C.F. ,and Wheatley, P.O. ,”Applied Numerical
Analysis”, Addison-Wesley Publishing Company,1994
[15] 王懷柱, 揭開飛行的奧秘, 全華科技, 2000
[16] 劉豹, 現代控制理論, 科技圖書, 1992
[17] 施澄鐘, 數值分析, 松崗圖書, 1989