**Page description appears here**

“UAV Path Planning using MILP with Experiments”

Authors: Anders Albert, Frederik S. Leira and Lars Imsland,
Affiliation: NTNU, Department of Engineering Cybernetics
Reference: 2017, Vol 38, No 1, pp. 21-32.

     Valid XHTML 1.0 Strict

Keywords: UAV, Path Planning, Mathematical Optimization

Abstract: In this paper, we look at the problem of tracking icebergs using multiple Unmanned Aerial Vehicles (UAVs). Our solutions use combinatorial optimization for UAV path planning by formulating a mixed integer linear programing (MILP) optimization problem. To demonstrate the approach, we present both a simulation and a practical experiment. The simulation demonstrates the possibilities of the MILP algorithm by constructing a case where three UAVs help a boat make a safe passage through an area with icebergs. Furthermore, we compare the performance of three against a single UAV. In the practical experiment, we take the first step towards full-scale experiments. We run the algorithm on a ground station and use it to set the path for a UAV tracking five simulated icebergs.

PDF PDF (940 Kb)        DOI: 10.4173/mic.2017.1.3

[1] IBM Ilog CPLEX optimization studio. (2015). IBM Ilog CPLEX optimization studio, http://www.ibm.com, Accessed: 2015-09-12. .
[2] ArduPilot. (2016). ArduPilot, http://ardupilot.com, Acc.: 2016-02-10. .
[3] Odroid U3. (2016). Odroid U3, http://www.odroid.com, Acc.: 2016-03-02. .
[4] Sky Walker Technology (HK). (2016). Sky Walker Technology (HK), http://www.skywalker-model.com, Accessed: 2016-02-10. .
[5] Ubiquiti rocket M5. (2016). Ubiquiti rocket M5, https://www.ubnt.com/airmax/rocketm/. Accessed: 2016-02-10. .
[6] Albert, A. and Imsland, L. (2015). Albert, A, and Imsland, L. Mobile sensor path planning for iceberg monitoring using a MILP framework. In 12th Proc. Intl. Conf. Inf. Control, Automation, Robotics, volume1. pages 131--138. .
[7] Asnis, G. and Blackman, S. (2011). Asnis, G, and Blackman, S. Optimal allocation of multi-platform sensor resources for multiple target tracking. In Information Fusion, Proc. 14th Intl. Conf. IEEE, pages 1--8. .
[8] Barton, K. and Kingston, D. (2013). Barton, K, and Kingston, D. Systematic surveillance for uavs: A feedforward iterative learning control approach. In American Control Conf. IEEE, pages 5917--5922. doi:10.1109/ACC.2013.6580766
[9] Bixby, R.E. (2002). Bixby, R, E. Solving real-world linear programs: A decade and more of progress. Operations research. 50(1):3--15. doi:10.1287/opre.
[10] Chen, D.-S., Batson, R.G., and Dang, Y. (2010). Chen, D, -S., Batson, R.G., and Dang, Y. Applied integer programming: modeling and solution. John Wiley & Sons. doi:10.1002/9781118166000
[11] Eik, K. (2008). Eik, K, Review of experiences within ice and iceberg management. Journal of Navigation. 61(4):557--572. doi:10.1017/S0373463308004839
[12] Enright, J., Frazzoli, E., Savla, K., and Bullo, F. (2005). Enright, J, , Frazzoli, E., Savla, K., and Bullo, F. On multiple uav routing with stochastic targets: Performance bounds and algorithms. In Proc. AIAA Conf. on Guidance, Navigation, Control. 2005. doi:10.2514/6.2005-5830
[13] Farmani, N., Sun, L., and Pack, D. (2015). Farmani, N, , Sun, L., and Pack, D. Tracking multiple mobile targets using cooperative unmanned aerial vehicles. In Intl. Conf. Unmanned Aircraft Systems. IEEE, pages 395--400. doi:10.1109/ICUAS.2015.7152315
[14] Grundel, D. and Jeffcoat, D. (2004). Grundel, D, and Jeffcoat, D. Formulation and solution of the target visitation problem. AIAA 1st Intell. Sys. Techn.. 1:1--6. doi:10.2514/6.2004-6212
[15] Haugen, J. and Imsland, L. (2013). Haugen, J, and Imsland, L. Optimization-based autonomous remote sensing of surface objects using an unmanned aerial vehicle. 2013 European Control Conference, ECC 2013. pages 1242--1249. .
[16] Hirsch, M.J. and Schroeder, D. (2015). Hirsch, M, J. and Schroeder, D. On the decentralized cooperative control of multiple autonomous vehicles. In Handbook Unmanned Aerial Vehicles, pages 1577--1600. 2015. doi:10.1007/978-90-481-9707-1_112
[17] Junger, M. and et.al. (2009). Junger, M, and et.al. 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-art. Springer Science & Business Media. doi:10.1007/978-3-540-68279-0
[18] Leira, F., Johansen, T.A., and Fossen, T.I. (2015). Leira, F, , Johansen, T.A., and Fossen, T.I. Automatic detection, classification and tracking of objects in the ocean surface from uavs using a thermal camera. In IEEE Aerospace Conference. 2015. doi:10.1109/AERO.2015.7119238
[19] Lesinskis, I. and Pavlovics, A. (2011). Lesinskis, I, and Pavlovics, A. The aspects of implementation of unmanned aerial vehicles for ice situation awareness in maritime traffic. Proc. Intl. Conf. Transport Means. pages 65--68. .
[20] Loefberg, J. (2004). Loefberg, J, YALMIP : A toolbox for modeling and optimization in MATLAB. In Proceedings of the CACSD Conference. Taipei, Taiwan, 2004. doi:10.1109/CACSD.2004.1393890
[21] Ma, C.S. and Miller, R.H. (2005). Ma, C, S. and Miller, R.H. Mixed integer linear programming trajectory generation for autonomous nap-of-the-earth flight in a threat environment. In 2005 IEEE Aerospace Conference. IEEE, pages 1--9. doi:10.1109/AERO.2005.1559599
[22] Martins, R., Dias, P.S., Marques, E.R., Pinto, J., Sousa, J.B., and Pereira, F.L. (2009). Martins, R, , Dias, P.S., Marques, E.R., Pinto, J., Sousa, J.B., and Pereira, F.L. IMC: A communication protocol for networked vehicles and sensors. In Oceans 2009-Europe. IEEE, pages 1--6. doi:10.1109/OCEANSE.2009.5278245
[23] Miller, C.E., Tucker, A.W., and Zemlin, R.A. (1960). Miller, C, E., Tucker, A.W., and Zemlin, R.A. Integer programming formulation of traveling salesman problems. Journal of the ACM (JACM). 7(4):326--329. doi:10.1145/321043.321046
[24] Noon, C.E. and Bean, J.C. (1993). Noon, C, E. and Bean, J.C. An efficient transformation of the generalized traveling salesman problem. INFOR. 31(1):39. doi:10.1080/03155986.1993.11732212
[25] Oberlin, P., Rathinam, S., and Darbha, S. (2010). Oberlin, P, , Rathinam, S., and Darbha, S. Today's traveling salesman problem. IEEE robotics & automation magazine. 17(4):70--77. doi:10.1109/MRA.2010.938844
[26] Oh, H., Shin, H.-S., Kim, S., Tsourdos, A., and White, B.A. (2015). Oh, H, , Shin, H.-S., Kim, S., Tsourdos, A., and White, B.A. Cooperative mission and path planning for a team of uavs. In Handbook of Unmanned Aerial Vehicles, pages 1509--1545. Springer. doi:10.1007/978-90-481-9707-1_14
[27] Pinto, J., Calado, P., Braga, J., Dias, P., Martins, R., Marques, E., and Sousa, J. (2012). Pinto, J, , Calado, P., Braga, J., Dias, P., Martins, R., Marques, E., and Sousa, J. Implementation of a control architecture for networked vehicle systems. In Proc. IFAC Navigation, Guidance, Control of Underwater Vehicles. IFAC. doi:10.3182/20120410-3-PT-4028.00018
[28] Pinto, J., Dias, P.S., Goncalves, R., Marques, E. R.B., Goncalves, G.M., Sousa, J.B., and Pereira, F.L. (2006). Pinto, J, , Dias, P.S., Goncalves, R., Marques, E. R.B., Goncalves, G.M., Sousa, J.B., and Pereira, F.L. Neptus: a framework to support a mission life cycle. In Proc. IFAC Conf. Manoeuvring and Control of Marine Craft. IFAC. .
[29] Schouwenaars, T., DeMoor, B., Feron, E., and How, J. (2001). Schouwenaars, T, , DeMoor, B., Feron, E., and How, J. Mixed integer programming for multi-vehicle path planning. In Control Conference (ECC), 2001 European. IEEE, pages 2603--2608. .
[30] Shetty, V.K., Sudit, M., and Nagi, R. (2008). Shetty, V, K., Sudit, M., and Nagi, R. Priority-based assignment and routing of a fleet of unmanned combat aerial vehicles. Computers & Operations Research. 35(6):1813--1828. doi:10.1016/j.cor.2006.09.013
[31] Sinha, A., Kirubarajan, T., and Bar-Shalom, Y. (2005). Sinha, A, , Kirubarajan, T., and Bar-Shalom, Y. Autonomous ground target tracking by multiple cooperative uavs. In 2005 IEEE Aerospace Conference. IEEE, pages 1--9. doi:10.1109/AERO.2005.1559601
[32] Valavanis, K. and Vachtsevanos, G. (2015). Valavanis, K, and Vachtsevanos, G. UAV applications: Introduction. Handbook of Unmanned Aerial Vehicles. pages 2639--2641. doi:10.1007/978-90-481-9707-1_151
[33] Walton, C., Gong, Q., Kaminer, I., and Royset, J. (2014). Walton, C, , Gong, Q., Kaminer, I., and Royset, J. Optimal motion planning for searching for uncertain targets. IFAC Proc.. 19:8977--8982. doi:10.3182/20140824-6-ZA-1003.01388

  title={{UAV Path Planning using MILP with Experiments}},
  author={Albert, Anders and Leira, Frederik S. and Imsland, Lars},
  journal={Modeling, Identification and Control},
  publisher={Norwegian Society of Automatic Control}


May 2016: MIC reaches 2000 DOI Forward Links. The first 1000 took 34 years, the next 1000 took 2.5 years.

July 2015: MIC's new impact factor is now 0.778. The number of papers published in 2014 was 21 compared to 15 in 2013, which partially explains the small decrease in impact factor.

Aug 2014: For the 3rd year in a row MIC's impact factor increases. It is now 0.826.

Dec 2013: New database-driven web-design enabling extended statistics. Article number 500 is published and MIC reaches 1000 DOI Forward Links.

Jan 2012: Follow MIC on your smartphone by using the RSS feed.


July 2011: MIC passes 1000 ISI Web of Science citations.

Mar 2010: MIC is now indexed by DOAJ and has received the Sparc Seal seal for open access journals.

Dec 2009: A MIC group is created at LinkedIn and Twitter.

Oct 2009: MIC is now fully updated in ISI Web of Knowledge.