進階搜尋


 
系統識別號 U0026-0812200913374015
論文名稱(中文) 多目標巡視之飛行路徑規劃研究
論文名稱(英文) The Study of Flight Path Planning for Multiple Target Visitations
校院名稱 成功大學
系所名稱(中) 航空太空工程學系碩博士班
系所名稱(英) Department of Aeronautics & Astronautics
學年度 95
學期 2
出版年 96
研究生(中文) 張文贏
研究生(英文) Wen-Ying Chang
學號 P4890102
學位類別 博士
語文別 英文
論文頁數 116頁
口試委員 口試委員-杲中興
指導教授-蕭飛賓
指導教授-許棟龍
口試委員-楊憲東
口試委員-何慶雄
口試委員-詹劭勳
召集委員-張帆人
口試委員-馬德明
口試委員-卓大靖
中文關鍵字 啟發式搜尋  飛行路徑規劃  路徑平滑化  目標巡視  軌跡產生  多層級  多重解析度  動態規劃 
英文關鍵字 target visitation  path smoothing  multi-resolution  hierarchical method  flight path planning  Dynamic programming  heuristics  trajectory generation 
學科別分類
中文摘要 本研究提出使用快速圖形搜尋演算法之方法,在三度空間真實地形上找尋通過數個目標點(導航點)之最佳可行飛行路徑。這個求解最佳路徑的問題包含了以下數個路徑規劃重點:飛行安全距離、真實飛行限制、飛機性能限制以及通過目標點之順序。
求解通過多目標點之飛行路徑之前,我們首先求解二點間之飛行路徑,求得之飛行路徑必需滿足許多限制條件以確保飛行安全及飛行效率。在飛行安全考量下,充分的安全飛行高度及水平安全距離是絕對必需的。實際上,飛機之起降方向、爬升率限制、轉彎率限制、燃料消耗比等亦都是飛行路徑規劃所必需考慮的。我們藉由建立虛擬地形於真實地形上作為搜尋空間,來包含真實飛行條件及飛機性能限制於路徑規劃的問題中,同時飛行安全考量及起飛降落階段亦可包含進來。除此之外,虛擬地形的建立也有效地將三維的搜尋空間減至二維空間,如此可以大大地減少演算法的運算量。然而在粗糙且 大部份的地形高度高於巡航高度的地形上,虛擬地形的建立可能使所求得路徑有上下起伏頻繁的缺點。另外由於空間格點的離散化,數值無差別(digital indiscrimination)的問題也將產生。因此,我們提出數個計算快速僅需不到一秒的後處理方法來克服這些問題。對於山谷間飛行之特殊任務需求,我們亦提出無因次之燃料消耗比來滿足此需求。如果爬升越過障礙物比水平轉彎繞過障礙物所消耗之燃料還要多,演算法將會選擇同高度之水平轉彎繞過障礙物,如此一來飛行路徑之縱向高度平滑度亦將獲得提升。藉由使用多重解析度(多層級)地形及快速啟發式搜尋法我們己經成功並有效地降低了演算法的計算時間,並且模擬結果顯示此二點間飛行路徑演算法是可行的。
接下來,我們擴展此二點間路徑演算法求解通過多目標點之飛行路徑問題。特別地,在求解多目標點之飛行路徑問題上,不僅僅是各路徑線段必需考量轉彎率限制,各路徑線段之連接點處亦需考慮該限制。此一複雜問題可以藉由使用虛擬地形、多重解析度及快速啟發式搜尋得到有效的解決。在決定通過目標點之最佳順序時,連接點處之轉彎率限制將被解除,如此將有益於較快求解距離矩陣(distance matrix),而求得具有最短總路徑長度之目標通過順序排列。求得之飛行路徑品質可進一步藉由利用數個快速後處理方法來獲得改善,模擬結果顯示我們的演算法是可以實行的,且其計算時間是可以接受的。
英文摘要 This study presents a method, using a fast graph-search algorithm, of finding a feasible flight path traversing multiple targets (waypoints) above a three-dimensional (3-D) real terrain map for air vehicle. This problem involves the flight safety clearance, the real flight constraints, the performance limits of the air vehicle, and the order of target visitation.
We deal with this problem by solving two-point path planning problem at first. The flight path must satisfy the many constraints required to make the flight safe and efficient. The considerations of sufficient safe altitude and horizontal distance are indispensable in flight safety concerns. In practice, the preferred directions of take-off/landing, the limits of climbing/turning rates, and the fuel consumption ratio should also be taken into account. We construct a virtual terrain as a search space above the real terrain, to take into account real flight conditions and the limitations of the vehicle’s performance. The safety concerns of flight path and the phase of take-off and landing are also included. The idea of a virtual terrain could also eliminate a significant amount of search space, from 3-Dimensions to 2-Dimensions, which takes much less computational time, but which may have a shortcoming in rugged terrain where most path points are higher than the cruise altitude. Additionally, the digital indiscrimination problem will show up when discretization is applied. Hence we propose further post processes, which take less than a second with no extra computational load, to overcome these problems. A dimensionless fuel consumption ratio between climbing and level-turn is proposed to deal with the case of level flight between valleys. If climbing requires greater fuel consumption than taking a level turn, the algorithm chooses the level altitude flight path, hence improving the vertical smoothness of the flight. Using all these methods, including multi-resolution terrain and a fast searching method using a heuristic, we have successfully reduced the computational time to an acceptable level, and the simulation results show that our two-point algorithm is feasible.
We next extend our two-point algorithm to solve the multi-point path planning problem. Particularly, the turning rate limit should be considered not only in each path segment itself but also at each junction between any two sequential path segments. This complex problem can be solved efficiently by utilizing both the heuristic and hierarchical schemes in a pre-constructed virtual terrain as well. Furthermore, to determine the optimal order of target visitation, the turning rate constraint at the junctions is relaxed while the distance matrix is computed. Subsequently, the order permutation associated with the minimum total distance is calculated. The quality of the planned path is improved by several fast post-process methods. The experimental simulation results showed that our algorithm is practical with an acceptable computational time.
論文目次 致謝 i
摘要 iii
Abstract v
Abstract in Chinese of Each Chapter vii
第一章 緒論 viii
第二章 飛行路徑規劃之考量因素 x
第三章 飛行路徑規劃之研究方法 xi
第四章 演算法及路徑品質之改良 xiii
第五章 模擬結果與討論 xv
第六章 結論 xvi
Contents xviii
List of Tables xxi
List of Figures xxii
Nomenclature xxv
Chapter 1 Introduction 1
1.1 Motivations and Objectives 1
1.2 Problem Statement 3
1.3 Literature Review 5
1.3.1 Research on two-point path planning problem 5
1.3.2 Research on multi-point path planning problem 8
1.4 Statement of Contributions 11
Chapter 2 Considerations in Flight Path Planning 13
2.1 Performance Limits of the Air Vehicle 14
2.2 Cost Function 17
2.3 Real Flight Constraints 18
Chapter 3 Methodology for Flight Path Planning 20
3.1 Discretization 20
3.2 Digital Terrain Elevation Map (DTEM) 24
3.3 Definition of Search Space 26
3.4 Construction of Virtual Terrain (Terrain Pre- process) 28
3.4.1 Vertical and horizontal clearance for flight sfety 29
3.4.2 Take-off and landing phases 31
3.5 Definition of Graph Structure 35
3.6 Review of Graph-search Algorithms 36
3.6.1 Dijkstra’s algorithm 36
3.6.2 A* algorithm 38
3.6.3 Dynamic programming method 39
3.7 Function Definition of Flight Path Planning 41
3.7.1 Forbidden matrix 41
3.7.2 Move and mapping 42
3.7.3 Distance function 43
3.7.4 Admissible set 44
3.7.5 Extended cost tensor and optimal move tensor 48
3.8 Flight Path Planning Algorithm 50
3.8.1 Two-point flight path generation 51
3.8.2 Multi-point flight path generation 53
Chapter 4 Improvements of Algorithm and Path Quality 60
4.1 Reduction of Search Space 60
4.1.1 Introduction 60
4.1.2 Hierarchical scheme (multi-resolution) 61
4.1.3 Heuristic scheme 63
4.2 Improvement of Path Quality 64
4.2.1 Introduction (digital indiscrimination) 64
4.2.2 Longitudinal process 66
4.2.3 Lateral process 66
4.2.4 B-spline curve fitting 71
4.3 Consideration of Fuel Consumption Ratio 72
Chapter 5 Experimental Simulation Results and Discussions 74
5.1 Two-point Flight Path Planning 76
5.2 Multi-point Flight Path Planning 86
Chapter 6 Conclusions 105
6.1 Conclusion Remarks 105
6.2 Future Directions 106
References 109
Publication List
VITA
參考文獻 [1] Y. Hwang, and N. Ahuja, “A Potential Field Approach to Path Planning,” IEEE Trans. on Robotics and Automation, Vol. 8, No. 1, 1992, pp. 23-32.
[2] J. Barraquand, B. Langlois, and J. Latombe, “Numerical Potential Field Techniques for Robot Path Planning,” IEEE Trans. on Systems, Man and Cybernetics, Vol. 22, No. 2, 1992, pp. 224-241.
[3] D. K. Pai, and L.-M. Reissell, “Multiresolution Rough Terrain Motion Planning,” IEEE Trans. on Robotics and Automation, Vol. 14, No. 1, Feb., 1998, pp. 19-33.
[4] B. Sinopoli, M. Micheli, G. Donato, and T. J. Koo, “Vision Based Navigation for an Unmanned Aerial Vehicle,” in Proc. of IEEE International Conference on Robotics and Automation, Korea, May 2001, pp. 1757-1764.
[5] E. Rippel, A. B. Gill, and N. Shimkin, “Fast Graph-Search Algorithms for General-Aviation Flight Trajectory Generation,“ Journal of Guidance, Control, and Dynamics, Vol. 28, No. 4, July-August 2005, pp. 801-811.
[6] D. Rathbun, S. Kragelund, A. Pongpunwattana, and B. Capozzi, “An Evolution Based Path Planning Algorithm for Autonomous Motion of a UAV Through Uncertain Environments,” Digital Avionics Systems Conference, Vol. 2, 2002, pp. 8D2-1-8D2-12.
[7] I. K. Nikolos, K. P. Valavanis, N. C. Tsourveloudis, and A. N. Kostaras, “Evolutionary Algorithm Based Offline/Online Path Planner for UAV Navigation,” IEEE Trans. on Systems, Man and Cybernetics—Part B: Cybernetics, Vol. 33, No. 6, Dec. 2003, pp. 898-912.
[8] E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, Volume 1, Issue 1, Dec 1959, pp. 269-271.
[9] P. E. Hart, N. J. Nilsson, B. Raphael, Correction to “A Formal Basis for the Heuristic Determination of Minimum Cost Paths, ” SIGART Newsletter, 37, 1972, pp. 28-29.
[10] A. Stentz, “The Focussed D* Algorithm for Real-Time Replanning,” In Proceedings of the International Joint Conference on Robotics and Automation, Aug. 1995, pp. 3310-3317.
[11] R. E. Bellman, “Dynamic Programming,” Dover Publications, Dover edition, 2003. ISBN 0486428095
[12] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, “Introduction to Algorithms,” Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937
[13] R. E. Larson, and J. L. Casti, “Principles of Dynamic Programming, Part II, Advanced Theory and Applications,” New York, Marcel Dekker, Inc., 1982. ISBN 0824765907
[14] W. Y. Chang, F. B. Hsiao, and D. L. Sheu, “Two-Point Flight Path Planning Using a Fast Graph-Search Algorithm,” AIAA Journal of Aerospace Computing, Information, and Communication, vol. 3, Sep. 2006, pp. 453-470.
[15] S. J. Asseo, “In-Flight Replanning of Penetration Routes to Avoid Threat Zones of Circular Shapes,” Aerospace and Electronics Conference, July 1998, pp. 383-391.
[16] R. Holdsworth, J. Lambert, and N. Harle, “Inflight Path Planning Replacing Pure Collision Avoidance, Using ADS-B,” Aerospace and Electronic Systems Magazine, Feb. 2001, pp. 27-32.
[17] K. S. Kwok, and B. J. Driessen, “Path Planning for Complex Terrain Navigation Via Dynamic Programming,” in Proc. of American Control Conference, S.D., Cal. , 1999, pp. 2941-2944.
[18] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, New York: John Wiley & Sons, 1985.
[19] D. A. Grundel and D. E. Jeffcoat, “Formulation and solution of the Target Visitation Problem,” AIAA 1st Intelligent Systems Technical Conf., Chicago, Sep. 2004.
[20] G. Laporte, “The Traveling Salesman Problem: An Overview of Exact and Approximate Algorithms,” European Journal of Operational Research, vol. 59, 1992, pp. 231-247.
[21] R.W. Beard, T.W. McLain, M.A. Goodrich, and E.P. Anderson, "Coordinated target assignment and intercept for unmanned air vehicles," IEEE Transactions on Robotics and Automation, vol. 18, no. 6, Dec 2002, pp. 911-922.
[22] J. Osborne and R. Rysdyk, “Waypoint guidance for small UAVs in wind,” Infotech@Aerospace, Virginia, Sep. 2005.
[23] L. Dubins, “On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents,” American Journal of Mathmatics, vol. 79, 1957, pp. 497-516.
[24] J.-D. Boissonnat, A. Cerezo, and J. Leblond, “Shortest paths of bounded curvature in the plane,” in Proc. of the 1992 IEEE Int. Conf. on Robotics and Automation, vol. 3, pp. 2315-2320.
[25] T. McGee, S. Spry, and K. Hedrick, “Optimal path planning in a constant wind with a bounded turning rate,” in Proc. of the AIAA Guidance, Navigation and Control Conference and Exhibit, California, Aug. 2005.
[26] A. Bicchi, G. Casalino, and C. Santilli, “Planning shortest bounded-curvature paths for a class of nonholonomic vehicles among obstacles,” Journal of Intelligent and Robotic Systems, vol. 16, 1996, pp. 387-405.
[27] P. K. Agarwal, P. Raghavan, and H. Tamakai, “Motion planning for a steering-constrained robot through moderate obstacles,” in Proc. of the 27th Annual ACM Symposium on the Theory of Computing, 1995, pp. 343-352.
[28] Z. Tang and Ü. Özgüner, “Motion planning for multitarget surveillance with mobile sensor agents,” IEEE Transactions on Robotics, vol. 21, no. 5, Oct. 2005, pp. 898-908.
[29] J. K. Howlett, T. W. McLain, and M. A. Goodrich, “Learning real-time A* path planner for unmanned air vehicle target sensing,” AIAA Journal of Aerospace Computing, Information, and Communication, vol. 3, March 2006, pp. 108-122.
[30] K. Savla, E. Frazzoli, and F. Bullo, “On the point-to-point and traveling salesperson problems for Dubins’ vehicle,” in Proc. of the American Controls Conference, Portland, OR, June 2005, pp. 786-791.
[31] G. Yang and V. Kapila, “Optimal path planning for unmanned air vehicles with kinematic and tactical constraints,” Proc. IEEE Conf. on Decision and Control, Dec. 2002, pp. 1301-1306.
[32] C. Hewitt, A. J., Henley, and J. D. Boyes, “A Ground and Obstacle Collision Avoidance Technique (GOCAT),” IEEE Aerospace and Electronic Systems Magazine, Vol. 6, No. 8, pp. 13-20, 1991.
[33] C. Hewitt and S. A. Broatch, “A Tactical Navigation and Routeing System for Low-Level Flight,” GEC-Marconi Avionics, Rochester, Kent, UK, AGARD, Italy, Technical Report, 1992.
[34] B. Tymczyszyn and G. Wilson, “Development and Flight Testing of a General/Corporate Aviation Terrain Awareness and Warning System,” Proceedings of the 46th Society of Experimental Test Pilots (SETP) Symposium, Lancaster, CA, 2002, pp. 94-107.
[35] R. C. Nelson, “Flight Stability and Automatic Control,” McGraw-Hill International, 1998. ISBN 0071158383
[36] J. D. Anderson, “Introduction to Flight,” McGraw-Hill International, 1989. ISBN 0072990716
[37] U.S. Geological Survey (USGS), GTOPO30 digital elevation model, Sioux Falls, South Dakota, USGS EROS Data Center, 1997. Available: http://edc.usgs.gov/products/elevation/gtopo30/gtopo30.html.
[38] P. Guth, Naval Academy, MICRODEM, a free software package with a built-in DEM converter. Available: http://www.usna.edu/Users/oceano/pguth/website/microdemdown.htm.
[39] D. P. Bertsekas, “Dynamic Programming: Deterministic and Stochastic Models,” Prentice-Hall, Inc., 1987. ISBN 0132215810
[40] K. K. Gifford, and R. R. Murphy, “Incorporating Terrain Uncertainties in Autonomous Vehicle Path Planning,” in Proc. IROS 96, 1996, pp. 1134-1140.
[41] K. J. Tsao, “Path Planning and Screen Remote Control for Vehicle’s Planner Motion,” Master Thesis, Institute of Applied Mechanics, Taiwan University, Taipei, Taiwan, 2002.
[42] P. T. Kuo, “Path Planning for Low-Altitude Flying Vehicles,” Master Thesis, Institute of Applied Mechanics, Taiwan University, Taipei, Taiwan, 2001.
[43] C. L. Tsai, “Path Planning for Flying Vehicles and Altimeter Error Analysis,” Master Thesis, Institute of Electrical Engineering, Taiwan University, Taipei, Taiwan, 2002.
[44] A. S. Willsky, “Multiresolution Markov Models for Signal and Image Processing,” Proceedings of the IEEE, Vol. 90, No. 8, August 2002.
[45] P. Graglia and A. Meystel, “Planning Minimum Time Trajectory in the Traversability Space of a Robot,” Proceedings of IEEE Symposium on Intelligent Control, Philadelphia, PA, 1987.
[46] C. Han, T. S. Hatsukami, J. N. Hwang, and C. Yuan, “A Fast Minimal Path Active Contour Model,” IEEE Transactions on Image Processing, Vol. 10, No. 6, June, 2001.
[47] C. S. Sallabergers and G. M. T. Deleuterio, “Optimal Robotic Path Planning using Dynamic Programming and Randomization,” Acta Astronautica, Vol. 35, No. 2/3, 1995, pp. 143-156.
[48] F. M. Jönsson, “An Optimal Pathfinder for Vehicles in Real-world Digital Terrain Maps,” Master Thesis, The Royal Institute of Science, School of Engineering Physics, Stockholm, Sweden, 1997.
[49] D. Z. Chen, R. J. Szczerba, and J. J. Uhran, Jr., “A Framed-Quadtree Approach for Determining Euclidean Shortest Paths in a 2-D Environment,” IEEE Transactions on Robotics and Automation, Vol. 13, No. 5, October 1997, pp. 668-681.
[50] M. Hebert, A. Stentz, and C. Thorpe, “Mobility Planning for Autonomous Navigation Multiple Robotic in Unstructured Environments,” Proceeding of IEEE ISIC/CIRA/ISAS Joint Conference, Gaithersburg, MD, 1998.
[51] P. N. Stiles and I. S. Glickstein, “Highly Parallelizable Route Planner Based on Cellular Automata Algorithms,” IBM J. Res. Develop, Vol. 38, No. 2, March, 1994.
[52] H. Male, M. Robinson, M. L. Kushner, and S. F. Anello, “An Integrated On-board Route Planner for Helicopter Applications,” Proceeding of IEEE/AIAA Digital Avionics Systems Conference, 1992.
[53] G. F. Wilber, “Strategic Route Planning Using Informed Best-First Search,” Proceeding of IEEE Aerospace and Electronics Conference, 1988.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2007-06-14起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2007-06-14起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw