论文标题
使用有限能量的K机器人对地下画廊进行有效检查
Efficient inspection of underground galleries using k robots with limited energy
论文作者
论文摘要
我们研究了使用K代理商最佳检查地下（水下）画廊的问题。我们考虑了一个带有一个开口的画廊，并带有树拓扑结构植根于开口。由于管道直径很小（洞穴），代理是小型机器人，自主权有限，在画廊的开口处有一个供应台。因此，它们最初被放置在根部，并且需要定期返回供应站。我们的目标是设计离线策略，以用$ k $小型机器人有效地覆盖树。我们考虑两个目标功能：覆盖时间（最大集体时间）和覆盖距离（总行进距离）。最大的集体时间是机器人花费的最大时间需要完成其分配的任务（假设所有机器人同时启动）；总行进距离是所有覆盖步道的长度的总和。由于问题对于大树很棘手，因此我们提出了近似算法。通过密集的数值实验，在随机树上均显示了次优溶液的效率和准确性。
We study the problem of optimally inspecting an underground (underwater) gallery with k agents. We consider a gallery with a single opening and with a tree topology rooted at the opening. Due to the small diameter of the pipes (caves), the agents are small robots with limited autonomy and there is a supply station at the gallery's opening. Therefore, they are initially placed at the root and periodically need to return to the supply station. Our goal is to design off-line strategies to efficiently cover the tree with $k$ small robots. We consider two objective functions: the covering time (maximum collective time) and the covering distance (total traveled distance). The maximum collective time is the maximum time spent by a robot needs to finish its assigned task (assuming that all the robots start at the same time); the total traveled distance is the sum of the lengths of all the covering walks. Since the problems are intractable for big trees, we propose approximation algorithms. Both efficiency and accuracy of the suboptimal solutions are empirically showed for random trees through intensive numerical experiments.
