||The Study of Flight Path Planning for Multiple Target Visitations
||Department of Aeronautics & Astronautics
flight path planning
求解通過多目標點之飛行路徑之前，我們首先求解二點間之飛行路徑，求得之飛行路徑必需滿足許多限制條件以確保飛行安全及飛行效率。在飛行安全考量下，充分的安全飛行高度及水平安全距離是絕對必需的。實際上，飛機之起降方向、爬升率限制、轉彎率限制、燃料消耗比等亦都是飛行路徑規劃所必需考慮的。我們藉由建立虛擬地形於真實地形上作為搜尋空間，來包含真實飛行條件及飛機性能限制於路徑規劃的問題中，同時飛行安全考量及起飛降落階段亦可包含進來。除此之外，虛擬地形的建立也有效地將三維的搜尋空間減至二維空間，如此可以大大地減少演算法的運算量。然而在粗糙且 大部份的地形高度高於巡航高度的地形上，虛擬地形的建立可能使所求得路徑有上下起伏頻繁的缺點。另外由於空間格點的離散化，數值無差別(digital indiscrimination)的問題也將產生。因此，我們提出數個計算快速僅需不到一秒的後處理方法來克服這些問題。對於山谷間飛行之特殊任務需求，我們亦提出無因次之燃料消耗比來滿足此需求。如果爬升越過障礙物比水平轉彎繞過障礙物所消耗之燃料還要多，演算法將會選擇同高度之水平轉彎繞過障礙物，如此一來飛行路徑之縱向高度平滑度亦將獲得提升。藉由使用多重解析度(多層級)地形及快速啟發式搜尋法我們己經成功並有效地降低了演算法的計算時間，並且模擬結果顯示此二點間飛行路徑演算法是可行的。
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.
Abstract in Chinese of Each Chapter vii
第一章 緒論 viii
第二章 飛行路徑規劃之考量因素 x
第三章 飛行路徑規劃之研究方法 xi
第四章 演算法及路徑品質之改良 xiii
第五章 模擬結果與討論 xv
第六章 結論 xvi
List of Tables xxi
List of Figures xxii
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
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, Volume 1, Issue 1, Dec 1959, pp. 269-271.
 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.
 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.
 R. E. Bellman, “Dynamic Programming,” Dover Publications, Dover edition, 2003. ISBN 0486428095
 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
 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
 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.
 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.
 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.
 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.
 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.
 D. A. Grundel and D. E. Jeffcoat, “Formulation and solution of the Target Visitation Problem,” AIAA 1st Intelligent Systems Technical Conf., Chicago, Sep. 2004.
 G. Laporte, “The Traveling Salesman Problem: An Overview of Exact and Approximate Algorithms,” European Journal of Operational Research, vol. 59, 1992, pp. 231-247.
 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.
 J. Osborne and R. Rysdyk, “Waypoint guidance for small UAVs in wind,” Infotech@Aerospace, Virginia, Sep. 2005.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 R. C. Nelson, “Flight Stability and Automatic Control,” McGraw-Hill International, 1998. ISBN 0071158383
 J. D. Anderson, “Introduction to Flight,” McGraw-Hill International, 1989. ISBN 0072990716
 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.
 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.
 D. P. Bertsekas, “Dynamic Programming: Deterministic and Stochastic Models,” Prentice-Hall, Inc., 1987. ISBN 0132215810
 K. K. Gifford, and R. R. Murphy, “Incorporating Terrain Uncertainties in Autonomous Vehicle Path Planning,” in Proc. IROS 96, 1996, pp. 1134-1140.
 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.
 P. T. Kuo, “Path Planning for Low-Altitude Flying Vehicles,” Master Thesis, Institute of Applied Mechanics, Taiwan University, Taipei, Taiwan, 2001.
 C. L. Tsai, “Path Planning for Flying Vehicles and Altimeter Error Analysis,” Master Thesis, Institute of Electrical Engineering, Taiwan University, Taipei, Taiwan, 2002.
 A. S. Willsky, “Multiresolution Markov Models for Signal and Image Processing,” Proceedings of the IEEE, Vol. 90, No. 8, August 2002.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 G. F. Wilber, “Strategic Route Planning Using Informed Best-First Search,” Proceeding of IEEE Aerospace and Electronics Conference, 1988.