Scholarlink

In this paper, we consider the pattern formation problem of mobile agents in \(n\times m\) dynamic grids, requiring k agents in the grid to stay at x designated&#xa0;(target) nodes to form some shape (pattern). We assume that at most one link is missing at each round. In this case, some agent’s movement may be always blocked and the agent cannot reach any target node. In addition, if the number k of agents is smaller than the number x of target nodes, several target nodes cannot be occupied. For this reason, focusing on the relationship between the values of k and x, we consider variants of the pattern formation problem in dynamic grids and examine how differences in these requirements and the number of agents influence the design and performance of algorithms. First, we consider the case of \(k \le x\) . In this case, we consider the approximate pattern formation problem, requiring at least \(k-1~(&lt;x_ target="" nodes="" to="" be="" occupied.="" For="" this="" problem_="" we="" propose="" an="" algorithm="" achieve="" approximate="" pattern="" formation="" in="" _O_kn_km_="" rounds.="" Next_="" consider="" the="" case="" of="" _k=""&gt; x\) . In this case, we consider the exact pattern formation problem, requiring each of the x target nodes to be occupied. For this problem, we propose an algorithm to achieve exact pattern formation in \(O(kn+km+mn)\) rounds. In particular, when \(k - x\) is sufficiently large, we show that exact pattern formation can be achieved in \(\varTheta (n+m)\) rounds.</x_>

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

Pattern Formation of Mobile Agents in Dynamic Grids

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Masahiro Shibata,
  • Sayaka Kamei,
  • Fukuhito Ooshita,
  • Hirotsugu Kakugawa

摘要

In this paper, we consider the pattern formation problem of mobile agents in \(n\times m\) dynamic grids, requiring k agents in the grid to stay at x designated (target) nodes to form some shape (pattern). We assume that at most one link is missing at each round. In this case, some agent’s movement may be always blocked and the agent cannot reach any target node. In addition, if the number k of agents is smaller than the number x of target nodes, several target nodes cannot be occupied. For this reason, focusing on the relationship between the values of k and x, we consider variants of the pattern formation problem in dynamic grids and examine how differences in these requirements and the number of agents influence the design and performance of algorithms. First, we consider the case of \(k \le x\) . In this case, we consider the approximate pattern formation problem, requiring at least \(k-1~(<x_ target="" nodes="" to="" be="" occupied.="" For="" this="" problem_="" we="" propose="" an="" algorithm="" achieve="" approximate="" pattern="" formation="" in="" _O_kn_km_="" rounds.="" Next_="" consider="" the="" case="" of="" _k=""> x\) . In this case, we consider the exact pattern formation problem, requiring each of the x target nodes to be occupied. For this problem, we propose an algorithm to achieve exact pattern formation in \(O(kn+km+mn)\) rounds. In particular, when \(k - x\) is sufficiently large, we show that exact pattern formation can be achieved in \(\varTheta (n+m)\) rounds.