One of the main challenges when using multiple robots to explore unknown environments is the allocation of target points or regions to the individual units. To date, commonly used approaches produce uneven assignment of targets in situations where multiple targets have to be assigned to each robot. This imbalance can lead to increased overall exploration time and poses an interesting task for further investigation. Based on insights from Multi-Robot Routing and Traveling Salesman Problem research, we propose a specific algorithm for target point allocation that has advantageous properties in highly dynamic applications like exploration. The presented pairwise optimization procedure is suitable for application in distributed and challenging settings, not requiring central coordination or all to all communication, making our exploration strategy robust and flexible. We provide a theoretical analysis and statistical evaluations. Comparisons with representative approaches from the literature show that our algorithm is competitive with the best performing centralized approach.

In the context of robotics coverage describes the deployment of mobile sensors or agents in a target area. This paper presents a new solution to coverage in nonconvex environments. We apply a modification to the coverage approach in (Cortes, et.al., 2004), making use of visibility sets and a contraction of the environment, leading to a change in the bounds of integration. The resulting feedback control is fully distributed, has guaranteed, inherent collision avoidance without separate path planning and reduced communication and computation requirements compared to similar approaches. We also formulate an extension to agents with limited sensing range. Our method works in unknown environments, if all regions are of equal interest. We provide simulation results demonstrating the advantageous properties of the approach.