An Efficient Recharging Task Planning Method For MultiRobot Autonomous Recharging Problem As robots are increasingly employed in the warehouse operation, an important problem that needs to be solved is the Autonomous Recharging Problem (ARP); that is deciding when and where to recharge robots. Former research in ARP is disjoint that only focuses on one of above two questions, considering the high computation time. In this paper, we describe an efficient recharging task planning method to solve ARP and it includes two phases: In the first phase, recharging task planning based on task sequence segmentation is proposed for individual robot, in which both when to recharge and where to recharge are considered to maximize operational efficiency. And it also improves the computation efficiency by segmenting task sequence and planning each recharging task recursively. In the second phase, all robots task sequences with planned recharging tasks are centralized and selected recharging stations of some planned recharging tasks are reallocated, using maximum bipartite graph matching to reduce waiting time for other robots recharging and improve overall task execution efficiency. The proposed method is validated by means of simulation in a real warehouse environment.

Heuristicbased Multiple Mobile Depots Route Planning for Recharging Persistent Surveillance Robots Persistent surveillance of a target space using multiple unmanned aerial vehicles (UAVs) has multiple applications such as geographical surveys, air quality monitoring, and security monitoring. The limited onboard battery capacity challenges the continuous operation in these applications of persistent robots. We consider the problem for recharging persistent robots using mobile depots. The mobile depots collectively compute a set of tours to recharge all persistent robots with the minimum total cost. Compared to other works, the persistent UAVs are not required to detour to a static depot for energy replenishment such as recharging or battery swapping. We formulate this problem as a Generalized Multiple Depots Travelling Salesman Problem (GMDTSP) on a complete graph. A heuristicbased algorithm Multiple Depots Random Select (RSMD) is proposed to solve the recharging problem efficiently. The RSMD has proved to have an analytical constant upper bound in the worstcase scenario. We also propose a postprocessing heuristic (RSMDIM) to improve the solution quality further. We demonstrate the efficiency and effectiveness of our algorithm via benchmark on multiple instances from TSPLIB and GTSPLIB. The simulation results show that RSMD and RSMDIM will perform significantly faster than the state of the art heuristic solver LKH with a loss of about 10% of solution quality.