**Page description appears here**

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

     Valid XHTML 1.0 Strict


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





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}
};

News

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.

Smartphone


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.