紀要論文

非同期自律分散ロボット群に対する集合アルゴリズム

ASYNCHRONOUS GATHERING ALGORITHMS FOR AUTONOMOUS MOBILE ROBOTS

jpn

24368083

https://doi.org/10.15002/00025384

法政大学大学院理工学研究科

法政大学大学院紀要. 理工学研究科編

63

1

8

2022-03-24

Version of Record

We consider a Gathering problem for n autonomous mobile robots in an asynchronous scheduler (ASYNC). We use two models of the robots that have the capability of detecting whether there is more than one robot or not at its current point called local weak multiplicity detection and persistent memory called light. The result has been provided that Gathering can be solved with strong multiplicity detection if and only if n is odd. In the light model, it is known that Gathering can be solved by robots with 10 colors. This paper shows that Gathering can be solved by n = 3, 4 robots with local weak multiplicity detection. Additionally, we improve the result by reducing the number of colors 10 to 3. We also show that we can construct a simulation algorithm of any unfair SSYNC algorithm using k colors by ASYNC robots with 3k colors, where unfairness does not guarantee that every robot is activated infinitely often.

Article