Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces the Surplus Parking Gathering Problem ($\mathcal{SPG}$), a coordination challenge for autonomous robots on an infinite grid where the number of robots exceeds parking capacity. The authors establish necessary conditions for solvability and present a deterministic distributed algorithm that efficiently saturates parking nodes while gathering surplus robots at a designated node. The algorithm is proven to terminate in finite time, achieving optimal move complexity bounds of $O(n(a+b)+n^2)$ and $\Omega(n(a+b))$ for the problem.
Surplus robots can be efficiently gathered on an infinite grid, even when their numbers exceed parking capacities, using a novel deterministic algorithm.
In this paper, we introduce the \emph{Surplus Parking Gathering Problem} ($\mathcal{SPG}$), a new coordination problem for robots deployed on an infinite grid. The input consists of a set of designated parking nodes, each associated with a prescribed capacity, while the total number of robots exceeds the total parking capacity. The objective is to saturate every parking node exactly according to its capacity while gathering all remaining surplus robots at a common grid node that is not specified a priori. The robots are assumed to be autonomous, anonymous, oblivious, identical, disoriented, and homogeneous. We consider the asynchronous (\textsc{async}) model with global visibility and global strong multiplicity detection. We first establish necessary conditions for the solvability of $\mathcal{SPG}$ by characterizing the initial configurations that admit no deterministic distributed algorithm. For all the remaining solvable configurations, we present a deterministic distributed algorithm that correctly solves the problem. The proposed algorithm proceeds in several phases and avoids collisions throughout its execution. We prove that the algorithm terminates in finite time and, upon termination, every parking node is saturated according to its prescribed capacity while all surplus robots are gathered at a uniquely determined gathering node. We further analyze the move complexity of the proposed algorithm, obtaining an $O(n(a+b)+n^2)$ upper bound together with an $\Omega(n(a+b))$ worst-case lower bound for the $\mathcal{SPG}$ problem.