We consider distributed systems of autonomous, punctiform, mobile robots that operate in the Euclidean plane by executing an infinite sequence of Look-Compute-Move cycles. Robots are anonymous, indistinguishable, homogeneous, and disoriented. In literature, four base models have been proposed to study four different memory-communication settings: \(\mathcal {OBLOT}\) (oblivious and silent), \(\mathcal {FSTA}\) (finite-state and silent), \(\mathcal {FCOM}\) (oblivious and finite-communication), and \(\mathcal {LUMI}\) (finite-state and finite-communication). In particular, the research has investigated how the computational power of these models is affected by considering three main classes of robot schedulers: FSYNCH (fully synchronous), SSYNCH (semi-synchronous), and ASYNCH (asynchronous). This paper focuses on a peculiar type of SSYNCH schedulers, the sequential ones, which activate only one robot at each round. We consider three subclasses: the general sequential scheduler (SEQ), the permutation scheduler (PERM), and the well-known round-robin (RROBIN). For each base model, we investigate how the robots’ computational power changes as the scheduler class varies, thus providing a first overview of the computational landscape of sequential schedulers.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the Computational Power of Mobile Robots Under Sequential Schedulers

  • Caterina Feletti,
  • Paola Flocchini,
  • Nicola Santoro

摘要

We consider distributed systems of autonomous, punctiform, mobile robots that operate in the Euclidean plane by executing an infinite sequence of Look-Compute-Move cycles. Robots are anonymous, indistinguishable, homogeneous, and disoriented. In literature, four base models have been proposed to study four different memory-communication settings: \(\mathcal {OBLOT}\) (oblivious and silent), \(\mathcal {FSTA}\) (finite-state and silent), \(\mathcal {FCOM}\) (oblivious and finite-communication), and \(\mathcal {LUMI}\) (finite-state and finite-communication). In particular, the research has investigated how the computational power of these models is affected by considering three main classes of robot schedulers: FSYNCH (fully synchronous), SSYNCH (semi-synchronous), and ASYNCH (asynchronous). This paper focuses on a peculiar type of SSYNCH schedulers, the sequential ones, which activate only one robot at each round. We consider three subclasses: the general sequential scheduler (SEQ), the permutation scheduler (PERM), and the well-known round-robin (RROBIN). For each base model, we investigate how the robots’ computational power changes as the scheduler class varies, thus providing a first overview of the computational landscape of sequential schedulers.