APPLICATION OF A GENETIC ALGORITHM TO THE AREA COVERAGE PROBLEM WITH A GROUP OF UNMANNED AERIAL VEHICLES SUPPORTED BY A GROUND MOBILE CHARGING STATION: A CHROMOSOME FORMATION
Abstract
The paper considers a problem of area coverage by unmanned aerial vehicles (UAV) using
mobile charging stations. Practical area coverage tasks require a simultaneous use of several
UAVs in order to optimize time consumption during a mission. Another limiting factor in UAVbased
coverage is a duration of a UAVs’ single-battery autonomous operation. To complete a
large territory coverage mission static or mobile charging stations could be employed in order to
recharge or replace an onboard battery. Static charging stations cause a mission interruption and
increase time required to complete the coverage mission. It is also important to choose proper
locations in the case of static charging stations. However, a process of installing the charging
stations is time-consuming, which makes them impractical for missions where coverage must be achieved within a short period of time, e.g., such as rescue or emergency search operations. Mobile
charging stations can move around the area to optimize a UAV battery recharging or replacing
process. A challenge of the latter case is to plan motion trajectories not only for UAVs but also
for a mobile charging station. Joint motion planning improves coverage efficiency but increases
computational complexity of a trajectory planning. This paper considers a problem of efficient
area coverage with multiple UAVs and a mobile charging station using a genetic algorithm.
To adapt a genetic algorithm for the coverage problem, a chromosome formation method is proposed
in the paper. The method allows encoding trajectories of the UAVs and the mobile charging
station, and takes into account time and a place of charging (replacing) the UAV batteries. To
evaluate the proposed approach, a software was developed in Python programming language. The
obtained results of the simulation demonstrated feasibility of the proposed approach
References
Systems, 2013, No. 12 (61), pp. 1258-1276.
2. Semenas R., Bausys R. Adaptive Strategy for Environment Exploration in Search and Rescue
Missions by Autonomous Robot Lecture Notes in Networks and Systems, ed. by H. Sharma
[et al.]. Singapore: Springer Singapore, 2021б зз. 335-353.
3. Almadhoun R., Taha T., Seneviratne L., Zweiri Y. A survey on multi-robot coverage path planning
for model reconstruction and mapping, SN Applied Sciences, 2019, No. 8 (1), pp. 847.
4. Cabreira T., Brisolara L., Ferreira Jr. P.R. Survey on Coverage Path Planning with Unmanned
Aerial Vehicles, Drones, 2019, No. 1 (3), pp. 4.
5. Bai Y., Wang Y., Svinin M., Magid E., Sun R. Adaptive Multi-Agent Coverage Control With
Obstacle Avoidance, IEEE Control Systems Letters, 2022, 6, pp. 944-949.
6. Hayat S., Yanmaz E., Brown T.X., Bettstetter C. Multi-objective UAV path planning for search
and rescue. Singapore, Singapore: IEEE, 2017, pp. 5569-5574.
7. Kalyaev I.A., Kapustyan S.G. Gruppovoe upravlenie robotami: problemy, resheniya [Group control
of robots: problems, solutions], Izvestiya vysshikh uchebnykh zavedeniy. Mashinostroenie [News of
higher educational institutions. Mechanical engineering], 2011, 13, pp. 7-12.
8. Karapetyan N., Benson K., McKinney C., Taslakian P., Rekleitis I. Efficient Multi-Robot Coverage
of a Known Environment, 2017, pp. 1846-1852.
9. Vasil'ev I.A, Polovko S.A., Smirnova E.Yu. Organizatsiya gruppovogo upravleniya mobil'nymi
robotami dlya zadach spetsial'noy robototekhniki [Organization of group control of mobile robots
for special robotics tasks], Informatika, telekommunikatsii i upravlenie [Informatics, telecommunications
and control], 2013, pp. 119-123.
10. Di Franco C., Buttazzo G. Energy-Aware Coverage Path Planning of UAVs. – Vila Real:
IEEE, 2015. – P. 111-117.
11. Suzuki K.A.O., Kemper Filho P., Morrison J.R. Automatic Battery Replacement System for UAVs:
Analysis and Design, Journal of Intelligent & Robotic Systems, 2012, No. 1–4 (65), pp. 563-586.
12. Li B., Patankar S., Moridian B., Mahmoudian, N. Planning Large-Scale Search and Rescue
using Team of UAVs and Charging Stations Philadelphia, PA, USA: IEEE, 2018, pp. 1-8.
13. Li B., Page B. R., Hoffman J., Moridian B., Mahmoudian N. Rendezvous Planning for Multiple
AUVs With Mobile Charging Stations in Dynamic Currents, IEEE Robotics and Automation
Letters, 2019, No. 2 (4), pp. 1653-1660.
14. Wei M., Isler V. Coverage Path Planning Under the Energy Constraint Brisbane, QLD: IEEE,
2018, pp. 368-373.
15. Tan C.S., Mohd-Mokhtar R., Arshad M.R. A Comprehensive Review of Coverage Path Planning in
Robotics Using Classical and Heuristic Algorithms, IEEE Access, 2021, 9, pp. 119310-119342.
16. Denisov E., Sagitov A., Yakovlev K.S., Su K.L., Svinin M.M., Magid E. Towards Total Coverage
in Autonomous Exploration for UGV in 2.5D Dense Clutter Environment: Prague, Czech
Republic: SCITEPRESS - Science and Technology Publications, 2019, pp. 409-416.
17. Pshikhopov V.Kh., Medvedev Yu.M., Kostyukov V.A., Khusseyn F. Kadim A. Trajectory planning
algorithms in two-dimensional environment with obstacles, Informatika i avtomatizatsiya
[Computer science and automation], 2022, 21 (3), pp. 459-492.
18. Gladkov L., Kureychik V., Kureychik V. Geneticheskie algoritmy [Genetic algorithms]. Moscow:
Fizmatlit, 2010, 368 p.
19. Umbarkar A.J., Sheth P.D. Crossover operators in genetic algorithms: a review, ICTACT
Journal on Soft Computing, 2015, No. 01 (06), pp. 1083-1092.
20. Lozano M., Herrera F., Cano J. Replacement strategies to preserve useful diversity in steadystate
genetic algorithms, Information Sciences, 2008, No. 23 (178), pp. 4421-4433.
21. Deb K., Deb A. Analysing mutation schemes for real-parameter genetic algorithms, International
Journal of Artificial Intelligence and Soft Computing, 2014, No. 1 (4), pp. 1.
22. Tuncer A., Yildirim M. Chromosome Coding Methods in Genetic Algorithm for Path Planning of Mobile
Robots,ed. by E. Gelenbe, R. Lent, G. Sakellari. London: Springer London, 2011, pp. 377-383.
23. Guruji A. K., Agarwal H., Parsediya D. K. Time-efficient A* Algorithm for Robot Path Planning,
Procedia Technology, 2016, 23, pp. 144-149.
24. Koenig S., Likhachev M. D* lite, In Eighteenth national conference on Artificial intelligence,
2002, pp. 476-483.
