Efficient communication-aware dynamic coverage using space-filling curves

In this paper, we consider a dynamic coverage problem where a team of mobile robots needs to cover a set of time-varying Points of Interest (POIs), while maintaining their connectivity to a remote station in a realistic communication environment. Our goal is to design the motion and communication strategies of the robots such that they periodically visit the POIs, communicate the gathered information to a remote station, minimize their total energy costs, including motion, sensing and communication energy, and satisfy other system constraints. In our previous work [1], we have shown how to pose this problem as a Mixed Integer Linear Program (MILP), which is computationally expensive. In this paper, we focus on designing a considerably more computationally-efficient heuristic approach to tackle this problem. More specifically, we propose to utilize the space-filling curves to efficiently assign the POIs and plan the trajectories of the robots. Under certain conditions, we mathematically show that our heuristic approach is at most a constant factor away from the global optimum. Our simulation results then confirm that our approach is considerably faster than solving the MILP, especially when the dimension of the problem is high. They further show that the energy consumption of our approach is only around 26% more than the optimum.