Charging Station Placement for Limited Energy Robots
摘要
We address the minimum charging station (Min-Station) placement problem for unlabelled robots. The input consists of a graph \(G=(V,E)\) , with given starting and target positions \(S \subset V\) and \(T \subset V\) , respectively, for a set of m robots. A robot moves one step by transitioning from one vertex to an adjacent vertex in G and has a movement capacity of r steps, meaning it can move up to r steps without recharging from either its starting position or a charging station. Each target position must be occupied by exactly one robot to complete the motion. The objective is to determine the minimum number of charging stations needed to ensure all target positions are reached. We prove that this problem is NP-hard, even for bounded degree graphs with a maximum degree of 6. However, on the positive side, we present linear and quadratic time algorithms for the Min-Station problem on paths and cycles.