Approximation Algorithms for Charging Station Placement for Mobile Robots

摘要

Optimal placement of charging stations in a workspace is a crucial problem to address, for efficient operation of battery-driven mobile robots. When the battery charge of a robot reaches a certain threshold, the robot must be able to reach a nearby charging station to recharge its battery. In this paper, we deal with two different versions of the optimization problem related to the optimal placement of charging stations in a robot workspace. The first problem is formulated to find an optimal number of charging stations given a battery threshold deciding the need to move to a charging station, and the second problem finds an optimal battery threshold for a given number of charging stations. Both the problems involve finding the locations of charging stations, such that from any obstacle-free location at least one charging station is reachable with at most threshold amount of battery charge remaining with the robot. In this paper, we prove these optimization problems to be NP-hard, i.e., computationally intractable. To handle intractability of the above minimization problems, we design two polynomial-time approximation algorithms to find near-optimal solutions. Our algorithms achieve significantly high scalability without compromising the quality of the solution beyond a certain factor of the optimal solution. Experimental results show that our algorithms run order-of-magnitude faster than a recently proposed Satisfiability Modulo Theory (SMT)-based approach and maintain solution quality within the theoretical bounds on the optimal solution.