Motion- and Communication-Planning of Unmanned Aerial Vehicles in Delay Tolerant Network using Mixed-Integer Linear Programming

“Motion- and Communication-Planning of Unmanned Aerial Vehicles in Delay Tolerant Network using Mixed-Integer Linear Programming”

Authors: Esten I. Grøtli and Tor A. Johansen,
Affiliation: SINTEF, NTNU, Department of Engineering Cybernetics and Centre for Autonomous Marine Operations and Systems (AMOS,NTNU)
Reference: 2016, Vol 37, No 2, pp. 77-97.

Keywords: Planning, UAV, Surveillance, Delay Tolerant Network

Abstract: Large amounts of data are typically generated in applications such as surveillance of power lines and railways, inspection of gas pipes, and security surveillance. In the latter application it is a necessity that the data is transmitted to the control centre ``on-the-fly'' for analysis. Also missions related to other applications would greatly benefit from near real-time analysis and operator interaction based on captured data. This is the motivation behind this paper on coarse offline motion- and communication-planning for cooperating Unmanned Aerial Vehicles (UAVs). A Mixed-Integer Linear Programming (MILP) problem is defined in order to solve the surveillance mission. To efficiently transmit the data back to the base station the vehicles are allowed to store data for later transmission and transmit via other vehicles, in addition to direct transmission. The paths obtained by solving the optimization problem are analyzed using a realistic radio propagation path loss simulator. If the radio propagation path loss exceeds the maximum design criterion the optimization problem is solved again with a stricter communication constraint, and the procedure is continued in an iterative manner until the criterion is met. The proposed algorithm is supported by simulations showing the resulting paths and communication topologies for different choices of delay tolerance.

PDF

PDF (1589 Kb) DOI: 10.4173/mic.2016.2.1

DOI forward links to this article:

[1] Yuguang Wei, Cafer Avc , Jiangtao Liu, Baloka Belezamo, Nizamettin Ayd n, Pengfei(Taylor) Li and Xuesong Zhou (2017), doi:10.1016/j.trb.2017.10.012

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

[3] Artur Zolich, David Palma, Kimmo Kansanen, Kay Fjørtoft, João Sousa, Karl H. Johansson, Yuming Jiang, Hefeng Dong and Tor A. Johansen (2018), doi:10.1007/s10846-018-0833-5

[4] Tong Wang, Ricardo M. Lima, Loïc Giraldi and Omar M. Knio (2018), doi:10.1016/j.cor.2018.08.008

[5] Shengtao Li and Jianying Li (2017), doi:10.1049/hve.2017.0026

[6] Kaan Celikbilek, Zainab Saleem, Ruben Morales Ferre, Jaan Praks and Elena Simona Lohan (2022), doi:10.3390/s22041421

[7] Rubens J. M. Afonso, Roberto K. H. Galvao, Gabriel A. Souza, Marcos R. O. A. Maximo and Angelo Caregnato Neto (2023), doi:10.1002/rnc.7012

[8] Angelo Caregnato Neto, Marcos R. O. A. Maximo and Rubens J. M. Afonso (2024), doi:10.1002/oca.3242

References:
[1] Alighanbari, M., Kuwata, Y., and How, J. (2003). Alighanbari, M, , Kuwata, Y., and How, J. Coordination and control of multiple UAVs with timing constraints and loitering. In Proc. of the American Control Conference, volume6. pages 5311 -- 5316 vol.6. doi:10.1109/ACC.2003.1242572
[2] Beard, R.W. and McLain, T.W. (2012). Beard, R, W. and McLain, T.W. Small Unmanned Aircraft: Theory and Practice. Princeton University Press. .
[3] Bemporad, A. and Morari, M. (1999). Bemporad, A, and Morari, M. Control of systems integrating logic, dynamics, and constraints. Automatica. 35:407--427. doi:10.1016/S0005-1098(98)00178-2
[4] Chaudhry, A., Misovec, K., and D'Andrea, R. (2004). Chaudhry, A, , Misovec, K., and D'Andrea, R. Low observability path planning for an unmanned air vehicle using mixed integer linear programming. In Proc. of the 43rd IEEE Conference on Decision and Control. pages 3823--3829. doi:10.1109/CDC.2004.1429334
[5] Dixon, C. and Frew, E. (2005). Dixon, C, and Frew, E. Electronic leashing of an unmanned aircraft to a radio source. In Proc. of the 44th IEEE Conference on Decision and Control and European Control Conference. pages 3560--3565. doi:10.1109/CDC.2005.1582714
[6] Dixon, C. and Frew, E.W. (2007). Dixon, C, and Frew, E.W. Decentralized extremum-seeking control of nonholonomic vehicles to form a communication chain. In Advances in Cooperative Control and Optimization, pages 311--322. Springer Berlin / Heidelberg. doi:10.1007/978-3-540-74356-9_19
[7] Earl, M.G. and D'Andrea, R. (2002). Earl, M, G. and D'Andrea, R. Modeling and control of a multi-agent system using mixed integer linear programming. In Proc. of the IEEE Conference on Decision and Control. pages 107 -- 111. doi:10.1109/CDC.2002.1184476
[8] Frew, E.W. and Brown, T.X. (2008). Frew, E, W. and Brown, T.X. Networking issues for small unmanned aircraft systems. Journal of Intelligent and Robotic Systems. 54:21--37. doi:10.1007/978-1-4020-9137-7_3
[9] Frew, E.W., Brown, T.X., Dixon, C., and Henkel, D. (2006). Frew, E, W., Brown, T.X., Dixon, C., and Henkel, D. Establishment and maintenance of a delay tolerant network through decentralized mobility control. In Proc. of the IEEE International Conference on Networking, Sensing and Control. pages 584--589. doi:10.1109/ICNSC.2006.1673211
[10] Grancharova, A., Grotli, E.I., Ho, D.-T., and Johansen, T.A. (2014). Grancharova, A, , Grotli, E.I., Ho, D.-T., and Johansen, T.A. UAVs trajectory planning by distributed MPC under radio communication path loss constraints. Journal of Intelligent and Robotic Systems. doi:10.1007/s10846-014-0090-1
[11] Grancharova, A., Grotli, E.I., and Johansen, T.A. (2012). Grancharova, A, , Grotli, E.I., and Johansen, T.A. Distributed path planning for a UAV communication chain by dual decomposition. In Proc. of the IFAC Workshop on Multivehicle Systems. pages 43--48. doi:10.3182/20121003-3-SF-4024.00001
[12] Grotli, E.I. and Johansen, T.A. (2012). Grotli, E, I. and Johansen, T.A. Path- and data transmission planning for cooperating UAVs in delay tolerant network. In Proc. of the 3rd International Workshop on Wireless Networking and Control for Unmanned Autonomous Vehicles: Architectures, Protocols and Applications. pages 1568--1573, 2012. doi:10.1109/GLOCOMW.2012.6477819
[13] Grotli, E.I. and Johansen, T.A. (2012). Grotli, E, I. and Johansen, T.A. Path planning for UAVs under communication constraints using SPLAT! and MILP. Journal of Intelligent and Robotic Systems, 2012. 65:265--282. doi:10.1007/s10846-011-9619-8
[14] Grotli, E.I. and Johansen, T.A. (2012). Grotli, E, I. and Johansen, T.A. Task assignment for cooperating UAVs under radio propagation path loss constraints. In Proc. of the American Control Conference. pages 3278--3283, 2012. doi:10.1109/ACC.2012.6315041
[15] Gunnerud, V. and Foss, B. (2010). Gunnerud, V, and Foss, B. Oil production optimization - a piecewise linear model, solved with two decomposition strategies. Computers & Chemical Engineering. 34:1803--1812. doi:10.1016/j.compchemeng.2009.10.019
[16] Hart, P.E., Nilsson, N.J., and Raphael, B. (1968). Hart, P, E., Nilsson, N.J., and Raphael, B. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics. 4(2):100--107. doi:10.1109/TSSC.1968.300136
[17] Henkel, D. and Brown, T.X. (2006). Henkel, D, and Brown, T.X. On controlled node mobility in delay-tolerant networks of unmanned aerial vehicles. In Proc. of International Symposium on Advanced Radio Technologies. 2006. .
[18] Ho, D.-T., Grotli, E.I., Sujit, P.B., Johansen, T.A., and deSousa, J.B. (2013). Ho, D, -T., Grotli, E.I., Sujit, P.B., Johansen, T.A., and deSousa, J.B. Performance evaluation of cooperative relay and particle swarm optimization path planning for uav and wireless sensor network. In Proc. of the 4th International Workshop on Wireless Networking and Control for Unmanned Autonomous Vehicles: Architectures, Protocols and Applications. pages 1403 -- 1408. doi:10.1109/GLOCOMW.2013.6825191
[19] Ho, D.-T., Grotli, E.I., Sujit, P.B., Johansen, T.A., and deSousa, J.B. (2015). Ho, D, -T., Grotli, E.I., Sujit, P.B., Johansen, T.A., and deSousa, J.B. Optimization of wireless sensor network and UAV data acquisition. Journal of Intelligent and Robotic Systems. doi:10.1007/s10846-015-0175-5
[20] Jain, S., Fall, K., and Patra, R. (2004). Jain, S, , Fall, K., and Patra, R. Routing in a delay tolerant network. In Proc. of the conference on Applications, technologies, architectures, and protocols for computer communications. pages 145--158, 2004. .
[21] Kennedy, J. and Eberhart, R. (1995). Kennedy, J, and Eberhart, R. Particle swarm optimization. In Proc. of the IEEE International Conference on Neural Networks. pages 1942--1948. doi:10.1109/ICNN.1995.488968
[22] Kim, Y., Gu, D.-W., and Postlethwaite, I. (2007). Kim, Y, , Gu, D.-W., and Postlethwaite, I. Real-time optimal mission scheduling and flight path selection. IEEE Transactions on Automatic Control. 52(6):1119 --1123. doi:10.1109/TAC.2007.899048
[23] Kingston, D.B. and Schumacher, C.J. (2005). Kingston, D, B. and Schumacher, C.J. Time-dependent cooperative assignment. In Proc. of the American Control Conference. pages 4084--4089, 2005. doi:10.1109/ACC.2005.1470617
[24] Kuwata, Y. and How, J.P. (2011). Kuwata, Y, and How, J.P. Cooperative distributed robust trajectory optimization using receding horizon MILP. IEEE Transaction on Control Systems Technology. 19(2):423--431. doi:10.1109/TCST.2010.2045501
[25] Kuwata, Y., Teo, J., Fiore, G., Karaman, S., Frazzoli, E., and How, J.P. (2009). Kuwata, Y, , Teo, J., Fiore, G., Karaman, S., Frazzoli, E., and How, J.P. Real-time motion planning with applications to autonomous urban driving. IEEE Transactions on Control Systems Technology. 17(5):1105--1118. doi:10.1109/TCST.2008.2012116
[26] LaValle, S.M. (2006). LaValle, S, M. Planning Algorithms. Cambridge University Press. .
[27] LaValle, S.M. and Kuffner, J. J.J. (2001). LaValle, S, M. and Kuffner, J. J.J. Randomized kinodynamic planning. International Journal of Robotics Research. 20(378):378--400. doi:10.1177/02783640122067453
[28] Likachev, M., Ferguson, D., Gordon, G., Stentz, A., and Thrun, S. (2005). Likachev, M, , Ferguson, D., Gordon, G., Stentz, A., and Thrun, S. Anytime dynamic A*: An anytime, replanning algorithm. In Proc. of the 15th International Conference on Automated Planning and Scheduling. pages 262--271. .
[29] Loefberg, J. (2008). Loefberg, J, Modeling and solving uncertain optimization problems in YALMIP. In Proc. of IFAC World Congress. pages 1337--1341. doi:10.3182/20080706-5-KR-1001.00229
[30] Longley, A.G. and Rice, P.L. (1968). Longley, A, G. and Rice, P.L. Prediction of tropospheric radio transmission loss over irregular terrain: A computer method. Technical report, U. S. Goverment. .
[31] Ma, C.S. and Miller, R.H. (2006). Ma, C, S. and Miller, R.H. MILP optimal path planning for real-time applications. In Proc. of the American Control Conference. pages 4945--4950, 2006. doi:10.1109/ACC.2006.1657504
[32] Maglicane, J. (2010). Maglicane, J, SPLAT! An RF signal propagation, loss and terrain analysis tool. 2010 (Accessed August 18, 2010). http://www.qsl.net/kd2bd/splat.html, .
[33] Prodan, I., Stoican, F., Olaru, S., and Niculescu, S.-I. (2012). Prodan, I, , Stoican, F., Olaru, S., and Niculescu, S.-I. Enhancements on the hyperplane arrangements in mixed-integer programming techniques. Journal of Optimization Theory and Applications. 154(2):549--572. doi:10.1007/s10957-012-0022-9
[34] Reinl, C. and von Stryk, O. (2007). Reinl, C, and von Stryk, O. Optimal control of multi-vehicle-systems under communication constraints using mixed-integer linear programming. In Proc. of the International Conference on Robot Communication and Coordination. 2007. .
[35] Richards, A. and How, J. (2005). Richards, A, and How, J. Mixed-integer programming for control. In Proc. of the American Control Conference. pages 2676--2683, 2005. doi:10.1109/ACC.2005.1470372
[36] Richards, A. and How, J.P. (2002). Richards, A, and How, J.P. Aircraft trajectory planning with collision avoidance using mixed integer linear programming. In Proc. of the American Control Conference. pages 1936--1941, 2002. doi:10.1109/ACC.2002.1023918
[37] Saska, M., Macas, M., Preucil, L., and Lhotska, L. (2006). Saska, M, , Macas, M., Preucil, L., and Lhotska, L. Robot path planning using particle swarm optimization of Ferguson splines. In Proc. of the IEEE Conference on Emerging Technologies and Factory Automation. pages 833 -- 839. doi:10.1109/ETFA.2006.355416
[38] 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 Proc. of the European Control Conference. 2001. .
[39] Schouwenaars, T., Stubbs, A., Paduano, J., and Feron, E. (2006). Schouwenaars, T, , Stubbs, A., Paduano, J., and Feron, E. Multivehicle path planning for nonline-of-sight communication. Journal of Field Robotics. 23:269--290. doi:10.1002/rob.20119
[40] Shengxiang, Z. and Hailong, P. (2008). Shengxiang, Z, and Hailong, P. Real-time optimal trajectory planning with terrain avoidance using MILP. In Proc. of the International Symposium on Systems and Control in Aerospace and Astronautics. pages 1 -- 5. doi:10.1109/ISSCAA.2008.4776318
[41] Spanos, D.P. and Murray, R.M. (2005). Spanos, D, P. and Murray, R.M. Motion planning with wireless network constraints. In Proc. of the American Control Conference. pages 87 -- 92, 2005. doi:10.1109/ACC.2005.1469913
[42] Stentz, A. (1994). Stentz, A, Optimal and efficient path planning for partially-known environments. In Proc. of the International Conference on Robotics and Automation. pages 3310--3317. doi:10.1109/ROBOT.1994.351061
[43] Sujit, P.B. and Beard, R. (2009). Sujit, P, B. and Beard, R. Multiple UAV path planning using anytime algorithms. In Proc. of the American Control Conference. pages 2978--2982, 2009. doi:10.1109/ACC.2009.5160222
[44] Tanenbaum, A.S. (2003). Tanenbaum, A, S. Computer Networks. Prentice Hall PTR, 4 edition. .
[45] Thunberg, J., Anisi, D.A., and Ogren, P. (2008). Thunberg, J, , Anisi, D.A., and Ogren, P. A comparative study of task assignment and path planning methods for multi-UGV missions. In Proc. of the International Conference on Cooperative Control and Optimization. 2008. .
[46] Tsourdos, A., White, B., and Shanmugavel, M. (2010). Tsourdos, A, , White, B., and Shanmugavel, M. Cooperative Path Planning of Unmanned Aerial Vehicles. Wiley. .
[47] Vielma, J.P., Ahmed, S., and Nemhauser, G. (2010). Vielma, J, P., Ahmed, S., and Nemhauser, G. Mixed-integer models for nonseparable piecewise-linear optimization: Unifying framework and extensions. Operations Research. 58:303--315. doi:10.1287/opre.1090.0721
[48] Vitus, M.P., Pradeep, V., Hoffmann, G.M., Waslander, S.L., and Tomlin, C.J. (2008). Vitus, M, P., Pradeep, V., Hoffmann, G.M., Waslander, S.L., and Tomlin, C.J. Tunnel MILP: Path planning with sequential convex polytopes. In Proc of the AIAA Guidance, Navigation, and Control Conference. 2008. .
[49] Williams, H.P. (1999). Williams, H, P. Model Building in Mathematical Programming. John Wiley and Sons, 4 edition. ISBN: 978-0471997887. .
[50] Wright, A. (2011). Wright, A, SPLAT! 1.3.1 for Windows. 2011 (Accessed June 29, 2011). http://www.ve3ncq.ca/wordpress/?page_id=62, .
[51] Zhao, W. and Ammar, M. (2003). Zhao, W, and Ammar, M. Message ferrying: Proactive routing in highly-partioned wireless ad hoc networks. In Proc. of the International Workshop on Future Trends of Distributed Computing Systems. pages 308--314. doi:10.1109/FTDCS.2003.1204352

BibTeX:
@article{MIC-2016-2-1,
  title={{Motion- and Communication-Planning of Unmanned Aerial Vehicles in Delay Tolerant Network using Mixed-Integer Linear Programming}},
  author={Grøtli, Esten I. and Johansen, Tor A.},
  journal={Modeling, Identification and Control},
  volume={37},
  number={2},
  pages={77--97},
  year={2016},
  doi={10.4173/mic.2016.2.1},
  publisher={Norwegian Society of Automatic Control}
};

Article

“Motion- and Communication-Planning of Unmanned Aerial Vehicles in Delay Tolerant Network using Mixed-Integer Linear Programming”