日本フィジカルAI新聞

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

群制御arXiv:cs/0212022

未知環境におけるロボット群の高速分散アルゴリズム

Algorithms for Rapidly Dispersing Robot Swarms in Unknown Environments

シェア:XThreadsFacebookLINEはてブBluesky

未知の領域にロボット群を素早く行き渡らせる分散アルゴリズムを提案し、単一入口では最適なmakespan 2A-1を達成、複数入口ではO(log(k+1))競合比を証明した。

著者: Tien-Ruey Hsiang, Esther M. Arkin, Michael Bender, Sandor P. Fekete, Joseph S. B. Mitchell

分類: cs.RO

原文アブストラクト

We develop and analyze algorithms for dispersing a swarm of primitive robots in an unknown environment, R. The primary objective is to minimize the makespan, that is, the time to fill the entire region. An environment is composed of pixels that form a connected subset of the integer grid. There is at most one robot per pixel and robots move horizontally or vertically at unit speed. Robots enter R by means of k>=1 door pixels Robots are primitive finite automata, only having local communication, local sensors, and a constant-sized memory. We first give algorithms for the single-door case (i.e., k=1), analyzing the algorithms both theoretically and experimentally. We prove that our algorithms have optimal makespan 2A-1, where A is the area of R. We next give an algorithm for the multi-door case (k>1), based on a wall-following version of the leader-follower strategy. We prove that our strategy is O(log(k+1))-competitive, and that this bound is tight for our strategy and other related strategies.

関連論文

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

OZ GAMING(GPU搭載BTOゲーミングPC)

OZ GAMING(GPU搭載BTOゲーミングPC)の公式広告バナーOZ GAMINGで完成品PCを見る ↗
PR本紙発行元 EmplifAI