日本フィジカルAI新聞

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

群制御arXiv:0905.3967

ビザンチン障害に耐えるロボットネットワークの最適収束アルゴリズム

Optimal byzantine resilient convergence in oblivious robot networks

シェア:XThreadsFacebookLINEはてブBluesky

記憶を持たず直接通信できないロボット群が、一部に任意の誤動作をするビザンチンロボットを含む場合でも、全員が同じ未知の位置に収束するための必要十分条件を示し、最適な耐障害性を持つ決定論的アルゴリズムを提案した。

著者: Zohir Bouzid, Maria Potop-Butucaru, Sébastien Tixeuil

分類: cs.DC, cs.RO

原文アブストラクト

Given a set of robots with arbitrary initial location and no agreement on a global coordinate system, convergence requires that all robots asymptotically approach the exact same, but unknown beforehand, location. Robots are oblivious-- they do not recall the past computations -- and are allowed to move in a one-dimensional space. Additionally, robots cannot communicate directly, instead they obtain system related information only via visual sensors. We draw a connection between the convergence problem in robot networks, and the distributed \emph{approximate agreement} problem (that requires correct processes to decide, for some constant $\epsilon$, values distance $\epsilon$ apart and within the range of initial proposed values). Surprisingly, even though specifications are similar, the convergence implementation in robot networks requires specific assumptions about synchrony and Byzantine resilience. In more details, we prove necessary and sufficient conditions for the convergence of mobile robots despite a subset of them being Byzantine (i.e. they can exhibit arbitrary behavior). Additionally, we propose a deterministic convergence algorithm for robot networks and analyze its correctness and complexity in various synchrony settings. The proposed algorithm tolerates f Byzantine robots for (2f+1)-sized robot networks in fully synchronous networks, (3f+1)-sized in semi-synchronous networks. These bounds are optimal for the class of cautious algorithms, which guarantee that correct robots always move inside the range of positions of the correct robots.

関連論文

  1. 1Boston Dynamics、車輪付きAtlasの研究試作機を紹介研究・技術
  2. 2newmoとKDDIが資本業務提携 2028年に堺市で自動運転タクシー商用化目指す提携・買収
  3. 3NVIDIA、CoRLでGR00T 2とIsaac Lab 3.0を発表新製品・発表
  4. 4GXOとApptronik、Apolloの物流現場試験を拡大 最大1,000台の展開を構想量産・展開
  5. 5Google DeepMind、ロボット向けAIを発表新製品・発表

PR・アフィリエイト広告

MINISFORUM(ミニPC)

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