Scholarlink

<p>The presence of symmetric and periodic configurations introduces complexities while solving various types of tasks on a grid graph using autonomous robots. Though symmetry and periodicity can be easily broken in some scenarios, it can be difficult and sometimes impossible to break the same in certain scenarios. This paper studies all possible types of symmetric and periodic configurations that exist in a grid and presents techniques that successfully break symmetry and periodicity in a finite grid within finite time. It highlights the scenarios where breaking of the same is impossible. This paper considers oblivious and asynchronous robots on grids that are endowed with unlimited visibility and pebbles but do not have a sense of direction or any communication among themselves. Though the proposed techniques may be used as a preliminary step while solving various types of tasks on a grid, we specifically present the use of these techniques for <i>exploration</i> of a grid using an already existing exploration algorithm.</p>

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

Techniques to Break Symmetry and Periodicity in Grids with Asynchronous Robots

  • 期刊论文

  • 发表日期：

    2025年7月29日

查看全文
  • Madhumita Sardar,
  • Deepanwita Das,
  • Srabani Mukhopadhyaya

摘要

The presence of symmetric and periodic configurations introduces complexities while solving various types of tasks on a grid graph using autonomous robots. Though symmetry and periodicity can be easily broken in some scenarios, it can be difficult and sometimes impossible to break the same in certain scenarios. This paper studies all possible types of symmetric and periodic configurations that exist in a grid and presents techniques that successfully break symmetry and periodicity in a finite grid within finite time. It highlights the scenarios where breaking of the same is impossible. This paper considers oblivious and asynchronous robots on grids that are endowed with unlimited visibility and pebbles but do not have a sense of direction or any communication among themselves. Though the proposed techniques may be used as a preliminary step while solving various types of tasks on a grid, we specifically present the use of these techniques for exploration of a grid using an already existing exploration algorithm.