Robot Swarms for Exploration and Triangulation of Unknown Environments

The authors consider a robot swarm in an unknown polygon. All robots have only a limited communication range. They, then look for a triangulation of the polygon using the robots as vertices such that the number of robots used for the triangulation is minimized. All edges in the triangulation have a length smaller than the communication range. Exploring and guarding polygonal regions are classical problems that have been investigated for decades. Hoffmann et al. considered the online exploration of simple polygons with unlimited vision, Icking et al. and Fekete et al. exploration with limited and time-discrete vision, respectively. Exploration with both limited and time-discrete vision is presented by Fekete et al..