Trajectory planning for unmanned aerial vehicles: a network optimization approach. (English) Zbl 1258.93116
Summary: This paper presents a new approach for trajectory planning of air vehicles. It considers scenarios with risk areas and forbidden zones and takes into account the maneuverability of the air vehicle. It is flexible as to allow different kinds of objective functions such as minimizing risk, flight path length or flight time, and allows to implement constraints on fuel consumption or other resources. Additionally, it can incorporate waypoints to be passed by the air vehicle with or without specified overflight directions. The method includes planning of one-way and return trips. The underlying model is based on a discretization of the airspace into a non-regular network. Every path in the network corresponds to a flyable trajectory which means that the trajectory is within the performance limits of the air vehicle. The generation of the network is done non-deterministically. One of the main benefits of the model is that one can make use of standard network optimization techniques.
MSC:
| 93E20 | Optimal stochastic control |
| 93A30 | Mathematical modelling of systems (MSC2010) |
| 49N90 | Applications of optimal control and differential games |
| 49M30 | Other numerical methods in calculus of variations (MSC2010) |
| 90B15 | Stochastic network models in operations research |
Keywords:
flight path optimization; route planning; aircraft trajectory; shortest path problem; network optimizationReferences:
| [1] | Ahuja RK, Magnanti TL, Orlin JB (1993) Networks flows: theory, algorithms, and applications. Prentice-Hall, New York |
| [2] | Beasley J, Christofides N (1989) An algorithm for the resource constrained shortest path problem. Networks 19(4): 379–394 · Zbl 0673.90085 · doi:10.1002/net.3230190402 |
| [3] | Boroujerdi A, Uhlmann J (1998) An efficient algorithm for computing least cost paths with turn constraints. Inf Process Lett 67(6): 317–321 · Zbl 1339.68199 · doi:10.1016/S0020-0190(98)00134-3 |
| [4] | Caldwell T (1961) On finding minimal routes in a network with turning penalties. Commun ACM 4: 107–108 · Zbl 0116.12302 · doi:10.1145/366105.366184 |
| [5] | Carlyle WM, Royset JO, Wood RK (2009) Routing military aircraft with a constrained shortest-path algorithm. Mil Oper Res 14(3): 31–52 |
| [6] | Choset H, Burgard W, Hutchinson S, Kantor G, Kavraki LE, Lynch K, Thrun S (2005) Principles of robot motion: theory, algorithms, and implementation. MIT Press, Cambridge · Zbl 1081.68700 |
| [7] | Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms. 3rd edn. MIT Press, Cambridge |
| [8] | Dumitrescu I, Boland N (2003) Improved preprocessing, labeling and scaling algorithm for the weight-constrained shortest path problem. Networks 42(3): 135–153 · Zbl 1031.68144 · doi:10.1002/net.10090 |
| [9] | Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. WH Freeman, San Francisco · Zbl 0411.68039 |
| [10] | Hassin R (1992) Approximated schemes for the restricted shortest path problem. Math Oper Res 17(1): 36–42 · Zbl 0763.90083 · doi:10.1287/moor.17.1.36 |
| [11] | Helgason RV, Kennington JL, Lewis KR (2001) Cruise missile mission planning: a heuristic algorithm for automatic path generation. J Heuristics 7(5): 473–494 · doi:10.1023/A:1011325912346 |
| [12] | Hwang YK, Ahuja N (1992) Gross motion planning–a survey. ACM Comput Surv 24(3): 219–291 · doi:10.1145/136035.136037 |
| [13] | Kim J, Hespanha JP (2003) Discrete approximations to continuous shortest-path: application to minimum-risk path planning for groups of UAVs. 42nd IEEE Conf Decis Control 2: 1734–1740 |
| [14] | Kuipers FA, Korkmaz T, Krunz M, Van Mieghem P (2004) Performance evaluation of constraint-based path selection algorithms. IEEE Netw 18(5): 16–23 · doi:10.1109/MNET.2004.1337731 |
| [15] | Latombe JC (1991) Robot motion planning. Kluwer Academic Publishers, Boston |
| [16] | Laumond JP (1998) Robot motion planning and control. LN control inf sci 229. Springer, New York |
| [17] | LaValle SM (2006) Planning algorithms. Cambridge University Press, Cambridge · Zbl 1100.68108 |
| [18] | Lorenz DH, Raz D (2001) A simple efficient approximation scheme for the restricted shortest path problem. Oper Res Lett 28(5): 213–219 · Zbl 0992.90057 · doi:10.1016/S0167-6377(01)00069-4 |
| [19] | Masehian E, Sedighizadeh D (2007) Classic and heuristic approaches in robot motion planning–a chronological review. World Acad Sci Eng Technol 29: 101–106 |
| [20] | Pfeiffer B, Batta R, Klamroth K, Nagi R (2005) Path planning for UAVs in the presence of threat zones using probabilistic modeling. Institute of Applied Mathematics, University of Erlangen, Erlangen |
| [21] | Soliman H, Peyton C (2002) An efficient routing algorithm for all-optical networks with turn constraints. In: Proceedings of the 10th IEEE international symposium on modeling, analysis and simulation of computer and telecommunication systems, pp 161–166 |
| [22] | Wattleworth JA, Shuldiner PW (1963) Analytical methods in transportation: left-turn penalties in traffic assignment models. J Eng Mech 89: 97–126 |
| [23] | Zabarankin M, Uryasev S, Pardalos P (2001) Optimal risk path algorithms. In: Murphey R, Pardalos P (eds) Cooperative control and optimization. Kluwer, Dordrecht, pp 271–303 |
| [24] | Zabarankin M, Uryasev S, Murphey R (2006) Aircraft routing under the risk of detection. Nav Res Logist 53(8): 728–747 · Zbl 1141.90592 · doi:10.1002/nav.20165 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
