日本フィジカルAI新聞

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

群制御arXiv:2106.03943

任意の匿名グラフにおける準最適な分散アルゴリズム

Near-Optimal Dispersion on Arbitrary Anonymous Graphs

シェア:XThreadsFacebookLINEはてブBluesky

複数ノードに初期配置されたロボットを各ノードに1台ずつ分散させる問題で、時間とメモリの両面で最適なマルチソースDFSアルゴリズムを提案した論文。

著者: Ajay D. Kshemkalyani, Gokarna Sharma

分類: cs.DC, cs.DS, cs.RO

原文アブストラクト

Given an undirected, anonymous, port-labeled graph of $n$ memory-less nodes, $m$ edges, and degree $\Delta$, we consider the problem of dispersing $k\leq n$ robots (or tokens) positioned initially arbitrarily on one or more nodes of the graph to exactly $k$ different nodes of the graph, one on each node. The objective is to simultaneously minimize time to achieve dispersion and memory requirement at each robot. If all $k$ robots are positioned initially on a single node, depth first search (DFS) traversal solves this problem in $O(\min\{m,k\Delta\})$ time with $\Theta(\log(k+\Delta))$ bits at each robot. However, if robots are positioned initially on multiple nodes, the best previously known algorithm solves this problem in $O(\min\{m,k\Delta\}\cdot \log \ell)$ time storing $\Theta(\log(k+\Delta))$ bits at each robot, where $\ell\leq k/2$ is the number of multiplicity nodes in the initial configuration. In this paper, we present a novel multi-source DFS traversal algorithm solving this problem in $O(\min\{m,k\Delta\})$ time with $\Theta(\log(k+\Delta))$ bits at each robot, improving the time bound of the best previously known algorithm by $O(\log \ell)$ and matching asymptotically the single-source DFS traversal bounds. This is the first algorithm for dispersion that is optimal in both time and memory in arbitrary anonymous graphs of constant degree, $\Delta=O(1)$. Furthermore, the result holds in both synchronous and asynchronous settings.

関連論文

  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・アフィリエイト広告

FRONTIER(GPU搭載BTOパソコン)

FRONTIER(GPU搭載BTOパソコン)の公式広告バナーFRONTIERでGPU搭載PCを見る ↗
PR本紙発行元 EmplifAI