Shortest Path Planning with an Energy-Constrained Robot
Shortest Path Planning with an Energy-Constrained Robot
复制标题
能量受限机器人的最短路径规划
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Gokarna Sharma
中科院分区：
文献类型：
--
作者：
Brian Sotolongo;Ayan Dutta;Stephen Sisley;Gokarna Sharma
本文研究了不具有无限移动能量的移动的机器人的最短路径规划问题。机器人在电池充满电的情况下最多可以行驶B距离。这个能量受限的机器人的目标是在k个充电站的存在下从位置S行进到位置G，同时最小化所产生的旅行成本。由于机器人受到能量的限制，它需要在一个或多个充电站停下来给电池充电。为了解决上述问题，我们提出了一种经典A* 搜索算法的变体，该算法以这样一种方式规划机器人的路径，即它在完全充电的情况下移动尽可能多的距离（最大值为B）。此外，它会选择一个作为下一个充电站，该充电站在从S到G的最短距离之上，最大限度地减少到达该充电站所需的额外距离。我们设计了新的启发式函数，引导搜索到这样的充电站，没有约束的最短路径的偏差是最小的。我们证明了所提出的方法是完整的。结果表明，我们提出的算法找到了一个最优的解决方案，而需要一个微不足道的时间来执行。
In this paper, we study the problem of shortest path planning for a mobile robot that does not possess unlimited energy for traveling. The robot can travel at most B distance with its battery fully charged. The objective of this energy-constrained robot is to travel from location S to location G in the presence of k charging stations while minimizing the incurred travel cost. As the robot is constrained by its energy, it needs to stop at one or more charging stations in order to recharge its battery. To solve the stated problem, we have proposed a variant of the classical A* search algorithm that plans the path of the robot in such a way that it moves as much distance as possible with a full recharge (the maximum being B). Furthermore, it chooses the one to be the next charging station that minimizes the extra distance that needs to be covered to reach it on top of the shortest distance from S to G. We have designed novel heuristic functions that guide the search towards such charging stations where the deviation from the shortest path without the constraint is the minimum. We prove that the proposed approach is complete. Results show that our proposed algorithm finds an optimal solution while taking a negligible time to execute.