Heterogeneous Coverage Path Planning For Multi-Agent Systems With ACO and GA

Coverage path planning (CPP) is a vital task in various fields, including agriculture, robotics, and unmanned aerial vehicles. It involves determining a path that covers all points of a given area while avoiding obstacles and minimizing overlapping. This paper presents a comprehensive approach to CPP that consists of two main phases: formation and coverage. Agents are divided into several groups, and each group reaches a consensus to establish a specific formation at a rendezvous point. Then Based on the agreed-upon location, a specific area is assigned to each group for coverage. For this purpose, first, the Voronoi division of the coverage space is done through triangular meshing then the scanning time of Voronoi cells by each group and the migration time of each group from its initial position to the destination cell have been utilized for region allocation. Finally, the Traveling Salesman Problem is tackled using ant colony and genetic algorithms to find the order of visitation for each group of agents. In this paper, obstacles have been considered in the cost function for both ant colony optimization and genetic algorithm, resulting in the optimal solution for the order of visitation for each group of agents. In addition, the proposed coverage path planning (CPP) method utilizes heterogeneous coverage to provide fast and effective coverage. The use of multiple agents covering their own areas ensures that if one agent fails, the mission does not stop, increasing the mission's strength and robustness.