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