In this article, we study multirobot path planning for persistent monitoring tasks. We consider the case where robots have a limited battery capacity with a discharge time$D$. We represent the areas to be monitored as the vertices of a weighted graph. For each vertex, there is a constraint on the maximum allowable time between robot visits, called the latency. The objective is to find the minimum number of robots that can satisfy these latency constraints while also ensuring that the robots periodically charge at a recharging depot. The decision version of this problem is known to be PSPACE-complete. We present a$O\left(\frac{\log D}{\log \log D} h \log \rho\right)$approximation algorithm for the problem where$\rho$is the ratio of the maximum and the minimum latency constraints, and$h$reflects the ratio of distance of vertices from the depot to their latency constraints. We also present an orienteering-based heuristic to solve the problem and show empirically that it typically provides higher quality solutions than the approximation algorithm. We extend our results to provide an algorithm for the problem of minimizing the maximum weighted latency given a fixed number of robots. We evaluate our algorithms on large problem instances in a patrolling scenario and in a wildfire monitoring application. We also compare the algorithms with an existing solver on benchmark instances.

In this paper, we present an approach for coverage path planning for a team of an energy-constrained Unmanned Aerial Vehicle (UAV) and an Unmanned Ground Vehicle (UGV). Both the UAV and the UGV have predefined areas that they have to cover. The goal is to perform complete coverage by both robots while minimizing the coverage time. The UGV can also serve as a mobile recharging station. The UAV and UGV need to occasionally rendezvous for recharging. We propose a heuristic method to address this NP-Hard planning problem. Our approach involves initially determining coverage paths without factoring in energy constraints. Subsequently, we cluster segments of these paths and employ graph matching to assign UAV clusters to UGV clusters for efficient recharging management. We perform numerical analysis on real-world coverage applications and show that compared with a greedy approach our method reduces rendezvous overhead on average by 11.33%. We demonstrate proof-of-concept with a team of a VOXL m500 drone and a Clearpath Jackal ground vehicle, providing a complete system from the offline algorithm to the field execution.

We introduce and investigate the recharging rendezvous problem for a collaborative team of Unmanned Aerial Vehicles (UAVs) and Unmanned Ground Vehicles (UGVs), in which UAVs with limited battery capacity and UGVS persistently monitor an area. The UGVs also act as mobile recharging stations for the UAVs. In contrast to prior work on such problems, we consider the challenge of dealing with stochastic energy consumption in a risk-aware fashion. Specifically, we consider a bi-criteria optimization problem of minimizing the time taken by the UAVs on recharging detours while ensuring that the probability that no UAV runs out of charge is greater than a user-defined risk tolerance. This problem (termed Risk-aware Recharging Rendezvous Problem (RRRP)) is a combinatorial problem with a matching constraint — to ensure UAVs are assigned to the limited UGV recharging slots, and a knapsack constraint — to capture the risk tolerance. We propose a novel bicriteria approximation algorithm to solve RRRP and demonstrate its effectiveness in the context of a persistent monitoring mission compared to baseline methods.