日本フィジカルAI新聞

世界のフィジカルAIを、日本語で。

群制御arXiv:1410.6726

移動ロボットによるバリアカバレッジ復旧のための最適オンライン・オフラインアルゴリズム

Optimal online and offline algorithms for robot-assisted restoration of barrier coverage

シェア:XThreadsFacebookLINEはてブBluesky

無線センサのバリアカバレッジを移動ロボットで復旧する問題に対し、ロボットの移動距離を最小化する最適な線形時間オフラインアルゴリズムと、バリア長の既知・未知に応じたオンラインアルゴリズムの競合比のタイトな上下界を与えた。

著者: J. Czyzowicz, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny

分類: cs.DS, cs.RO

原文アブストラクト

Cooperation between mobile robots and wireless sensor networks is a line of research that is currently attracting a lot of attention. In this context, we study the following problem of barrier coverage by stationary wireless sensors that are assisted by a mobile robot with the capacity to move sensors. Assume that $n$ sensors are initially arbitrarily distributed on a line segment barrier. Each sensor is said to cover the portion of the barrier that intersects with its sensing area. Owing to incorrect initial position, or the death of some of the sensors, the barrier is not completely covered by the sensors. We employ a mobile robot to move the sensors to final positions on the barrier such that barrier coverage is guaranteed. We seek algorithms that minimize the length of the robot's trajectory, since this allows the restoration of barrier coverage as soon as possible. We give an optimal linear-time offline algorithm that gives a minimum-length trajectory for a robot that starts at one end of the barrier and achieves the restoration of barrier coverage. We also study two different online models: one in which the online robot does not know the length of the barrier in advance, and the other in which the online robot knows the length of the barrier. For the case when the online robot does not know the length of the barrier, we prove a tight bound of $3/2$ on the competitive ratio, and we give a tight lower bound of $5/4$ on the competitive ratio in the other case. Thus for each case we give an optimal online algorithm.

関連論文

  1. 1Boston Dynamics、車輪付きAtlasの研究試作機を紹介研究・技術
  2. 2Google DeepMind、ロボット向けAIを発表新製品・発表
  3. 3GXOとApptronik、Apolloの物流現場試験を拡大 最大1,000台の展開を構想量産・展開
  4. 4SoftBank主導、Agile Robotsが5億ドル調達 NVIDIAと日立も参加資金調達
  5. 5パナソニックHDなど、触覚に即応する両手作業AI「T-Rex」を共同開発研究・技術

PR・アフィリエイト広告

MINISFORUM(ミニPC)

MINISFORUM(ミニPC)の公式広告バナーMINISFORUM公式ストアを見る ↗
PR本紙発行元 EmplifAI