エネルギー制約付きオンライン被覆経路計画の定数近似アルゴリズム
A Constant-Factor Approximation Algorithm for Online Coverage Path Planning with Energy Constraint
限られたエネルギーで未知環境を探索し充電を挟みながら全領域を被覆する問題に対し、経路長を最適解の定数倍に抑えるDFSベースの探索戦略を提案した。
著者: Ayan Dutta, Gokarna Sharma
分類: cs.RO, cs.DS
原文アブストラクト
In this paper, we study the problem of coverage planning by a mobile robot with a limited energy budget. The objective of the robot is to cover every point in the environment while minimizing the traveled path length. The environment is initially unknown to the robot. Therefore, it needs to avoid the obstacles in the environment on-the-fly during the exploration. As the robot has a specific energy budget, it might not be able to cover the complete environment in one traversal. Instead, it will need to visit a static charging station periodically in order to recharge its energy. To solve the stated problem, we propose a budgeted depth-first search (DFS)-based exploration strategy that helps the robot to cover any unknown planar environment while bounding the maximum path length to a constant-factor of the shortest-possible path length. Our $O(1)$-approximation guarantee advances the state-of-the-art of log-approximation for this problem. Simulation results show that our proposed algorithm outperforms the current state-of-the-art algorithm both in terms of the traveled path length and run time in all the tested environments with concave and convex obstacles.
