Genetic Algorithm Approach for a Class of Multi-Criteria, Multi-Vehicle Planner of UAVs

This work presents an solution for the problem of planning the routes of a small fleet of hand-launched fixed-wing UAVs to monitor by vision an area of forest at the minimum possible time, for rescuing support, fire detection, deforestation mitigation, among other important applications in the Amazon rain forest operational scenario. However, time is not the only criteria to be considered. Given that it is virtually impossible to recover a missing airplane in the deep jungle, another relevant objective is to apply as fewer UAVs as possible, to reduce the risks for the whole UAV system. Moreover, another aspect that complicates this specific application is the non-holonomic constraint of the fixed wing airplanes (lack of instantaneous lateral velocity). We had to restrict the changing of heading, and thus, the roll angle, to prevent the drifting of the PoI (point-of-interest) out of the camera plane. As a consequence, long turn radius imply longer route. The authors modeled this problem using the multi vehicle routing problem, combined with Dubins path generator to address the non-holonomicity aspect, in a multicriteria formulation to reach a solution that simultaneously takes into account time, number of UAVs and expended resources. The resulting problem formulation has a computational effort that tends to be extremely high as the number of way-points increases. The authors applied Genetic Algorithm to solve this multi-criteria NP-hard Dubins adapted routing problem. The presented results, applied to a fleet of mini-UAVs, show the effectiveness of the proposed work in providing a satisfactory solution in a very reasonable execution time.