Asynchronous pattern formation by anonymous oblivious mobile robots

Nao Fujinaga, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita

研究成果: 書籍/レポート タイプへの寄稿会議への寄与

30 被引用数 (Scopus)

抄録

We present an oblivious pattern formation algorithm for anonymous mobile robots in the asynchronous model. The robots obeying the algorithm, starting from any initial configuration I, always form a given pattern F, if I and F do not contain multiplicities and ρ(I) divides ρ(F), where ρ(·) denotes the geometric symmetricity. Our algorithm substantially outdoes an algorithm by Dieudonné et al. proposed in DISC 2010, which is dedicated to ρ(I) = 1. Our algorithm is best possible (as long as I and F do not contain multiplicities), since there is no algorithm that always forms F from I when ρ(F) is not divisible by ρ(I). All known pattern formation algorithms are constructed from scratch. We instead use a bipartite matching algorithm (between the robots and the points in F) we proposed in OPODIS 2011 as a core subroutine, to make the description of algorithm concise and easy to understand.

本文言語英語
ホスト出版物のタイトルDistributed Computing - 26th International Symposium, DISC 2012, Proceedings
ページ312-325
ページ数14
DOI
出版ステータス出版済み - 2012
イベント26th International Symposium on Distributed Computing, DISC 2012 - Salvador, ブラジル
継続期間: 10月 16 201210月 18 2012

出版物シリーズ

名前Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
7611 LNCS
ISSN(印刷版)0302-9743
ISSN(電子版)1611-3349

その他

その他26th International Symposium on Distributed Computing, DISC 2012
国/地域ブラジル
CitySalvador
Period10/16/1210/18/12

!!!All Science Journal Classification (ASJC) codes

  • 理論的コンピュータサイエンス
  • コンピュータサイエンス一般

フィンガープリント

「Asynchronous pattern formation by anonymous oblivious mobile robots」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル