遅延とエネルギー制約下でのグラフの持続的カバリング
Persistent Covering of a Graph under Latency and Energy Constraints
バッテリー制約のある複数UAVで広域を持続的にカバーするため、幾何・位相的性質を利用して最適化問題を縮小し、必要最小台数と巡回経路を効率的に求める手法を提案した。
著者: Jyh-Ming Lien, Sam Rodriguez, Marco Morales
分類: cs.RO
原文アブストラクト
Most consumer-level low-cost unmanned aerial vehicles (UAVs) have limited battery power and long charging time. Due to these energy constraints, they cannot accomplish many practical tasks, such as monitoring a sport or political event for hours. The problem of providing the service to cover an area for an extended time is known as persistent covering in the literature. In the past, researchers have proposed various hardware platforms, such as battery-swapping mechanisms, to provide persistent covering. However, algorithmic approaches are limited mostly due to the computational complexity and intractability of the problem. Approximation algorithms have been considered to segment a large area into smaller cells that require periodic visits under the latency constraints. However, these methods assume unlimited energy. In this paper, we explore geometric and topological properties that allow us to significantly reduce the size of the optimization problem. Consequently, the proposed method can efficiently determine the minimum number of UAVs needed and schedule their routes to cover an area persistently. We demonstrated experimentally that the proposed algorithm has better performance than the baseline methods.
