Development of a method for determining the area of operation of unmanned vehicles formation by using the graph theory

Iryna Zhuravska, Inessa Kulakovska, Maksym Musiyenko

Abstract


The results of research into influence of modification of the topology of a heterogeneous formation of unmanned vehicles on the area, covered by this formation are presented. We proposed an approach, according to which the method for modeling the structure of complex technical systems is applied to describe the behavior of unmanned vehicles’ formation. The changes in topology and in the covered area as a result of unmanned vehicles’ rearrangement within a formation were considered.

Based on the result of present study, a method for determining the area of unmanned vehicles’ formation operation involving the graph theory was proposed. Formation of the loaded directed graphs that correspond to the main (star, ring, bus) and mixed (hierarchical star with a bus, hierarchical star with a ring) formation topologies was considered in detail. The adjacency matrix and the loading matrix for the topology "hierarchical star" were analyzed.

In addition, the study conducted allows us to conclude that to ensure a full coverage of a certain territory, the mathematical model of the structure of a dynamic system must be characterized by a random number of vertices that correspond to a variable number of unmanned vehicle in a formation. Various technical characteristics of unmanned vehicles, which belong to different classes by weight or control type, must be considered into account when constructing the matrix of graph loading. Calculation of the area, covered by an unmanned vehicles’ formation, is performed as calculation of the area of polygons, assigned by their vertices, using the interpolation concept to count the intermediate values of magnitudes by a discrete set of known coordinate values. Calculation of the formation area is based on the ranges, within which sustainable communication between the drones of different models is provided.

Partition of the loading matrix into subordination units makes it possible to decrease computational complexity and thereby prolong operation of a formation. Application of this approach will allow us to plan more effectively the time and the number of drones in a formation, necessary for covering the territory of the specified size.


Keywords


unmanned vehicle; heterogeneous formation; loaded directed graph; formation operation area

Full Text:

PDF

References


Locklear, M. (2018). Intel put on an Olympic light show with 1,218 drones. Engadget. Available at: https://www.engadget.com/2018/02/09/intel-olympic-light-show-1-218-drones/

China launched a record swarm of drones (2017). Xinhua News Agency. Available at: http://russian.news.cn/2017-06/11/c_136356942.htm

Naomi Leonard: Flocks and Fleets: Collective Motion in Nature and Robotics. Available at: https://www.youtube.com/watch?v=HMqas_hhMwQ

Musiyenko, M. P., Denysov, O. O., Zhuravska, I. M., Burlachenko, I. S. (2016). Development of double median filter for optical navigation problems. 2016 IEEE First International Conference on Data Stream Mining & Processing (DSMP). doi: 10.1109/dsmp.2016.7583535

Burlachenko, I., Zhuravska, I., Musiyenko, M. (2017). Devising a method for the active coordination of video cameras in optical navigation based on the multi-agent approach. Eastern-European Journal of Enterprise Technologies, 1 (9 (85)), 17–25. doi: 10.15587/1729-4061.2017.90863

Benkovich, Yu. B., Kolesov, Yu. B., Senichenkov, Yu. B. (2002). Practical modeling of dynamic systems. Saint Petersburg: BHV Petersburg, 464.

Mizokami, K. (2016). All the Combat Vehicles of the U.S. Military in One Giant Poster. Popular Mechanics. Available at: https://www.popularmechanics.com/military/weapons/a21049/all-the-combat-vehicles-of-the-us-military-in-one-giant-poster/

Fortenberry, M., Calvert, D., Van Landingham, K., Geng, X. Design of an autonomous ground vehicle by the university of west Florida unmanned systems lab for the 2014 intelligent ground vehicle competition. Available at: http://www.igvc.org/design/2014/29.pdf

Mainstreaming Unmanned Undersea Vehicles into Future U.S. Naval Operations: Abbreviated Version of a Restricted Report (2016). Washington: The National Academies Press. doi: 10.17226/21862

Baiduzh, R. (2017). Rules of Aircraft Operation of Unmanned Aircraft in Ukraine (Concept). State aviation administration of Ukraine. Available at: http://drone.ua/wp-content/uploads/2017/04/20171006_Kontseptsiya-BPS.pdf

PARROT DISCO FPV: technical specifications. Available at: https://www.parrot.com/us/drones/parrot-disco-fpv#spare-parts

Voyager 5: Spec. Walkera. Available at: http://www.walkera.com/index.php/Goods/canshu/id/66.html

DJI Phantom 4 PRO. Available at: https://www.dji.com/ru/phantom-4-pro/info

Blade Chroma CGO3 4K Camera. Available at: https://www.horizonhobby.com/media/chroma/BLH8675.html

Krainyk, Y., Perov, V., Musiyenko, M., Davydenko, Y. (2017). Hardware-oriented turbo-product codes decoder architecture. 2017 9th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS). doi: 10.1109/idaacs.2017.8095067

Zhuravska, I. M. (2016). Ensuring a stable wireless communication in cyber-physical systems with moving objects. Technology audit and production reserves, 5 (2 (31)), 58–64. doi: 10.15587/2312-8372.2016.80784

Kolesov, Yu. B., Senichenkov, Yu. B. (2012). Modeling of systems. Dynamic and hybrid systems. Saint Petersburg: BHV Petersburg, 224.

Courtois, P. J. (1985). On time and space decomposition of complex structures. Communications of the ACM, 28 (6), 590–603. doi: 10.1145/3812.3814

Guenard, A., Ciarletta, L. (2012). The AETOURNOS Project: Using a Flock of UAVs as a Cyber Physical System and Platform for Application-driven Research. Procedia Computer Science, 10, 939–945. doi: 10.1016/j.procs.2012.06.127

Zykov, A. A. (1987). Foundations of Graph Theory. Мoscow: Nauka, 384.

Pogudina, O. K. (2012). Development of simulation model of co-operation of pilotless aircrafts for research of possibility of joint flight. Information Processing Systems, 7, 140–143.

Gozhyj, О. Р. (2015). Development of Fuzzy Situational Networks with Time Constraints for Modeling Dynamic Systems. Naukovi Visti NTUU KPI, 5, 15–22.

Trunov, A. (2017). Recurrent transformation of the dynamics model for autonomous underwater vehicle in the inertial coordinate system. Eastern-European Journal of Enterprise Technologies, 2 (4 (86)), 39–47. doi: 10.15587/1729-4061.2017.95783

Diestel, R. (2017). Graph Theory. Springer-Verlag, 429. doi: 10.1007/978-3-662-53622-3

Kresse, W., Danko, D. M. (2012). Springer Handbook of Geographic Information. Berlin; Heidelberg: Springer Science & Business Media. doi: 10.1007/978-3-540-72680-7


GOST Style Citations


Locklear M. Intel put on an Olympic light show with 1,218 drones // Engadget. 2018. URL: https://www.engadget.com/2018/02/09/intel-olympic-light-show-1-218-drones/

China launched a record swarm of drones // Xinhua News Agency. 2017. URL: http://russian.news.cn/2017-06/11/c_136356942.htm

Naomi Leonard: Flocks and Fleets: Collective Motion in Nature and Robotics. URL: https://www.youtube.com/watch?v=HMqas_hhMwQ

Development of double median filter for optical navigation problems / Musiyenko M. P., Denysov O. O., Zhuravska I. M., Burlachenko I. S. // 2016 IEEE First International Conference on Data Stream Mining & Processing (DSMP). 2016. doi: 10.1109/dsmp.2016.7583535 

Burlachenko I., Zhuravska I., Musiyenko M. Devising a method for the active coordination of video cameras in optical navigation based on the multi-agent approach // Eastern-European Journal of Enterprise Technologies. 2017. Vol. 1, Issue 9 (85). P. 17–25. doi: 10.15587/1729-4061.2017.90863 

Benkovich Yu. B., Kolesov Yu. B., Senichenkov Yu. B. Practical modeling of dynamic systems. Saint Petersburg: BHV Petersburg, 2002. 464 p.

Mizokami K. All the Combat Vehicles of the U.S. Military in One Giant Poster // Popular Mechanics. 2016. URL: https://www.popularmechanics.com/military/weapons/a21049/all-the-combat-vehicles-of-the-us-military-in-one-giant-poster/

Design of an autonomous ground vehicle by the university of west Florida unmanned systems lab for the 2014 intelligent ground vehicle competition / Fortenberry M., Calvert D., Van Landingham K., Geng X. // URL: http://www.igvc.org/design/2014/29.pdf

Mainstreaming Unmanned Undersea Vehicles into Future U.S. Naval Operations: Abbreviated Version of a Restricted Report. Washington: The National Academies Press, 2016. doi: 10.17226/21862 

Baiduzh R. Rules of Aircraft Operation of Unmanned Aircraft in Ukraine (Concept) // State aviation administration of Ukraine. 2017. URL: http://drone.ua/wp-content/uploads/2017/04/20171006_Kontseptsiya-BPS.pdf

PARROT DISCO FPV: technical specifications. URL: https://www.parrot.com/us/drones/parrot-disco-fpv#spare-parts

Voyager 5: Spec // Walkera. URL: http://www.walkera.com/index.php/Goods/canshu/id/66.html

DJI Phantom 4 PRO. URL: https://www.dji.com/ru/phantom-4-pro/info

Blade Chroma CGO3 4K Camera. URL: https://www.horizonhobby.com/media/chroma/BLH8675.html

Hardware-oriented turbo-product codes decoder architecture / Krainyk Y., Perov V., Musiyenko M., Davydenko Y. // 2017 9th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS). 2017. doi: 10.1109/idaacs.2017.8095067 

Zhuravska I. M. Ensuring a stable wireless communication in cyber-physical systems with moving objects // Technology audit and production reserves. 2016. Vol. 5, Issue 2 (31). Р. 58–64. doi: 10.15587/2312-8372.2016.80784 

Kolesov Yu. B., Senichenkov Yu. B. Modeling of systems. Dynamic and hybrid systems. Saint Petersburg: BHV Petersburg, 2012. 224 p.

Courtois P. J. On time and space decomposition of complex structures // Communications of the ACM. 1985. Vol. 28, Issue 6. P. 590–603. doi: 10.1145/3812.3814 

Guenard A., Ciarletta L. The AETOURNOS Project: Using a Flock of UAVs as a Cyber Physical System and Platform for Application-driven Research // Procedia Computer Science. 2012. Vol. 10. P. 939–945. doi: 10.1016/j.procs.2012.06.127 

Zykov A. A. Foundations of Graph Theory. Мoscow: Nauka, 1987. 384 p.

Pogudina O. K. Development of simulation model of co-operation of pilotless aircrafts for research of possibility of joint flight // Information Processing Systems. 2012. Issue 7. P. 140–143.

Gozhyj О. Р. Development of Fuzzy Situational Networks with Time Constraints for Modeling Dynamic Systems // Naukovi Visti NTUU KPI. 2015. Issue 5. P. 15–22.

Trunov A. Recurrent transformation of the dynamics model for autonomous underwater vehicle in the inertial coordinate system // Eastern-European Journal of Enterprise Technologies. 2017. Vol. 2, Issue 4 (86). P. 39–47. doi: 10.15587/1729-4061.2017.95783 

Diestel R. Graph Theory. 5th ed. Springer-Verlag, 2017. 429 p. doi: 10.1007/978-3-662-53622-3 

Kresse W., Danko D. M. Springer Handbook of Geographic Information. Berlin; Heidelberg: Springer Science & Business Media, 2012. doi: 10.1007/978-3-540-72680-7 



DOI: https://doi.org/10.15587/1729-4061.2018.128745

Refbacks

  • There are currently no refbacks.




Copyright (c) 2018 Iryna Zhuravska, Inessa Kulakovska, Maksym Musiyenko

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

ISSN (print) 1729-3774, ISSN (on-line) 1729-4061