arXiv CSopen access

The Surplus Parking Gathering Problem in Infinite Grids

The Surplus Parking Gathering Problem in Infinite Grids Animesh Maiti1

Abhinav Chakraborty2

Subhash Bhagat1

1 Department of Mathematics

Indian Institute of Technology Jodhpur, Rajasthan, India Email: [email protected], [email protected]

arXiv:2607.05983v1 [cs.DC] 7 Jul 2026

2 Department of Mathematics

Birla Institute of Technology Mesra, Ranchi, Jharkhand, India Email: [email protected] Abstract In this paper, we introduce the Surplus Parking Gathering Problem (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 (async) model with global visibility and global strong multiplicity detection. We first establish necessary conditions for the solvability of 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) + n2 ) upper bound together with an Ω(n(a + b)) worst-case lower bound for the SPG problem.

1

Introduction

The coordination of large collections of autonomous mobile robots has been one of the central research topics in distributed computing and swarm robotics over the past three decades. Fundamental tasks such as gathering [13, 31, 14, 19], pattern formation [21, 7, 10], exploration [20, 3] and mutual visibility [24, 1, 26] have been extensively studied under various computational models. These problems are motivated by various applications including automated parking systems, environmental monitoring, search-and-rescue operations, and precision agriculture [29, 2]. The primary objective is to design distributed algorithms that enable robots to accomplish a common task despite their limited computational capabilities and the absence of explicit communication. In the traditional robot model, the robots are assumed to be autonomous (there is no central co1

ordinator), anonymous (they have no unique identifiers), homogeneous (all robots execute the same deterministic algorithm), and identical (they are physically indistinguishable). Depending on the underlying computational model, robots may operate either in a continuous Euclidean space or on the nodes of a graph. Robots are generally modeled as dimensionless points in Euclidean space in most existing work. In recent years, graph-based models have attracted considerable attention because they are able to capture many structured environments where robot movements are constrained by the topology of the underlying network. In this work, we consider robots deployed on the nodes of an infinite grid, where robot movements are restricted to adjacent grid nodes [4, 17]. The robots do not share a common global coordinate system; instead, each robot is equipped with its own local coordinate system whose origin is located at its current position. The directions and orientations of the coordinate axes may differ from one robot to another. However, since the robots are deployed on the nodes of an infinite square grid, they share a common unit of distance, namely the distance between two adjacent grid nodes, commonly referred to as the one-hop distance. In some computational models, the robots are assumed to have agreement on the directions and orientations of one or both coordinate axes. Furthermore, the robots may share a common sense of chirality, i.e., a common notion of clockwise orientation. However, in this paper, we assume that the robots are fully disoriented. That is, they do not agree on either the directions or the orientations of their local coordinate axes, nor do they possess a common chirality. Each robot is equipped with a visibility sensor, that enables it to observe the positions of other robots. Depending on the model, the visibility range may be limited or global. In this paper, we assume global visibility; hence, every robot can observe the positions of all other robots in the system. The robots are assumed to be silent; that is, they do not possess any explicit means of communication. The grid also contains a set of designated nodes, called parking nodes, each associated with a prescribed parking capacity. At any given time, a robot is either active or inactive. If a robot is active, it executes a Look–ComputeMove (LCM) cycle. During the Look phase, a robot obtains a snapshot of the current robot configuration and the locations of the parking nodes. In the Compute phase, it computes a destination node based on the snapshot obtained during the Look phase. The computed destination node may coincide with its current position. During the Move phase, it moves toward the computed destination. If the computed position is the current position, then a robot performs a null movement. After completing the cycle, the robot becomes inactive until it is activated again by the scheduler. In this paper, we assume instantaneous movement. Consequently, robots are observed only at grid nodes and never while traversing the edges of the grid graph. At any instant of time, a robot may move toward one of its adjacent nodes, and the movement must be only along the edges of the input grid graph. The robots are oblivious; that is, they possess no persistent memory and cannot recall any information from previous Look–Compute–Move (LCM) cycles, including past observations, computations, or movements. The activation of the robots and the execution of the phases in their computational cycles are governed by a scheduler. Depending on the synchronization assumptions, three standard computational models are commonly considered in the literature: Fully Synchronous (fsync), Semi-Synchronous (ssync), and Asynchronous (async). In the fsync model, all robots are activated simultaneously and execute their Look–Compute–Move cycles. The ssync model relaxes this assumption by allowing only a subset of the robots to be activated in each round; however, all activated robots complete their computational cycles synchronously within that round. In contrast, the async model assumes no global notion of time. Robots are activated independently by an adversarial scheduler, and the duration of each phase of the Look–Compute–Move cycle is finite but unpredictable. Consequently, the Look, Compute, and Move phases of different robots may overlap arbitrarily. Furthermore, the robots are not equipped with 2

motion-detection capabilities and therefore cannot distinguish between moving and stationary robots. As a result, a robot may perform its computation based on an outdated snapshot of the configuration. Throughout this paper, we consider the async model. The scheduler is assumed to be fair, ensuring that every robot is activated infinitely often. The robots may be equipped with multiplicity detection, which enables them to distinguish nodes occupied by multiple robots. Depending on the computational model, multiplicity detection may be either weak or strong. In this paper, we assume that the robots possess a global strong multiplicity detection. That is, every robot can determine the exact number of robots located at each occupied node in the configuration. Under local strong multiplicity detection, a robot can determine only the number of robots occupying its own node, rather than the multiplicities at all occupied nodes. Global strong multiplicity detection is essential for solving our problem, since otherwise the robots cannot determine whether the desired terminal configuration has been reached. We allow robots to be initially deployed on parking nodes. Each parking node is assigned a fixed capacity that determines the maximum number of robots that may occupy the node at any time during the execution. The capacities of the parking nodes are part of the input and are known to all robots. We assume that the total number of robots is strictly greater than the sum of the capacities of all parking nodes. The SPG problem combines two fundamental coordination tasks that have traditionally been studied independently. The first is the parking problem, in which robots are required to occupy a prescribed set of target locations. In our setting, this task is further constrained by the requirement that each designated parking node be occupied by exactly the number of robots specified by its capacity [9]. The second is the classical gathering problem, in which all robots must converge to a single node that is not known in advance. Formally, the objective of this problem is to transform any initial configuration into a final configuration such that, at some finite time (t > 0), every parking node contains exactly as many robots as its capacity. The remaining robots, referred to as surplus robots, must gather at a common grid node that is not specified in advance and must be determined autonomously by the robots. Consequently, the robots must simultaneously determine which robots should occupy the parking nodes and which robots should eventually form the surplus gathering, while preserving the correctness of both tasks throughout the execution.

1.1

Motivation

The SPG problem is motivated by both algorithmic and practical considerations. From an algorithmic perspective, SPG integrates two fundamental coordination tasks that have traditionally been studied independently. The parking problem assumes that every robot can eventually be assigned to a target location [9], whereas classical gathering algorithms require all robots to converge to a single location. In contrast, SPG requires both objectives to be achieved simultaneously under capacity constraints, i.e., the designated parking nodes must be saturated exactly according to their prescribed capacities, while all remaining surplus robots must gather at a common node that is not specified a priori. The problem is also motivated by practical applications involving capacity-constrained service locations, such as autonomous parking facilities, charging stations in robotic warehouses, and docking hubs in logistics systems. In these environments, a limited number of robots can be accommodated at designated service stations, while the remaining robots must wait in an organized manner until resources become available. Furthermore, most classical robot coordination models assume that robots move freely as dimensionless points in a continuous Euclidean space, where infinitesimally small movements with arbitrary precision 3

can be performed to avoid collisions. In some models, robots are even allowed to execute guided movements, that is, to follow prescribed curves during motion [11, 27]. Such assumptions, however, are often unrealistic in practical settings. Many real-world robotic systems operate in structured environments, such as warehouses, automated parking facilities, and agricultural fields, where robot movements are constrained by aisles, tracks, or other predefined pathways. Motivated by these applications, we model the environment as an infinite grid and restrict robot movements to its edges.

1.2

Related Work

The coordination of autonomous mobile robots has been extensively studied in distributed computing under a variety of computational models and environmental settings. Among the most fundamental coordination problems are gathering [13, 31, 14, 19], pattern formation [21, 7, 10] and mutual visibility [24, 1, 26], each aiming to enable a collection of autonomous robots to accomplish a common task despite severe computational limitations. Gathering is one of the most extensively studied coordination problems for autonomous mobile robots. The objective is to bring all robots to a single location that is not specified a priori. Depending on the computational model, gathering has been investigated under various assumptions. In recent years, considerable attention has been devoted to gathering in discrete environments, where robots are deployed on the nodes of anonymous graphs [15, 17, 25, 23]. Klasing et al. [25] investigated the gathering problem on anonymous rings and established that deterministic gathering is impossible in the absence of weak multiplicity detection. D’Angelo et al. [15] addressed deterministic gathering on finite grids. Di Stefano et al. [17] investigated the optimal gathering problem on infinite grids and proposed a distributed algorithm that gathers all robots at a Weber point while minimizing the total travel distance of the swarm. Their algorithm assumes global strong multiplicity detection, where the Weber point is defined as the graph node minimizing the sum of the shortest-path distances from all robot positions. Shibata et al. [28] considered the gathering problem for a system of seven autonomous mobile robots deployed on a triangular grid. Goswami et al. [23] considered the gathering problem of n ≥ 2 mobile robots on an infinite triangular grid, assuming that the robots possess limited visibility. They further proved that gathering on a triangular grid with 1-hop vision of robots is not possible even under a fsync scheduler if the robots do not agree on any axis. Arbitrary Pattern Formation (apf) is one of the fundamental coordination problems in swarm robotics, in which a collection of autonomous mobile robots is required to form an arbitrary geometric pattern specified as input. The problem was first introduced in [30], where the authors characterized the class of formable patterns using the notion of symmetricity. Subsequently, Flocchini et al. [21] investigated apf in the asynchronous (async) model for oblivious robots. Bose et al. [7] further investigated apf in the Euclidean plane under the opaque robot model, where the visibility of a robot may be obstructed by other robots. In contrast to apf, which requires robots to realize a prescribed geometric pattern, SPG requires robots to satisfy prescribed parking capacities while simultaneously gathering the remaining surplus robots. The parking problem [9] is another important coordination problem in swarm robotics, where robots are required to occupy a prescribed set of designated parking nodes while satisfying application-specific constraints. Unlike gathering, the objective is not to bring all robots to a common location but to distribute them among designated parking nodes. The parking problem may be regarded as a variant of the partitioning problem [18], where robots partition themselves into m groups and converge to separate regions. Several related coordination problems also require robots to occupy prescribed target locations. Fujinaga et al. [22] introduced the notion of fixed points while studying the landmark covering problem in the 4

Problem Gathering

Domain Plane, rings, grids

Triangular-grid gathering Pattern formation Parking

Triangular grid

Fixed-point / meeting-node problems Mutual visibility / exploration SPG

Plane or infinite grid

Plane or regular grids Infinite grid

Grids and graphs Infinite grid with capacities

Objective Gather all robots at one location Gather under limited visibility Form a prescribed pattern Occupy designated parking nodes Occupy fixed points or meet at designated nodes

Reference [25, 15, 17]

Ensure visibility or explore nodes Saturate parking nodes and gather surplus robots

[24, 1, 20]

[28, 23] [30, 21, 7, 10] [9] [22, 12, 4]

This paper

Table 1: Comparison with related coordination problems. Euclidean plane. The problem requires the robots to reach a configuration in which they all occupy a common fixed point or landmark. Building on this concept, Cicerone et al. [12] investigated the Embedded Pattern Formation problem and proposed a distributed algorithm that guarantees each robot occupies a unique fixed point within finite time without assuming common chirality. Similarly, the kcircle formation problem [16, 6] requires robots to form disjoint circles centered at predefined locations, with each circle containing exactly k robots positioned at distinct points on its circumference. Bhagat et al. [4, 5] subsequently extended this line of research by studying the Gathering over Meeting Nodes problem on infinite square grids, where the robots are deployed on grid nodes and a subset of the nodes is designated as meeting nodes. Unlike these problems, SPG requires robots to simultaneously satisfy parking-capacity constraints while gathering the remaining surplus robots at a common location. Other coordination problem investigated on infinite grids include the Mutual Visibility [24, 1, 26]. The Mutual Visibility problem requires the design of a distributed algorithm that enables robots to relocate to distinct positions such that no three of them become collinear. A comparison of SPG with closely related coordination problems is presented in Table 1. Although the above coordination problems have been extensively investigated, they have traditionally been studied independently. To the best of our knowledge, no existing work considers the simultaneous execution of parking and gathering under parking-capacity constraints on infinite grids. We address this gap by introducing the SPG , which integrates these two objectives within a unified distributed framework and introduces new challenges arising from symmetry, asynchronous execution, collision avoidance, and parking-capacity constraints.

1.3

Technical Challenges

The SPG problem poses several challenges that do not arise in classical gathering or parking problems. First, the robots must simultaneously accomplish two interdependent objectives. Unlike the parking problem, not all robots can be assigned to the designated parking nodes because the total number of robots exceeds the combined capacities of all parking nodes. Unlike the classical gathering problem, however, a subset of the robots must always be parked at a parking node in accordance with the specified capacity. Therefore, the robots must simultaneously determine, in a distributed manner, which robots will occupy the parking nodes and which will constitute the gathering. Second, the parking-node configuration may have reflectional or rotational symmetry, and the initial 5

robot configuration may either preserve or break this symmetry. Since the robots are anonymous, oblivious, and execute the same deterministic algorithm, they may be unable to make different movement decisions in symmetric configurations. Therefore, the algorithm must preserve symmetry whenever possible and break it only when necessary to ensure deterministic progress. Third, the robots operate in the asynchronous (async) model, where they are activated independently and may observe the configuration at different times. As a result, a robot may compute its movement using an outdated view of the system. Moreover, since the robots cannot distinguish between moving and stationary robots, coordinating their movements becomes more difficult than in synchronous models. Finally, all robot movements must remain collision-free while preserving the desired structural properties of the configuration. It is crucial that the algorithm avoids creating undesired multiplicity nodes that may prevent robots from uniquely identifying the current execution phase. Due to asynchronous activations and movement restrictions imposed by the underlying grid, the challenge is not only to achieve the desired final configuration, but also to maintain the necessary invariants throughout the execution. These challenges show that the SPG problem cannot be solved by simply combining existing parking and gathering algorithms. They motivate the design of the distributed algorithm presented in the next section.

1.4

Our Contributions

We introduce the SPG problem, a new coordination problem for autonomous mobile robots deployed on an infinite grid. In SPG, a set of designated parking nodes is associated with prescribed capacities, and the objective is to ensure that each parking node is occupied by exactly the number of robots specified by its capacity while all remaining surplus robots gather at a common grid node. Our main contributions are summarized as follows: • We formalize the SPG problem and its underlying computational model. • We characterize the initial configurations for which a deterministic solution to SPG is impossible. • For all remaining solvable configurations, we present a deterministic distributed algorithm that solves the SPG problem. • We show that the proposed algorithm is collision-free despite the movement restrictions imposed by the grid environment and the asynchronous execution of the robots. • We prove that the proposed algorithm always terminates in finite time, saturates every parking node according to its prescribed capacity, and gathers all surplus robots at a common node. • We establish an upper bound of O(n(a + b) + n2 ) and a worst-case lower bound of Ω(n(a + b)) on the move complexity of the proposed algorithm and the SPG problem, respectively.

1.5

Outline

The remainder of the paper is organized as follows. Section 2 introduces the computational model, notation, and formal definition of the Surplus Parking Gathering (SPG ) problem. Section 3 characterizes the initial configurations for which the SPG problem is unsolvable. Section 4 presents our deterministic distributed algorithm for solving the SPG problem from all solvable configurations. Section 5 establishes the correctness of the proposed algorithm and proves that it terminates in finite time. Section 6 presents the move complexity analysis of the proposed algorithm by establishing an upper bound and

6

a worst-case lower bound. Finally, Section 7 concludes the paper and discusses possible directions for future research.

2

Model, Definitions, and Notations

We consider a system of n mobile robots operating on an infinite square grid. The robots are autonomous, anonymous, homogeneous, identical, silent, oblivious, dimensionless, and disoriented. Let P∞ = (Z, E ′ ) denote the infinite path graph on the set of integers, where E ′ = {(i, i + 1) | i ∈ Z}. The underlying environment is the infinite square grid graph G = (V, E) = P∞ × P∞ , obtained as the Cartesian product of two infinite path graphs. The vertex set V represents the grid nodes, and robot movements are restricted to adjacent grid nodes. Let R = {r1 , r2 , . . . , rn } be the set of robots. The grid also contains a finite set of designated parking nodes P = {p1 , p2 , . . . , pm } ⊂ V. Each parking node has an associated capacity, specifying the number of robots that must eventually occupy that node.

2.1

Basic Notations

For two grid nodes u, v ∈ V , let dM (u, v) denote the Manhattan distance between u and v in the grid graph G. For a robot ri ∈ R, the node occupied by ri at time t is denoted by ri (t). The multiset of robot positions at time t is denoted by R(t) = {r1 (t), r2 (t), . . . , rn (t)}. Initially, say at t0 , all robots occupy distinct grid nodes, that is, ri (t0 ) ̸= rj (t0 ), for all i ̸= j. However, during the execution, multiple robots may occupy the same grid node. For every node v ∈ V , let λt (v) = |{ri ∈ R : ri (t) = v}| denote the number of robots located at v at time t. Hence, λt (v) = 0 if no robot occupies v. Each parking node p ∈ P has a prescribed capacity, denoted by κ(p). We extend the capacity function κ to all grid nodes by defining ( κ(p), if v = p ∈ P, κ(v) = 0, otherwise. Thus, κ(v) > 0 precisely when v is a parking node. The configuration of the system at time t is represented by C(t) = (R(t), P, κ). The function λt is not listed as an independent component of C(t) because it is uniquely determined by the multiset R(t). For every node v ∈ V , we define its status at time t by the pair Θt (v) = (λt (v), κ(v)). The first component of Θt (v) records the number of robots located at v, while the second component records the parking capacity of v. If v is not a parking node, then κ(v) = 0. Thus, the status pair Θt (v) distinguishes the following cases: λt (v) κ(v) Θt (v) Node type empty non-parking node 0 0 (0, 0) single robot on non-parking node 1 0 (1, 0) robot multiplicity on non-parking node ≥2 0 (λt (v), 0) empty parking node of capacity c 0 c (0, c) one robot on parking node of capacity c 1 c (1, c) robot multiplicity on parking node of capacity c ≥ 2 c (λt (v), c)

7

2.2

Configurations and Symmetry

An automorphism of the infinite grid graph G = (V, E) is a bijection ϕ : V → V such that, for any two nodes u, v ∈ V , (u, v) ∈ E ⇐⇒ (ϕ(u), ϕ(v)) ∈ E. Thus, ϕ preserves adjacency in the grid. An automorphism ϕ of G is called an automorphism of the configuration C(t) if it preserves the status of every grid node, that is, Θt (v) = Θt (ϕ(v)) for every v ∈ V. Equivalently, ϕ preserves both the robot multiplicity and the parking-node capacity at every node. The set of all automorphisms of C(t) is denoted by Aut(C(t)). If Aut(C(t)) contains only the identity automorphism, then C(t) is called asymmetric. Otherwise, C(t) is called symmetric. Since the set of robots and parking nodes is finite, no non-trivial translational symmetry can occur. Hence, a symmetric configuration in the infinite square grid may admit only reflectional or rotational symmetry. A reflectional symmetry is determined by a line of symmetry, which may be horizontal, vertical, or diagonal. Such a line may pass through either grid nodes or grid edges. A rotational symmetry is determined by a center of rotation and an angle of rotation. In the square grid, the possible non-trivial rotation angles are 90◦ and 180◦ . Definition 1 (Reflection Map). Let C(t) admit a unique line of symmetry L, and let X be a finite set of entities of C(t), where an entity is either an occupied robot node or a parking node. The reflection map with respect to L is the map µL : X → X defined as follows. For every x ∈ X, µL (x) denotes the entity whose position is the mirror image of the position of x with respect to L. If x lies on L, then x is fixed by the reflection, and hence µL (x) = x. For notational simplicity, whenever the line of symmetry L is fixed or uniquely determined by the configuration under consideration, we write µ instead of µL . Definition 2 (Rotational Map). Let C(t) admit a rotational symmetry with center c and order q ≥ 2. Let X be a finite set of entities of C(t), where an entity is either an occupied robot node or a parking node. The rotational map about c is the map ρc : X → X defined as follows. For every x ∈ X, ρc (x) denotes the entity whose position is obtained by rotating the position of x about c through the angle . Therefore, ρqc (x) = x for every x ∈ X. The set Orbitx = {x, ρc (x), ρ2c (x), . . . , ρq−1 θ = 2π c (x)} is q called the rotational orbit of x under ρc . For notational simplicity, whenever the center of rotation c is fixed or uniquely determined by the configuration under consideration, we write ρ instead of ρc . Let ϕ ∈ Aut(C(t)) be an automorphism of finite order q > 1. The cyclic group generated by ϕ is denoted by ⟨ϕ⟩ = {ϕ0 , ϕ1 , . . . , ϕq−1 }, where ϕ0 is the identity automorphism. For a subgroup H ≤ Aut(C(t)), the orbit of a node v ∈ V under H is defined as OH (v) = {ψ(v) : ψ ∈ H}. The orbits induced by H form a partition of V . Definition 3 (Partitive Automorphism). Let X ⊆ V . An automorphism ϕ ∈ Aut(C(t)) is called partitive on X if the cyclic group ⟨ϕ⟩ has order q > 1 and every node of X has an orbit of size exactly q, i.e., |O⟨ϕ⟩ (v)| = q for every v ∈ X. Equivalently, no node of X is fixed by any non-identity element of ⟨ϕ⟩. Definition 4 (Partitive Configuration). A configuration C(t) is said to be partitive on X ⊆ V if there exists an automorphism ϕ ∈ Aut(C(t)) such that ϕ is partitive on X. In this case, the nodes of X are divided into disjoint orbits of equal size q > 1 under the action of ⟨ϕ⟩. If F = V \ X is the set of nodes fixed by the symmetry, then we also say that C(t) is partitive outside F . Thus, every node in X has a non-trivial symmetric counterpart, whereas the nodes in F may remain 8

fixed under the symmetry. For example, suppose that C(t) admits a reflection symmetry with respect to a line L. If no grid node lies on L, then the reflection maps every grid node to a distinct symmetric node. Hence, C(t) is partitive on V . On the other hand, if L passes through grid nodes, then the nodes on L are fixed, while all nodes outside L occur in symmetric pairs. In this case, C(t) is partitive on V \ L. Similarly, if C(t) admits a rotational symmetry about a center c, then the configuration may be partitive on V \ {c} whenever c is a grid node fixed by the rotation. If the center of rotation is not a grid node, then no grid node is fixed by the center, and the configuration may be partitive on the whole node set V.

2.3

Minimum Enclosing Rectangle, Strings, Key Corner, and Leading Corner

For a configuration C(t), let MERC (t) denote the minimum grid-aligned rectangle containing all occupied robot nodes and all parking nodes. Similarly, let MERP denote the minimum grid-aligned rectangle containing only the parking-node set P. Both rectangles are aligned with the grid axes. The length of a side of such a rectangle is measured by the number of grid edges on that side. Suppose that the side lengths of MERC (t) are a and b. Since the side lengths are measured by the number of grid edges, there are a + 1 grid nodes along one side and b + 1 grid nodes along the other side. Hence, the total number of grid nodes contained in MERC (t) is (a + 1)(b + 1).

Figure 1: An illustration of the key corner and leading-corner-based ordering of robots and parking nodes. The black rectangle denotes MERC with len(AB) < len(AD), while the brown rectangle denotes MERP with len(A′ B ′ ) < len(A′ D′ ). The parking nodes are p1 , p2 , . . . , p6 with capacities 2, 2, 4, 1, 2, and 3, respectively. The parking nodes p6 and p3 contain 2 and 3 robots, respectively, and the node represented by r9 is a multiplicity node containing 4 robots. The key corner of MERC is A with string direction AD, and the leading corner of MERP is B ′ with string direction B ′ A′ , with parking string ρB ′ = 40000030000010000000000000022002. A scan string associated with a corner of MERC (t) is defined as the sequence of symbols obtained by visiting all nodes of MERC (t) exactly once in a prescribed scan order. During such a scan, each encountered node v contributes the status pair Θt (v) = (λt (v), κ(v)), where λt (v) denotes the number of robots located at v at time t, and κ(v) denotes the capacity of v. Therefore, every scan string is a finite sequence of status pairs of length (a + 1)(b + 1). 9

The scan strings are compared lexicographically. The underlying order on the status pairs is defined as follows: for two symbols (x, y) and (x′ , y ′ ), (x, y) ≺ (x′ , y ′ ) if either x < x′ , or x = x′ and y < y ′ . Hence, robot multiplicities are compared first, and parking capacities are used to break ties. Let Q be a corner of MERC (t), and let Q1 and Q2 be the two corners adjacent to Q. Starting from Q, the rectangle can be scanned in two possible directions, namely in the directions parallel to QQ1 and QQ2 . The corresponding scan strings are denoted by ST RQQ1 (t) and ST RQQ2 (t), respectively. Thus, each corner of MERC (t) gives rise to two scan strings, and altogether eight scan strings are obtained from the four corners. First, consider the case where MERC (t) is a non-square rectangle. For a corner Q, among the two sides incident to Q, the direction parallel to the shorter side is chosen as the string direction associated with Q. Suppose, without loss of generality, that the side from Q to Q1 is shorter than the side from Q to Q2 , i.e., len(QQ1 ) < len(QQ2 ). Then the string associated with Q is defined as ST RQ (t) = ST RQQ1 (t). The direction parallel to QQ1 is called the string direction associated with Q, while the direction parallel to QQ2 is called the non-string direction associated with Q. If MERC (t) is a square, then the two strings ST RQQ1 (t) and ST RQQ2 (t) associated with the same corner Q are compared lexicographically, and the string associated with Q is defined as ST RQ (t) = max{ST RQQ1 (t), ST RQQ2 (t)}. A corner Q∗ of MERC (t) is called a key corner of C(t) if ∗

ST RQ (t) = max{ST RQ (t) : Q is a corner of MERC (t)}. Any corner that is not a key corner is called a non-key corner. If the maximum string is unique, then the key corner is uniquely determined. In particular, if C(t) is asymmetric, then the lexicographically maximum string is unique, and hence the key corner and the corresponding string direction are uniquely determined. In Figure 1, the lexicographically maximum scan string associated with the key corner A is ST RAB (t)=((1,0), (1,0), (0,0), (0,0), (0,0), (0,0), (1,0), (1,0), (0,0), (0,0), (4,0), (0,0), (0,0), (0,0), (1,0), (0,0), (0,0), (0,0), (0,0), (3,4), (0,0), (0,0), (0,0), (1,0), (2,3), (1,0), (0,0), (0,0), (0,0), (1,0), (0,0), (0,0), (0,0), (0,0), (0,0), (0,0), (0,0), (0,0), (0,0), (0,0), (0,1), (0,0), (0,0), (0,0), (1,0), (0,0), (0,0), (0,0), (0,0), (0,0), (0,0), (1,0), (0,0), (0,0), (0,0), (1,0), (0,0), (0,0), (0,0), (0,2), (0,0), (1,0), (0,0), (1,0), (0,0), (0,0), (0,2), (1,0), (0,0), (0,2), (0,0), (1,0), (0,0), (0,0), (0,0), (1,0), (0,0), (0,0)). We define the leading corner of the parking-node set in an analogous way, but using only parking capacities. For every node v ∈ V , define π(v) = κ(v). Thus, π(v) = 0 if v is not a parking node, and π(v) is the capacity of v otherwise. For each corner Q of MERP , a string ρQ is constructed by scanning MERP and recording π(v) for every visited node v. A corner QP of MERP is called a leading corner if ρQP = max{ρQ : Q is a corner of MERP }. If the maximum string is unique, then the parking-node set admits a unique leading corner (see Figure 1). Otherwise, the parking-node set is symmetric with respect to the corresponding rectangle-string representation.

2.4

Configuration View

The configuration view is defined using the key corner and the string direction introduced above. Suppose that the configuration C(t) has a unique key corner Q∗ of MERC (t), and let the corresponding ∗ string direction be fixed by the string ST RQ (t). 10

Starting from Q∗ and scanning MERC (t) in this string direction, the nodes of MERC (t) are visited in a canonical order. For a node v ∈ MERC (t), let indQ∗ (v) denote the position of v in this scan order.
∗ The configuration view
of v is defined as ViewC(t) (v) = indQ (v), Θt (v) . Equivalently, ViewC(t) (v) = indQ∗ (v), (λt (v), κ(v)) . Thus, the configuration view of a node records two pieces of information: its position in the canonical scan order and its status pair, which encodes both the number of robots located at that node and the parking capacity of that node. Whenever the key corner and the corresponding string direction are unique, the configuration view induces a deterministic ordering of the nodes of MERC (t). Consequently, occupied robot nodes can be ordered according to their positions in the scan order. If more than one robot occupies the same node, then these robots have the same configuration view and are treated as a multiplicity at that node. Similarly, if the parking-node set P has a unique leading corner QP , then the scan of MERP starting from QP induces a deterministic ordering of the parking nodes. For two parking nodes pi , pj ∈ P, we write pi ≺P pj , if pi appears before pj in this scan order.

2.5

The Surplus Parking Gathering Problem

Pm P κ , and define s = n− We assume that n > m i i=1 κi to be the number of surplus robots. Assume that i=1 s ≥ 2, since these s robots are required for the gathering process. Let R(v, t) = { r ∈ R | r(t) = v }. The objective of the SPG problem (SPG) is to transform any initial configuration C(t0 ) into a configuration C(t), for some finite time t > 0, such that the following conditions hold: 1. Every parking node pi is saturated at time t0 , that is, |R(pi , t)| = κi , ∀i = 1, 2, . . . , m, where R(pi , t) denotes the set of robots occupying pi and κi denote the capacity of the parking node pi . 2. There exists a node G ∈ V \ P, called the gathering node, such that all surplus robots occupy G , i.e., at time t, |R(G , t)| = s. No capacity constraint is imposed on the gathering node G . 3. Any robot activated after time t computes a null move and therefore remains at its current location. The gathering node G is not specified a priori and must be determined autonomously by the robots during the execution of the algorithm. A configuration satisfying Conditions (1)–(3) is called a surplus parking gathering configuration. The SPG problem is solved if, starting from any initial configuration, the robots reach a surplus parking gathering configuration in finite time.

Figure 2: Partition of the configuration space based on the initial configuration C(t0 ).

11

2.6

Partitioning of the Initial Configuration C(t0 )

The symmetry of the parking-node configuration plays a fundamental role in determining the behavior of the robots. Since anonymous and oblivious robots executing the same deterministic algorithm cannot distinguish symmetric situations, different symmetry classes require different algorithmic strategies. Accordingly, we partition the initial configurations into several classes based on the symmetry of the parking-node configuration and the overall robot configuration. (see Figure 2) C1 : Asymmetric parking-node configuration. The parking nodes are asymmetric. Consequently, the overall configuration C(t0 ) is also asymmetric. An example is shown in Figure 1.

Figure 3: An example of a C21 configuration, where the parking-node set is symmetric with respect to line L, and the robot configuration is asymmetric. C2 : Parking nodes with a unique line of symmetry. The parking nodes are symmetric with respect to a unique line of symmetry L. This class is divided according to whether the overall configuration C(t0 ) is symmetric or asymmetric. • C21 : If C(t0 ) is asymmetric, then the configuration belongs to C21 . (see Figure 3) • C22 : If C(t0 ) is symmetric with respect to L, then the configuration belongs to C22 . The class C22 is further partitioned as follows:

(a) C221 : robots on L.

(b) C222 : empty L.

(c) C223 : parking nodes on L.

Figure 4: Representative configurations for the subcases of C22 . – C221 : At least one robot occupies a position on L. (see Figure 4(a)) – C222 : No robot position and no parking node lie on the line of symmetry L. (see Figure 4(b)) – C223 : No robot occupies a position on L, whereas at least one parking node lies on L. (see Figure 4(c)) 12

Figure 5: An example of a C31 configuration, where the parking-node set is rotationally symmetric, and the robot configuration is asymmetric. C3 : Rotationally symmetric parking-node configuration. The parking-node configuration admits rotational symmetry with center c. This class is further partitioned according to whether the overall configuration C(t0 ) is symmetric or asymmetric. • C31 : If C(t0 ) is asymmetric, then the configuration belongs to C31 . (see Figure 5) • C32 : If C(t0 ) is rotationally symmetric with respect to c, then the configuration belongs to C32 . The class C32 is further partitioned as follows: – C321 : Exactly one robot occupies the center of symmetry c. (see Figure 6(a)) – C322 : Neither a robot nor a parking node occupies the center of symmetry c. (see Figure 6(b)) – C323 : A parking node occupies the center of symmetry c, but no robot occupies c. (see Figure 6(c))

(a) C321 : robot at c.

(b) C322 : empty c.

(c) C323 : parking node at c.

Figure 6: Representative configurations for the subcases of C32 . The capacities of the parking nodes are part of the input and are known to all robots. This information is required for the robots to compute the configuration view correctly. Without this information, robots may be unable to distinguish between different configuration classes. The notation frequently used in the description of the model, the algorithm, and the correctness analysis is summarized in Table 2. 13

Notation

Description

G = (V, E)

Infinite square grid graph, where V is the set of grid nodes and E is the set of grid edges. Infinite path graph on the integer set Z, used to define the square grid as P∞ × P∞ . Set of n mobile robots. Node occupied by robot ri at time t. Multiset of robot positions at time t. Finite set of designated parking nodes. Prescribed capacity of parking node p ∈ P. Number of robots located at node v at time t. Status pair of node v at time t, defined by Θt (v) = (λt (v), κ(v)). Configuration of the system at time t, C(t) = (R(t), P, κ). Manhattan distance between two grid nodes u, v ∈ V . Minimum grid-aligned rectangle containing all occupied robot nodes and all parking nodes. Minimum grid-aligned rectangle containing only the parking-node set P. Set of all automorphisms of the configuration C(t). Unique line of reflectional symmetry, when it exists. Center of rotational symmetry, when it exists. Reflection map with respect to L. Rotational map about the center c. Order of rotational symmetry. Rotational orbit of an entity x. Configuration view of node v with respect to the key corner and scan direction. String representation associated with corner Q. Key corner of MERC (t). Leading corner of MERP . Parking string associated with corner Q of MERP . Parking-capacity indicator used for parking strings, defined by π(v) = κ(v). P Number of surplus robots, s = n − m i=1 κ(pi ). Set of surplus robots at time t. Set of unsaturated robots at time t. Set of saturated parking nodes. Set of unsaturated parking nodes. Gathering node for surplus robots. Multiplicity or gathering node created on the formation line in reflectional cases. Multiplicity or gathering node associated with the center of rotational symmetry. Distance value used for selecting surplus robots.

P∞ = (Z, E ′ ) R = {r1 , r2 , . . . , rn } ri (t) R(t) P = {p1 , p2 , . . . , pm } κ(p) λt (v) Θt (v) C(t) dM (u, v) MERC (t) MERP Aut(C(t)) L c µ ρ q Orbitx ViewC(t) (v) ST RQ (t) Q∗ QP ρQ π(v) s Rs (t) Ru (t) PS PU G NL Nc ∆i

Table 2: Summary of notation used in the paper.

14

3

Impossibility Results

In this section, we identify the configurations for which the surplus parking gathering problem cannot be solved under the considered model. The SPG problem consists of two requirements: saturating all parking nodes according to their prescribed capacities and gathering all surplus robots at a uniquely identifiable node. Hence, if either exact parking or surplus gathering is impossible, then SPG is also impossible. Our impossibility results are based on known impossibility arguments for grid-based mobile robots. In particular, we use the parking impossibility results of Chakraborty and Mukhopadhyaya [9], the symmetry-based gathering impossibility of D’Angelo et al. [15], and the partitive-configuration argument for gathering over meeting nodes by Bhagat et al. [4]. These results are adapted as necessary conditions for solving SPG. Accordingly, we separate the impossibility results into two parts: those arising from the parking requirement and those arising from the surplus gathering requirement.

3.1

Impossibility of the Parking Requirement

We first state some impossibility results that arise from the parking requirement of SPG. Since SPG requires every parking node to be saturated exactly according to its prescribed capacity, any violation of the parking structure makes the entire problem unsolvable. The following results are based on the impossibility arguments of Chakraborty and Mukhopadhyaya [9]. Theorem 1 (Chakraborty and Mukhopadhyaya [9]). Let A be a deterministic algorithm for SPG on an infinite grid. If, during some execution of A, a multiplicity node is created at a node other than a parking node or the eventual gathering node, then A cannot guarantee a correct solution to SPG under async scheduler. The proof follows from the indistinguishability argument of Chakraborty and Mukhopadhyaya [9]. Assume, for contradiction, that there exists a deterministic algorithm A that correctly solves SPG. Suppose that, during some execution of A, a multiplicity is created at a node that is neither a parking node nor the eventual gathering node. Since impossibility under the semi-synchronous (ssync) model also implies impossibility under the asynchronous (async) model, it is sufficient to establish the result under the ssync model. Consider an adversarial ssync scheduler. All robots occupying the multiplicity node have identical views and execute the same deterministic algorithm. Therefore, whenever the scheduler activates these robots simultaneously, they compute identical destinations and perform identical movements. Consequently, the multiplicity at the non-designated node is preserved throughout the execution. However, in any correct execution of SPG, multiplicity can occur only at parking nodes and the eventual gathering node. Hence, the persistent multiplicity at the non-designated node prevents the algorithm from reaching a valid final configuration. This contradicts the assumption that A correctly solves SPG. Therefore, no such deterministic algorithm exists. Theorem 2 (Chakraborty and Mukhopadhyaya [9]). Without strong multiplicity detection, the surplus parking gathering problem is unsolvable under async scheduler. The proof follows from the necessity of strong multiplicity detection established by Chakraborty and Mukhopadhyaya [9]. In SPG, each parking node pi is associated with a prescribed capacity κi , and the robots must determine whether exactly κi robots occupy pi . Without strong multiplicity detection, the robots cannot determine the exact multiplicity at a parking node and, consequently, cannot verify whether the required capacity has been achieved. Furthermore, the proposed algorithm relies on multiplicity nodes to identify different execution phases and to determine the gathering of the surplus robots. Without strong multiplicity detection, the robots cannot distinguish multiplicity nodes from ordinary occupied nodes or determine the exact number of 15

robots gathered at a node. Consequently, they cannot verify whether the desired terminal configuration has been reached. Therefore, no deterministic algorithm can correctly solve SPG without strong multiplicity detection. Theorem 3 (Chakraborty and Mukhopadhyaya [9]). Let C(t0 ) ∈ C223 , and let pl be a parking node located on the line of symmetry L. If the capacity of pl is an odd integer, then SPG is unsolvable under async scheduler. The proof follows from Lemma 3 of Chakraborty and Mukhopadhyaya [9]. Assume, for contradiction, that there exists a deterministic algorithm A that correctly solves SPG. Since C(t0 ) ∈ C223 , the configuration is symmetric with respect to the line L, no robot is initially located on L, and at least one parking node lies on L. Let pl be a parking node on L with odd capacity κ(pl ) = 2k + 1. Since impossibility under the semi-synchronous (ssync) model also implies impossibility under the asynchronous (async) model, it is sufficient to consider an adversarial ssync scheduler. The scheduler activates every robot simultaneously with its mirror image with respect to L. Because each pair of symmetric robots has identical local views and executes the same deterministic algorithm, both robots compute identical destinations and perform identical movements. Consequently, robots can reach the parking node pl only in symmetric pairs. Hence, the number of robots occupying pl is always even. Since the capacity of pl is odd, namely 2k + 1, the parking node can never be saturated exactly. Therefore, the parking requirement of SPG cannot be satisfied, contradicting the assumption that A correctly solves SPG. Hence, SPG is unsolvable for such configurations. Theorem 4 (Chakraborty and Mukhopadhyaya [9]). Let C(t0 ) ∈ C323 , and let pc be the parking node located at the center of rotational symmetry c. If the capacity of pc is not divisible by the order of the rotational symmetry, then SPG is unsolvable under async scheduler. The proof follows from the rotational-symmetry impossibility result of Chakraborty and Mukhopadhyaya [9]. Assume, for contradiction, that there exists a deterministic algorithm A that correctly solves SPG. Since C(t0 ) ∈ C323 , the parking-node configuration is rotationally symmetric, and no robot is initially located at the center of symmetry c. Since impossibility under the semi-synchronous (ssync) model also implies impossibility under the asynchronous (async) model, it is sufficient to consider an adversarial ssync scheduler that preserves the rotational symmetry of the execution. Because the robots belonging to the same rotational orbit have identical local views and execute the same deterministic algorithm, they compute identical destinations and perform identical movements. Consequently, robots can reach the parking node at the center only in complete rotational orbits. Hence, the number of robots that can occupy the parking node at c must always be a multiple of the order of rotational symmetry. If the prescribed capacity of pc is not divisible by the order of the rotational symmetry, then the parking node can never be saturated exactly. Therefore, the parking requirement of SPG cannot be satisfied, contradicting the assumption that A correctly solves SPG. Hence, SPG is unsolvable for such configurations.

3.2

Impossibility of the Surplus Gathering Requirement

We now state the impossibility results that arise from the surplus gathering requirement of SPG. Since SPG requires both the exact saturation of all parking nodes and the gathering of all surplus robots at a single node, the problem becomes unsolvable whenever the surplus gathering subproblem cannot be solved deterministically. The following result is based on the partitive-configuration argument for gathering over meeting nodes.

16

(a)

(b)

Figure 7: Illustrative examples of partitive configurations: (a) with respect to the line of symmetry L; (b) with respect to the rotational symmetry centered at c. Theorem 5 (Bhagat et al. [4]). Let C(t0 ) be a symmetric initial configuration, and let V0 ⊆ V be a set of nodes fixed by an automorphism ϕ such that V0 ∩ R(t0 ) = ∅. Suppose that ϕ is partitive on V \ V0 . If no admissible gathering node of SPG belongs to V0 , then no deterministic algorithm can guarantee the surplus gathering requirement of SPG under async scheduler. The argument follows from the partitive-symmetry impossibility result of Bhagat et al. [4]. Under a symmetric execution, robots belonging to the same orbit have identical views and execute the same deterministic algorithm. An adversarial scheduler can preserve the orbit structure throughout the execution. Hence, the robots cannot deterministically select a unique gathering node in V \ V0 . Since no admissible gathering node lies in V0 , the surplus gathering requirement cannot be guaranteed. Consequently, SPG is unsolvable for such configurations. Corollary 1. Let C(t0 ) admit a unique line of symmetry L. If L contains neither a robot nor an admissible gathering node, and the configuration is partitive with respect to L, then SPG is unsolvable under async scheduler. Indeed, by taking V0 as the set of nodes on L, the configuration remains partitive on V \ V0 under a symmetric execution. Therefore, gathering can be guaranteed only at a node on L. Since L contains no admissible gathering node, the surplus gathering requirement of SPG cannot be satisfied (see Figure 7 (a)). Corollary 2. Let C(t0 ) admit rotational symmetry with center c, where c is a grid node. If c contains neither a robot nor an admissible gathering node, and the configuration is partitive with respect to c, then SPG is unsolvable under async scheduler. The proof is analogous to Corollary 1. By taking V0 = {c}, every symmetry-preserving execution keeps the robots partitioned into rotational orbits. Thus, a unique gathering node outside c cannot be deterministically selected. Since c is not an admissible gathering node, the surplus gathering requirement cannot be achieved (see Figure 7 (b)).

17

4

Algorithm spg()

4.1

High-Level Idea

Depending on the type of the initial configuration, the algorithm spg() executes different sequences of phases. For configurations C21 and C31 , it proceeds through four phases: Line Formation, Multiplicity Creation, Saturation, and Gathering. For the remaining configurations, the algorithm works in only two phases: Saturation and Gathering. During the Line Formation phase, the robots arrange themselves on a line on distinct nodes in a manner that implicitly identifies two groups: parking robots, which will eventually occupy the parking nodes, and surplus robots, which will ultimately gather at a common node. The Multiplicity Creation phase follows the line formation phase and creates a unique multiplicity node on the line. Due to the presence of this unique multiplicity, the robots can detect the transition between the line formation phase and the saturation phase. In the Saturation phase, the robots are assigned to the parking nodes according to the ordering defined for the corresponding configuration. Each robot moves sequentially in a collision-free manner, ensuring that every parking node reaches its prescribed capacity while maintaining the invariants established in the earlier phases. After all parking nodes have been saturated, every robot that does not occupy a parking node is defined as a surplus robot. Finally, in the Gathering phase, the remaining robots are treated as surplus robots and move to the designated gathering node. An exception occurs for configurations C222 and C322 , where the Gathering phase is executed before the Saturation phase. Pending Move Analysis: In this section, we analyze the effect of a pending move on the configuration C(t) during the execution of the algorithm spg(). If C(t) is asymmetric, then the ordering of robots remains unaffected even in the presence of a pending move. Hence, pending moves require special attention only for symmetric configurations. Pending moves play two different roles depending on the configuration class. In C221 and C321 , the algorithm intentionally breaks the symmetry by moving a uniquely selected robot away from the line of symmetry or from the center of rotation. In this case, AllowtoMove() is used as a safety test before initiating the symmetry-breaking move. In contrast, in C222 and C322 , the algorithm does not break the symmetry. Instead, the selected robots move in symmetric pairs or rotational orbits, and pending moves are used only to detect incomplete symmetric movements. Definition 5. For any fixed time t ≥ 0, let βt = {v ∈ V | v is occupied by a robot at time t}. Define the occupancy function αt : V → {0, 1} by αt (v) = 1βt (v), where 1βt denotes the indicator function on the set βt . Two binary strings are said to be nearly equal if one can be transformed into the other by replacing exactly one occurrence of the substring 01 by 10, or conversely. Such a local change represents the effect of a pending move of a robot from an occupied node to an adjacent free node along the corresponding half-line. Pending moves in C221 and C321 (symmetry-breaking case): We first consider the configurations in which the algorithm intentionally breaks the symmetry by moving a uniquely selected robot. Let C(t) ∈ C221 be symmetric with respect to a unique line of symmetry L. Let r be the unique robot on L having the maximum configuration view according to the ordering O3 . Since r lies on L, the two relevant strings are generated from r in the two directions away from L. These strings are denoted by ST Rleft (r) and ST Rright (r). The configuration is said to be nearly reflective if these two strings are nearly equal (see Figure 8(a)). In this case, a pending move has already affected one side of L, and therefore the robot r is not allowed to initiate a new symmetry-breaking move. 18

(a)

(b)

Figure 8: Examples of nearly reflective and nearly rotational configurations. (a) A nearly reflective configuration, where the strings generated by the robot r in the directions away from L are {1010, 1001}. (b) A nearly rotational configuration, where the strings generated by the robot r are {110, 110, 110, 101}. The parking nodes p3 , p5 , p6 , p7 , and p8 are occupied by robots. Next, let C(t) ∈ C321 , where the center of rotation c is occupied by a robot r. In this case, the strings are generated with respect to the robot r at the center c. From r, consider the four halflines in the left, right, upward, and downward directions. The corresponding strings are denoted by ST Rleft (r), ST Rright (r), ST Rupward (r), ST Rdownward (r). These strings are compared according to the rotational symmetry around c. If the rotational order is 2, then the opposite directions are compared in above. If the rotational order is 4, then all four directions are compared cyclically. The configuration is said to be nearly rotational if the strings are identical except for a local 01 ↔ 10 change caused by a pending move in one or more directions. (see Figure 8(b)) Before allowing the unique robot on L ∪ {c} to move to an adjacent free node, each robot executes AllowtoMove(). If the current configuration is detected as nearly reflective or nearly rotational, then the procedure returns false, and no new symmetry-breaking move is started. Otherwise, if a suitable adjacent free node exists, the unique robot is allowed to move away from L ∪ {c}, and the symmetry is broken. Pending moves in C222 and C322 (symmetry-preserving case): We now consider the configurations in which the algorithm preserves the symmetry during movement. Let C(t) ∈ C222 . In this case, the line of symmetry L contains no robot. Hence, robots are selected in symmetric pairs with respect to L. Let (r, µ(r)) be such a selected pair, where µ denotes the reflection map with respect to L. Let ℓ(r, µ(r)) be the line passing through r and µ(r), and let x = ℓ(r, µ(r)) ∩ L be its intersection node with the line of symmetry. The string representation is now defined with respect to the node x. From x, we consider the two opposite half-lines along ℓ(r, µ(r)), one toward r and the other toward µ(r). Along each half-line, we record the robot occupancy value λt (v) of every visited node v, starting from the node adjacent to x and continuing up to the farthest occupied node in that direction. Let the two resulting strings be denoted by ST R+ (x) and ST R− (x). If ST R+ (x) and ST R− (x) are nearly equal, then the configuration represents a pending reflective movement. This means that one robot of the selected symmetric pair has already moved toward its destination, while the other robot has not yet completed the corresponding 19

symmetric move. In this case, the robot that has already progressed remains stationary, and the pending robot continues its movement so that the reflectional symmetry is restored. No new symmetric pair is selected until this pending move is completed. Next, let C(t) ∈ C322 . Here, the configuration is rotationally symmetric with center c, and the center is not occupied by a robot. Robots are selected in rotational orbits with respect to c. Let ρ be the rotational map about c. Mote that the rotational order is q ∈ {2, 4}. Suppose that the selected orbit is Orbitr = {r, ρ(r), ρ2 (r), . . . , ρq−1 (r)}. The string representation is defined with respect to the center c. From c, the occupancy values are recorded along the directions determined by the robots in the selected orbit and their rotated copies. For each i ∈ {0, 1, . . . , q − 1}, define ( 1, if ρi (r) has already progressed toward its assigned destination, bi = 0, otherwise. The binary string B(Orbitr ) = b0 b1 · · · bq−1 is called the movement-status string of the selected rotational orbit. If q = 2, then the possible movement-status strings are 00, 01, 10, 11. The strings 00 and 11 correspond to symmetric states before and after the completion of the orbit movement, respectively. The strings 01 and 10 correspond to pending rotational movements, since exactly one robot of the selected orbit has progressed while the other has not. If q = 4, then the movement-status string has length four. The strings 0000 and 1111 correspond to symmetric states before and after the completion of the orbit movement. Every other string, for example 1000, 0100, 1010, 1100, and, 1110 represents a pending rotational movement, since some but not all robots of the selected orbit have progressed toward their assigned destinations. Thus, in C222 and C322 , pending moves are not used to break symmetry. They only indicate that a symmetry-preserving movement has been partially completed. During such a pending state, the robots that have already progressed remain stationary, while the remaining robots of the same symmetric pair or rotational orbit continue toward their corresponding destinations. No new pair or orbit is allowed to move until the current pending movement is completed and the corresponding symmetry is restored. The pseudocode for maintaining symmetry during pending move is presented in Algorithm 1.

4.2

Ordering for Algorithmn spg()

In this section, we introduce different orderings of parking nodes and robot positions that are used throughout the algorithm. The different orderings are as follows: • O1 : Consider the case where the set of parking nodes is asymmetric. By the definition of asymmetry for the set P, there always exists a unique lexicographically maximum string ST Ri . Consequently, a unique leading corner, say, Kp of MERP of the set P of the parking nodes can be determined. Now consider the string representation ST Ri associated with Kp . The parking nodes are ordered according to their order of appearance in this string, from first to last. Let us assume that p1 ≺P p2 ≺P · · · ≺P pm be the sequence of parking nodes obtained in this way. This ordering is denoted by O1 . • O2 : Consider an asymmetric configuration C(t) in which the parking-node configuration is either reflective, with a unique line of symmetry L, or rotationally symmetric with center c. Although the parking-node configuration itself is symmetric, the overall configuration C(t) is asymmetric. 20

Algorithm 1 : HandlePendingMove(C(t)) Require: C(t) ∈ {C222 , C322 } Ensure: Pending symmetry-preserving move is completed if C(t) ∈ C222 then Let (r, µ(r)) be the selected symmetric pair Let x = ℓ(r, µ(r)) ∩ L Construct ST R+ (x) and ST R− (x) along the two opposite half-lines from x if ST R+ (x) and ST R− (x) are nearly equal then Move only the pending robot of (r, µ(r)) Keep its symmetric partner stationary else Move r and µ(r) symmetrically toward their destinations end if end if if C(t) ∈ C322 then Let Orbitr = {r, ρ(r), . . . , ρq−1 (r)} be the selected orbit Construct the movement-status string B(Orbitr ) = b0 b1 · · · bq−1

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: if B(Orbitr ) = 00 or 0000 then 16: Move all robots in Orbitr symmetrically toward their destinations 17: else if B(Orbitr ) = 11 or 1111 then 18: The orbit movement is complete 19: else 20: Move only the pending robots of Orbitr 21: Keep the already-progressed robots stationary 22: end if 23: end if 24: No new pair or orbit is selected until the symmetry is restored

Consequently, the asymmetry of C(t) induces a total ordering on all entities (i.e., both the robots and the parking nodes). Whenever multiple robots or parking nodes share the same maximum Manhattan distance from L (in the reflective case) or from c (in the rotational case), the tie is broken by selecting the entity that possesses the highest order under the induced total ordering. We denote this resulting ordering by O2 . Since the entities in an asymmetric configuration are totally orderable [7], the ordering O2 is structurally well-defined. • O3 : Consider the case where a set of entities (robots or parking nodes) is symmetric with respect to a unique line of symmetry L, and at least one entity lies on L. In this scenario, there may exist either one or two key corners of the corresponding MER (Minimal Enclosing Rectangle). If there exists a unique key corner K, then L must be a diagonal line of symmetry. The two strings associated with K are identical, and one of the two directions is chosen arbitrarily as the string direction. Let ST Ri be the corresponding string representation. The entities lying on L are then ordered from first to last according to their appearance in ST Ri . This ordering is denoted by O3 . If there exist two key corners, the string representations associated with both key corners are evaluated, and O3 is defined in an identical manner. Since O3 depends solely on the positions of the entities and the key corners, it uniquely determines an ordering at every time instant. Consequently, when applied to robots, this ordering may change as they move during the execution; when applied to parking nodes, which are stationary, the ordering remains invariant. • O4 : Consider a configuration C(t) ∈ {C222 , C322 }. 1. Suppose that C(t) ∈ C222 , and let L be the line of symmetry. Define SL = L ∩ MERP to be the line segment of the symmetry line L contained in MERP . Let VL = SL ∩ V . Thus, VL denotes the set of grid nodes lying on the segment SL . Let QP be the leading corner of MERP . The string direction determined from QP induces a total order on the nodes of VL . We denote this order by ≺L . Hence, for any two nodes u, v ∈ VL , either u ≺L v or v ≺L u holds. This gives a unique ordering of the nodes of VL along the symmetry line L. Let µ denote the image with respect to L. Since C(t) is symmetric with respect to L, the robot set R can be partitioned into symmetric pairs Π = {(r, µ(r)) : r ∈ R}. For each symmetric pair π = (r, µ(r)) ∈ Π, define dL (π) = ming∈VL dM (r, g). Since every node g ∈ VL 21

Figure 9: Phase transition diagram of the algorithm for different initial configuration classes. lies on the symmetry line L, we have dM (r, g) = dM (µ(r), g). Therefore, dL (π) is also equal to ming∈VL dM (µ(r), g). Among the nodes of VL attaining the minimum distance dL (π), let gL (π) be the first node according to the order ≺L . In other words, gL (π) is the first node in the leading-corner string order among all nodes of VL that are closest to the symmetric pair π. Now let QC be the key corner of the current configuration C(t). The string direction determined from QC induces an order on the symmetric robot pairs in Π. We denote this pair-order by ≺C . The ordering O4 is now defined as follows. The symmetric pairs in Π are ordered in nondecreasing order of dL (π). If two symmetric pairs π and π ′ satisfy dL (π) = dL (π ′ ), then the tie is resolved by comparing their corresponding closest nodes gL (π) and gL (π ′ ) according to the order ≺L . That is, π precedes π ′ if gL (π) ≺L gL (π ′ ). If a tie still remains, then it is resolved using the pair-order ≺C induced by the key-corner string of C(t). The resulting ordered sequence of symmetric robot pairs is defined as the ordering O4 for configurations in C222 . Since ≺L and ≺C are total orders, the first symmetric pair in O4 is uniquely determined. 2. Suppose that C(t) ∈ C322 , and let c be the center of rotation. Let ρ denote the smallest non-trivial rotation about c that preserves the configuration. The robot set R is partitioned into distinct closed rotational orbits Ω1 , Ω2 , . . . , Ωk , where each orbit is of the form Ω(r) = {r, ρ(r), ρ2 (r), . . . , ρq−1 (r)}, q is the order of the rotational symmetry, and ρq (r) = r. For each closed orbit Ωj , define its distance from the center of rotation c as D(Ωj ) = minr∈Ωj dM (r, c). The closed rotational orbits are first ordered in non-decreasing order of their distances from c. That is, for two orbits Ωi and Ωj , Ωi ⪯ Ωj , if D(Ωi ) ≤ D(Ωj ). If two distinct closed orbits have the same distance from c, then the tie is resolved using the string 22

direction induced by the leading corner of the parking-node configuration. More precisely, let QP be the leading corner of MERM . The string direction determined from QP induces a total order on the robot positions. For each orbit Ωj , let rep(Ωj ) be the first robot of Ωj in this string order. Then, for two orbits Ωi and Ωj satisfying D(Ωi ) = D(Ωj ), we order them according to their representatives: if

Ωi ≺ Ωj

rep(Ωi ) ≺ rep(Ωj )

in the leading-corner string order. The resulting ordered sequence of closed rotational orbits is defined as the ordering O4 for configurations in C322 . Since the leading-corner string order is a total order, the first closed orbit in O4 is uniquely determined.

4.3

Description of the Algorithm spg()

In this section, we describe the algorithm for solving the Surplus Parking Gathering Problem. The algorithm is designed according to the structural class of the initial configuration. Depending on the symmetry of the parking nodes and the robot configuration, the execution is divided into either two or four different phases. The overall execution flow of the algorithm depends on the initial configuration class C(t0 ); the corresponding phase transitions, together with the impossible cases, are summarized in Figure 9. Line Formation Phase: This phase is executed only when the initial configuration C(t0 ) belongs to either C21 or C31 . The movement of robots for each configuration is performed by the algorithm MoveToDestination(). A detailed description of the phase corresponding to different configurations is provided below. Algorithm 2 : LineFormation(C(t)) Require: Current configuration C(t), robot set R(t), parking node set P Ensure: All robots occupy distinct nodes on the formation line L if C(t0 ) ∈ / {C21 , C31 } then return end if if C(t0 ) ∈ C21 then Let L be the unique line of symmetry of P For each robot ri ∈ R(t), compute η(ri ) = dM (ri , L) dL ← max{η(ri ) : ri ∈ R(t)} Select a unique robot rg using O2 among all robots satisfying η(ri ) = dL

1: 2: 3: 4: 5: 6: 7: 8: 9: else if C(t0 ) ∈ C31 then 10: Let c be the center of rotational symmetry of P 11: For each robot ri ∈ R(t), compute η(ri ) = dM (ri , c) 12: dc ← max{η(ri ) : ri ∈ R(t)} 13: Select a unique robot rg using O2 among all robots satisfying η(ri ) = dc 14: end if 15: (w, L ) ← ComputeFormationLine(C(t), rg , MERP ) 16: if rg ∈/ L then 17: PlaceRobotOnFormationLine(rg , w, L ) 18: end if 19: while there exists a robot ri ∈ R(t) such that ri ∈/ L do 20: Let Ru (t) = {ri ∈ R(t) : ri ∈/ L } 21: Select a robot ru ∈ Ru (t) having maximum value of η(ru ) 22: Break ties using the ordering O2 23: Select a node wi ∈ L as the destination node for ru 24: PlaceRobotOnFormationLine(ru , wi , L ) 25: end while 26: return

• C21 Configuration: In this configuration, the parking node set P admits a unique line of symmetry L, whereas the robot configuration R(t0 ) is asymmetric. Define dL = max{dM (ri , L) : ri ∈ R}. A unique robot rg is selected using the ordering O2 among all robots attaining the distance dL . Let AB, BC, CD, and DA be the four sides of MERP such that AB and CD are parallel to 23

(a)

(b)

Figure 10: Illustration of the line-formation process for the configuration C21 . (a) Selection of the formation line L and the auxiliary line L ′ ; (b) final placement of robots on L while preserving the prescribed ordering. L. Let l be the line passing through rg and intersecting the sides BC and DA at nodes u and v, respectively, where dM (rg , u) < dM (rg , v). If rg lies inside or on MERP , then it moves along the line l away from v toward a node w ∈ l outside MERP and stops at w such that dM (u, w) = 2 (see Figure 10(a)). Let L be the line passing through w and parallel to L. Clearly, in this case, dM (L, rg ) < dM (L, w). If rg is outside MERP and satisfies dM (L, rg ) < dM (L, w), then rg reaches w (see Figure 10(b)). If the robot rg is outside MERP and dM (L, rg ) > dM (L, w), then rg is away from w. In this case, rg moves towards w. If R ∩ {w} = ∅, that is, node w does not contain another robot, then robot rg moves to w. Otherwise the robot rg moves along l towards w and stops at a node w′ ∈ l such that dM (w, w′ ) = 1. Consider an auxiliary line L ′ passing through w′ and parallel to L . In this case, robot rg moves along a line L ′ and finds a free node, say w′′ ∈ L . Once a free node w′′ ∈ L is identified, the robot rg moves to w′′ and stops there. Similarly, for any robot ru ̸= rg satisfying dM (L, ru ) < dM (L, w), an auxiliary line L ′′ can be defined analogously to L ′ to reach distinct node on L . Also, this line L ′′ satisfies dM (L, L ′′ ) < dM (L, L ′ ). • C31 Configuration: In this configuration, the parking node set P admits a center of rotational symmetry c, whereas the robot configuration R(t0 ) is asymmetric. Define dc = max{dM (ri , c) : ri ∈ R}. A unique robot rg is selected using the ordering O2 , among all the robots attaining the distance dc . Let AB, BC, CD, and DA be the four sides of MERP . Let l be the line passing through rg and intersecting any two parallel sides of MERP , say BC and DA at nodes u and v, respectively, where dM (rg , u) < dM (rg , v). If rg is located inside or on the boundary of MERP , it moves along the line l, increasing its distance from both c and u, until it reaches a node w ∈ l that lies outside MERP . The robot stops at w such that dM (u, w) = 2. Let L be the line passing through w and perpendicular to the line l. Clearly, in this case, dM (c, rg ) < dM (c, w). Once the line L is identified, the remaining computation for executing the Line Formation Phase in configuration C31 follows the same procedure as in configuration C21 , except that every comparison based on the distance from 24

Algorithm 3 : ComputeFormationLine(C(t), rg , MERP ) Require: Initial configuration C(t0 ) ∈ {C21 , C31 }, guard robot rg , rectangle MERP Ensure: A node w and the formation line L if C(t0 ) ∈ C21 then Let L be the unique line of symmetry of P Let AB, BC, CD, DA be the four sides of MERP such that AB and CD are parallel to L Let l be the line passing through rg and intersecting BC and DA at nodes u and v, respectively

1: 2: 3: 4: 5: Choose u and v such that dM (rg , u) < dM (rg , v) 6: Choose a node w ∈ l outside MERP in the direction away from v such that dM (u, w) = 2 7: Let L be the line passing through w and parallel to L 8: else if C(t0 ) ∈ C31 then 9: Let c be the center of rotational symmetry of P 10: Let AB, BC, CD, DA be the four sides of MERP 11: Let l be the line passing through rg and intersecting any two parallel sides of MERP , BC and DA, at nodes u and v 12: Choose u and v such that dM (rg , u) < dM (rg , v) 13: Choose a node w ∈ l outside MERP in the direction away from c and u such that dM (u, w) = 2 14: Let L be the line passing through w and perpendicular to l 15: else 16: return 17: end if 18: return (w, L )

the line of symmetry L is replaced by the corresponding comparison based on the distance from the center of rotational symmetry c. The auxiliary lines L ′ and L ′′ are used to avoid the creation of multiple multiplicity nodes. If multiple multiplicity nodes are created in the configuration, then the Line Formation Phase and the Saturation Phase (discussed in detail on Page 26) cannot be uniquely identified. Once the line L is formed (referred to as the formation line), all robots uniquely identify it and move sequentially to distinct nodes on L according to the decreasing order of their Manhattan distances from L or c. Robots already located on L remain stationary during the Line Formation Phase. This phase terminates when all n robots occupy distinct nodes on L . The detailed pseudocode for this phase is given in Algorithms 2, 3, and 4. Algorithm 4 : PlaceRobotOnFormationLine(r, w, L ) Require: A selected robot r, a node w ∈ L , and the formation line L Ensure: Robot r reaches a distinct node on L if r ∈ L then return end if if R(t) ∩ {w} = ∅ then while r ̸= w do Robot r moves by one hop along a shortest Manhattan path toward w All other robots remain stationary end while else Let w′ be a node on the approach line of r such that dM (w, w′ ) = 1 Let L ′ be the auxiliary line passing through w′ and parallel to L while r ̸= w′ do Robot r moves by one hop along a shortest Manhattan path toward w′ All other robots remain stationary end while Select a free node w′′ ∈ L such that R(t) ∩ {w′′ } = ∅ while r ̸= w′′ do Robot r moves by one hop along a shortest Manhattan path toward w′′ All other robots remain stationary end while end if return

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22:

Multiplicity Creation Phase: If C(t0 ) ∈ {C21 , C31 }, then this phase is executed after the completion of the Line Formation Phase. Otherwise, the algorithm proceeds directly to the next phase for all the other configurations. The purpose of this phase is to create a multiplicity node so that the robots can distinguish between the Line Formation Phase and the Saturation Phase. For configuration C21 , let [r1 , rn ] be the line segment on L induced by the robots, where r1 and rn are the two terminal robots on L . If [r1 , rn ] contains an odd number of nodes, then its unique middle node is chosen as the multiplicity 25

(a)

(b)

Figure 11: Illustration of the multiplicity creation phase after line formation for the configuration C21 : (a) all robots are positioned distinctly on the formation line L with terminal robots r2 and r5 ; (b) the node NL is selected as the unique multiplicity node with two leading corners p3 and p4 . node. Otherwise, [r1 , rn ] contains two middle nodes; the one closer to the leading corners of MERP is chosen as the multiplicity node (see Figure 11(a)). Note that, as the configuration is asymmetric, there always exists a unique key corner. Let the multiplicity node be denoted by NL for the configuration C21 (see Figure 11(b)). For the configuration C31 , let Nc denote the intersection node of L and the line passing through c that is perpendicular to L . This node is selected as the multiplicity node. Observe that if any robot is located at the multiplicity node in either configuration C21 or C31 , then it remains stationary. The movement of robots for each configuration is performed by the algorithm MoveToDestination(). The detailed pseudocode for this phase is given in Algorithm 5. Saturation Phase: If C(t0 ) ∈ {C21 , C31 }, then this phase is executed after the completion of the Multiplicity Phase. If C(t0 ) ∈ {C222 , C322 }, then this phase is executed after the completion of the Gathering Phase. Otherwise, this phase is executed as the first phase of the algorithm spg(). Once a multiplicity node or a gathering node is created, no robot located at that node is allowed to leave it. Since the robots are equipped with global strong multiplicity detection, each robot can determine whether it is located at the multiplicity node or the gathering node. Hence, such robots remain stationary in all subsequent phases. Since the robots have global visibility, they can distinguish among the different configuration classes. Note that the movement of robots for each configuration is performed by the algorithm MoveToDestination(). The detailed description of this phase is as follows. • C1 Configuration: Since the set of parking nodes P is asymmetric, all the parking nodes in P can be uniquely ordered. The robots in R first establish a common ordering O1 of the unsaturated parking nodes. They saturate these parking nodes sequentially according to the ordering O1 , that is, p1 is saturated first, followed by p2 , and so on. The procedure for saturating a single unsaturated parking node is formally described in Algorithm 6. Let Ru (t) = {r1 (t), r2 (t), . . . , rm (t)} ⊂ R(t) denote the set of unsaturated robot positions, and let p be the selected unsaturated parking node with capacity κ. The robots in Ru (t) are ordered such that dM (r1 (t), p) ≤ dM (r2 (t), p) ≤ · · · ≤ dM (rm (t), p), where dM (ri , p) denotes the Manhattan distance between the robot ri and the parking node p. Note that a robot selected to saturate an unsaturated parking node must not occupy any saturated parking node. The set of selected robots is defined as R∗p = {r1 , r2 , . . . , rκ }. 26

Algorithm 5 : MultiplicityCreation(C(t)) Require: Current configuration C(t0 ), robot set R(t), formation line L , rectangle MERP , ordering O2 Ensure: A unique multiplicity node is created on L if C(t0 ) ∈ / {C21 , C31 } then return end if if C(t0 ) ∈ C21 then Let r1 and rn be the two terminal robots on L Let [r1 , rn ] be the line segment on L induced by the robots Let S denote the set of nodes on the segment [r1 , rn ] if |S| is odd then Let NL be the unique middle node of [r1 , rn ] else Let x and y be the two middle nodes of [r1 , rn ] Let K be the unique key corner of MERP if dM (x, K) < dM (y, K) then NL ← x else NL ← y end if end if N ← NL else if C(t0 ) ∈ C31 then Let c be the center of rotational symmetry of P Let lc be the line passing through c and perpendicular to L Let Nc be the intersection node of lc and L N ← Nc end if while |R(t) ∩ {N}| < 2 do Let Ru (t) = R(t) \ (R(t) ∩ {N}) Select a robot r ∈ Ru (t) having minimum value of dM (r, N) Break ties using the ordering O2 Robot r moves toward N using MoveToDestination(r, N) Every robot already located at N remains stationary end while return

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33:

Algorithm 6 : SaturateParkingNode(p, O) Require: An unsaturated parking node p and a tie-breaking ordering O Ensure: The parking node p becomes saturated while |R(t) ∩ {p}| < κ do Let Ru (t) be the set of unsaturated robots Order the robots in Ru (t) increasingly according to dM (r, p) Break ties using the ordering O Let r be the first robot in the resulting order Robot r moves toward p using MoveToDestination(r, p) All other robots remain stationary during this move end while return

1: 2: 3: 4: 5: 6: 7: 8: 9:

Thus, the first κ robots in this ordering move toward p in a sequential order. If multiple robots have the same distance from p, the ties are broken using a fixed ordering [7], depending on the configuration of the robot positions. Since the capacities of the parking nodes are known, the strong multiplicity detection capability enables every robot to determine when the occupancy of a parking node reaches its prescribed capacity. The unsaturated parking nodes are saturated sequentially in order to avoid collisions among robots and prevent the formation of multiple multiplicity nodes. Note that if a robot is already a saturated robot, then it will never become unsaturated. • C21 Configuration: The parking-node configuration P admits a unique line of symmetry L, whereas the robot configuration R(t0 ) is asymmetric. Let P S and P U denote the sets of saturated and unsaturated parking nodes, respectively, where the set of parking nodes is P = P S ∪ P U . Further, let PL ⊆ P U denote the set of unsaturated parking nodes lying on L and let P U \ PL denote the set of unsaturated parking nodes lying outside L. (see Figure 12) The saturation phase is executed in two stages. In the first stage, the parking nodes belonging to PL are saturated. Once all these parking nodes have reached their prescribed capacities, the algorithm proceeds to saturate the parking nodes in P U \ PL . For the first stage, let pL be the unsaturated parking node on L selected according to the ordering 27

Algorithm 7 : SaturationPhaseC1(C(t)) Require: Current configuration C(t0 ), parking node set P Ensure: All parking nodes are saturated if C(t0 ) ∈ / C1 then return end if Construct the common ordering O1 = (p1 , p2 , . . . , pm ) of the unsaturated parking nodes in P for i = 1 to m do SaturateParkingNode(pi , O1 ) end for return

1: 2: 3: 4: 5: 6: 7: 8:

(a)

(b)

Figure 12: Illustration of the saturation process for configuration C21 : (a) creation of the unique multiplicity node at NL ; (b) since PL = {p7 , p8 } ⊆ P U , the parking node p7 is saturated with capacity κ7 = 4. O3 , and let its capacity be κ. Let Ru (t) = {r1 (t), r2 (t), . . . , rκ (t)} denote the set of unsaturated robots on L . The robots are ordered in nondecreasing order of their Manhattan distances from pL , i.e., dM (r1 , pL ) ≤ dM (r2 , pL ) ≤ · · · ≤ dM (rκ , pL ). Ties are resolved using the ordering O2 . The first κ robots in this ordering are selected to saturate pL . As the robots have strong multiplicity detection capability, every robot can determine when pL has reached its prescribed capacity. After all parking nodes on L have been saturated, consider the remaining unsaturated parking nodes P U \ PL = {p1 , p2 , . . . , pd }, ordered in nondecreasing order of their Manhattan distances from the multiplicity node NL , with ties broken according to O2 . The parking nodes are then saturated sequentially following this order. For each selected parking node pi with capacity κ, the unsaturated robots are ordered in nondecreasing order of their Manhattan distances from pi , with ties broken according to O2 . The first κ robots in the resulting order are assigned to pi . Again, strong multiplicity detection capability enables the robots to identify when the parking node has become saturated, after which the algorithm proceeds to the next parking node in the sequence. The detailed pseudocode for this phase is given in Algorithm 7. The parking nodes are saturated one at a time to ensure collision-free movements and to prevent the creation of unintended multiplicity nodes during the execution. • C31 Configuration: The parking-node configuration P admits rotational symmetry with center 28

Algorithm 8 : SaturationPhaseC21C31(C(t)) Require: Current configuration C(t0 ) ∈ {C21 , C31 } Ensure: All parking nodes are saturated if C(t0 ) ∈ / {C21 , C31 } then return end if Let P U be the set of unsaturated parking nodes if C(t0 ) ∈ C21 then Let L be the unique line of symmetry of P Let N = NL Let PL = {p ∈ P U : p ∈ L} while PL ̸= ∅ do Select a parking node pL ∈ PL using the ordering O3 SaturateParkingNode(pL , O2 ) Update P U and PL end while Let Pout = P U \ PL else if C(t0 ) ∈ C31 then Let c be the center of rotational symmetry of P Let N = Nc ∈ L if there exists an unsaturated parking node pc located at c then SaturateParkingNode(pc , O2 ) Update P U Let Pout = P U \ {pc } else Let Pout = P U end if end if while Pout ̸= ∅ do Select a farthest parking node pd ∈ Pout from N Break ties using the ordering O2 SaturateParkingNode(pd , O2 ) Update P U Pout ← P U ∩ Pout end while return

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33:

of rotation c, while the robot configuration R(t0 ) is asymmetric. Let P = P S ∪ P U , where P S and P U denote the sets of saturated and unsaturated parking nodes, respectively. Let pc ∈ P U be the unique unsaturated parking node located at the center of rotation c, and let P U \ {pc } denote the set of all remaining unsaturated parking nodes. The Saturation Phase is carried out in two stages. In the first stage, the parking node pc is saturated. Let Ru (t) = {r1 (t), r2 (t), . . . , rm (t)} ⊆ R(t) denote the set of unsaturated robots at time t. The robots are ordered according to their Manhattan distance from pc , namely, dM (r1 , pc ) ≤ dM (r2 , pc ) ≤ · · · ≤ dM (rm , pc ). Suppose that pc has capacity κ. Then the first κ robots in this ordering, R∗p = {r1 , r2 , . . . , rκ }, are selected to saturate pc and move toward it. If multiple robots are equidistant from pc , ties are resolved using the fixed ordering O2 defined in [7]. By means of strong multiplicity detection, the robots can determine when pc becomes saturated. Once pc is saturated, the algorithm then proceeds to saturate the remaining parking nodes in P U \{pc }. Let P U \{pc } = {p1 , p2 , . . . , pd }, where the parking nodes are ordered in non-decreasing order of their Manhattan distance from Nc , that is, dM (p1 , Nc ) ≤ dM (p2 , Nc ) ≤ · · · ≤ dM (pd , Nc ). The farthest parking node, pd , is selected first for saturation; ties are broken according to the ordering O2 . The unsaturated robots are ordered according to their Manhattan distance from pd , and the first κ robots on L in this ordering, where κ is the capacity of pd , are selected to saturate it. Ties are again resolved using the ordering O2 . After pd becomes saturated, the remaining unsaturated parking nodes are saturated sequentially by repeatedly applying the same procedure until every parking node reaches its prescribed capacity. This sequential saturation strategy prevents collisions among robots and avoids the creation of multiple multiplicity nodes during execution. The detailed execution of the saturation phase for configurations C21 and C31 is given in Algorithm 8. • C221 Configuration: Consider the set of robots lying on the line of symmetry L. Let re1 and re2 denote the two terminal robots, i.e., the robots located at the endpoints of the line segment 29

Algorithm 9 : SaturationPhaseC221C321(C(t)) Require: Initial configuration C(t0 ) ∈ {C221 , C321 } Ensure: The symmetry is broken and all parking nodes are saturated if C(t0 ) ∈ / {C221 , C321 } then return end if if C(t0 ) ∈ C221 then Let L be the unique line of symmetry of P Let re1 and re2 be the two terminal robots on L

1: 2: 3: 4: 5: 6: 7: if both re1 and re2 lie strictly inside MERP then 8: Let u and v be the intersection nodes of L with the two sides of MERP perpendicular to L 9: Move re1 along L to the node one hop beyond u 10: Move re2 along L to the node one hop beyond v 11: Select one terminal robot, say re1 , using the ordering O3 12: else 13: Select a terminal robot lying on or outside MERP , say re1 , using the ordering O3 14: Move re1 one hop along L away from the nearest side of MERP 15: end if 16: Select an adjacent free node g such that g ∈/ L 17: if re1 is in a pending move state then 18: Execute AllowtoMove(re1 ) 19: else 20: Move re1 to g 21: end if 22: if C(t) is asymmetric then 23: Execute SaturationPhaseC21C31(C(t)) 24: end if 25: else if C(t0 ) ∈ C321 then 26: Let c be the center of rotational symmetry of P 27: Let rc be the robot located at c 28: Designate rc as the symmetry-breaking robot 29: Execute AllowtoMove(rc ) 30: if C(t) is asymmetric then 31: Execute SaturationPhaseC21C31(C(t)) 32: end if 33: end if 34: return

formed by all robots on L. One of these terminal robots is eventually selected to perform the symmetry-breaking. If both re1 and re2 lie strictly inside MERP , then each robot moves along L toward the nearest side of MERP whose supporting line is perpendicular to L. Let u and v denote the intersection nodes of L with these two sides. The robots continue moving until they reach the nodes on L located one hop beyond u and v, respectively. If a terminal robot already lies on a side of MERP , then it moves along L to the node located one hop beyond its current position. After these movements are completed, one of the terminal robots is uniquely selected using the ordering O3 . Assume that without loss of generality that the selected robot is re1 . The selected robot re1 then moves to an adjacent free node g such that g ∈ / L, thereby breaking the symmetry of the configuration. If at least one terminal robot lies on the boundary of MERP or outside MERP , then such a terminal robot is selected for symmetry breaking. Ties are broken accordingly. The selected robot moves along L, away from the corresponding side of MERP , by one hop. Next, it moves to an adjacent free node g such that g ∈ / L, thereby breaking the symmetry of the configuration. If the selected robot is in a pending move state, the symmetry of the configuration is, however, broken during the execution of the procedure AllowtoMove() [8]. Once the symmetry is broken and the configuration becomes asymmetric, the algorithm proceeds to the Saturation Phase as described for the configuration C21 . • C321 Configuration: In this configuration, one robot, say rc , is located at the center of rotation c. This robot rc is eventually selected to perform the symmetry-breaking operation. The procedure of the algorithm AllowtoMove() [8] is used to transform the initial symmetric configuration C(t0 ) into an asymmetric configuration. Also, if the selected robot is in a pending move state, the symmetry of the configuration is, however, broken during the execution of the procedure Allow30

toMove() [8]. Once the initial configuration C(t0 ) becomes asymmetric, the Saturation Phase is executed in the same manner as for the configuration C31 , where no parking node is located at c. Algorithm 9 describes the saturation phase for configurations C221 and C321 , where the symmetry is first broken by a uniquely selected robot and the resulting asymmetric configuration is then handled by SaturationPhaseC21C31. • C222 Configuration: In this configuration, both P and R admit the same unique line of symmetry L, and initially no parking node or robot position lies on L. In this configuration, the Gathering Phase is executed first in order to preserve the symmetry of robot movements so that the configuration C(t) remains symmetric throughout the execution. If the configuration C(t) becomes asymmetric at any instant of time, collisions may occur, which may lead to an unsolvable configuration due to the creation of multiple multiplicity nodes. After completing the Gathering Phase, the Saturation Phase starts. At the end of the Gathering Phase, all the surplus robots are gathered at the node G located on L. Algorithm 10 : SaturationPhaseC222(C(t)) Require: Symmetric configuration C(t0 ) ∈ C222 , line of symmetry L, gathering node G Ensure: All parking nodes are saturated while preserving reflection symmetry if C(t0 ) ∈ / C222 then return end if while there exists an unsaturated parking node do Let P U be the set of unsaturated parking nodes Partition P U into symmetric pairs (p, µ(p)) with respect to L For each representative pi , compute di = dM (pi , G ) Let dmax = maxpi ∈P1 di

1: 2: 3: 4: 5: 6: 7: 8: 9: Select a symmetric parking-node pair (pi , µ(pi )) attaining dmax using the ordering O4 10: Let κ = κ(pi ) = κ(µ(pi )) 11: while |R(t) ∩ {pi }| < κ or |R(t) ∩ {µ(pi )}| < κ do 12: Let Ru (t) be the set of unsaturated robots 13: Partition Ru (t) into symmetric pairs (r, µ(r)) with respect to L 14: For each representative rj , compute Dj = dM (rj , pi ) 15: Let Dmin = min Dj 16: Select a symmetric robot pair (rj , µ(rj )) attaining Dmin using the ordering O4 17: if one robot of the selected pair is in a pending move state then 18: Execute Algorithm 1 for the pending robot until reflection symmetry is restored 19: else 20: Execute MoveToDestination(rj , pi ) 21: Execute MoveToDestination(µ(rj ), µ(pi )) 22: end if 23: end while 24: end while 25: return

Let P U denote the set of unsaturated parking nodes in the infinite grid (V, E). Initially, P U = P; hence, |P U | = m. Since the configuration C(t) ∈ C222 is symmetric with respect to the line of symmetry L, and no parking node lies on L, the set P U can be partitioned into symmetric pairs, P U = P1 ∪ µ(P1 ), where P1 = {p1 , p2 , . . . , p|P U |/2 }, and µ(pi ) denotes the reflection of pi with respect to L. For each representative parking node pi ∈ P1 , let di = dM (pi , G ) denote its Manhattan distance from the multiplicity node G , where G ∈ L. Since reflection preserves the Manhattan distance, dM (pi , G ) = dM (µ(pi ), G ), each symmetric parking-node pair (pi , µ(pi )) is uniquely associated with the common distance di . Let dmax = maxpi ∈P1 di . Among all symmetric parking-node pairs attaining the distance dmax , the ordering O4 uniquely selects one pair, say (pi , µ(pi )). Let κ = κ(pi ) = κ(µ(pi )) denote their common capacity. Let Ru (t) ⊆ R(t) denote the set of unsaturated robots. Since C(t) remains symmetric with respect to L, the robots in Ru (t) also occur in symmetric pairs. Accordingly, Ru (t) = R1 (t) ∪ µ(R1 (t)), where R1 (t) = {r1 , r2 , . . . , r|Ru (t)|/2 }. For each representative robot rj ∈ R1 (t), compute Dj = dM (rj , pi ). By reflection symmetry, dM (rj , pi ) = dM (µ(rj ), µ(pi )). Let Dmin = minrj ∈R1 (t) Dj . 31

Among all symmetric robot pairs attaining this minimum distance, the ordering O4 uniquely selects one pair, say (rj , µ(rj )). If one robot of the selected pair is in a pending move state, the procedure in Algorithm 1 is executed for the pending robot while its symmetric partner and all other robots remain stationary. Once the pending movement is completed, the reflection symmetry of the configuration is restored. Otherwise, the robots rj and µ(rj ) simultaneously move toward the parking nodes pi and µ(pi ), respectively, using the procedure MoveToDestination. This process is repeated until both parking nodes reach their prescribed capacity κ. After the selected parking-node pair becomes saturated, it is removed from P U . The algorithm continues by repeating these steps. It uses the O4 ordering to find the next pair of symmetric parking nodes that are not yet saturated, specifically considering the pair with the largest Manhattan distance from the multiplicity node G . The process continues until every parking node is saturated. Throughout the execution, the reflection symmetry of the configuration is preserved, and strong multiplicity detection enables the robots to determine when a parking node has reached its prescribed capacity. Algorithm 10 describes the saturation phase for configuration C222 while preserving reflection symmetry. • C322 Configuration: In this configuration, both the parking-node configuration P and the robot configuration R admit rotational symmetry with center of rotation c, and initially neither a parking node nor a robot occupies c. The Gathering Phase is executed first to preserve the rotational symmetry of robot movements throughout the execution. If the configuration C(t) becomes asymmetric at any time, collisions may occur, leading to the creation of multiple multiplicity nodes and exhibit the problem unsolvable. Let P U denote the set of unsaturated parking nodes in the infinite grid (V, E). Initially, P U = P, and hence |P U | = m. Since the configuration C(t) ∈ C322 is rotationally symmetric with respect to the center of rotation c, the set P U is partitioned into disjoint rotational orbits under the rotational map ρ. Let P1 = {p1 , p2 , . . . , p|P U |/q } be aSset containing exactly one representative parking node from each rotational orbit. Then, P U = pi ∈P1 Orbitpi , where Orbitpi = {pi , ρ(pi ), ρ2 (pi ), . . . , ρq−1 (pi )}. For each representative parking node pi ∈ P1 , let di = dM (pi , c) denote its Manhattan distance from the center of rotation c. Since the rotational map ρ preserves the Manhattan distance, dM (pi , c) = dM (ρj (pi ), c),0 ≤ j ≤ q − 1. Hence, every parking node in the orbit Orbitpi is associated with the common distance di . Let dmax = maxpi ∈P1 di . Among all parking-node orbits attaining the maximum distance dmax , the ordering O4 uniquely selects one orbit, denoted by Orbitpi . Let κ = κ(pi ) denote the common capacity of every parking node in the selected orbit. Since ρj (pi ) is obtained by rotating pi about the center of rotation c, and the rotational map ρ preserves the Manhattan distance from c, we have dM (pi , c) = dM (ρj (pi ), c), 0 ≤ j ≤ q − 1. Hence, every parking node in the orbit Orbitpi is associated with the common distance di . Let dmax = maxpi ∈P1 di . Among all parking-node orbits attaining the maximum distance dmax , the ordering O4 uniquely selects one orbit, denoted by Orbitpi . Let κ be the common capacity of every parking node in the selected orbit. Let Ru (t) ⊆ R(t) denote the set of unsaturated robots at time t. Since the configuration C(t) ∈ C322 is rotationally symmetric with respect to the center of rotation c, the set Ru (t) can be partitioned into disjoint rotational orbits under the rotational map ρ. Let R1 (t) = {r1 , r2 , . . . , r|Ru (t)|/q } be a set containing exactly one representative robot from each rotational orbit. Then, Ru (t) = S 2 q−1 (ri )}. For each robot ri ∈ R′u , let pi be ri ∈R1 (t) Orbitri , where Orbitri = {ri , ρ(ri ), ρ (ri ), . . . , ρ the unsaturated parking node selected for ri according to the ordering O4 . Define Di = dM (ri , pi ). 32

Algorithm 11 : SaturationPhaseC322(C(t0 )) Require: Initial configuration C(t0 ) ∈ C322 , center of rotation c, rotational map ρ Ensure: All parking nodes are saturated while preserving rotational symmetry if C(t0 ) ∈ / C322 then return end if while there exists an unsaturated parking node do Let P U be the set of unsaturated parking nodes Partition P U into rotational orbits under ρ Let P1 be a set of representatives of the parking-node orbits For each pi ∈ P1 , compute di = dM (pi , c) Let dmax = max di

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17:

pi ∈P1

Select the parking-node orbit Orbitpi attaining dmax using the ordering O4 Let κ ← κ(pi ) while some parking node in Orbitpi has occupancy less than κ do Let Ru (t) be the set of unsaturated robots Partition Ru (t) into rotational orbits under ρ Let R1 (t) be a set of representatives of the robot orbits For each rj ∈ R1 (t), compute Dj = dM (rj , pi ) Let Dmin =

min

rj ∈R1 (t)

Dj

18: Select the robot orbit Orbitrj attaining Dmin using the ordering O4 19: if some robot in Orbitrj is in a pending move state then 20: Execute Algorithm 1 for the pending robot until the rotational symmetry is restored 21: else 22: for a = 0 to q − 1 do 23: Execute MoveToDestination(ρa (rj ), ρa (pi )) 24: end for 25: end if 26: end while 27: end while 28: return

Similarly, for every rotational image ρj (ri ) of ri , the corresponding parking node is ρj (pi ), and its Manhattan distance is dM (ρj (ri ), ρj (pi )), 0 ≤ j ≤ q − 1. For each representative robot ri ∈ R1 (t), let Di = dM (ri , pi ) denote the Manhattan distance between ri and the representative parking node pi of the selected parking-node orbit. Since ρj (ri ) and ρj (pi ) are obtained by rotating ri and pi , respectively, about the center of rotation c, and the rotational map ρ preserves the Manhattan distance, we have dM (ri , pi ) = dM (ρj (ri ), ρj (pi )) 0 ≤ j ≤ q − 1. Hence, every robot orbit is associated with the common distance Di . Let Dmin = minri ∈R1 (t) Di . Among all robot orbits attaining the minimum distance Dmin , the ordering O4 uniquely selects one orbit, denoted by Orbitri . If one robot in the selected orbit is in a pending move state, the procedure Algorithm 1 is executed for the pending robot until the rotational symmetry of the configuration is restored. Otherwise, for every 0 ≤ a ≤ q −1, the robot ρa (ri ) moves toward the parking node ρa (pi ) using the procedure MoveToDestination. This process is repeated until every parking node in the selected orbit reaches its prescribed capacity κ. After the selected parking-node orbit becomes saturated, it is removed from P U . The algorithm then repeats the above procedure by selecting another parking-node orbit attaining the maximum Manhattan distance from the center of rotation c, with ties broken according to the ordering O4 . The process continues until every parking node is saturated. Throughout the execution, the rotational symmetry of the configuration is preserved, and strong multiplicity detection enables the robots to determine when a parking node reaches its prescribed capacity. The pseudo-code corresponding to this phase is given in Algorithm 11. Gathering Phase: If C(t0 ) ∈ {C222 , C322 }, then this phase is executed as the initial phase of the algorithm spg(). For all other solvable configurations, the Gathering Phase is executed only after the completion of the Saturation Phase. Note that the problem SPG is unsolvable when the initial configuration satisfies C(t0 ) ∈ {C223 , C323 }. The Gathering Phase is described in detail below. 33

• C1 Configuration: In this configuration, the Gathering Phase is executed only after the completion of Saturation Phase. Since the set of parking nodes P is asymmetric, all parking nodes in P can be uniquely ordered. Consequently, a unique leading corner, say Kp of MERP can be determined. Let ST Ri denote the string representation associated with the corner Kp . The gathering node, denoted by G , is chosen as the unique node outside MERP such that: 1. G is adjacent to the corner Kp , and 2. there exists a ray (grid-line) originating from G and lying outside MERP such that the ray is parallel to the string direction ST Ri . Algorithm 12 GatheringPhaseC1(C(t0 )) Require: Initial configuration C(t0 ) ∈ C1 , parking-node set P, surplus robot set Rs (t) Ensure: All surplus robots gather at the unique gathering node G if C(t0 ) ∈ / C1 then return end if if the Saturation Phase is not completed then return end if Determine the unique leading corner Kp of MERP

1: 2: 3: 4: 5: 6: 7: 8: Let ST Ri be the string representation associated with Kp 9: Select the unique gathering node G outside MERP adjacent to Kp 10: Let Lg be the ray originating at G , lying outside MERP , and parallel to the direction of ST Ri 11: while there exists a surplus robot r ∈ Rs (t) such that r ̸= G do 12: For each surplus robot ri ∈ Rs (t), compute ∆i = dM (ri , G ) 13: Let ∆min = r ∈R min ∆i s (t) i 14: Select a surplus robot r ∈ Rs (t) satisfying dM (r, G ) = ∆min , breaking ties using ordering on C(t) 15: Execute MoveToDestination(r, G ) 16: Update the surplus robot set Rs (t) 17: end while 18: return

Consider the surplus robot set Rs (t) = {r1 (t), r2 (t), . . . , rs (t)} ⊆ R(t). For each surplus robot ri ∈ Rs (t), let ∆i = dM (ri , G ). Define ∆min = minri ∈Rs (t) ∆i . Among all surplus robots attaining the minimum distance ∆min , one robot ri is selected (ties are broken using ordering on C(t)). The selected robot moves toward G using the procedure MoveToDestination. After the movement is completed, the surplus robot set is updated and the same procedure is repeated. The Gathering Phase terminates when every surplus robot reaches the gathering node G . The pseudo-code corresponding to this phase is given in Algorithm 12. • C21 Configuration: For this configuration, the Gathering Phase is executed only after the completion of the Saturation Phase (see Figure 13(a)) . At this stage, all robots lie on the line L obtained during the Line Formation Phase, and the multiplicity node NL has been established during the Multiplicity Creation Phase. The objective of this phase is to move all surplus robots to NL . Consider the surplus robot set Rs (t) = {r1 (t), r2 (t), . . . , rs (t)} ⊂ R(t) on L . Since every surplus robot lies on L , for each robot ri ∈ Rs (t), define ∆i = dM (ri , NL ), where dM (ri , NL ) denotes the Manhattan distance between the robot ri and the gathering node NL . Assume ∆min = min{∆i : ri ∈ Rs (t)}. The surplus robot whose distance from NL is ∆min is selected to move first. If ∆min = 0, then a robot ri is already located at NL and hence remains stationary. If multiple robots attain the same minimum distance ∆min , ties are broken using a fixed ordering [7], depending on the configuration of the robot positions. Without loss of generality, let the robots be ordered such that ∆1 ≤ ∆2 ≤ · · · ≤ ∆s . According to this ordering (ties are broken using a fixed ordering [7], depending on the configuration of the robot positions), all surplus robots sequentially move along L towards NL and gather at the node NL . This phase terminates when

34

Algorithm 13 : GatheringPhaseC21 C221(C(t)) Require: Current configuration C(t) ∈ {C21 , C221 }, formation line L , multiplicity node NL Ensure: All surplus robots gather at the multiplicity node NL if C(t0 ) ∈ / {C21 , C221 } then return end if if the Saturation Phase is not completed then return end if if C(t0 ) ∈ C221 then The terminal robot re1 breaks the symmetry during the Saturation Phase

1: 2: 3: 4: 5: 6: 7: 8: 9: The configuration C(t) is transformed into a C21 configuration 10: end if 11: Let Rs (t) = {r1 (t), r2 (t), . . . , rs (t)} be the set of surplus robots 12: All robots in Rs (t) lie on the formation line L 13: while there exists a surplus robot ri ∈ Rs (t) such that ri ̸= NL do 14: For each surplus robot ri ∈ Rs (t), compute ∆i = dM (ri , NL ) 15: Let ∆min = min{∆i : ri ∈ Rs (t)} 16: if ∆min = 0 then 17: Every surplus robot already located at NL remains stationary 18: end if 19: Select a surplus robot r ∈ Rs (t) satisfying dM (r, NL ) = ∆min 20: If more than one surplus robot attains ∆min , break ties using the fixed ordering 21: Robot r moves along L toward NL using MoveToDestination(r, NL ) 22: All other surplus robots remain stationary during this move 23: Update the surplus robot set Rs (t) 24: end while 25: return

all surplus robots reach NL . (see Figure 13(b)). The pseudo-code corresponding to this phase is given in Algorithm 13. • C221 Configuration: During the Saturation Phase, the terminal robot re1 breaks the symmetry of the configuration, transforming it to a C21 configuration. The subsequent Gathering Phase is then executed exactly as described for C21 . The pseudo-code corresponding to this phase is given in Algorithm 13. • C222 Configuration: In this configuration, both P and R admit the same unique line of symmetry L, and neither a parking node nor a robot position lies on L. To preserve the symmetry of the configuration, the Gathering Phase is executed before the Saturation Phase. This ensures that the symmetry of C(t) is maintained throughout the execution. Breaking the symmetry may lead to collisions among robots, resulting in the creation of multiple multiplicity nodes and consequently an unsolvable configuration. Since every robot knows the total capacity of the parking nodes in P, it can determine the number of surplus robots. As the total number of robots exceeds the sum of the capacities of all parking nodes by at least two, there exist surplus robots that can participate in the Gathering Phase. Hence, the Gathering Phase is well defined for the initial configuration C(t0 ). Consider the surplus robot set Rs ⊆ R, where |Rs | = d and d is even. Define SL = L ∩ MERR to be the line segment of the symmetry line L contained in MERR . Equivalently, SL is the sub-grid containing grid nodes on L that lie within MERR . Now define VL = SL ∩ V. Thus, VL denotes the set of all grid nodes lying on the line segment SL . Since, the configuration C(t) ∈ C222 is symmetric with respect to the line of symmetry L, the robots in Rs appear in symmetric pairs with respect to L. Therefore, Rs can be partitioned into two subsets R′s and µ(R′s ), where R′s = {r1 , r2 , . . . , r d } and µ(R′s ) = {µ(r1 ), µ(r2 ), . . . , µ(r d )}. Hence, 2 2 Rs = R′s ∪ µ(R′s ). Here, µ(ri ) denotes the image of ri under the reflection map µ (See Definition 1) with respect to L. Consider ∆i = dM (ri , VL ), where, ri ∈ R′s . Similarly, the symmetric image µ(ri ) of ri is associated with the symmetric parking node µ(pi ), and its corresponding Manhattan distance is dM (µ(ri ), VL ). Since µ(ri ) is the reflection of ri with respect to the line of symmetry L, and since reflection preserves the grid Manhattan distance, we have dM (ri , VL ) = dM (µ(ri ), VL ). 35

(a)

(b)

Figure 13: Illustration of the final stage of the algorithm for the configuration C21 : (a) all parking nodes are saturated; (b) the surplus robots gather at the node NL . Assume ∆min = min{∆i :, ri ∈ R′s }. For the fixed Manhattan distance value ∆min , the number of robots in R′s at distance ∆min may be either one or more than one. If exactly one robot, say ri , is at distance ∆min , then it determines a unique symmetric pair of robots (ri , µ(ri )), which in turn uniquely determines a gathering node, say G ∈ VL . Otherwise, multiple symmetric pairs of robots correspond to the distance value ∆min . In this case, the ordering O4 is used to uniquely identify one such symmetric pair, say (ri , µ(ri )), which consequently determines a unique gathering node G ∈ VL . This pair (ri , µ(ri )) of robots initiates the Gathering Phase. Due to the asynchronous nature of the robot activations, one of the robots may be in a pending move state. Our aim is to preserve the symmetry of the configuration in order to avoid collisions among robots. Using the Algorithm 1, a robot in the pending move state can always be identified. Whenever a robot in the pending move state is identified, its paired robot remains stationary until the pending robot reaches a position where the symmetry of the configuration is restored, and collision is avoided. Thus, the configuration remains symmetric. The robots in R′s are ordered according to the ordering O ′ such that dM (r1 , G ) ≤ dM (r2 , G ) ≤ · · · ≤ dM (r d , G ). By symmetry, this induces the same ordering on their symmetric counterparts: 2 , i.e., dM (µ(r1 ), G ) ≤ dM (µ(r2 ), G ) ≤ · · · ≤ dM (µ(r d ), G ). 2

The symmetric pair (ri , µ(ri )) that initiates the Gathering Phase moves toward G and creates a multiplicity node at G . Once the multiplicity node at G is created, all surplus robots in Rs detect this node and move sequentially toward G according to the ordering O ′ (ties are broken using ordering O4 ). Using the strong multiplicity detection capability, the robots in R can determine the exact number of surplus robots gathered at G . This phase terminates when all surplus robots reach G . Note that a configuration C222 transforms into a configuration of type C221 after the completion of the Gathering phase. However, since the robots have strong multiplicity detection capability, they can identify this transition. Therefore, after the Gathering phase, the robots proceed with the Saturation phase using the strategy prescribed for configurations of type C222 . The pseudo-code corresponding to this phase is given in Algorithm 14. 36

Algorithm 14 : GatheringPhaseC222(C(t)) Require: Symmetric configuration C(t) ∈ C222 , line of symmetry L, surplus robot set Rs (t) Ensure: All surplus robots gather at a unique node G ∈ L if C(t0 ) ∈ / C222 then return end if Let SL = L ∩ MERR Let VL = SL ∩ V Partition Rs (t) into symmetric pairs with respect to L Let R′s = {r1 , r2 , . . . , r d } contain one representative from each symmetric pair

1: 2: 3: 4: 5: 6: 7: 2 8: Rs (t) = R′s ∪ µ(R′s ) 9: for each robot ri ∈ R′s do 10: Compute ∆i = dM (ri , VL ) 11: end for 12: Let ∆min = min{∆i : ri ∈ R′s } 13: if exactly one robot ri ∈ R′s satisfies ∆i = ∆min then 14: Select the symmetric robot pair (ri , µ(ri )) 15: else 16: Select a unique symmetric robot pair (ri , µ(ri )) attaining ∆min using the ordering O4 17: end if 18: Let G ∈ VL be the unique gathering node determined by the selected pair (ri , µ(ri )) 19: while |Rs (t) ∩ G | < 2 do 20: if one robot of the selected pair (ri , µ(ri )) is in a pending move state then 21: The paired robot remains stationary 22: Execute Algorithm 1 for the pending robot until the reflection symmetry is restored 23: else 24: Robot ri moves toward G using MoveToDestination(ri , G ) 25: Robot µ(ri ) moves toward G using MoveToDestination(µ(ri ), G ) 26: end if 27: end while 28: A multiplicity node is created at G 29: while there exists a surplus robot r ∈ Rs (t) such that r ̸= G do 30: Partition the robots in Rs (t) \ (Rs (t) ∩ G ) into symmetric pairs 31: Let R′′s contain one representative from each remaining symmetric pair 32: for each robot rj ∈ R′′s do 33: Compute Dj = dM (rj , G ) 34: end for 35: Let Dmin = min{Dj : rj ∈ R′′s } 36: Select a symmetric pair (rj , µ(rj )) attaining Dmin 37: Break ties using the ordering O4 38: if one robot of the selected pair (rj , µ(rj )) is in a pending move state then 39: The paired robot remains stationary 40: Execute Algorithm 1 for the pending robot until the reflection symmetry is restored 41: else 42: Robot rj moves toward G using MoveToDestination(rj , G ) 43: Robot µ(rj ) moves toward G using MoveToDestination(µ(rj ), G ) 44: end if 45: Using strong multiplicity detection, update the number of surplus robots gathered at G 46: end while 47: return

• C31 Configuration: The set of parking nodes P admits rotational symmetry with center of rotation c, while the robot configuration R(t0 ) is asymmetric. For this configuration, the Gathering Phase is executed only after the completion of the Saturation Phase. In Line Formation Phase, all robots are on the L and in Multiplicity Creation Phase, the multiplicity node Nc on L is created, hence all surplus robots gather at Nc . Consider the surplus robot set Rs (t) = {r1 (t), r2 (t), . . . , rs (t)} ⊂ R(t). Here, all robots in Rs lie on the line L obtained after the completion of the Line Formation Phase. For each robot ri ∈ Rs (t), define ∆i = dM (ri , Nc ), where dM (ri , Nc ) denotes the Manhattan distance between the robot ri and the gathering node Nc . Assume ∆min = min{∆i : ri ∈ Rs (t)}. The surplus robot whose distance from Nc is ∆min is selected to move first. If ∆min = 0, then a robot ri is already located at Nc and hence remains stationary. If multiple robots attain the same minimum distance ∆min , ties are broken using a fixed ordering [7], depending on the configuration of the robot positions. Without loss of generality, let the robots be ordered such that ∆1 ≤ ∆2 ≤ · · · ≤ ∆s . According to this ordering (ties are broken using a fixed ordering [7], depending on the configuration of the robot positions), all surplus robots sequentially move along L towards Nc and gather at the node Nc . This phase terminates when 37

Algorithm 15 : GatheringPhaseC31C321(C(t)) Require: Current configuration C(t) ∈ {C31 , C321 }, formation line L , multiplicity node Nc Ensure: All surplus robots gather at the multiplicity node Nc if C(t0 ) ∈ / {C31 , C321 } then return end if if the Saturation Phase is not completed then return end if if C(t0 ) ∈ C321 then Let rc be the robot located at the center of rotation c During the Saturation Phase, robot rc performs the symmetry-breaking operation The configuration C(t) is transformed into a C31 configuration end if Let Rs (t) = {r1 (t), r2 (t), . . . , rs (t)} be the set of surplus robots All robots in Rs (t) lie on the formation line L while there exists a surplus robot ri ∈ Rs (t) such that ri ̸= Nc do For each surplus robot ri ∈ Rs (t), compute ∆i = dM (ri , Nc ) Let ∆min = min{∆i : ri ∈ Rs (t)} if ∆min = 0 then Every surplus robot already located at Nc remains stationary end if Select a surplus robot r ∈ Rs (t) satisfying dM (r, Nc ) = ∆min If more than one surplus robot attains ∆min , break ties using the fixed ordering Robot r moves along L toward Nc using MoveToDestination(r, Nc ) All other surplus robots remain stationary during this move Update the surplus robot set Rs (t) end while return

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26:

all surplus robots reach Nc . The pseudo-code corresponding to this phase is given in Algorithm 15. • C321 Configuration: In this configuration, a robot rc is located at the center of rotation c. During the Saturation Phase, the robot rc performs the symmetry-breaking operation, thereby transforming the configuration into C31 configuration. Thereafter, the Gathering Phase is executed in the same manner as described for C31 . The pseudo-code corresponding to this phase is given in Algorithm 15. • C322 Configuration: In this configuration, both P and R admit rotational symmetry with center of rotation c, and initially no parking node or robot position lies at c. For this configuration, the Gathering Phase is executed first in order to preserve the symmetry of robot movements so that the configuration C(t) remains symmetric throughout the execution. If the configuration C(t) becomes asymmetric at any instant of time, collisions may occur, making the problem unsolvable due to the creation of multiple multiplicity nodes. Consider the surplus robot set Rs ⊆ R, where |Rs | = d and d is divisible by q, q is the order of rotational symmetry. Since the configuration C(t) ∈ C322 is rotationally symmetric with respect to the center of rotational symmetry c, the robots in Rs can be partitioned into disjoint rotational orbits under the rotational map ρ (See Definition 2). For each robot ri ∈ Rs , define its rotational orbit as Orbitri = {ri , ρ(ri ), ρ2 (ri ), . . . , ρq−1 (ri )}, where q ≥ 2 denotes the order of rotational symmetry. Let R′s = {r1 , r2 , . . . , r d } be a set containing S q exactly one representative robot from each rotational orbit. Then, Rs = ri ∈R′s Orbitri . Define ∆i = dM (ri , c). Similarly, for every rotational image ρj (ri ) of ri with respect to c, and its Manhattan distance is dM (ρj (ri ), c), 0 ≤ j ≤ q − 1. Since ρj (ri ) is obtained by rotating ri about the center of rotational symmetry c, and since rotation preserves the grid Manhattan distance, we have dM (ri , c) = dM (ρj (ri ), c) for every 0 ≤ j ≤ q − 1. Assume ∆min = min{∆i : ri ∈ R′s }. For the fixed Manhattan distance value ∆min , the number of representative robots in R′s at distance ∆min may be either one or more than one. If exactly one representative robot, say ri , is at distance ∆min , then it determines a unique rotational orbit 38

Orbitri . Otherwise, multiple rotational orbits correspond to the distance value ∆min . In this case, the ordering O4 is used to uniquely identify one such rotational orbit, say Orbitri . This rotational orbit Orbitri = {ri , ρ(ri ), ρ2 (ri ), . . . , ρq−1 (ri )} initiates the Gathering Phase. Due to the asynchronous nature of robot activations, one or more robots in the orbit may be in a pending move state. Our aim is to preserve the rotational symmetry of the configuration in order to avoid collisions among robots. Using the Algorithm 1, a robot in the pending move state can always be identified. Whenever such a robot is identified, all other robots belonging to the same rotational orbit remain stationary until the pending robot reaches a position where the rotational symmetry of the configuration is restored and collision is avoided. Thus, the configuration remains rotationally symmetric throughout the execution. The representative robots in R′s are ordered according to the ordering, say O ′′ such that dM (r1 , c) ≤ dM (r2 , c) ≤ · · · ≤ dM (r d , c). By symmetry, this induces the same ordering on the corresponding q

rotational orbits. The rotational orbit Orbitri = {ri , ρ(ri ), ρ2 (ri ), . . . , ρq−1 (ri )} that initiates the Gathering Phase moves toward the center of rotation c and reaches c. All remaining surplus robots in Rs detect the center of rotation c and move orbit by orbit toward c according to the ordering O ′′ , where ties are broken using the ordering O4 . Using the strong multiplicity detection capability, the robots in R can determine the exact number of surplus robots gathered at c. This phase terminates when all surplus robots in Rs reach c. Note that a configuration C322 transforms into a configuration of type C321 after the completion of the Gathering phase. However, since the robots have strong multiplicity detection capability, they can identify this transition. Therefore, after the Gathering phase, the robots proceed with the Saturation phase using the strategy prescribed for configurations of type C322 . The pseudo-code corresponding to this phase is given in Algorithm 16. Note that the movement of robots for each configuration during the Gathering Phase is performed by the algorithm MoveToDestination().

4.4

Routine MoveToDestination()

The routine MoveToDestination() specifies how a selected robot moves toward its designated destination node during the execution of Algorithm spg(). This routine is invoked in the Line Formation Phase, Multiplicity Creation Phase, Saturation Phase, and Gathering Phase. In each phase, the admissible robot is selected according to the ordering defined for the corresponding configuration. During the Line Formation Phase, let S denote the corresponding reference structure, where S is either the line of symmetry L or the center of rotational symmetry c. For each robot ri (t), let vi denote its assigned destination node on the reference structure. Define Di (t) = dM (ri (t), S), where dM denotes the Manhattan distance. The admissible robot is selected as r∗ (t) ∈ arg maxri (t)∈R(t) Di (t), with ties broken according to the ordering prescribed for the corresponding configuration. During the Multiplicity Creation Phase, Saturation Phase, and Gathering Phase, let vi denote the destination node assigned to robot ri (t). Let Ra (t) denote the set of robots eligible to move in the current phase. The admissible robot is selected as r∗ (t) ∈ arg minri (t)∈Ra (t) dM (ri (t), vi ), where ties are again broken according to the ordering defined for the corresponding configuration. Once the admissible robot r∗ (t) is selected, it remains the only moving robot until it reaches its assigned destination node v ∗ . More precisely, for every intermediate time t′ > t before r∗ reaches v ∗ , all other robots remain stationary. The robot r∗ moves along a shortest Manhattan path from its current position to v ∗ . At each move, the robot advances by one grid hop along this shortest path. The robot continues moving until dM (r∗ (t), v ∗ ) = 0, at which point it reaches its destination and becomes stationary. The ordering 39

Algorithm 16 : GatheringPhaseC322(C(t)) Require: Rotationally symmetric configuration C(t) ∈ C322 , center of rotation c, rotational map ρ, surplus robot set Rs (t) Ensure: All surplus robots gather at the center of rotation c if C(t0 ) ∈ / C322 then return end if Let q be the order of rotational symmetry Let Rs (t) be the set of surplus robots, where |Rs (t)| = d and q divides d Partition Rs (t) into disjoint rotational orbits under the rotational map ρ Let R′s = {r1 , r2 , . . . , r d } contain exactly one representative robot from each rotational orbit

1: 2: 3: 4: 5: 6: 7: q 8: for each representative robot ri ∈ R′s do 9: Compute ∆i = dM (ri , c) 10: end for 11: Let ∆min = min{∆i : ri ∈ R′s } 12: if exactly one representative robot ri ∈ R′s satisfies ∆i = ∆min then 13: Select the rotational orbit Orbitri 14: else 15: Select a unique rotational orbit Orbitri attaining ∆min using the ordering O4 16: end if 17: while not all robots in Orbitri have reached c do 18: if some robot in Orbitri is in a pending move state then 19: All other robots in Orbitri remain stationary 20: Execute Algorithm 1 for the pending robot until rotational symmetry is restored 21: else 22: for a = 0 to q − 1 do 23: Robot ρa (ri ) moves toward c using MoveToDestination(ρa (ri ), c) 24: end for 25: end if 26: end while 27: while there exists a surplus robot r ∈ Rs (t) such that r ̸= c do 28: Let Rus (t) = {r ∈ Rs (t) : r ̸= c} be the set of surplus robots not yet gathered at c 29: Partition Rus (t) into disjoint rotational orbits under ρ 30: Let Rb s contain exactly one representative robot from each remaining rotational orbit 31: for each representative robot rj ∈ Rb s do 32: Compute Dj = dM (rj , c) 33: end for 34: Let Dmin = min{Dj : rj ∈ Rb s } 35: Select a rotational orbit Orbit(rj ) attaining Dmin 36: Break ties using the ordering O4 37: if some robot in Orbit(rj ) is in a pending move state then 38: All other robots in Orbit(rj ) remain stationary 39: Execute Algorithm 1 for the pending robot until rotational symmetry is restored 40: else 41: for a = 0 to q − 1 do 42: Robot ρa (rj ) moves toward c using MoveToDestination(ρa (rj ), c) 43: end for 44: end if 45: Update the number of surplus robots gathered at c 46: end while 47: return

is then recomputed over the remaining eligible robots, and the next admissible robot is selected for movement. Since at most one robot moves at any time while all others remain stationary, collisions and non-designated multiplicity nodes are avoided. If the configuration C(t0 ) admits a line of symmetry L, then a symmetric pair of robots, say (r, µ(r)), is selected for movement according to the appropriate ordering, where µ(·) denotes the reflection mapping with respect to L. The robots r and µ(r) move simultaneously toward their respective destination nodes along shortest Manhattan paths that are symmetric with respect to L. Hence, the symmetry of C(t) with respect to L is preserved throughout the movement. Moreover, these two paths do not intersect before the robots reach their destination nodes; otherwise, by symmetry, an undesired multiplicity or collision would be created before the designated destination is reached. Similarly, if the configuration C(t0 ) admits a rotational symmetry of order k, then all robots belonging to the same rotational orbit Orbit(r) = r, ρ(r), ρ2 (r), . . . , ρk−1 (r) are selected for movement according to the appropriate ordering, where ρ denotes the rotation operator about the center of rotational symmetry. These robots move simultaneously toward their respective destination nodes along shortest Manhattan paths that are rotationally symmetric images of one another. Therefore, the rotational symmetry of C(t) is maintained at every time instant during the movement. Furthermore, the paths of robots in the 40

same orbit do not intersect before reaching their corresponding destination nodes.

5

Correctness of the Algorithm spg()

We prove the correctness of the algorithm spg() by establishing the correctness of its four phases. We first state a common property of the movement routine, which will be used repeatedly in the phase-wise proofs. Lemma 1. The procedure MoveToDestination() guarantees that the designated robot, symmetric pair of robots, or rotational orbit of robots reaches its assigned destination after finitely many hops. Throughout its execution, the required symmetry is preserved, and no unintended collision or multiplicity node is created. Proof. We prove the statement by considering the possible types of selected entities (robots/ parking nodes) in the procedure MoveToDestination(). Case 1: A single designated robot is selected. Let r be the designated robot and let v be its assigned destination. The robot r moves along a shortest Manhattan path from its current node to v. After each hop, the Manhattan distance from r to v decreases by exactly one. Since this distance is a nonnegative integer, after finitely many hops it becomes zero. Hence, r reaches its destination v in finite time. During this movement, no other robot is allowed to move. Moreover, r is allowed to stop on an occupied node only if that node is explicitly prescribed by the current phase, such as a saturated parking node, the multiplicity node, or the gathering node. Therefore, no unintended collision or multiplicity node is created. Case 2: A symmetric pair of robots is selected. Suppose that a pair of robots (r, µ(r)) is selected with respect to the line of symmetry L, where µ denotes the reflection map. Let their assigned destinations be v and µ(v), respectively. If r ∈ / L, then r and µ(r) lie on opposite sides of L; otherwise, r = µ(r) lies on L and is treated as a single designated robot using an appropriate ordering. Assume first that r ∈ / L. The robot r moves along a shortest Manhattan path from r to v, while µ(r) moves along the reflected copy of the same path from µ(r) to µ(v). Hence, after every hop, the Manhattan distance of each robot from its own destination decreases by one. Since these distances are nonnegative integers, both robots reach their respective destinations after finitely many hops. Moreover, the two prescribed paths are mirror images of each other with respect to L. Therefore, the reflectional symmetry of the configuration is preserved after every hop. Since the two robots lie on opposite sides of L and move along symmetric paths, their paths do not intersect before reaching their assigned destinations. No robot outside the selected pair is allowed to move during this execution. A collision may occur only when a destination node is explicitly prescribed by the current phase of the algorithm, namely, a multiplicity node, a saturated parking node, or the gathering node. Therefore, any such collision is intentional and occurs only at a prescribed destination. Thus, no unintended collision or multiplicity node is created. If a robot lying on L is selected for an intentional symmetry-breaking move, then this movement is not treated as a symmetric-pair movement; it is handled separately as a single designated-robot movement using the prescribed ordering and the procedure AllowtoMove(). Case 3: A rotational orbit of robots is selected. Suppose that a rotational orbit of robots is selected with respect to the center of rotational symmetry c. Let ρ be the rotational map defined in Definition 2, and let Orbitr = {r, ρ(r), ρ2 (r), . . . , ρq−1 (r)} be the selected orbit. Let v be the assigned destination of the representative robot r. Then, for each i ∈ {0, 1, . . . , q − 1}, the robot ρi (r) is assigned the destination ρi (v). The representative robot r moves along a shortest Manhattan path from r to v. For every i, the robot ρi (r) moves along the path obtained by applying the rotational map ρi to the 41

path of r. Thus, all robots in the orbit move along rotated copies of the same prescribed path toward their respective destinations. After every hop, the Manhattan distance between each robot ρi (r) and its assigned destination ρi (v) decreases by one. Since these distances are nonnegative integers, all robots in the selected rotational orbit reach their assigned destinations after finitely many hops. Moreover, the destinations and the prescribed paths are closed under the rotational map ρ. Hence, after every hop, the image of the position of ρi (r) under ρ coincides with the position of ρi+1 (r), for all i modulo q. Therefore, the rotational symmetry of the configuration is preserved throughout the execution. No robot outside the selected rotational orbit is allowed to move during this procedure. Also, by the construction of the prescribed paths, the moving robots do not create any unintended collision before reaching their destinations. A robot may terminate on an occupied node only when that node is explicitly designated by the current phase of the algorithm, namely, a multiplicity node, a saturated parking node, or the gathering node. Therefore, no unintended collision or multiplicity node is created. Combining the three cases, the procedure MoveToDestination() guarantees that the selected robot, symmetric pair, or rotational orbit reaches its assigned destination after finitely many hops, preserves the required symmetry, and avoids every unintended collision or multiplicity node. Lemma 2. For every initial configuration C(t0 ) ∈ {C21 , C31 }, the Line Formation Phase terminates in finite time with all robots occupying distinct nodes of a uniquely identifiable formation line L . Proof. We first show that the formation line is uniquely determined. Case 1. C(t0 ) ∈ C21 . Since the parking-node set P admits a unique line of reflectional symmetry L, every robot can independently compute L, the rectangle MERP , and the Manhattan distance of every robot from L. The robot rg is then selected from the set of robots farthest from L, with ties broken according to the ordering O2 . As the robot configuration is asymmetric, the ordering O2 yields a unique choice of rg . Let u denote the point where the line through rg perpendicular to L intersects the nearest side of MERP . The node w is then uniquely determined by the condition dM (u, w) = 2 and by requiring w to lie on the ray from u directed away from MERP . Hence, the formation line L , defined as the line passing through w and parallel to L, is uniquely determined. Case 2. C(t0 ) ∈ C31 . The center of rotational symmetry c is uniquely determined. Every robot can therefore compute its Manhattan distance from c. The robot rg is selected from the set of robots farthest from c, with ties broken according to the ordering O2 . Since the ordering is deterministic, the selected robot rg is unique. Consequently, the grid line passing through c and rg is uniquely determined. Let u denote the point where this line meets the boundary of MERP in the direction of rg . The node w is then uniquely determined by the condition dM (u, w) = 2 and by requiring w to lie beyond MERP along the same line. Hence, the formation line L , defined as the line passing through w and perpendicular to the line joining c and rg , is uniquely determined. Thus, the formation line L is uniquely determined in both configuration classes. If the designated destination node on L is already occupied, the auxiliary-line rule is applied to locate another free node on L . Since only finitely many nodes of L are occupied by robots, whereas L contains infinitely many grid nodes, such a free node always exists. Hence, every robot can be assigned a distinct destination node on L . By Lemma 1, each selected robot reaches its assigned destination after finitely many hops without creating any collision or unintended multiplicity node. Once a robot reaches its destination on L , it remains stationary and is never selected again. Therefore, the number of robots outside L decreases by one after each successful movement and never increases. Since the number of robots is finite, after finitely many movements every robot occupies a distinct node on L . Hence, the Line Formation Phase 42

terminates with all robots positioned at the distinct nodes of the uniquely determined formation line L. Lemma 3. After the Line Formation Phase, the Multiplicity Creation Phase correctly creates a unique and stable multiplicity node in finite time. Proof. By Lemma 2, after the Line Formation Phase, all robots occupy distinct nodes on the uniquely determined formation line L . Case 1. C(t0 ) ∈ C21 . The terminal robots r1 and rn on L uniquely determine the segment [r1 , rn ]. If this segment contains an odd number of nodes, then its middle node is unique. Otherwise, the segment contains exactly two middle nodes. Since the parking-node set P has a unique line of symmetry, among these two nodes, the one uniquely closer, say NL to the two leading corners of MERP is selected. Hence, every robot identifies the same node NL . If NL is already occupied by a robot, then that robot remains stationary, and another designated robot is moved to NL . The designated robot is chosen as the closest robot on L to NL . If two such closest robots exist, then they lie on opposite sides of NL along L . Otherwise, a designated robot(s) first moves to NL and remains stationary there. Then, another designated robot(s) moves to the same node. Consequently, NL becomes the unique multiplicity node. Case 2. C(t0 ) ∈ C31 . The center of rotational symmetry c and the formation line L are uniquely determined in a configuration C31 . After the line-formation phase is completed, all robots lie on L , and hence every robot identifies the same node Nc on L . Once Nc is identified, the procedure for creating a unique and stable multiplicity node is the same as that used for configuration C21 . By Lemma 1, every designated robot reaches its assigned destination after finitely many hops without creating any undesired collision or unintended multiplicity node. Once a robot reaches the designated node, it remains stationary. Therefore, after finitely many movements, a unique and stable multiplicity node is created. Lemma 4. For configurations C(t0 ) ∈ {C21 , C31 }, the multiplicity node created in the Multiplicity Creation Phase enables every robot to distinguish the completion of the Line Formation Phase from the beginning of the Saturation Phase. Proof. By Lemma 2, at the completion of the Line Formation Phase, all robots occupy distinct nodes on the uniquely determined formation line L . The following cases are to be considered. Case 1. C(t0 ) ∈ C21 . By Lemma 2, the terminal configuration of the Line Formation Phase consists of all robots occupying distinct nodes on the formation line L . Furthermore, by Lemma 3, the Multiplicity Creation Phase creates a unique and stable multiplicity node NL . Since the robots have global strong multiplicity detection, every robot can determine whether a multiplicity node exists. Therefore, a configuration in which all robots lie on L and no multiplicity node is present is uniquely recognized as the terminal configuration of the Line Formation Phase. After the unique multiplicity node NL is created, every robot recognizes the resulting configuration as the initial configuration of the Saturation Phase. Hence, the completion of the Line Formation Phase is unambiguously distinguishable from the beginning of the Saturation Phase. Case 2. C(t0 ) ∈ C31 . By Lemma 2, the terminal configuration of the Line Formation Phase consists of all robots occupying distinct nodes on the formation line L . Furthermore, by Lemma 3, the Multiplicity Creation Phase creates a unique and stable multiplicity node Nc . Since the robots have global strong multiplicity detection, every robot can determine whether a multiplicity node exists. Therefore, a 43

configuration in which all robots lie on L and no multiplicity node is present is uniquely recognized as the terminal configuration of the Line Formation Phase. After the unique multiplicity node Nc is created, every robot recognizes the resulting configuration as the initial configuration of the Saturation Phase. Hence, the completion of the Line Formation Phase is unambiguously distinguishable from the beginning of the Saturation Phase. Hence, for both configuration classes, the unique multiplicity node enables every robot to distinguish the end of the Line Formation Phase from the beginning of the Saturation Phase. Lemma 5. For every configuration in which the Saturation Phase is executed, the procedure saturates every parking node to its prescribed capacity in finite time, without disturbing previously saturated parking nodes or creating unintended multiplicity nodes. Proof. We first establish that, in every case, the next parking node, symmetric pair of parking nodes, or rotational orbit of parking nodes to be saturated is uniquely determined. Case 1. C(t0 ) ∈ C1 . Since P is asymmetric, all parking nodes are uniquely ordered according to O1 . Hence, the next parking node to be saturated is uniquely determined. Case 2. C(t0 ) ∈ C21 . The parking nodes lying on the line of symmetry L are saturated first according to O2 . The remaining parking nodes are ordered by their Manhattan distance from the multiplicity node NL , with ties broken according to O2 . Hence, the next parking node or symmetric pair of parking nodes to be saturated is uniquely determined. Case 3. C(t0 ) ∈ C31 . If a parking node is located at the center of rotational symmetry c, it is saturated first. The remaining parking nodes are ordered by their Manhattan distance from the multiplicity node Nc , with ties broken according to O2 . Hence, the next parking node or rotational orbit of parking nodes to be saturated is uniquely determined. Case 4. C(t0 ) ∈ {C221 , C321 }. The prescribed symmetry-breaking operation transforms the configuration into an asymmetric configuration of type C21 or C31 , respectively. Therefore, the corresponding ordering established in Cases 2 and 3 applies uniquely. Case 5. C(t0 ) ∈ C222 . The Gathering Phase first creates the gathering node G on the line of symmetry L. The parking nodes are then considered in reflected pairs, and the ordering O4 uniquely selects the next pair to be saturated. Case 6. C(t0 ) ∈ C322 . The Gathering Phase first creates the gathering node G on ⌋. The parking nodes are grouped into rotational orbits about the center c, and the ordering O4 uniquely selects the next orbit to be saturated. Thus, in every configuration class, the next parking node, symmetric pair of parking nodes, or rotational orbit of parking nodes is uniquely determined. For each selected parking node p with prescribed capacity κ(p), the unsaturated robots are ordered by their Manhattan distance from p, with ties broken according to the prescribed ordering. Hence, the robots assigned to saturate p are uniquely determined. In symmetric configurations, the same rule is applied pairwise or orbit-wise, thereby preserving the required reflectional or rotational symmetry. Strong multiplicity detection allows every robot to determine when the occupancy of a parking node reaches its prescribed capacity. Once a parking node becomes saturated, it is never selected again, and the robots occupying it remain stationary. Therefore, previously saturated parking nodes remain unchanged. 44

P Define Φ(t) = p∈P max{0, κ(p) − occt (p)}, where occt (p) denotes the number of robots occupying the parking node p at time t. Since the number of parking nodes is finite, Φ(t) is a finite nonnegative integer. Whenever a selected robot reaches an unsaturated parking node, the occupancy of that node increases by one, and hence Φ(t) decreases by one. By Lemma 1, every selected robot reaches its assigned destination after finitely many hops without creating any undesired collision or unintended multiplicity node. Therefore, Φ(t) eventually reaches zero. Consequently, every parking node attains its prescribed capacity after finitely many movements, previously saturated parking nodes remain unchanged, and no unintended multiplicity node is created. Lemma 6. For every solvable configuration, the Gathering Phase gathers all surplus robots at a uniquely identifiable gathering node in finite time, without disturbing saturated parking nodes. Proof. We first establish that the gathering node is uniquely determined. Case 1. C(t0 ) ∈ C1 . Since P is asymmetric, the leading corner Kp of MERP and the corresponding string direction are uniquely determined. Hence, the node G adjacent to Kp and lying outside MERP is uniquely determined. Case 2. C(t0 ) ∈ C21 . The gathering node is the unique multiplicity node NL created during the Multiplicity Creation Phase. Case 3. C(t0 ) ∈ C31 . The gathering node is the unique multiplicity node Nc created during the Multiplicity Creation Phase. Case 4. C(t0 ) ∈ {C221 , C321 }. The prescribed symmetry-breaking operation transforms the configuration into one of type C21 or C31 , respectively. Hence, by Cases 2 and 3, the gathering node is uniquely determined. Case 5. C(t0 ) ∈ C222 . The gathering node G is selected on the line of symmetry L using the closest symmetric pair of surplus robots, with ties broken according to O4 . Hence, G is uniquely determined. Case 6. C(t0 ) ∈ C322 . The gathering node is the uniquely determined as the center of rotational symmetry c. Thus, in every configuration class, the gathering node is uniquely determined. Only surplus robots participate in the Gathering Phase. Robots already occupying saturated parking nodes are never selected and therefore remain stationary. Hence, previously saturated parking nodes remain unchanged. The surplus robots are ordered by their Manhattan distance from the gathering node, with ties broken according to the ordering O4 . Consequently, the next surplus robot, symmetric pair of surplus robots, or rotational orbit of surplus robots is uniquely determined. In symmetric configurations, the robots move in reflected pairs or rotational orbits, while pending movements are handled by allowing the corresponding paired or orbit robots to wait until symmetry is restored. Therefore, the required symmetry is preserved throughout the gathering process. Let G denote the gathering node and define Ψ(t) = |{ri ∈ Rs (t) : ri ̸= G }| . Since the number of surplus robots is finite, Ψ(t) is a finite nonnegative integer. Whenever a selected surplus robot reaches G , it remains stationary, and Ψ(t) decreases by one. In reflection-symmetric configurations, Ψ(t) decreases by two, whereas in rotationally symmetric configurations it decreases by the size of the selected rotational orbit. By Lemma 1, every selected surplus robot reaches G after finitely many hops without creating any undesired collision or unintended multiplicity node. Therefore, Ψ(t) eventually reaches zero. Consequently, after finitely many movements, all surplus robots are gathered at the uniquely determined gathering node G , while previously saturated parking nodes remain unchanged. 45

Theorem 6. For every solvable initial configuration, the algorithm spg() correctly solves the surplus parking gathering problem. Proof. We consider each solvable configuration class separately. The following cases are to be considered. Case 1. C(t0 ) ∈ C1 . The algorithm first executes the Saturation Phase. By Lemma 5, every parking node is saturated to its prescribed capacity. The algorithm then executes the Gathering Phase. By Lemma 6, all surplus robots gather at the uniquely determined gathering node. Case 2. C(t0 ) ∈ C21 . The algorithm first executes the Line Formation Phase. By Lemma 2, all robots occupy distinct nodes on the uniquely determined formation line. Next, the Multiplicity Creation Phase creates a unique and stable multiplicity node by Lemma 3. The algorithm then executes the Saturation Phase, which correctly saturates every parking node by Lemma 5. Finally, the Gathering Phase gathers all surplus robots at the gathering node by Lemma 6. Case 3. C(t0 ) ∈ C31 . The proof is identical to Case 2. The Line Formation Phase, Multiplicity Creation Phase, Saturation Phase, and Gathering Phase are executed sequentially, and their correctness follows from Lemmas 2, 3, 5, and 6, respectively. Case 4. C(t0 ) ∈ {C221 , C321 }. The prescribed symmetry-breaking operation first transforms the configuration into one of type C21 or C31 , respectively. Therefore, the correctness follows directly from Cases 2 and 3. Case 5. C(t0 ) ∈ C222 . The algorithm first executes the Gathering Phase. By Lemma 6, all surplus robots gather at the selected gathering node while preserving the required reflectional symmetry. The algorithm then executes the Saturation Phase, which saturates every parking node to its prescribed capacity by Lemma 5. Case 6. C(t0 ) ∈ C322 . The algorithm first executes the Gathering Phase. By Lemma 6, all surplus robots gather at the selected gathering node while preserving the required rotational symmetry. The algorithm then executes the Saturation Phase, which saturates every parking node to its prescribed capacity by Lemma 5. Since each phase decreases its associated progress measure and terminates after finitely many robot movements, the algorithm cannot deadlock before reaching the final configuration. Therefore, for every solvable configuration class, the algorithm terminates after finitely many movements and reaches a configuration in which every parking node is saturated to its prescribed capacity and all surplus robots are gathered at the uniquely determined gathering node. Moreover, by Lemma 1, the required symmetry is preserved throughout the execution, and no undesired collision or unintended multiplicity node is created. Hence, spg() correctly solves the surplus parking gathering problem for every solvable initial configuration.

6

Move Complexity of the Algorithm

In this section we analyze the efficiency of the algorithm spg() in terms of the total number of hop-moves performed by all robots (move complexity). Throughout, let a, b denote the side lengths of MERC (t0 ), and writePD = a + b. Recall that n is the total number of robots, m the number of parking nodes, and s=n− m i=1 κi the number of surplus robots.

46

6.1

Upper Bound

Theorem 7. The algorithm spg() has move complexity O n(a + b) + n2 , where a and b denote the side lengths of the initial minimum enclosing rectangle MERC (t0 ). Proof. Let D = a + b, which is an upper bound on the Manhattan diameter of MERC (t0 ). We analyze the move complexity of each phase separately. Throughout the execution, the procedure MoveToDestination() routes every selected robot (or symmetric pair or rotational orbit) along a shortest Manhattan path. Line Formation Phase. Each robot first reaches the formation line L from its initial position. Since L is constructed inside MERC (t0 ) or at a constant offset from it, this requires at most O(D) moves per robot, contributing O(nD) moves in total. To place all robots on distinct consecutive nodes of L , the occupied segment of the line may P grow to length O(n). Consequently, the cumulative displacement 2 2 of the robots along L is bounded by n−1 i=0 O(i) = O(n ). Hence, MLF = O(nD + n ). Multiplicity Creation Phase. Only O(1) robots move to create the multiplicity node, each over a shortest path of length at most O(D + n). Therefore, MMC = O(D + n). Saturation Phase. Exactly n − s robots move from the formation line to their assigned parking nodes. Since every parking node lies inside MERP ⊆ MERC (t0 ), each robot traverses at most O(D + n) edges. Therefore, MSat = O((n − s)(D + n)) = O(nD + n2 ). Gathering Phase. The remaining s surplus robots move from the formation line to the gathering node G . Each movement has length at most O(D + n), yielding MGath = O(s(D + n)) = O(nD + n2 ). Summing the contributions of the four phases, M = MLF + MMC + MSat + MGath = O(nD + n2 ) + O(D + n) + O(nD + n2 ) + O(nD + n2 ) = O(nD + n2 ). Since D = a + b, the overall move complexity is
O n(a + b) + n2 . Theorem 8. In the worst case, any algorithm solving the SPG problem requires Ω(n(a + b)) robot moves. Proof. Let D = a + b denote the Manhattan diameter of the initial minimum enclosing rectangle MERC (t0 ). Consider the family of instances illustrated in Figure 14, in which all n robots are initially clustered in a small neighborhood of one corner of MERC (t0 ), whereas all parking nodes are clustered near the opposite corner. The parking capacities are chosen such that n − s = Θ(n) robots must eventually occupy parking nodes. Such an instance is valid since the parking-node locations and capacities are specified as part of the input. The Manhattan distance between the two clusters is Θ(D) = Θ(a + b). Consequently, every one of the n − s = Θ(n) parking-bound robots must traverse at least Θ(D) edges before reaching its assigned parking node, regardless of the algorithm used. Hence every correct algorithm performs at least (n − s) · Θ(D) = Θ(n) · Θ(D) = Ω(nD) robot moves. Substituting D = a + b yields the desired lower bound Ω(n(a + b)). Remark 1. The above results establish a worst-case upper bound of O(n(a + b) + n2 ) and a general lower bound of Ω(n(a + b)). The gap between these bounds remains open. The additional n2 term arises from the line-formation strategy employed by spg(). Whether this term can be eliminated by designing a more efficient distributed algorithm, or whether a stronger lower bound can be established for the SPG problem, remains an interesting direction for future research.

47

Figure 14: An illustration of the worst-case instance used in the proof of Theorem 8. The robots are initially clustered near one corner of the minimum enclosing rectangle, while all parking nodes are located near the opposite corner. The capacities of the parking nodes p1 , p2 , p3 , and p4 are 2, 1, 1, and 1, respectively. Since Θ(n) robots must each travel a Manhattan distance of Θ(a + b) to reach their assigned parking nodes, every correct algorithm requires Ω(n(a + b)) robot moves.

7

Conclusion and Future Work

In this paper, we introduced the mathcalSP G problem, a new coordination problem for mobile robots deployed on the nodes of an infinite grid. Unlike the classical parking and gathering problems, SPG simultaneously requires every designated parking node to be saturated according to its prescribed capacity while all remaining surplus robots gather at a common grid node determined autonomously during the execution. We considered anonymous, oblivious, disoriented, and silent robots operating under the asynchronous model with global visibility and global strong multiplicity detection. We first characterized the initial configurations from which SPG is deterministically unsolvable. For every remaining solvable configuration, we presented a deterministic distributed algorithm that correctly solves the problem. We proved that the algorithm is collision-free and terminates in finite time. Upon termination, every parking node is occupied according to its prescribed capacity, and all surplus robots are gathered at a uniquely determined gathering node. Several interesting directions remain for future research. One natural extension is to study the case where the total number of robots is smaller than the total parking capacity. In this setting, an interesting objective is to maximize the number of saturated parking nodes. Another direction is to design algorithms that optimize movement complexity, for example by minimizing the total distance traveled by all robots or the maximum distance traveled by any individual robot. Another interesting direction for future work is to investigate whether the current upper bound can be improved, or whether a matching lower bound can be established for the SPG problem. Finally, extending the problem to other graph classes, such as trees, rings, and general graphs, or investigating fault-tolerant variants in the presence of robot failures, constitutes promising directions for future research.

48

References [1] Ranendu Adhikary, Kaustav Bose, Manash Kumar Kundu, and Buddhadeb Sau. Mutual visibility on grid by asynchronous luminous robots. Theoretical Computer Science, 922:218–247, 2022. [2] Dario Albani, Joris Ijsselmuiden, Ramon Haken, and Vito Trianni. Monitoring and mapping with robot swarms for agricultural applications. pages 1–6, 08 2017. [3] Roberto Baldoni, François Bonnet, Alessia Milani, and Michel Raynal. Anonymous graph exploration without collision by mobile robots. Information Processing Letters, 2008. [4] Subhash Bhagat, Abhinav Chakraborty, Bibhuti Das, and Krishnendu Mukhopadhyaya. Gathering over meeting nodes in infinite grid. Fundamenta Informaticae, 187(1):1–30, 2022. [5] Subhash Bhagat, Abhinav Chakraborty, Bibhuti Das, and Krishnendu Mukhopadhyaya. Optimal gathering over weber meeting nodes in infinite grid. Int. J. Found. Comput. Sci., 34(1):25–49, 2023. [6] Subhash Bhagat, Bibhuti Das, Abhinav Chakraborty, and Krishnendu Mukhopadhyaya. k-circle formation and k-epf by asynchronous robots. Algorithms, 14(2):62, 2021. [7] Kaustav Bose, Ranendu Adhikary, Manash Kumar Kundu, and Buddhadeb Sau. Arbitrary pattern formation on infinite grid by asynchronous oblivious robots. Theoretical Computer Science, 815:213– 227, 2020. [8] Abhinav Chakraborty, Subhash Bhagat, and Krishnendu Mukhopadhyaya. Gathering over heterogeneous meeting nodes. The Computer Journal, 67(5):1794–1813, 2024. [9] Abhinav Chakraborty and Krishnendu Mukhopadhyaya. Parking problem by oblivious mobile robots in infinite grids. Theoretical Computer Science, 1023:114953, 2025. [10] Serafino Cicerone, Alessia Di Fonso, Gabriele Di Stefano, and Alfredo Navarra. Arbitrary pattern formation on infinite regular tessellation graphs. Theoretical Computer Science, 942:1–20, 2023. [11] Serafino Cicerone, Gabriele Di Stefano, and Alfredo Navarra. Asynchronous arbitrary pattern formation: the effects of a rigorous approach. Distrib. Comput., 32(2):91–132, April 2019. [12] Serafino Cicerone, Gabriele Di Stefano, and Alfredo Navarra. Embedded pattern formation by asynchronous robots without chirality. Distributed Comput., 32(4):291–315, 2019. [13] Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Solving the robots gathering problem. In Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, and Gerhard J. Woeginger, editors, Automata, Languages and Programming, pages 1181–1196, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg. [14] Reuven Cohen and David Peleg. Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM Journal on Computing, 34(6):1516–1528, 2005. [15] Gianlorenzo d’Angelo, Gabriele Di Stefano, Ralf Klasing, and Alfredo Navarra. Gathering of robots on anonymous grids and trees without multiplicity detection. Theoretical Computer Science, 610:158–168, 2016. [16] Bibhuti Das, Abhinav Chakraborty, Subhash Bhagat, and Krishnendu Mukhopadhyaya. k -circle formation by disoriented asynchronous robots. Theor. Comput. Sci., 916:40–61, 2022. [17] Gabriele Di Stefano and Alfredo Navarra. Gathering of oblivious robots on infinite grids with minimum traveled distance. Information and Computation, 254:377–391, 2017. SSS 2014.

49

[18] Asaf Efrima and David Peleg. Distributed algorithms for partitioning a swarm of autonomous mobile robots. pages 180–194, 01 2007. [19] P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Gathering of asynchronous robots with limited visibility. Theoretical Computer Science, 337(1-3):147 – 168, 2005. [20] Paola Flocchini, David Ilcinkas, Andrzej Pelc, and Nicola Santoro. Computing without communicating: Ring exploration by asynchronous oblivious robots. In Principles of Distributed Systems: 11th International Conference, OPODIS 2007, Guadeloupe, French West Indies, December 17-20, 2007. Proceedings, page 105–118, Berlin, Heidelberg, 2007. Springer-Verlag. [21] Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer. Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. Theoretical Computer Science, 407(1):412–447, 2008. [22] Nao Fujinaga, Hirotaka Ono, Shuji Kijima, and Masafumi Yamashita. Pattern formation through optimum matching by oblivious corda robots. In Chenyang Lu, Toshimitsu Masuzawa, and Mohamed Mosbah, editors, Principles of Distributed Systems, pages 1–15, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. [23] Pritam Goswami, Avisek Sharma, Satakshi Ghosh, and Buddhadeb Sau. Time optimal gathering of myopic robots on an infinite triangular grid. Theoretical Computer Science, 1023:114930, 2025. [24] Rory Hector, Ramachandran Vaidyanathan, Gokarna Sharma, and Jerry L. Trahan. Optimal Convex Hull Formation on a Grid by Asynchronous Robots With Lights . IEEE Transactions on Parallel & Distributed Systems, 33(12):3532–3545, December 2022. [25] R. Klasing, E. Markou, and A. Pelc. Gathering asynchronous oblivious mobile robots in a ring. Theoretical Computer Science, 390(1):27–39, 2008. [26] Giuseppe Antonio Di Luna, Paola Flocchini, Sruti Gan Chaudhuri, Federico Poloni, Nicola Santoro, and Giovanni Viglietta. Mutual visibility by luminous robots without collisions. Inf. Comput., 254:392–418, 2017. [27] Debasish Pattanayak, Kaushik Mondal, Ramesh H., and Partha Sarathi Mandal. Gathering of mobile robots with weak multiplicity detection in presence of crash-faults. Journal of Parallel and Distributed Computing, 123:145–155, 2019. [28] Masahiro Shibata, Masaki Ohyabu, Yuichi Sudo, Junya Nakamura, Yonghwan Kim, and Yoshiaki Katayama. Gathering of seven autonomous mobile robots on triangular grids. In IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPS Workshops 2021, Portland, OR, USA, June 17-21, 2021, pages 566–575. IEEE, 2021. [29] Daniel Stormont. Autonomous rescue robot swarms for first responders. pages 151 – 157, 01 2005. [30] Kazuo Sugihara and Ichiro Suzuki. Distributed algorithms for formation of geometric patterns with many mobile robots. J. Field Robotics, 13:127–139, 1996. [31] Ichiro Suzuki and Masafumi Yamashita. Distributed anonymous mobile robots: Formation of geometric patterns. SIAM Journal on Computing, 28(4):1347–1363, 1999.

50