Grid navigation algorithm disperses agents efficiently in optimal time
Beyond the Boundary: Optimal Grid Dispersion by Spread, Reverse, and Collect
Distributed, Parallel, and Cluster Computing
Summary
The problem is to move multiple agents on a grid so each ends up on a different square without overlap. Previous methods needed either slow or complicated communication. The authors present a new way to spread agents using a zigzag sweep that goes out and then back inside the grid, requiring no knowledge of the grid size. This approach is faster for small groups of agents and uses limited memory, matching known theoretical limits.
What this means in practice
- •For robotic system engineers: Design movement protocols for groups of robots to efficiently spread out on grid-like spaces with minimal communication and memory.
- •For wireless sensor network developers: Implement node activation strategies to quickly distribute devices within grid-mapped deployment areas while using local communication only.
Authors
Manish Kumar, Anisur Rahaman Molla, Debasish Pattanayak, Subhajit Pramanick
Abstract
\emph{Dispersion} requires a set of mobile agents to occupy distinct nodes of a graph such that each node contains at most one agent. We study deterministic dispersion of $k\le n$ agents on an $n$-node oriented square grid, where each node has globally consistent North, East, South, and West port labels, from arbitrary initial configurations. This includes both \emph{rooted} configurations, where all agents are co-located initially, and \emph{general} configurations, where agents are initially distributed arbitrarily across the nodes. On oriented square grids, Kshemkalyani, Molla, and Sharma~\cite{KMS20} gave an $O(\min(k,\Side))$-round algorithm in the local-communication model, where only agents on the same node can exchange information, and an $O(\sqrt{k})$-round algorithm in the global-communication model, where any two agents can communicate regardless of position, both using $O(\log k)$ bits per agent. The bound in the local communication model is optimal when $k=Θ(n)$, but it remains open whether local communication alone can match the $Ω(\sqrt{k})$ time lower bound when $k=o(n)$. We solve this by presenting \textsc{Spread--Reverse--Collect} (SRC), a deterministic algorithm that disperses any $k\le n$ agents in $O(\sqrt{k})$ synchronous rounds using $O(\log k)$ bits of persistent memory per agent, matching both time and memory lower bounds. SRC is based on a geometric primitive, a \sharpS-shaped parallel sweep, together with a simple priority rule. Unlike earlier grid algorithms that gather agents at the boundary and spread out from there, each SRC sweep starts from the agents' current position, and when it reaches the boundary the group simply reflects its sweep back inside and continues. SRC therefore needs no knowledge of the grid size and runs unchanged on an infinite oriented grid.