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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Charging Station Placement for Limited Energy Robots

  • Arun Kumar Das

摘要

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.