.png){kind=icon}
返回
Approximation Algorithms for Charging Station Placement for Mobile Robots
.png){kind=icon}
PRE
AI
DOI：10.1109/IROS55552.2023.10341361.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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.
期刊
I
IF:
0
论文数:
55
被引数:
0
机构
引用论文
.png){kind=icon}
Online Coverage of Planar Environments by a Battery Powered Autonomous Mobile Robot电池供电的自主移动机器人对平面环境的在线覆盖
PREAI
分享收藏
查看更多内容