UAV Path Planning using MILP with Experiments

“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.

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

DOI forward links to this article:

[1] Jonatan Olofsson, Clas Veiback, Gustaf Hendeby and Tor Arne Johansen (2017), doi:10.1109/RED-UAS.2017.8101636

[2] Alena Otto, Niels Agatz, James Campbell, Bruce Golden and Erwin Pesch (2018), doi:10.1002/net.21818

[3] Anders Albert and Lars Imsland (2018), doi:10.1080/23335777.2018.1483969

[4] Fan Kai, Han Songchen, Liao Wenjing and Liang Binbin (2019), doi:10.1145/3378891.3378902

[5] Sung Hoon Chung, Bhawesh Sah and Jinkun Lee (2020), doi:10.1016/j.cor.2020.105004

[6] Grzegorz Bocewicz, Grzegorz Radzki, Izabela Nielsen, Marcin Witczak and Banaszak Zbigniew (2020), doi:10.1016/j.ifacol.2020.12.2798

[7] Mohit Srinivasan, Ankush Chakrabarty, Rien Quirynen, Nobuyuki Yoshikawa, Toshisada Mariyama and Stefano Di Cairano (2021), doi:10.1016/j.ifacol.2021.11.237

[8] Ibrahim H. Cihan (2022), doi:10.3846/aviation.2022.16878

[9] Hatem A. Alharbi, Barzan A. Yosuf, Mohammad Aldossary, Jaber Almutairi and Jaafar M. H. Elmirghani (2022), doi:10.1109/ACCESS.2022.3201112

[10] Angelo Caregnato-Neto, Marcos R. O. A. Maximo and Rubens J. M. Afonso (2022), doi:10.1080/01691864.2022.2117997

[11] Anees ul Husnain, Norrima Mokhtar, Noraisyah Mohamed Shah, Mahidzal Dahari and Masahiro Iwahashi (2023), doi:10.3390/drones7020118

[12] Johannes Schmidt and Armin Fugenschuh (2023), doi:10.1007/s10589-023-00450-x

[13] Ritu Maity, Ruby Mishra, Prasant Kumar Pattnaik and Nguyen Thi Dieu Linh (2023), doi:10.4018/978-1-6684-9317-5.ch002

[14] Yan Li, Xuejun Zhang, Yuanjun Zhu and Ziang Gao (2023), doi:10.1109/DASC58513.2023.10311219

[15] Jiahao Wu, Yang Ye and Jing Du (2024), doi:10.1016/j.autcon.2023.105253

[16] slam Guven and Ev en Yanmaz (2024), doi:10.1016/j.adhoc.2024.103520

[17] Ev en Yanmaz, Hamid Majidi Balanji and slam Guven (2024), doi:10.1109/TVT.2024.3363840

References:
[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.50.1.3.17780
[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

BibTeX:
@article{MIC-2017-1-3,
  title={{UAV Path Planning using MILP with Experiments}},
  author={Albert, Anders and Leira, Frederik S. and Imsland, Lars},
  journal={Modeling, Identification and Control},
  volume={38},
  number={1},
  pages={21--32},
  year={2017},
  doi={10.4173/mic.2017.1.3},
  publisher={Norwegian Society of Automatic Control}
};

Article

“UAV Path Planning using MILP with Experiments”