Generating a Region Map for The Problem of Complete Coverage and Path Planning

Emergency response procedures for the victims of natural disasters require information about the number and location of victims and their needs or injuries. Unmanned Aerial Vehicles (UAVs) can efficiently reconnaissance the disaster area. The sum of UAVs’ routes has to cover the entire disaster area, which is divided into sectors with priorities. The sector identification is based on merging areas with a similar expected number of victims. We prioritize sectors with more victims; UAVs should visit them as early as possible. This paper proposes a new method of building sectors for real-world data from GIS (Geographic Information System) data sets. The process is based on merging cells into regions using a flood-fill search approach, which can be implemented directly on the input due to the rasterized structure of these data sets. We verify the usefulness of the method by computer simulations.We perform experiments optimizing UAV paths for four areas in Poland. We divide each area in five ways into collections of regions and compare the usefulness of the division for optimizing UAV routes regarding two objectives to be minimized: the execution time of the operation and the size of the area over the curve of the cumulative distribution function of detected victims over time. A good division of the area into regions can increase the quality of the results.