Charging Station Placement for Indoor Robotic Applications

For an autonomous mobile robot, when the available power goes below a certain threshold, the robot needs to abort its current task and move towards a charging station to recharge its battery. The efficiency of an autonomous mobile robot depends significantly on the location of the charging stations. In this paper, we address the charging station placement problem for mobile robots in a controlled workspace. We propose two algorithms to place a number of charging stations so that a robot is always capable of reaching one of the charging stations from any obstacle-free location in the workspace without aborting its task too early. We reduce the charging-station placement problem to a series of Satisfiability Modulo Theory (SMT) problems and use the off-the-shelf SMT solver Z3 to implement our algorithm. The algorithm produces as output the locations of the charging stations in the workspace and the trajectories from any obstacle-free locations to one of the charging stations. Our experimental results show how our algorithm can efficiently find the locations of the charging stations and robot trajectories to reach the charging stations. We demonstrate through simulation how the generated trajectories can be effectively used by a robot to reach a charging stations autonomously without getting depleted with power.