Paper deep dive
When Robots Crash: Optimal Asynchronous Gathering at Weber Meeting Nodes
Animesh Maiti, Prakhar Shukla, Abhinav Chakraborty, Subhash Bhagat
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 10/7/2026, 7:43:33 AM
Summary
This paper addresses the optimal gathering problem for asynchronous, anonymous, and oblivious mobile robots on an infinite grid with crash faults. The objective is to gather all non-faulty robots at a Weber Meeting Node, which minimizes the total Manhattan distance from initial positions. The authors propose the CrashTolerantWeberGathering() algorithm, which handles up to n-2 crash faults. They prove that strong multiplicity detection is necessary and that optimal gathering is impossible from certain fully symmetric configurations. The algorithm ensures that non-faulty robots select a unique common target and gather in finite time without waiting for crashed robots.
Entities (8)
Relation Signals (6)
CrashTolerantWeberGathering → targets → Weber Meeting Node
confidence 98% · our algorithm CrashTolerantWeberGathering() selects a unique common target... gather all non-faulty robots at a Weber Meeting Node
CrashTolerantWeberGathering → tolerates → Crash Fault
confidence 97% · Up to n-2 robots may crash permanently... our algorithm... guarantee gathering in finite time despite up to n-2 crash faults
CrashTolerantWeberGathering → requires → Strong Multiplicity Detection
confidence 96% · We prove that, under strong multiplicity detection, optimal gathering is impossible from certain fully symmetric configurations... strong multiplicity detection is necessary
CrashTolerantWeberGathering → operateson → Infinite Grid
confidence 95% · mobile robots on an infinite grid under crash faults
Weber Meeting Node → minimizes → Manhattan Distance
confidence 93% · Weber Meeting Node, that is, a meeting node minimizing the total Manhattan distance from the initial robot positions
Symmetry → prevents → Optimal Gathering
confidence 92% · optimal gathering is impossible from certain fully symmetric configurations
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study the \textit{optimal gathering} problem over a finite set of designated \textit{meeting nodes} for \textit{asynchronous, anonymous,} and \textit{oblivious} mobile robots on an infinite grid under crash faults. The robots have global visibility and strong multiplicity detection, but share neither a coordinate system nor chirality. The objective is to gather all non-faulty robots at a \textsc{Weber Meeting Node}, minimizing the total Manhattan distance from their initial positions. Up to $n-2$ robots may crash permanently, and such crashes are indistinguishable from arbitrary delays. Existing approaches often rely on a designated robot to break symmetry, whose crash may block the remaining robots indefinitely. Instead, our approach enables every robot to independently select the same target from its snapshot, while target-dependent restricted shortest paths preserve the target as a \textsc{Weber Meeting Node}. We prove that, under strong multiplicity detection, optimal gathering is impossible from certain fully symmetric configurations. For all remaining configurations, our algorithm \textsc{CrashTolerantWeberGathering()} selects a unique common target, preserves its optimality throughout the execution, and allows non-faulty robots to progress without waiting for crashed robots, thereby guaranteeing gathering in finite time.
Tags
Links
- Source: https://arxiv.org/abs/2610.06939v1
- Canonical: https://arxiv.org/abs/2610.06939v1
Trouble viewing inline? Open PDF directly →
Full Text
126,706 characters extracted from source content.
Expand or collapse full text
When Robots Crash: Optimal Asynchronous Gathering at Weber Meeting Nodes Animesh Maiti †thanks: Corresponding author. Affiliation: Department of Mathematics, Indian Institute of Technology Jodhpur, Jodhpur, Rajasthan, India E-mail p22ma201@iitj.ac.in, p23ma0011@iitj.ac.in, sbhagat@iitj.ac.in Prakhar Shukla Affiliation: Department of Mathematics, Indian Institute of Technology Jodhpur, Jodhpur, Rajasthan, India E-mail p22ma201@iitj.ac.in, p23ma0011@iitj.ac.in, sbhagat@iitj.ac.in Abhinav Chakraborty Affiliation: Department of Mathematics, Birla Institute of Technology Mesra, Ranchi, Jharkhand, India E-mail abhinavchakraborty@bitmesra.ac.in Subhash Bhagat Affiliation: Department of Mathematics, Indian Institute of Technology Jodhpur, Jodhpur, Rajasthan, India E-mail p22ma201@iitj.ac.in, p23ma0011@iitj.ac.in, sbhagat@iitj.ac.in Abstract We study the optimal gathering problem over a finite set of designated meeting nodes for asynchronous, anonymous, and oblivious mobile robots on an infinite grid under crash faults. The robots have global visibility and strong multiplicity detection, but share neither a coordinate system nor chirality. The objective is to gather all non-faulty robots at a Weber Meeting Node, minimizing the total Manhattan distance from their initial positions. Up to n−2n-2 robots may crash permanently, and such crashes are indistinguishable from arbitrary delays. Existing approaches often rely on a designated robot to break symmetry, whose crash may block the remaining robots indefinitely. Instead, our approach enables every robot to independently select the same target from its snapshot, while target-dependent restricted shortest paths preserve the target as a Weber Meeting Node. We prove that, under strong multiplicity detection, optimal gathering is impossible from certain fully symmetric configurations. For all remaining configurations, our algorithm CrashTolerantWeberGathering() selects a unique common target, preserves its optimality throughout the execution, and allows non-faulty robots to progress without waiting for crashed robots, thereby guaranteeing gathering in finite time. Keywords: Swarm Robotics Optimal gathering Weber Meeting Nodes Crash faults Infinite grid Asynchronous scheduler. 1 Introduction Background and motivation. Swarm robotics is inspired by the collective behaviour of social insects such as ants, bees, and termites. A robot swarm consists of several simple and inexpensive robots that work together, without centralized control or explicit communication, to perform tasks such as exploration, pattern formation, convergence, and gathering. The main question is how robots with limited computational capabilities can coordinate to achieve a common goal. In the classical distributed model, robots are autonomous (operate without centralized coordination), homogeneous (identical in capabilities and behaviour), anonymous (have no unique identifiers), oblivious (have no memory of past actions), and silent (do not communicate explicitly). Each robot executes the same deterministic algorithm and repeatedly performs a Look–Compute–Move (LCM) cycle: it observes the current configuration, computes a destination, and either remains stationary or moves toward that destination. The robots are disoriented and share neither a coordinate system nor chirality. We consider robots deployed on an infinite grid, where initially each robot occupies a distinct grid node and moves along grid edges. Movements are instantaneous, so robots are observed only at grid nodes. They have global visibility and strong global multiplicity detection; hence, they observe the complete configuration and know the exact number of robots at each occupied node. Every robot makes its decision only from the snapshot expressed in its local coordinate system. The grid contains a finite set of distinguished nodes, called meeting nodes, which may represent charging stations, communication points, maintenance facilities, or evacuation sites. In the gathering over meeting nodes problem, the robots must gather at one of these designated nodes rather than at an arbitrary grid node. For optimal gathering, the destination must be a Weber Meeting Node, that is, a meeting node minimizing the total Manhattan distance from the initial robot positions. The robots operate under a fair asynchronous (ASYNC) scheduler, which activates every non-faulty robot infinitely often. They have no common notion of time, and their Look, Compute, and Move phases may take unpredictable amounts of time. Up to n−2n-2 robots may crash permanently. A crashed robot stops executing its LCM cycles but remains visible at its last position. Since a crash is indistinguishable from an arbitrary delay, the non-faulty robots cannot rely on the future movement of any particular robot. We characterize the initial configurations from which crash-tolerant optimal gathering is possible and give a deterministic algorithm that gathers all non-faulty robots at the same Weber Meeting Node without waiting for any other robot. Related work. Gathering has been studied in the continuous plane under different assumptions on visibility, multiplicity detection, orientation, and activation schedules [26, 19], and in discrete environments such as rings, trees, grids, and hypercubes [24, 16, 22, 15, 6]. For rings, impossibility and algorithmic results under different forms of multiplicity detection were given in [24, 17, 23]. Gatherable configurations on finite grids and trees were characterized in [15]. Problems with prescribed destinations include landmark covering [20], embedded pattern formation [11], and gathering over meeting points [10]. Bhagat et al. [2] studied gathering over meeting nodes on an infinite grid in the fault-free setting. Fault-tolerant gathering has been studied in the plane [1, 13, 8, 21, 4] and on graphs under different faults [7, 9, 18, 12]. Pelc [25] considered labeled agents with memory and communication, while Bose et al. [5] considered anonymous robots on finite grids with at most one crash. In contrast, we study crash-tolerant optimal gathering over a finite set of designated meeting nodes on an infinite grid, where the gathering destination must be a Weber Meeting Node. Our model allows up to n−2n-2 permanent crash faults, which are indistinguishable from arbitrary activation delays, and therefore does not permit the robots to rely on the future movement of any particular robot. Our contributions. Our main contributions to crash-tolerant optimal gathering at Weber Meeting Nodes are as follows: • We prove that weak multiplicity detection is insufficient for optimal Weber-meeting-node gathering in the presence of up to n−2n-2 crash faults, even under a fully synchronous (FSYNC) scheduler, where all non-faulty robots are activated simultaneously in each round and execute their Look–Compute–Move cycles synchronously. Thus, strong multiplicity detection is necessary. • We characterize reflectionally and rotationally symmetric configurations for which optimal gathering becomes impossible when robots occupying symmetry-breaking positions crash. • For every remaining configuration, we give a deterministic algorithm that selects a unique Weber Meeting Node without relying on the movement of any distinguished robot. • We introduce target-dependent restricted shortest paths and prove that they preserve the selected region and the target Weber Meeting Node throughout the execution. This guarantees that all non-faulty robots gather at the selected target in finite time despite up to n−2n-2 crash faults. Terminology and notation. We use the infinite-grid model and basic terminology of [3]. Let =(,ℰ)G=(V,E) denote the infinite square grid, ℳ=m1,…,ms⊂M=\m_1,…,m_s\ the finite set of meeting nodes, and ℛ(t)=r1(t),…,rn(t)R(t)=\r_1(t),…,r_n(t)\ the multiset of robot positions at time t. The entire configuration is ℐ(t)=(ℛ(t),ℳ)I(t)=(R(t),M), with initial time t0t_0. For u,v∈u,v , let d(u,v)d(u,v) denote their Manhattan distance, and let λt(v) _t(v) denote the number of robots occupying v at time t. Initially, λt0(v)≤1 _t_0(v)≤ 1 for every v∈v . For each m∈ℳm , define ct(m)=∑v∈d(v,m)λt(v)c_t(m)= _v d(v,m) _t(v) and (t)=argminm∈ℳct(m)W(t)= _m c_t(m). The nodes in (t)W(t) are called Weber Meeting Nodes. We classify configurations using the reflectional and rotational symmetries of ℳM and ℐ(t)I(t). Throughout the paper, we also use traversal strings Γ , pivot corners, Candidate Weber sets, canonical traversal strings α, anchor corners aK_a, and balanced or unbalanced regions in our target-selection and movement rules. Due to page constraints, the formal definitions of grid deployment and symmetry, the complete traversal conventions, an illustrative computation, and the required Weber-node invariance property are provided in the APPENDIX. Problem Definition. Let f≤n−2f≤ n-2 denote an upper bound on the number of crash faults that the algorithm can tolerate. For a given execution, let ℱ⊆ℛF denote the set of robots that crash during the execution, where |ℱ|≤f|F|≤ f. The set of non-faulty robots is denoted by ℛnf=ℛ∖ℱ.R_nf=R . Consequently, |ℛnf|=n−|ℱ|≥2.|R_nf|=n-|F|≥ 2. A crashed robot remains permanently stationary at the node where it crashes. The crash-tolerant gathering over Weber Meeting Nodes problem requires all non-faulty robots to gather at a common Weber Meeting Node of the initial configuration. More precisely, an execution starting from ℐ(t0)I(t_0) is successful if there exist a finite time T and a meeting node, say m†∈(t0)m (t_0) such that pr(t)=m†,for every r∈ℛnf and every t≥T.p_r(t)=m ,\ \ for every r _nf and every t≥ T. The crashed robots are not required to reach m†m . Partition of the Initial Configuration. Let ℐ(t0)=(ℛ(t0),ℳ)I(t_0)=(R(t_0),M) be an initial configuration, (t0)W(t_0) the set of Weber Meeting Nodes, and c(t0)W_c(t_0) the set of Candidate Weber Meeting Nodes. We partition all initial configurations into the following mutually exclusive and exhaustive classes. ℐ1I_1: The configuration admits a unique Weber Meeting Node; that is, |(t0)|=1.|W(t_0)|=1. ℐ2I_2: The meeting-node configuration ℳM is asymmetric and admits multiple Weber Meeting Nodes; namely, |(t0)|≥2.|W(t_0)|≥ 2. In this case, there exists a unique Candidate Weber Meeting Node, i.e.,|c(t0)|=1.|W_c(t_0)|=1. ℐ3I_3: The meeting-node configuration ℳM admits a unique line of symmetry ℒL and multiple Weber Meeting Nodes; namely, |(t0)|≥2.|W(t_0)|≥ 2. Moreover, the initial robot configuration ℛ(t0)R(t_0) is asymmetric. The following subclasses are distinguished. (a) ℐ31I_31: At least one Weber Meeting Node lies on the symmetry line ℒL; that is, (t0)∩ℒ≠∅.W(t_0) ≠ . This class is further partitioned as follows. (a.1) ℐ311I_311: If the symmetry line ℒL is horizontal or vertical, then exactly one Candidate Weber Meeting Node exists, i.e., |c(t0)|=1.|W_c(t_0)|=1. (a.2) ℐ312I_312: The symmetry line ℒL is diagonal. In this case, either one or two Candidate Weber Meeting Nodes exist; that is, |c(t0)|∈1,2.|W_c(t_0)|∈\1,2\. (b) ℐ32I_32: No Weber Meeting Node lies on the symmetry line ℒL, and exactly two Candidate Weber Meeting Nodes exist; that is, (t0)∩ℒ=∅W(t_0) = and |c(t0)|=2.|W_c(t_0)|=2. This class is further partitioned as follows. (b.1) ℐ321I_321: The symmetry line ℒL is horizontal or vertical. (b.2) ℐ322I_322: The symmetry line ℒL is diagonal, and the configuration admits a unique pivot corner. (b.3) ℐ323I_323: The symmetry line ℒL is diagonal, and the configuration admits two pivot corners. ℐ4I_4: The meeting-node configuration ℳM admits a nontrivial rotational symmetry with center c and multiple Weber Meeting Nodes; namely, |(t0)|≥2.|W(t_0)|≥ 2. The initial robot configuration ℛ(t0)R(t_0) is asymmetric. This class is further divided into the following subclasses. (a) ℐ41I_41: The center of rotation is itself a Weber Meeting Node; that is, c∈(t0).c (t_0). (b) ℐ42I_42: The center of rotation is not a Weber Meeting Node, and there exist at least two Candidate Weber Meeting Nodes; namely, c∉(t0)c (t_0) and |c(t0)|≥2.|W_c(t_0)|≥ 2. This class is further partitioned as follows. (b.1) ℐ421I_421: At least one Candidate Weber Meeting Node lies in an open quadrant; that is, c(t0)∩(⋃i=14i)≠∅.W_c(t_0)∩ ( _i=1^4Q_i )≠ . This class is further partitioned as follows. (b.1.1) ℐ4211I_4211: There exists a unique quadrant that contains the maximum number of Candidate Weber Meeting Nodes; that is, writing μk=|c(t0)∩k| _k=|W_c(t_0) _k| and μmax=maxkμkμ = _k _k, |k:μk=μmax|=1. |k: _k=μ |=1. (b.1.2) ℐ4212I_4212: There exist multiple quadrants that contain the maximum number of Candidate Weber Meeting Nodes; that is, :=k:μk=μmax,||≥2.S:=k: _k=μ ,|S|≥ 2. This class is further partitioned as follows. (b.1.2.1) ℐ42121I_42121: The configuration is unbalanced: a unique quadrant in S attains νmaxν _S; that is, |k∈:νk=νmax|=1. |k : _k=ν _S |=1. (b.1.2.2) ℐ42122I_42122: The configuration is balanced: it is not unbalanced; that is, |k∈:νk=νmax|≥2. |k : _k=ν _S |≥ 2. (b.2) ℐ422I_422: No Candidate Weber Meeting Node lies in any open quadrant; that is, c(t0)∩(⋃i=14i)=∅.W_c(t_0)∩ ( _i=1^4Q_i )= . This class is further partitioned as follows. (b.2.1) ℐ4221I_4221: The configuration is unbalanced: a unique quadrant attains νmaxν ; that is, |k:νk=νmax|=1 |k: _k=ν |=1. (b.2.2) ℐ4222I_4222: The configuration is balanced: |k:νk=νmax|≥2 |k: _k=ν |≥ 2. Let ℐ(t0)I(t_0) denote the set of all initial configurations. Note that the classes and subclasses defined above form a partition of ℐ(t0)I(t_0). Since every robot has global visibility of the initial configuration ℐ(t0)I(t_0), all robots uniquely identify the same class and subclass during their Look phase. Hence, no ambiguity or conflict arises in the classification. 2 Impossibility Results The impossibility results are based on a common geometric obstruction: robots occupying symmetric positions cannot deterministically break the symmetry when no admissible gathering node is fixed by that symmetry [3]. Impossibility inherited from the crash-free setting. The partitive-symmetry results of [3] imply that gathering is impossible from any symmetric initial configuration in which the fixed part of the symmetry contains no admissible target. In particular, this includes reflectionally symmetric configurations whose symmetry line contains no meeting node, and rotationally symmetric configurations whose center is not a meeting node. For optimal gathering, the same conclusion holds when the fixed part contains no Weber Meeting Node. These results remain valid in our model because every crash-free execution is an admissible execution when up to n−2n-2 robots may crash. Theorem 2.1 (Crash-induced symmetry impossibility) No deterministic algorithm can guarantee gathering at a meeting node in any of the following cases: (i) ℐ(t0)I(t_0) is reflectionally symmetric about a line ℒL, ℳ∩ℒ=∅M = , and all robots initially on ℒL crash before moving; (i) ℐ(t0)I(t_0) is rotationally symmetric about a grid node c∉ℳc , and the robot initially at c crashes before moving; or (i) ℐ(t0)I(t_0) is rotationally symmetric about c∉ℳc , and all robots initially on two invariant perpendicular grid lines through c crash before moving. In each case, at least one complete nontrivial symmetry orbit outside the crashed set remains non-faulty. Consequently, gathering at a Weber Meeting Node is also impossible. Theorem 2.2 (Impossibility under weak multiplicity detection) No deterministic distributed algorithm equipped only with global weak multiplicity detection can solve optimal Weber-meeting-node gathering in the presence of up to n−2n-2 crash faults, even under FSYNC activation and rigid movement. In the FSYNC model, all non-crashed agents are activated synchronously in each round. Thus, in every round, each non-crashed agent performs a complete Look–Compute–Move cycle, and all agents observe the same global configuration before making their moves. The complete proofs of these two theorems are given in the APPENDIX. Therefore, global strong multiplicity detection is necessary, even under FSYNC activation and rigid movement. Let I be the set of all initial configurations and let ⊆U contain the configurations excluded by the preceding impossibility results. The proposed algorithm is therefore defined for every initial configuration ℐ(t0)∈∖I(t_0) . 3 Algorithm CrashTolerantWeberGathering() High-Level Idea of the Algorithm. The algorithm consists of two phases: Target Selection and Crash-Tolerant Directed Gathering. Upon activation, a robot observes the current configuration and identifies the applicable configuration class from the symmetry of ℳM and the robot positions. In the first phase, the robot either selects a common target Weber Meeting Node m†m directly or first determines a target region. Direct selection applies when ℳM is asymmetric, when c∈ℳc is the unique Weber Meeting Node, or when a suitable candidate Weber Meeting Node lies on the symmetry line ℒL. In the remaining symmetric cases, the prescribed occupancy and tie-breaking rules determine either a target half-plane ℬ†B or a target quadrant †Q . In the rotational case, the selected region is †∪ℒ1++∪ℒ2++Q _1^++ _2^++, where ℒ1++L_1^++ and ℒ2++L_2^++ bound †Q . A unique node m†m associated with the selected region is then chosen. In the second phase, every non-faulty robot executes either Direct Gathering or Transfer Plane. Under Direct Gathering, the robot invokes MoveToDestination() to move toward m†m . This applies when m†m is selected directly and also when m†∈ℒ1++∪ℒ2++m _1^++ _2^++. Under Transfer Plane, a robot first moves into ℬ†B in the unique-reflection case or into †Q in the rotational case, and then invokes MoveToDestination() to proceed toward m†m . The overall structure of the algorithm is illustrated in Figure 1. 3.1 Phase I: Target Selection In this phase, every robot selects a common target Weber Meeting Node m†m , either directly or, when required by symmetry, after first determining a target half-plane or quadrant. No-region Target Weber Meeting Node Selection: For the configurations considered in this subsection, a unique target Weber Meeting Node can be determined directly. Hence, neither a target half-plane nor a target quadrant needs to be selected. The target Weber meeting node m†m is determined according to one of the following cases. Configuration ℐ1I_1: The configuration admits a unique Weber Meeting Node, i.e., |(t0)|=1|W(t_0)|=1. Every robot deterministically identifies this node and selects it as m†m . Figure 1: Overview of the two phases of the CrashTolerantWeberGathering() algorithm. Configuration ℐ2I_2: The meeting-node configuration ℳM is asymmetric and admits multiple Weber Meeting Nodes, i.e., |(t0)|≥2|W(t_0)|≥ 2. The unique canonical traversal determined by ℰℛℳSER_M induces a canonical ordering of the meeting nodes; the node ranked highest in this ordering is uniquely selected as m†m . Configuration ℐ311I_311: At least one Weber Meeting Node lies on the symmetry line ℒL, i.e., (t0)∩ℒ≠∅.W(t_0) ≠ . Moreover, the symmetry line ℒL is horizontal or vertical, and there exists exactly one Candidate Weber Meeting Node, i.e., |c(t0)|=1.|W_c(t_0)|=1. This unique candidate node is selected as m†m . Since m†m lies on ℒL, it remains invariant under reflection, and hence every robot independently identifies the same target meeting node. Configuration ℐ312I_312: The symmetry line ℒL is diagonal. In this case, either one or two Candidate Weber Meeting Nodes exist; that is, |c(t0)|∈1,2.|W_c(t_0)|∈\1,2\. Accordingly, the following two cases arise: If |c(t0)|=1|W_c(t_0)|=1, then the unique Candidate Weber Meeting Node is selected as the target Weber Meeting Node m†m . If |c(t0)|=2|W_c(t_0)|=2, and since the entire configuration ℐ(t0)I(t_0) is asymmetric, then the Candidate Weber Meeting Node at the last position of the unique canonical traversal string from the anchor corner is selected as the target Weber Meeting Node m†m . In this configuration, where |c(t0)|=2|W_c(t_0)|=2, the ambiguity between the two candidates is resolved once at least one of the two or more non-faulty robots moves toward m†m . Consequently, the number of candidate Weber Meeting Nodes is reduced to one, i.e., |c(t)|=1|W_c(t)|=1. Configuration ℐ41I_41: The meeting-node configuration ℳM admits a nontrivial rotational symmetry with center c, and the center of rotation is itself the unique Weber Meeting Node, i.e., c∈(t0)c (t_0). Since c is invariant under the rotational symmetry, every robot deterministically selects m†=c.m =c. Half-plane and Target Weber Meeting Selection(Reflection): Suppose that the meeting-node configuration admits a unique line of symmetry ℒL. The line ℒL divides the grid, excluding the nodes on ℒL, into two open bounded half-planes, denoted by ℬ1B_1 and ℬ2B_2, which are mapped onto each other under reflection across ℒL. For configurations in which the target Weber meeting node lies outside ℒL, its selection is performed in two stages. First, a unique target half-plane ℬ†B is determined; subsequently, a unique target Weber meeting node m†m associated with ℬ†B is selected. Phase I-A (Target Half-Plane Selection): This sub-phase determines the target half-plane ℬ†B whenever the candidate distribution alone does not directly determine the target Weber meeting node. Configuration ℐ32I_32: No Weber Meeting Node lies on the reflection line ℒL, and exactly two Candidate Weber Meeting Nodes exist; that is, (t0)∩ℒ=∅W(t_0) = and |c(t0)|=2. |W_c(t_0) |=2. The target half-plane is selected according to the following hierarchical rule. Unequal candidate distribution: If ωi>ωj _i> _j, then ℬiB_i is the unique half-plane containing the maximum number of Candidate Weber Meeting Nodes. Consequently, ℬ†=ℬi.B =B_i. The other half-plane ℬjB_j is designated as the transfer half-plane. Equal candidate distribution: If ω1=ω2 _1= _2, then, since |c(t0)|=2 |W_c(t_0) |=2, each half-plane contains exactly one Candidate Weber Meeting Node. In this case we have following two cases. Unbalanced case: If νi>νj _i> _j, then the unique half-plane containing the maximum number of robots is selected: ℬ†=ℬi.B =B_i. The remaining half-plane ℬjB_j becomes the transfer half-plane. This rule applies independently of the orientation of ℒL and the number of pivot corners. Balanced case: If ν1=ν2 _1= _2, then neither the candidate distribution nor the robot occupancy distinguishes the two half-planes. The tie is therefore resolved according to the subclass of ℐ32I_32. Subclass ℐ321I_321(ℒL is horizontal or vertical): Let a†K_a be the anchor corner determined by the canonical comparison of the traversal strings of ℰℛℐ(t0)SER_I(t_0). The unique half-plane not containing a†K_a is selected as the target half-plane: ℬ†=B =the unique half-plane not containing a†.K_a . Subclass ℐ322I_322(ℒL is diagonal): There is a unique pivot corner. The target half-plane is selected by considering the following two cases. Case 1 (ℰℛℐ(t0)=ℰℛℳCLOSE(SER_I(t_0)=SER_M): Let P denote the unique pivot corner, and let αPQ _PQ and αPS _PS be the canonical traversal strings associated with the two traversal directions originating at P. Denote by ℬPQB_PQ and ℬPSB_PS the corresponding half-planes. The target half-plane is selected as ℬ†=ℬPS,if αPS≻lexαPQ,ℬPQ,if αPQ≻lexαPS.B = casesB_PS,&if _PS _lex _PQ,\\[2.84526pt] B_PQ,&if _PQ _lex _PS. cases Case 2 (ℰℛℳ⊊ℰℛℐ(t0)):(SER_M _I(t_0)): Let ℬ1B_1 and ℬ2B_2 denote the two half-planes induced by ℒL. For each i∈1,2i∈\1,2\, define ηi=|(ℬi∩ℰℛℐ(t0))∩ℤ2|, _i= | (B_i _I(t_0) ) ^2 |, where the grid nodes lying on ℒL are excluded from both counts. Thus, ηi _i denotes the number of grid nodes of ℰℛℐ(t0)SER_I(t_0) lying strictly in ℬiB_i. If η1≠η2 _1≠ _2, the half-plane containing more grid nodes is selected as the target half-plane. Hence, ℬ†=ℬ1,if η1>η2,ℬ2,if η2>η1.B = casesB_1,&if _1> _2,\\[2.84526pt] B_2,&if _2> _1. cases Suppose now that η1=η2 _1= _2. Let a†K_a denote the unique anchor corner of the entire initial configuration ℐ(t0)I(t_0). Let γ1 _1 and γ2 _2 denote the two canonical traversal strings originating at a†K_a , and let ℬγ1B_ _1 and ℬγ2B_ _2 denote the corresponding half-planes. The target half-plane is then selected as ℬ†=ℬγ1,if γ1≻lexγ2,ℬγ2,if γ2≻lexγ1.B = casesB_ _1,&if _1 _lex _2,\\[2.84526pt] B_ _2,&if _2 _lex _1. cases Thus, when ℰℛℐ(t0)=ℰℛℳSER_I(t_0)=SER_M, the target half-plane is determined using the canonical traversal strings originating at the unique pivot corner. When ℰℛℳ⊊ℰℛℐ(t0)SER_M _I(t_0), the half-plane containing more grid nodes is selected; if the two grid-node counts are equal, the tie is resolved using the canonical traversal strings originating at the unique anchor corner of ℐ(t0)I(t_0). Subclass ℐ323I_323(ℒL is diagonal): There are two pivot corners. The target half-plane is selected by considering the following two cases. Case 1 (ℰℛℐ(t0)=ℰℛℳ):(SER_I(t_0)=SER_M): Using the prescribed cyclic labelling P,Q,R,SP,Q,R,S of the corners of ℰℛℐ(t0)SER_I(t_0), let P and R be the two pivot corners. Consider αPS _PS and αRS _RS are the two canonical traversal strings associated with the two corners P and R, respectively. Denote by ℬPQB_PQ and ℬPSB_PS the corresponding half-planes. The target half-plane is selected as ℬ†=ℬPS,if αPS≻lexαRS,ℬPQ,if αRS≻lexαPS.B = casesB_PS,&if _PS _lex _RS,\\[2.84526pt] B_PQ,&if _RS _lex _PS. cases Case 2 (ℰℛℳ⊊ℰℛℐ(t0)):(SER_M _I(t_0)): If η1≠η2 _1≠ _2, the half-plane containing more grid nodes is selected as the target half-plane. Thus, ℬ†=ℬ1,if η1>η2,ℬ2,if η2>η1.B = casesB_1,&if _1> _2,\\[2.84526pt] B_2,&if _2> _1. cases Suppose that η1=η2 _1= _2. Let a†K_a be the unique anchor corner of the entire initial configuration ℐ(t0)I(t_0). For each half-plane, consider only the canonical traversal string whose traversal direction lies within that half-plane. Let β1 _1 and β2 _2 denote the resulting canonical traversal strings associated with ℬ1B_1 and ℬ2B_2, respectively. The target half-plane is then selected as ℬ†=ℬ1,if β1≻lexβ2,ℬ2,if β2≻lexβ1.B = casesB_1,&if _1 _lex _2,\\[2.84526pt] B_2,&if _2 _lex _1. cases Thus, when ℰℛℐ(t0)=ℰℛℳSER_I(t_0)=SER_M, the two pivot-corner traversal strings lying in the same half-plane are compared to determine the anchor corner and, consequently, the target half-plane. When ℰℛℳ⊊ℰℛℐ(t0)SER_M _I(t_0), the target half-plane is determined by the grid-node counts, and any remaining tie is resolved using the canonical traversal strings associated with the unique anchor corner. The half-plane different from ℬ†B is denoted by ℬtrB^tr. Phase I-B (Target Weber Meeting Node Selection): Once the target half-plane ℬ†B has been determined, define the set of Candidate Weber Meeting Nodes contained in the selected half-plane by c†(t0)=c(t0)∩ℬ†.W_c (t_0)=W_c(t_0) . By the target-half-plane selection rule, c†(t0)≠∅W_c (t_0)≠ . The target Weber meeting node m†m is selected as follows. Unique candidate in the target half-plane: If |c†(t0)|=1 |W_c (t_0) |=1, then its unique element is directly selected as the target Weber meeting node. Thus, if c†(t0)=mW_c (t_0)=\m\, then m†=m =m. The selected half-plane contains exactly one Candidate Weber Meeting Node. Multiple candidates in the target half-plane: Suppose that |c†(t0)|>1 |W_c (t_0) |>1. Since, |c(t0)|=2 |W_c(t_0) |=2, this implies |c†(t0)|=2 |W_c (t_0) |=2 under which both Candidate Weber Meeting Nodes lie in the selected half-plane ℬ†B . Let τ†τ denote the prescribed canonical traversal associated with ℬ†B . According to the subclass of ℐ32I_32, this traversal is determined as follows: For ℐ321I_321, τ†τ is the canonical traversal determined by the anchor corner a†K_a . For ℐ322I_322, τ†τ is the traversal from the unique pivot corner P in the direction associated with ℬ†B . For ℐ323I_323, τ†τ is the canonical traversal associated with the corner pair determining ℬ†B . More precisely, it is the traversal represented by αPS _PS when ℬ†=ℬPSB =B_PS, and its reflected counterpart when ℬ†=μℒ(ℬPS).B = _L (B_PS ). Let u1†,u2†,…,uℓ†u _1,u _2,…,u _ be the ordered sequence of grid nodes encountered according to τ†τ . The robots scan this sequence and select the first encountered node belonging to c†(t0)W_c (t_0). Formally, define j†=minj∈1,…,ℓ:uj†∈c†(t0).j = \j∈\1,…, \:u _j _c (t_0) \. The target Weber meeting node is then defined as m†=uj†.m =u _j . Quadrant and Target Weber Meeting Node Selection(Rotation): When the meeting-node configuration ℳM possesses a nontrivial rotational symmetry about the center c and contains multiple Weber Meeting Nodes (not lying on c), each robot independently identifies the same target meeting node m†m . Whenever a quadrant selection is required, every robot also consistently chooses the same quadrant †Q according to the following rules. Phase I-A (Target Quadrant Selection). The target quadrant †Q is selected according to the applicable configuration class. Configuration ℐ4211I_4211. The unique quadrant containing the maximum number of Candidate Weber Meeting Nodes is selected as †Q . Configurations ℐ42121I_42121 and ℐ4221I_4221. The unique quadrant in S attaining νmax _S is selected as †Q . Configuration ℐ42122I_42122. Here, at least two specified quadrants attain νmax _S ; hence, the target quadrant is selected according to the following subclasses. Subclass ℐ42122(1)I_42122^(1). The meeting-node configuration admits rotational symmetry of angle 180∘180 , and at least one specified quadrant contains both a Candidate Weber Meeting Node and a pivot corner. Among all such quadrants attaining νmax _S , the unique quadrant whose pivot corner is associated with the lexicographically largest string αi _i is selected as †Q . Subclass ℐ42122(2)I_42122^(2). The meeting-node configuration admits rotational symmetry of angle 180∘180 , and none of the specified quadrants containing a Candidate Weber Meeting Node contains a pivot corner. Among all such quadrants attaining νmax _S , the unique quadrant whose non-pivot corner is associated with the lexicographically largest string βi _i is selected as †Q . Subclass ℐ42122(3)I_42122^(3). The meeting-node configuration admits rotational symmetry of angle 90∘90 . Among the specified quadrants attaining νmax _S , the unique quadrant whose pivot corner is associated with the lexicographically largest canonical traversal string αi _i is selected as †Q . Configuration ℐ4222I_4222. Here, at least two specified quadrants attain νmax _S ; hence, robot occupancy alone cannot determine †Q . Subclass ℐ42221I_42221. Among all specified quadrants attaining νmax _S , the unique quadrant whose pivot corner is associated with the lexicographically smallest canonical traversal string αi _i is selected as †Q . Phase I-B (Target Weber Meeting Node Selection): In this sub-phase, every robot selects the unique target Weber Meeting Node m†m according to the applicable configuration class. Configuration ℐ41I_41: The center of rotation is itself a Weber Meeting Node, i.e., c∈(t0)c (t_0). Since c is invariant under the rotational symmetry, every robot deterministically selects m†=cm =c. Configurations ℐ4211I_4211, ℐ42121I_42121, ℐ42122(1)I_42122^(1), ℐ42122(2)I_42122^(2), and ℐ42122(3)I_42122^(3): Let †Q be the unique quadrant selected by the corresponding quadrant-selection rule, let p†p be the corner of ℰℛℳSER_M associated with †Q , and define †=c(t)∩†W =W_c(t) . If a unique node of †W minimizes its distance from p†p , it is selected as the target Weber Meeting Node; that is, m†=argminm∈†dM(p†,m)m = m \,d_M(p ,m). Otherwise, let min†=m∈†:dM(p†,m)=minw∈†dM(p†,w)W_ =\m :d_M(p ,m)= _w d_M(p ,w)\ be the set of tied candidates. Among these nodes, the unique node minimizing its distance from the boundary half-line ℒ1++L_1^++ is selected; hence, m†=argminm∈min†dM(m,ℒ1++)m = m _ \,d_M(m,L_1^++). Configurations ℐ4221I_4221 and ℐ42221I_42221: Let †Q be the unique quadrant selected by the corresponding quadrant-selection rule, and let p†p denote its associated pivot corner. Define ¯†=c(t)∩(ℒ1++∪ℒ2++) W =W_c(t)∩(L_1^++ _2^++). If |¯†|=1| W |=1, its unique element is selected as m†m . If |¯†|>1| W |>1, the asymmetry of the robot configuration uniquely determines the direction of the canonical traversal from a†K_a . Let u1†,u2†,…,uℓ†u_1 ,u_2 ,…,u_ be the ordered sequence of grid nodes encountered in this traversal, and define j†=minj∈1,…,ℓ:uj†∈¯†j = \j∈\1,…, \:u_j ∈ W \. The first encountered candidate is then selected; that is, m†=uj†m =u_j . 3.2 Phase I: Crash-Tolerant Directed Gathering Once Phase I determines the target Weber Meeting Node m†m and, if necessary, a target region, every activated non-faulty robot executes the corresponding gathering rule described below. Direct Gathering: This subroutine applies to configurations ℐ1I_1, ℐ2I_2, ℐ31I_31, and ℐ41I_41. Every activated non-faulty robot not already located at m†m executes MoveToDestination() and moves one hop toward m†m along a shortest path. A robot already located at m†m remains stationary. Half-Plane Transfer and Gathering(Reflection): This subroutine is executed for every configuration in ℐ32I_32, namely, for the subclasses ℐ321I_321, ℐ322I_322, and ℐ323I_323. In each of these cases, Phase I-A selects a unique target half-plane ℬ†B . The other half-plane is denoted by ℬtrB^tr and is called the transfer half-plane. Phase I-B subsequently selects m†∈c(t0)∩ℬ†.m _c(t_0) . The movements of robots in the two half-planes occur concurrently and are determined by their current positions. A robot located in ℬ†B executes MoveToDestination() and performs its next hop toward m†m along a prescribed shortest path contained in ℬ†B . A robot located on the reflection line ℒL executes MoveToDestination() and selects a prescribed restricted shortest path whose first hop enters ℬ†B . It then continues toward m†m along a shortest path contained in ℬ†B . A robot located in the transfer half-plane ℬtrB^tr follows a prescribed restricted shortest path toward m†m . It first moves toward ℒL, subsequently crosses ℒL and enters ℬ†B , and thereafter remains in ℬ†B while proceeding toward m†m . Thus, its positional transition is ℬtr⟶ℒ⟶ℬ†⟶m†.B^tr m . Once such a robot enters ℬ†B , it follows the Direct Gathering rule at every subsequent activation until it reaches m†m . Every path prescribed by MoveToDestination() is a shortest path toward the same target m†m . Consequently, every completed hop from r to r′r satisfies d(r′,m†)=d(r,m†)−1.d(r ,m )=d(r,m )-1. Meanwhile, robots already belonging to ℬ†B continue moving toward m†m without waiting for robots in ℬtrB^tr to cross ℒL. Therefore, gathering within ℬ†B and the transfer of robots from ℬtrB^tr occur simultaneously rather than as two separate sequential phases. Quadrant Transfer and Gathering(Rotation): For rotationally symmetric configurations, every activated robot follows the prescribed movement rule according to whether m†m lies in the interior of †Q or on one of its boundary half-lines, ℒ1++L_1^++ or ℒ2++L_2^++. Case 1( m†m is in the interior of †Q ): This case applies to configurations in ℐ4211,ℐ42121,ℐ42122(1),ℐ42122(2),ℐ42122(3)I_4211,I_42121,I_42122^(1),I_42122^(2),I_42122^(3) whenever the selected target m†∈†m lies strictly inside †Q . Relative to †Q , the two quadrants that share a boundary half-line with it, along ℒ1L_1 and ℒ2L_2, respectively, are called the adjacent quadrants and are denoted by 1adjQ^adj_1 and 2adjQ^adj_2. The remaining quadrant shares no boundary half-line with †Q and intersects it only at the center of rotation c. We refer to this quadrant as the opposite quadrant and denote it by oppQ^opp. Three types of movement occur concurrently. (i) a robot already located in †Q executes MoveToDestination() toward m†m along a shortest path contained in †Q . (i) a robot located in 1adjQ^adj_1, 2adjQ^adj_2, or on ℒ1L_1 or ℒ2L_2, executes MoveToDestination() along the prescribed restricted shortest path that crosses directly into, and subsequently remains in, †Q ; upon crossing, it continues toward m†m along a shortest path contained in †Q . (i) a robot located in oppQ^opp shares no boundary half-line with †Q ; it therefore executes MoveToDestination() to move along the prescribed shortest path toward c. Once it reaches c, at its next activation it selects the prescribed restricted shortest path whose first hop enters †Q across ℒ1L_1 or ℒ2L_2, and thereafter proceeds as above. Its local transition is opp⟶c⟶ℒ1 or ℒ2⟶†⟶m†Q^opp c _1 or L_2 m . Case 2 (m†m is on ℒ1++L_1^++ or ℒ2†L_2 ): This case applies to configurations in ℐ4221I_4221 and ℐ42221I_42221, where ¯† W may contain candidates lying on the boundary half-lines, and whenever the selected target satisfies m†∈ℒ1++∪ℒ2++m _1^++ _2^++. Without loss of generality, assume m†∈ℒ1++m _1^++; the case m†∈ℒ2++m _2^++ is symmetric. As in Case 1, let 1adj,2adjQ^adj_1,Q^adj_2 denote the two quadrants adjacent to †Q along ℒ1L_1 and ℒ2L_2 respectively, and let oppQ^opp denote the quadrant diagonally opposite to †Q . Four types of movement occur concurrently. (i) a robot already located in †Q executes MoveToDestination() toward m†m along a shortest path contained in †∪ℒ1++Q _1^++. (i) a robot positioned in either 1adjQ^adj_1 or 2adjQ^adj_2 and sufficiently close to m†m so that m†m is reachable via a shortest path directly executes MoveToDestination() toward m†m along such a path. (i) a robot located in 1adjQ^adj_1 or 2adjQ^adj_2 that is farthest from m†m , for which no such direct shortest path exists, instead executes MoveToDestination() to move toward the boundary half-line it shares with †Q (ℒ1++L_1^++ or ℒ2†L_2 , respectively). Once it reaches that half-line, it continues toward m†m along a shortest path contained in the half-line (or, if the half-line is ℒ2++L_2^++, it proceeds via c onto ℒ1++L_1^++, as in the next case). (iv) a robot located in oppQ^opp shares no boundary half-line with †Q or with ℒ1++L_1^++; it therefore executes MoveToDestination() to move along the prescribed shortest path toward c. Once it reaches c, at its next activation, it selects the prescribed shortest path along ℒ1†L_1 toward m†m . Its local transition is opp⟶c⟶ℒ1++⟶m†Q^opp c _1^++ m . 3.3 Routine MoveToDestination() After Phase I, every robot computes the same target Weber Meeting Node m†m . The routine MoveToDestination() specifies the path followed by an activated robot toward m†m . Let r be a robot located at the grid node prp_r. If pr≠m†p_r≠ m , then r moves to an adjacent grid node r′r satisfying d(r′,m†)=d(pr,m†)−1d(r ,m )=d(p_r,m )-1. Thus, every move is one hop along a Manhattan shortest path toward m†m ; a robot already located at m†m remains stationary. The restrictions imposed on the choice of a shortest path depend on the symmetry of the meeting-node configuration ℳM. Movement when ℳM is asymmetric: When ℳM is asymmetric, Phase I uniquely determines m†m , and no target half-plane or quadrant needs to be preserved. Therefore, a robot may follow any Manhattan shortest path from its current position to m†m . Movement when ℳM has a line of symmetry: Suppose that ℳM has a unique line of symmetry ℒL, which divides the grid into two open half-planes ℬiB_i and ℬjB_j. Phase I either directly selects a target m†m on ℒL or first selects one half-plane as the target half-plane and subsequently determines m†m within it. Since multiple shortest paths to the target may exist, allowing robots to choose any of them may fail to break the tie used to select the target half-plane. Therefore, the prescribed shortest paths ensure that every robot progresses toward m†m without entering the non-selected half-plane, so that the selected target half-plane and m†m remain unchanged. Movement within the target half-plane. Suppose that r∈ℬir _i. The robot selects a canonical shortest path to mim_i that remains entirely in ℬiB_i; a path intersecting ℒL or entering ℬjB_j is not used. If r=mir=m_i, the robot does not move. Movement toward the target half-plane. Suppose that r∈ℬj∪ℒr _j . The robot follows a canonical shortest path to mim_i that crosses ℒL only once. Before crossing ℒL, the path remains in ℬj∪ℒB_j ; afterward, it remains in ℬiB_i. For a robot in ℬjB_j, the restricted path is chosen so that d(r′,mi)−d(r′,mj)≤d(r,mi)−d(r,mj)d(r ,m_i)-d(r ,m_j)≤ d(r,m_i)-d(r,m_j). When the robot is on ℒL, its next hop enters ℬiB_i and satisfies d(r′,mi)=d(r,mi)−1d(r ,m_i)=d(r,m_i)-1 and d(r′,mj)=d(r,mj)+1d(r ,m_j)=d(r,m_j)+1. Hence, every non-faulty robot starting in ℬjB_j eventually crosses ℒL, enters ℬiB_i, and follows the rule for movement within the target half-plane. Let ℐ(t′)I(t ) be obtained from ℐ(t)I(t) after one such hop. Then ct′(mi)−ct′(mj)=ct(mi)−ct(mj)+(d(r′,mi)−d(r,mi))−(d(r′,mj)−d(r,mj))c_t (m_i)-c_t (m_j)=c_t(m_i)-c_t(m_j)+ (d(r ,m_i)-d(r,m_i) )- (d(r ,m_j)-d(r,m_j) ) and therefore ct′(mi)−ct′(mj)≤ct(mi)−ct(mj)c_t (m_i)-c_t (m_j)≤ c_t(m_i)-c_t(m_j). For a hop from ℒL into ℬiB_i, the inequality is strict: ct′(mi)−ct′(mj)=ct(mi)−ct(mj)−2c_t (m_i)-c_t (m_j)=c_t(m_i)-c_t(m_j)-2. The same hop also increases the number of robots in the target half-plane. Since every robot crossing ℒL enters ℬiB_i, concurrent movements cannot reverse this comparison. Figure 5 in the APPENDIX illustrates these paths. Movement when ℳM has Rotational Symmetry: Suppose that ℳM has rotational symmetry about the center c. Phase I either determines m†m directly or first selects the target quadrant †Q and then selects m†m within it. In the latter case, an unrestricted shortest path may pass through a non-selected quadrant and change the occupancy or candidate comparison used to select †Q or m†m . Therefore, the movement paths are restricted according to the current position of the robot relative to †Q , its boundary half-lines, and c. (a) (b) Figure 2: Restricted shortest paths toward m2†m_2 . The green dots represent the robots activated to move. (a) If m2†∈†m_2 , robots enter †Q directly, except those in oppQ^opp, which pass through c. (b) If m2†∈ℒ1++m_2 _1^++, robots first reach ℒ1++L_1^++ through their prescribed regions and then proceed along it toward m2†m_2 . Movement toward a Weber Meeting Node in †Q . Let m2†∈†m_2 be the target Weber Meeting Node; see Figure 2(a). Each robot is classified according to its current position relative to †Q . Robots already in †Q . A robot in †Q executes MoveToDestination() toward m2†m_2 along a shortest path contained entirely in †Q . Robots in the adjacent quadrants 1adjQ_1^adj and 2adjQ_2^adj. These quadrants share the boundary half-lines ℒ1++L_1^++ and ℒ2++L_2^++, respectively, with †Q . A robot in either adjacent quadrant follows a restricted shortest path that enters †Q through the corresponding shared boundary without passing through c, and then follows the rule for robots already in the target quadrant. Such a robot is never directed through c, the other adjacent quadrant, or oppQ^opp. Robots in oppQ^opp. Since oppQ^opp and †Q meet only at c, a robot in oppQ^opp first follows a shortest path to c. From c, it enters †Q through ℒ1++L_1^++ or ℒ2++L_2^++ and continues toward m2†m_2 ; thus, opp⟶c⟶†⟶m2†Q^opp c m_2 . Several robots may meet at c while following this route. Such a multiplicity causes no ambiguity, as c lies outside all open quadrants and is equidistant from rotationally symmetric candidate nodes. Robots on ℒ1++L_1^++ or ℒ2++L_2^++. A robot on either boundary half-line follows a shortest path toward m2†m_2 . If the path leaves the boundary, it enters †Q directly; the robot is not routed through c. Robots on ℒ1−−L_1^-- or ℒ2−−L_2^--. A robot on a half-line bounding oppQ^opp first follows a shortest path to c, then enters †Q and proceeds toward m2†m_2 . For every prescribed hop from r to r′r , d(r′,m2†)=d(r,m2†)−1d(r ,m_2 )=d(r,m_2 )-1. No robot is routed through a non-target open quadrant other than the quadrant in which it is currently located. Consequently, the movement does not increase the occupancy of any non-selected quadrant and does not alter the comparison used to select †Q . Movement toward Candidate Weber Meeting Nodes on ℒ1++L_1^++ and ℒ2++L_2^++. Without loss of generality, let m2†m_2 lie on the boundary half-line ℒ1++L_1^++ of †Q ; see Figure 2(b). The case m2†∈ℒ2++m_2 _2^++ is symmetric, with the roles of ℒ1++L_1^++ and ℒ2++L_2^++, and those of 1adjQ_1^adj and 2adjQ_2^adj, interchanged. Here, ¯† W contains the selected candidate m2†m_2 on ℒ1++L_1^++ and another candidate m1†m_1 , possibly on ℒ2++L_2^++. Robots in †Q . A robot in †Q first follows a shortest path to the nearest reachable node of ℒ1++L_1^++; except for its endpoint, this path remains in †Q . It then moves along the half-line toward m2†m_2 . Robots on ℒ1++L_1^++. A robot already on ℒ1++L_1^++ follows the half-line directly toward m2†m_2 . Robots in 1adjQ_1^adj. Since 1adjQ_1^adj shares ℒ1++L_1^++ with †Q , a robot in this quadrant follows a shortest grid path directly to m2†m_2 . Robots in 2adjQ_2^adj or on ℒ2++L_2^++. A robot in 2adjQ_2^adj first follows a restricted shortest path that enters †Q directly through ℒ2++L_2^++, moves to ℒ1++L_1^++, and proceeds along it toward m2†m_2 . A robot on ℒ2++L_2^++ is treated as a robot in 2adjQ_2^adj. Robots in oppQ^opp. A robot in oppQ^opp first follows the prescribed shortest path to c, then moves onto ℒ1++L_1^++ and proceeds along it toward m2†m_2 ; thus, opp⟶c⟶ℒ1++⟶m2†Q^opp c _1^++ m_2 . A robot already at c follows the same rule from c onward. Robots on ℒ1−−L_1^-- or ℒ2−−L_2^--. A robot on either half-line bounding oppQ^opp first follows a shortest path to c and then proceeds along ℒ1++L_1^++ toward m2†m_2 . For every prescribed hop from r to r′r , d(r′,m2†)=d(r,m2†)−1d(r ,m_2 )=d(r,m_2 )-1, and the restricted paths satisfy d(r′,m2†)−d(r,m2†)≤d(r′,m1†)−d(r,m1†).d(r ,m_2 )-d(r,m_2 )≤ d(r ,m_1 )-d(r,m_1 ). Let ℐ(t′)I(t ) be obtained from ℐ(t)I(t) after this hop. Then ct′(m2†)−ct′(m1†)=ct(m2†)−ct(m1†)+(d(r′,m2†)−d(r,m2†))−(d(r′,m1†)−d(r,m1†))c_t (m_2 )-c_t (m_1 )=c_t(m_2 )-c_t(m_1 )+ (d(r ,m_2 )-d(r,m_2 ) )- (d(r ,m_1 )-d(r,m_1 ) ) and therefore ct′(m2†)−ct′(m1†)≤ct(m2†)−ct(m1†)c_t (m_2 )-c_t (m_1 )≤ c_t(m_2 )-c_t(m_1 ). The inequality becomes strict when a robot makes a committed move toward m2†m_2 along ℒ1++L_1^++, or enters the side associated with ℒ1++L_1^++ from c or †Q . Consequently, if ct(m2†)=ct(m1†)c_t(m_2 )=c_t(m_1 ), the first such successful hop gives ct′(m2†)<ct′(m1†)c_t (m_2 )<c_t (m_1 ). The candidate m1†m_1 is then no longer a Weber Meeting Node, whereas m2†m_2 remains one; all subsequent movements preserve this strict inequality. 4 Correctness of the Algorithm For a snapshot ℐ(t)=(ℛ(t),ℳ)I(t)=(R(t),M), let m†(t)m (t) denote the target Weber Meeting Node computed by an activated robot and, when applicable, let ℬ†(t)B (t) or †(t)Q (t) denote the computed target region. Let ℱF be the unknown, possibly empty, set of crash-faulty robots. Due to page constraints, the proofs of the following results are provided in the APPENDIX. Lemma 1 (Uniqueness of the target region) For every configuration in ℐ321I_321, ℐ322I_322, or ℐ323I_323, Phase I-A uniquely selects one of ℬ1B_1 and ℬ2B_2. For every configuration in ℐ4211I_4211, ℐ42121I_42121, ℐ42122(1)I_42122^(1), ℐ42122(2)I_42122^(2), ℐ42122(3)I_42122^(3), ℐ4221I_4221, or ℐ42221I_42221, it uniquely selects one of 1,…,4Q_1,…,Q_4. Lemma 2 (Uniqueness of the target node) For every solvable configuration, Phase I determines exactly one target Weber Meeting Node m†∈(t)m (t) from the current snapshot. Lemma 3 (Invariance of the selected half-plane) Let ℬ†B be the target half-plane selected from a configuration in ℐ321I_321, ℐ322I_322, or ℐ323I_323. If every subsequent move follows MoveToDestination(), every configuration reached during Phase I selects the same half-plane ℬ†B . Lemma 4 (Invariance of the selected quadrant) Let †Q be the target quadrant selected at the beginning of Phase I. Every subsequent configuration reached during Phase I selects the same quadrant †Q . Lemma 5 (Invariance of the selected target) Let m†m be selected from ℐ(t)I(t). If every move completed after time t follows MoveToDestination() toward m†m , then every subsequent snapshot selects the same target m†m . Lemma 6 (Independent progress under crash faults) Let r∉ℱr be a non-faulty robot activated at time t, with r(t)≠m†r(t)≠ m , and let t′>t >t be the time at which it completes the move prescribed by MoveToDestination(). Then d(r(t′),m†)≤d(r(t),m†)−1d(r(t ),m )≤ d(r(t),m )-1. The completion of this move does not require the activation or movement of any other robot. Lemma 7 (Finite-time gathering) Under every fair asynchronous schedule, all non-faulty robots reach m†m after finitely many completed moves and remain there. Theorem 4.1 (Correctness) Let ℐ(t0)∉I(t_0) , and suppose that at most n−2n-2 robots crash. Under every fair asynchronous schedule, CrashTolerantWeberGathering() gathers all non-faulty robots in finite time at a common node m†∈(t0)m (t_0). Moreover, no non-faulty robot must wait for another robot to move or become activated. Proof Because ℐ(t0)∉I(t_0) , the applicable rules of Phase I are defined. Lemmas 1 and 2 provide a unique m†∈(t0)m (t_0) and, when necessary, a unique target region. Lemma 5 shows that every subsequent snapshot yields the same choices. Lemma 8 (see APPENDIX) additionally ensures that m†m remains a Weber Meeting Node throughout Phase I. A crash only prevents the faulty robot from moving further. By Lemma 6, it neither blocks another robot nor forces a non-faulty robot to wait. Finally, Lemma 7 implies that fairness brings every non-faulty robot to m†m in finite time and that all such robots remain there. 5 Conclusion and Future Work We studied crash-tolerant optimal gathering at Weber Meeting Nodes for asynchronous, anonymous, oblivious, and disoriented robots on an infinite grid, assuming global visibility, global strong multiplicity detection, and up to n−2n-2 crashes. We established both inherited and crash-specific impossibility results and showed that global weak multiplicity detection cannot preserve min-sum optimality, even under FSYNC activation and rigid movements. For every remaining configuration, CrashTolerantWeberGathering() selects a unique target m†∈(t0)m (t_0) and, when required, a unique target region.Restricted shortest paths preserve these choices and ensure that all non-faulty robots gather at the common target in finite time under any fair ASYNC scheduler. Future work includes characterizing solvable configurations under weaker multiplicity detection, possibly using persistent memory or visible lights; removing the grid-node restriction on symmetry lines and rotation centers; and considering limited or obstructed visibility, Byzantine faults, and alternative optimization criteria such as maximum travel distance or completion time. References [1] N. Agmon and D. Peleg (2006) Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM Journal on Computing 36 (1), p. 56–82. External Links: Document Cited by: §1. [2] S. Bhagat, A. Chakraborty, B. Das, and K. Mukhopadhyaya (2022) Gathering over meeting nodes in infinite grid. Fundamenta Informaticae 187 (1), p. 1–30. External Links: Document, https://journals.sagepub.com/doi/pdf/10.3233/FI-222128 Cited by: §1, Detailed Definitions and Notation. [3] S. Bhagat, A. Chakraborty, B. Das, and K. Mukhopadhyaya (2023) Optimal gathering over weber meeting nodes in infinite grid. International Journal of Foundations of Computer Science 34 (01), p. 25–49. External Links: Document, https://doi.org/10.1142/S0129054122500174 Cited by: §1, §2, §2, Detailed Definitions and Notation, Detailed Definitions and Notation, Detailed Definitions and Notation, Detailed Definitions and Notation. [4] S. Bhagat, S. G. Chaudhuri, and K. Mukhopadhyaya (2016) Fault-tolerant gathering of asynchronous oblivious mobile robots under one-axis agreement. Journal of Discrete Algorithms 36, p. 50–62. External Links: Document Cited by: §1. [5] K. Bose, R. Adhikary, S. G. Chaudhuri, and B. Sau (2017) Crash tolerant gathering on grid by asynchronous oblivious robots. CoRR abs/1709.00877. External Links: 1709.00877 Cited by: §1. [6] K. Bose, M. K. Kundu, R. Adhikary, and B. Sau (2019) Optimal gathering by asynchronous oblivious robots in hypercubes. In Algorithms for Sensor Systems, Lecture Notes in Computer Science, Vol. 11410, p. 102–117. External Links: Document Cited by: §1. [7] S. Bouchard, Y. Dieudonné, and B. Ducourthial (2016) Byzantine gathering in networks. Distributed Computing 29 (6), p. 435–457. External Links: Document Cited by: §1. [8] Z. Bouzid, S. Das, and S. Tixeuil (2013) Gathering of mobile robots tolerating multiple crash faults. In IEEE 33rd International Conference on Distributed Computing Systems, ICDCS 2013, 8-11 July, 2013, Philadelphia, Pennsylvania, USA, p. 337–346. External Links: Document Cited by: §1. [9] J. Chalopin, Y. Dieudonné, A. Labourel, and A. Pelc (2016) Rendezvous in networks in spite of delay faults. Distributed Computing 29 (3), p. 187–205. External Links: Document Cited by: §1. [10] S. Cicerone, G. D. Stefano, and A. Navarra (2018) Gathering of robots on meeting-points: feasibility and optimal resolution algorithms. Distributed Computing 31 (1), p. 1–50. External Links: Document Cited by: §1. [11] S. Cicerone, G. D. Stefano, and A. Navarra (2019) Embedded pattern formation by asynchronous robots without chirality. Distributed Computing 32 (4), p. 291–315. External Links: Document Cited by: §1. [12] S. Das, R. Focardi, F. L. Luccio, E. Markou, and M. Squarcina (2019) Gathering of robots in a ring with mobile faults. Theoretical Computer Science 764, p. 42–60. External Links: Document Cited by: §1. [13] X. Défago, M. Gradinariu, S. Messika, and P. Raipin-Parvédy (2006) Fault-tolerant and self-stabilizing mobile robots gathering. In Distributed Computing, Lecture Notes in Computer Science, Vol. 4167, p. 46–60. External Links: Document Cited by: §1. [14] G. Di Stefano and A. Navarra (2013) Optimal gathering of oblivious robots in anonymous graphs. In Structural Information and Communication Complexity, T. Moscibroda and A. A. Rescigno (Eds.), Lecture Notes in Computer Science, Vol. 8179, Cham, p. 213–224. External Links: ISBN 978-3-319-03578-9, Document Cited by: Detailed Definitions and Notation. [15] G. D’Angelo, G. D. Stefano, R. Klasing, and A. Navarra (2016) Gathering of robots on anonymous grids and trees without multiplicity detection. Theoretical Computer Science 610, p. 158–168. External Links: Document Cited by: §1. [16] G. D’Angelo, G. D. Stefano, and A. Navarra (2014) Gathering on rings under the Look–Compute–Move model. Distributed Computing 27 (4), p. 255–285. External Links: Document Cited by: §1. [17] G. D’Angelo, G. D. Stefano, and A. Navarra (2014) Gathering six oblivious robots on anonymous symmetric rings. Journal of Discrete Algorithms 26, p. 16–27. External Links: Document Cited by: §1. [18] P. Flocchini, E. Kranakis, D. Krizanc, F. L. Luccio, N. Santoro, and C. Sawchuk (2004) Mobile agents rendezvous when tokens fail. In Structural Information and Communication Complexity, Lecture Notes in Computer Science, Vol. 3104, p. 161–172. External Links: Document Cited by: §1. [19] P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer (2005) Gathering of asynchronous robots with limited visibility. Theoretical Computer Science 337 (1–3), p. 147–168. External Links: Document Cited by: §1. [20] N. Fujinaga, H. Ono, S. Kijima, and M. Yamashita (2010) Pattern formation through optimum matching by oblivious CORDA robots. In Principles of Distributed Systems, Lecture Notes in Computer Science, Vol. 6490, p. 1–15. External Links: Document Cited by: §1. [21] T. Izumi, S. Souissi, Y. Katayama, N. Inuzuka, X. Défago, K. Wada, and M. Yamashita (2012) The gathering problem for two oblivious robots with unreliable compasses. SIAM J. Comput. 41 (1), p. 26–46. External Links: Document Cited by: §1. [22] T. Izumi, T. Izumi, S. Kamei, and F. Ooshita (2010) Mobile robots gathering algorithm with local weak multiplicity in rings. In Structural Information and Communication Complexity, Lecture Notes in Computer Science, Vol. 6058, p. 101–113. External Links: Document Cited by: §1. [23] S. Kamei, A. Lamani, F. Ooshita, and S. Tixeuil (2011) Asynchronous mobile robot gathering from symmetric configurations without global multiplicity detection. In Structural Information and Communication Complexity, Lecture Notes in Computer Science, Vol. 6796, p. 150–161. External Links: Document Cited by: §1. [24] R. Klasing, E. Markou, and A. Pelc (2008) Gathering asynchronous oblivious mobile robots in a ring. Theoretical Computer Science 390 (1), p. 27–39. External Links: Document Cited by: §1. [25] A. Pelc (2018) Deterministic gathering with crash faults. Networks 72 (2), p. 182–199. External Links: Document Cited by: §1. [26] G. Prencipe (2007) Impossibility of gathering by a set of autonomous mobile robots. Theoretical Computer Science 384 (2–3), p. 222–231. External Links: Document Cited by: §1. APPENDIX Detailed Definitions and Notation Grid Deployment and Symmetry. Let =(ℤ,ℰ′)P=(Z,E ) be the infinite path, where ℰ′=i,i+1:i∈ℤE =\\i,i+1\:i \, and let =×=(,ℰ)G=P×P=(V,E) be the infinite grid. The finite set of meeting nodes is ℳ=m1,…,ms⊂M=\m_1,…,m_s\ , and ℛ(t)=r1(t),…,rn(t)R(t)=\r_1(t),…,r_n(t)\ is the multiset of robot positions at time t. The entire configuration is ℐ(t)=(ℛ(t),ℳ)I(t)=(R(t),M), with initial time t0t_0. For u,v∈u,v , d(u,v)d(u,v) denotes their Manhattan distance. Let λt(v) _t(v) be the number of robots at v and let ft(v)=1f_t(v)=1 if v∈ℳv , and ft(v)=0f_t(v)=0 otherwise. Although the set of meeting nodes is fixed and hence ftf_t is independent of time, we retain the subscript t for notational consistency with the time-dependent configuration ℐ(t)I(t). Note that initially, λt0(v)≤1 _t_0(v)≤ 1 for every v∈v . A grid automorphism Φ is a configuration automorphism at time t if ft(v)=ft(Φ(v))f_t(v)=f_t( (v)) and λt(v)=λt(Φ(v)) _t(v)= _t( (v)) for every v∈v . Since the configuration is finite, only reflectional and rotational symmetries are relevant. Reflection lines may be horizontal, vertical, or diagonal, and rotations may be by 90∘90 or 180∘180 whenever they preserve the grid. We use partitive automorphisms and their orbits in the sense of [2]. Weber Meeting Nodes. For each m∈ℳm , define ct(m)=∑v∈d(v,m)λt(v)c_t(m)= _v d(v,m) _t(v). A meeting node minimizing ctc_t is called a Weber Meeting Node, and (t)=argminm∈ℳct(m)W(t)= _m c_t(m) denotes the set of all such nodes. Thus, any node in (t0)W(t_0) minimizes the sum of the initial Manhattan distances from all robots to a designated meeting node. Under global strong multiplicity detection, every robot can determine λt(v) _t(v) exactly at every grid node and hence compute (t)W(t) from its snapshot. Traversal strings and pivot corners. Let ℰℛℳ=PQRSSER_M=PQRS be the smallest axis-aligned rectangle containing ℳM, and let ℰℛℐ(t)SER_I(t) be the smallest axis-aligned rectangle containing ℛ(t)∪ℳR(t) . Following the traversal construction of [3], a corner together with one of its incident directions determines an ordered scan of the rectangle. The hop-distances of the meeting nodes encountered during this scan form a traversal string, denoted by ΓPQ _PQ when the scan starts at corner P in the direction of side PQPQ. For a non-square rectangle, only the traversal parallel to the shorter side is considered, whereas for a square, both directions are considered. In the collinear case, traversals from the two opposite ends are used. All relevant traversal strings of ℰℛℳSER_M are compared lexicographically. A corner producing a lexicographically smallest string is called a pivot corner, and its associated scan is its traversal direction. Thus, our pivot corner is the leading corner of [3]. Let pivK_piv be the set of pivot corners. For each p∈pivp _piv, let wp(t)w_p(t) be the last node of (t)W(t) encountered in the traversal associated with p. The candidate Weber set, corresponding to the Potential Weber meeting nodes of [3], is defined as c(t)=wp(t):p∈pivW_c(t)=\w_p(t):p _piv\. The following invariance property, proved for Weber points in [14] and adapted to meeting nodes in [3], will be used throughout. Lemma 8 Let m†∈(t)m (t), and let ℐ(t′)I(t ) be obtained from ℐ(t)I(t) after a robot, or a group of co-located robots, moves toward m†m along a shortest path. Then m†∈(t′)m (t ) and (t′)⊆(t)W(t ) (t). Thus, moving toward m†m preserves it as a Weber Meeting Node and creates no new Weber Meeting Node. Observation 1 If the rotation center c of ℐ(t0)I(t_0) is a meeting node, then c∈(t0)c (t_0). Canonical traversal strings and anchor corner. To distinguish configurations having identical meeting-node traversal strings, each node u encountered by a prescribed traversal τ is encoded by ⟨ft(u),λt(u)⟩ f_t(u), _t(u) . These pairs are ordered by first comparing λt _t and then ftf_t, and the corresponding canonical traversal string is (⟨ft(u1τ),λt(u1τ)⟩,…,⟨ft(uℓτ),λt(uℓτ)⟩) ( f_t(u_1^τ), _t(u_1^τ) ,…, f_t(u_ ^τ), _t(u_ ^τ) ). A canonical string originating from a pivot corner is called an α-string; one originating from a non-pivot corner is called a β-string. The first and second letters in a subscript specify the starting corner and initial traversal direction, respectively, as in PS(t) α_PS(t). The admissible canonical strings of ℰℛℐ(t0)SER_I(t_0) are compared lexicographically. If ℐ(t0)I(t_0) is asymmetric, their unique minimum originates from the anchor corner; its string is denoted by anchor(t0) α_anchor(t_0). This notion plays the role of the key corner of [3], while explicitly using the smallest enclosing rectangle of the entire configuration. Regions and balance. If ℳM has a unique reflection line ℒL, let ℋ1,ℋ2H_1,H_2 be the two open half-planes determined by ℒL, and let ℬi=ℋi∩ℰℛℐ(t0)B_i=H_i _I(t_0). Define ωi=|c(t0)∩ℬi| _i=|W_c(t_0) _i| and νi=∑u∈ℬiλt0(u) _i= _u _i _t_0(u). Thus, ωi _i counts the candidate Weber meeting nodes and νi _i counts the robots in ℬiB_i; objects on ℒL are excluded. The configuration is balanced if ν1=ν2 _1= _2, and unbalanced otherwise. If ℳM has rotational symmetry about c, let ℒ1,ℒ2L_1,L_2 be the perpendicular grid lines through c, parallel to the sides of ℰℛℳ=PQRSSER_M=PQRS. These lines determine the open quadrants 1,…,4Q_1,…,Q_4 containing, respectively, p1=S,p2=P,p3=Q,p4=Rp_1=S,p_2=P,p_3=Q,p_4=R. Let ℬk=k∩ℰℛℐ(t0)B_k=Q_k _I(t_0), ωk=|c(t0)∩ℬk| _k=|W_c(t_0) _k|, and νk=∑u∈ℬkλt0(u) _k= _u _k _t_0(u). Nodes on ℒ1∪ℒ2L_1 _2 are excluded from these counts. Set ωmax=maxkωkω = _k _k, =k:ωk=ωmaxS=\k: _k=ω \, νmax=maxk∈νk _S = _k _k, and max=k∈:νk=νmaxS =\k : _k= _S \. The quadrants indexed by S are called the specified quadrants. The configuration is balanced if |max|≥2|S |≥ 2, and unbalanced otherwise. Illustrative Computation This APPENDIX gives the detailed computation for the configuration in Figure 3. Taking the marked grid node as (0,0)(0,0) and one grid edge as one hop, the robot positions are r1 r_1 =(−4,−4), =(-4,-4), r2 r_2 =(−2,−4), =(-2,-4), r3 r_3 =(2,−4), =(2,-4), r4 r_4 =(4,−2), =(4,-2), r5 r_5 =(−2,0), =(-2,0), r6 r_6 =(2,4), =(2,4), and the meeting nodes are m1 m_1 =(−4,0), =(-4,0), m2 m_2 =(−2,−2), =(-2,-2), m3 m_3 =(2,−2), =(2,-2), m4 m_4 =(4,0), =(4,0), m5 m_5 =(−2,2), =(-2,2), m6 m_6 =(2,2), =(2,2), m7 m_7 =(4,2). =(4,2). Figure 3: An asymmetric configuration with ℰℛℳ=PQRSSER_M=PQRS and ℰℛℐ=P′Q′R′S′SER_I=P Q R S . Here, (t0)=m2,m3W(t_0)=\m_2,m_3\. Under the shorter-side traversal rule for the non-square rectangle ℰℛℳSER_M, ΓSR _SR is the unique lexicographically smallest relevant Γ -string; hence, S is the pivot corner and c(t0)=m2W_c(t_0)=\m_2\. Moreover, αP′S′ _P S is the unique lexicographically smallest canonical traversal string of the entire configuration, so P′P is the anchor corner. The two enclosing rectangles are ℰℛℳ _M =PQRS=[−4,4]×[−2,2], =PQRS=[-4,4]×[-2,2], ℰℛℐ _I =P′Q′R′S′=[−4,4]×[−4,4]. =P Q R S =[-4,4]×[-4,4]. Consequently, P P =(−4,2), =(-4,2), Q Q =(−4,−2), =(-4,-2), R R =(4,−2), =(4,-2), S S =(4,2), =(4,2), P′ P =(−4,4), =(-4,4), Q′ Q =(−4,−4), =(-4,-4), R′ R =(4,−4), =(4,-4), S′ S =(4,4). =(4,4). Weber costs. The aggregate costs of the seven meeting nodes are ct0(m1) c_t_0(m_1) =4+6+10+10+2+10=42, =4+6+10+10+2+10=42, ct0(m2) c_t_0(m_2) =4+2+6+6+2+10=30, =4+2+6+6+2+10=30, ct0(m3) c_t_0(m_3) =8+6+2+2+6+6=30, =8+6+2+2+6+6=30, ct0(m4) c_t_0(m_4) =12+10+6+2+6+6=42, =12+10+6+2+6+6=42, ct0(m5) c_t_0(m_5) =8+6+10+10+2+6=42, =8+6+10+10+2+6=42, ct0(m6) c_t_0(m_6) =12+10+6+6+6+2=42, =12+10+6+6+6+2=42, ct0(m7) c_t_0(m_7) =14+12+8+4+8+4=50. =14+12+8+4+8+4=50. Therefore, (t0)=m2,m3. W(t_0)=\m_2,m_3\. The eight Γ -strings of ℰℛℳSER_M. The rectangle contains 9×5=459× 5=45 grid nodes. Assigning scan index 11 to the starting corner gives τ Order of the meeting nodes Γτ _τ PQ (m1,m5,m2,m6,m3,m7,m4)(m_1,m_5,m_2,m_6,m_3,m_7,m_4) (3,11,15,31,35,41,43)(3,11,15,31,35,41,43) PS (m5,m6,m7,m1,m4,m2,m3)(m_5,m_6,m_7,m_1,m_4,m_2,m_3) (3,7,9,19,27,39,43)(3,7,9,19,27,39,43) QP (m1,m2,m5,m3,m6,m4,m7)(m_1,m_2,m_5,m_3,m_6,m_4,m_7) (3,11,15,31,35,43,45)(3,11,15,31,35,43,45) QR (m2,m3,m1,m4,m5,m6,m7)(m_2,m_3,m_1,m_4,m_5,m_6,m_7) (3,7,19,27,39,43,45)(3,7,19,27,39,43,45) RQ (m3,m2,m4,m1,m7,m6,m5)(m_3,m_2,m_4,m_1,m_7,m_6,m_5) (3,7,19,27,37,39,43)(3,7,19,27,37,39,43) RS (m4,m7,m3,m6,m2,m5,m1)(m_4,m_7,m_3,m_6,m_2,m_5,m_1) (3,5,11,15,31,35,43)(3,5,11,15,31,35,43) SP (m7,m6,m5,m4,m1,m3,m2)(m_7,m_6,m_5,m_4,m_1,m_3,m_2) (1,3,7,19,27,39,43)(1,3,7,19,27,39,43) SR (m7,m4,m6,m3,m5,m2,m1)(m_7,m_4,m_6,m_3,m_5,m_2,m_1) (1,3,11,15,31,35,43)(1,3,11,15,31,35,43) Since ℰℛℳSER_M has dimensions 8×48× 4, the non-square-rectangle rule retains only the traversals parallel to its shorter side, namely PQ,QP,RSPQ,QP,RS, and SRSR. Among these four relevant strings, ΓSR<ΓPQ,ΓQP,ΓRS. _SR< _PQ, _QP, _RS. Hence, S is the unique pivot corner and SRSR is its traversal direction. Along SRSR, the two Weber Meeting Nodes occur in the order m3≺m2m_3 m_2. Since m2m_2 is the last one encountered, c(t0)=m2. W_c(t_0)=\m_2\. Although ΓSP<ΓSR _SP< _SR when all eight strings are compared, SPSP is not relevant to the pivot comparison because it is parallel to the longer side of the non-square rectangle. The eight α-strings of ℰℛℐSER_I. For each traversal τ, let ατ=(⟨ft0(u1τ),λt0(u1τ)⟩,…,⟨ft0(u81τ),λt0(u81τ)⟩), _τ= ( f_t_0(u_1^τ), _t_0(u_1^τ) ,…, f_t_0(u_81^τ), _t_0(u_81^τ) ), where ft0(u)=1,u∈ℳ,0,u∉ℳ,f_t_0(u)= cases1,&u ,\\ 0,&u , cases and λt0(u) _t_0(u) is the number of robots occupying u. Although each entry is written as ⟨ft0(u),λt0(u)⟩ f_t_0(u), _t_0(u) , the comparison first considers λt0(u) _t_0(u) and then ft0(u)f_t_0(u). The symbol ∣ below only separates consecutive parallel scan lines. αP′Q′= _P Q = (⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,1⟩∣ ( 0,0 , 0,0 , 0,0 , 0,0 , 1,0 , 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 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 ⟨0,0⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,1⟩∣ 0,0 , 0,0 , 1,0 , 0,0 , 0,1 , 0,0 , 1,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 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 ⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩∣ 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 ⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,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⟩,⟨1,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,1⟩∣ 0,1 , 0,0 , 1,0 , 0,0 , 0,0 , 0,0 , 1,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 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 OPEN⟨0,0⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨0,0⟩). 0,0 , 0,0 , 1,0 , 0,0 , 1,0 , 0,0 , 0,1 , 0,0 , 0,0 ). αP′S′= _P S = (⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨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,1 , 0,0 , 0,0 ⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩∣ 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,0⟩,⟨1,0⟩,⟨0,0⟩,⟨1,0⟩∣ 0,0 , 0,0 , 1,0 , 0,0 , 0,0 , 0,0 , 1,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,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 ⟨1,0⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨1,0⟩∣ 1,0 , 0,0 , 0,1 , 0,0 , 0,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,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,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,1⟩∣ 0,0 , 0,0 , 1,0 , 0,0 , 0,0 , 0,0 , 1,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 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 OPEN⟨0,1⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨0,0⟩). 0,1 , 0,0 , 0,1 , 0,0 , 0,0 , 0,0 , 0,1 , 0,0 , 0,0 ). αQ′P′= _Q P = (⟨0,1⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨1,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⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,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⟩,⟨1,0⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,0⟩∣ 0,1 , 0,0 , 1,0 , 0,0 , 0,1 , 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,0⟩∣ 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 ⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩∣ 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 ⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,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⟩,⟨1,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,1⟩∣ 0,1 , 0,0 , 1,0 , 0,0 , 0,0 , 0,0 , 1,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 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 OPEN⟨0,0⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,0⟩). 0,0 , 0,0 , 0,1 , 0,0 , 1,0 , 0,0 , 1,0 , 0,0 , 0,0 ). αQ′R′= _Q R = (⟨0,1⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨0,0⟩∣ ( 0,1 , 0,0 , 0,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⟩∣ 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,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,1⟩∣ 0,0 , 0,0 , 1,0 , 0,0 , 0,0 , 0,0 , 1,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 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 ⟨1,0⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨1,0⟩∣ 1,0 , 0,0 , 0,1 , 0,0 , 0,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,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,0⟩,⟨1,0⟩,⟨0,0⟩,⟨1,0⟩∣ 0,0 , 0,0 , 1,0 , 0,0 , 0,0 , 0,0 , 1,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,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 OPEN⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨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,1 , 0,0 , 0,0 ). αR′Q′= _R Q = (⟨0,0⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨0,1⟩∣ ( 0,0 , 0,0 , 0,1 , 0,0 , 0,0 , 0,0 , 0,1 , 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 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 ⟨0,1⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,0⟩∣ 0,1 , 0,0 , 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,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,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨1,0⟩∣ 1,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,1 , 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,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 ⟨1,0⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,0⟩∣ 1,0 , 0,0 , 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,0⟩∣ 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 OPEN⟨0,0⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩). 0,0 , 0,0 , 0,1 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 ). αR′S′= _R S = (⟨0,0⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,0⟩∣ ( 0,0 , 0,0 , 0,1 , 0,0 , 1,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,0⟩∣ 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 ⟨0,1⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,1⟩∣ 0,1 , 0,0 , 1,0 , 0,0 , 0,0 , 0,0 , 1,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 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 ⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩∣ 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 ⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,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⟩,⟨1,0⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,0⟩∣ 0,1 , 0,0 , 1,0 , 0,0 , 0,1 , 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,0⟩∣ 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 OPEN⟨0,1⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨1,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 ). αS′P′= _S P = (⟨0,0⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨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⟩,⟨0,0⟩,⟨0,0⟩,⟨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⟩,⟨1,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,0⟩∣ 1,0 , 0,0 , 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,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,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨1,0⟩∣ 1,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,1 , 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,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 ⟨0,1⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,0⟩∣ 0,1 , 0,0 , 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,0⟩∣ 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 OPEN⟨0,0⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨0,1⟩). 0,0 , 0,0 , 0,1 , 0,0 , 0,0 , 0,0 , 0,1 , 0,0 , 0,1 ). αS′R′= _S R = (⟨0,0⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,1⟩,⟨0,0⟩,⟨0,0⟩∣ ( 0,0 , 0,0 , 1,0 , 0,0 , 1,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⟩∣ 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 ⟨0,1⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,1⟩∣ 0,1 , 0,0 , 1,0 , 0,0 , 0,0 , 0,0 , 1,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 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 ⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩∣ 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 ⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩∣ 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,1⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,1⟩∣ 0,0 , 0,0 , 1,0 , 0,0 , 0,1 , 0,0 , 1,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 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 , 0,0 OPEN⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨1,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,0⟩,⟨0,1⟩). 0,0 , 0,0 , 0,0 , 0,0 , 1,0 , 0,0 , 0,0 , 0,0 , 0,1 ). The canonical string at each corner is αP′ _P =minαP′Q′,αP′S′=αP′S′, = \ _P Q , _P S \= _P S , αQ′ _Q =minαQ′P′,αQ′R′=αQ′P′, = \ _Q P , _Q R \= _Q P , αR′ _R =minαR′Q′,αR′S′=αR′Q′, = \ _R Q , _R S \= _R Q , αS′ _S =minαS′P′,αS′R′=αS′R′. = \ _S P , _S R \= _S R . Moreover, αP′S′=minαP′Q′,αP′S′,αQ′P′,αQ′R′,αR′Q′,αR′S′,αS′P′,αS′R′. _P S = \ _P Q , _P S , _Q P , _Q R , _R Q , _R S , _S P , _S R \. Therefore, P′ is the unique anchor corner, with direction P′S′. P is the unique anchor corner, with direction P S . Altogether, (t0)=m2,m3,c(t0)=m2,pivot corner=S,anchor corner=P′. gatheredW(t_0)=\m_2,m_3\, _c(t_0)=\m_2\,\\ pivot corner=S, corner=P . gathered Proof of the Crash-Induced Symmetry Impossibility Theorem 2.2 (Impossibility under weak multiplicity detection). There is no deterministic distributed algorithm that solves optimal Weber-meeting-node gathering for crash-faulty robots up to n−2n-2 operating under FSYNC with rigid movement, if robots are equipped only with weak multiplicity detection. Proof Assume that a deterministic distributed algorithm A solves optimal gathering under FSYNC activation and rigid movements using only global weak multiplicity detection. Let m1=(0,0)andm2=(8,0),m_1=(0,0)\ and\ m_2=(8,0), and consider the multiplicity-free initial configuration r1 r_1 =(2,0), =(2,0), r2 r_2 =(3,0), =(3,0), r3 r_3 =(4,0), =(4,0), r4 r_4 =(5,0), =(5,0), r5 r_5 =(6,0), =(6,0), r6 r_6 =(4,−2), =(4,-2), r7 r_7 =(3,1), =(3,1), r8 r_8 =(5,1), =(5,1), r9 r_9 =(3,−1), =(3,-1), r10 r_10 =(4,−1). =(4,-1). Let r1,r2,r4r_1,r_2,r_4, and r6r_6 be crash-faulty initially, hence 4≤n−2=10−2=84≤ n-2=10-2=8. The aggregate costs are ct0(m1)=45<47=ct0(m2),c_t_0(m_1)=45<47=c_t_0(m_2), so m1m_1 is the unique initial Weber Meeting Node. Consider the first FSYNC round C1C_1, in which the non-faulty robots make rigid one-hop moves toward m1m_1 and reach the following nodes: r3,r7,r9 r_3,r_7,r_9 ⟶p2=(3,0), p_2=(3,0), r10 r_10 ⟶q=(4,0), q=(4,0), r5,r8 r_5,r_8 ⟶p4=(5,0). p_4=(5,0). Let p1=(2,0)andp6=(4,−2).p_1=(2,0)\ and\ p_6=(4,-2). At the end of C1C_1, p2p_2 and p4p_4 are multiplicity nodes containing exactly four and three robots, respectively. Accordingly, with respect to the ordered nodes (p1,p2,q,p6,p4)(p_1,p_2,q,p_6,p_4), the exact multiplicity profile is Λ=(1,4,1,1,3) =(1,4,1,1,3) and total number of robots is 10=1+4+1+1+310=1+4+1+1+3. (a) (b) Figure 4: Immediately before the next round C2C_2, let r7r_7, r8r_8 and r9r_9 also get crashed. Thus, only r3,r5r_3,r_5, and r10r_10 remain non-faulty, and the total number of crash-faulty robots is 7≤n−2=8.7≤ n-2=8. Since the robots are equipped only with global weak multiplicity detection, they observe p2p_2 and p4p_4 as multiplicity nodes but cannot determine their exact multiplicities. Their weak multiplicity profile, with respect to the ordered nodes (p1,p2,q,p6,p4)(p_1,p_2,q,p_6,p_4), is therefore (1,,1,1,)(1, M,1,1, M). Even if the robots know that n=10n=10, the three singly occupied nodes p1p_1, q, and p6p_6 allow them to infer only that λ(p2)+λ(p4)=7λ(p_2)+λ(p_4)=7, where both λ(p2)λ(p_2) and λ(p4)λ(p_4) are at least two. Consequently, both distributions (2,5)(2,5) and (5,2)(5,2) are consistent with the same weak snapshot. Suppose that the computations of r5r_5 and r10r_10 are based on the compatible exact multiplicity profile Λr5=Λr10=(1,2,1,1,5) _r_5= _r_10=(1,2,1,1,5), whereas the computation of r3r_3 is based on the compatible profile Λr3=(1,5,1,1,2) _r_3=(1,5,1,1,2). In both cases, the entries of the profile sum to ten: 1+2+1+1+5=1+5+1+1+2=101+2+1+1+5=1+5+1+1+2=10. Consider an execution E of algorithm A and the FSYNC round C2C_2 occurring at time t′>t0t >t_0. Since all non-faulty robots are activated in this round, they perform their Look and Compute phases simultaneously. The computations of r5r_5 and r10r_10 are based on the compatible multiplicity profile Λr5=Λr10=(1,2,1,1,5) _r_5= _r_10=(1,2,1,1,5). For this profile, the current Weber costs are (ct′(m1),ct′(m2))=(43,41) (c_t (m_1),c_t (m_2) )=(43,41). Hence, both r5r_5 and r10r_10 identify m2m_2 as the unique Weber Meeting Node during their Compute phases. In contrast, the computation of the non-faulty robot r3r_3 is based on the compatible multiplicity profile Λr3=(1,5,1,1,2) _r_3=(1,5,1,1,2). In this case, the current Weber costs are (ct′(m1),ct′(m2))=(37,47) (c_t (m_1),c_t (m_2) )=(37,47). Therefore, r3r_3 identifies m1m_1 as the unique Weber Meeting Node. During the Move phase of the same round C2C_2, robot r3r_3, having identified m1m_1 as the unique Weber Meeting Node, makes at least one rigid hop toward m1m_1. In contrast, robots r5r_5 and r10r_10, having identified m2m_2 as the unique Weber Meeting Node, each make at least one rigid hop toward m2m_2. Thus, their first hops in round C2C_2 are r3:(3,0)⟶(2,0),r10:(4,0)⟶(5,0),r5:(5,0)⟶(6,0).r_3:(3,0) (2,0), r_10:(4,0) (5,0), r_5:(5,0) (6,0). At time t0t_0, m1m_1 was the unique Weber Meeting Node of the initial configuration. During round C1C_1, all non-faulty robots moved along shortest paths toward m1m_1. However, in round C2C_2, robots r5r_5 and r10r_10 move rightward toward m2m_2, thereby increasing their distances from m1m_1 by one. These movements do not lie on any shortest path from their initial positions to m1m_1. In fact, both robots first move one hop toward m1m_1 in round C1C_1 and then move one hop in the opposite direction in round C2C_2. This reversal adds at least two grid edges to the total distance traveled by each robot compared with a shortest path to m1m_1. Therefore, the min-sum optimality condition is violated as soon as r5r_5 and r10r_10 make their first rightward hops in round C2C_2. Thus, the indistinguishability of the exact multiplicity profiles under global weak multiplicity detection causes the non-faulty robots to move toward different meeting nodes, leading to a violation of the min-sum optimality condition. Consequently, algorithm A cannot solve optimal gathering in both indistinguishable executions. This completes the proof. ∎ Lemma 9 (Unsolvability when all robots on the symmetry line crash) Suppose that the initial entire configuration ℐ(t0)I(t_0) is symmetric with respect to a unique line ℒL, and that ℳ∩ℒ=∅M = . If all robots initially located on ℒL and crash before performing any move, while at least two robots outside ℒL remain non-faulty, then gathering all non-faulty robots at a meeting node is unsolvable. Consequently, gathering at a Weber Meeting Node is also unsolvable. Proof Consider an admissible execution in which all robots on ℒL crash before moving and the non-faulty robots outside ℒL are activated symmetrically. Since the robots are anonymous and deterministic, the reflectional symmetry with respect to ℒL is preserved throughout the execution. Therefore, any common gathering node must lie on ℒL. However, ℳ∩ℒ=∅M = , so no meeting node lies on ℒL. Hence, gathering at a meeting node is unsolvable. Since every Weber Meeting Node is a meeting node, optimal gathering at a Weber Meeting Node is also unsolvable. ∎ Lemma 10 (Unsolvability when the robot at the center of rotation crashes) Suppose that the initial entire configuration ℐ(t0)I(t_0) is rotationally symmetric about a center c, and that c∉ℳc . If the robot initially located at c crashes before performing any move, while at least two robots outside c remain non-faulty, then gathering all non-faulty robots at a meeting node is unsolvable. Consequently, gathering at a Weber Meeting Node is also unsolvable. Proof Consider an admissible execution in which the robot at c crashes before moving, while the non-faulty robots outside c are activated symmetrically. Since the robots are anonymous and deterministic, the rotational symmetry about c is preserved throughout the execution. Hence, any common gathering node must be fixed by the rotation and therefore must coincide with c. However, c∉ℳc , so c is not a meeting node. Thus, gathering at a meeting node is unsolvable. Since every Weber Meeting Node is a meeting node, gathering at a Weber Meeting Node is also unsolvable. ∎ Lemma 11 (Unsolvability when robots on two perpendicular symmetry lines crash) Suppose that the initial entire configuration ℐ(t0)I(t_0) is rotationally symmetric about a grid node c. Let ℒ1L_1 and ℒ2L_2 be two perpendicular grid lines passing through c, whose union is invariant under the same rotation. If every robot initially located on ℒ1∪ℒ2L_1 _2 crashes before performing any move, while at least two robots outside ℒ1∪ℒ2L_1 _2 remain non-faulty, then gathering all non-faulty robots at a meeting node is unsolvable. Consequently, gathering at a Weber Meeting Node is also unsolvable. Proof The crashed robots remain stationary, and their configuration on ℒ1∪ℒ2L_1 _2 preserves the rotational symmetry about c. The adversary can activate the non-faulty robots outside these lines in symmetric groups, thereby preserving the same rotational symmetry throughout the execution. Hence, any common gathering node must be fixed by the rotation and must therefore coincide with c. Since c∉ℳc , gathering at a meeting node is impossible. Consequently, gathering at a Weber Meeting Node is also impossible. ∎ In the remainder of the paper, we assume that whenever an initial configuration admits a unique line of symmetry ℒL, the line ℒL passes through grid nodes. Similarly, whenever an initial configuration admits a nontrivial rotational symmetry, its center of rotation is a grid node. Let ℐ(t0)I(t_0) denote the set of all initial configurations, and let ⊆U denote the set of initial configurations from which gathering is impossible, as established by Lemmas 9–11. Thus, ℐ(t0)∖I(t_0) denotes the set of initial configurations considered for the proposed gathering algorithm. Figure 5: Target-dependent restricted shortest paths. Robot r may follow one of the purple paths through S or r′r toward m1m_1. The red path through r′r leads toward the reflected candidate m2m_2. Full Correctness Proofs For readability, each result stated in the main correctness section is restated before its complete proof. Lemma 1 (Uniqueness of the target region). For every configuration in ℐ321I_321, ℐ322I_322, or ℐ323I_323, Phase I-A uniquely selects one of ℬ1B_1 and ℬ2B_2. For every configuration in ℐ4211I_4211, ℐ42121I_42121, ℐ42122(1)I_42122^(1), ℐ42122(2)I_42122^(2), ℐ42122(3)I_42122^(3), ℐ4221I_4221, or ℐ42221I_42221, it uniquely selects one of 1,…,4Q_1,…,Q_4. Proof Consider first the reflectional classes. Phase I-A initially compares ω1 _1 and ω2 _2. If ωi>ωj _i> _j, then ℬiB_i is uniquely selected. If ω1=ω2 _1= _2, the two half-planes are compared by their robot occupancies. Thus, νi>νj _i> _j uniquely determines ℬ†=ℬiB =B_i. Suppose that both comparisons are tied. In ℐ321I_321, the entire configuration is asymmetric and therefore has a unique anchor corner. Exactly one of the two half-planes does not contain this corner, and hence the prescribed rule selects it uniquely. For ℐ322I_322, if ℰℛℐ(t)=ℰℛℳSER_I(t)=SER_M, the strings αPS _PS and αPQ _PQ are compared. These strings cannot be equal, since their equality would imply identical meeting-node indicators and robot multiplicities at every pair of nodes related by reflection across ℒL. Consequently, the entire configuration would be reflectionally symmetric. Therefore, exactly one of ℬPSB_PS and ℬPQB_PQ is selected. If ℰℛℳ⊊ℰℛℐ(t)SER_M _I(t), the unequal values of η1 _1 and η2 _2 determine the target half-plane uniquely. When η1=η2 _1= _2, equality of the two prescribed canonical strings from the anchor corner would again imply reflectional symmetry of the entire configuration. Hence, their lexicographic comparison is strict. The same argument applies to ℐ323I_323. If the two enclosing rectangles coincide, equality of the two pivot-corner strings compared by the rule would imply reflectional symmetry. Otherwise, an unequal grid-node counts determine the target half-plane, and a remaining tie is resolved by the two canonical strings associated with the unique anchor corner. Since the configuration is asymmetric, these strings are distinct. Thus, each reflectional class selects exactly one of ℬ1B_1 and ℬ2B_2. For ℐ4211I_4211, the uniqueness of †Q follows from the unique maximum candidate count. For ℐ42121I_42121 and ℐ4221I_4221, it follows from the unique maximum occupancy among the specified quadrants. In each subclass of ℐ42122I_42122 and in ℐ42221I_42221, the remaining tied quadrants are compared by the prescribed α- or β-strings. If two distinct competing corners had the same final string, then the entire configuration would admit the corresponding rotational symmetry, which contradicts the assumption that the configuration is asymmetric. Hence, the final comparison is strict and exactly one quadrant is selected. Lemma 2 (Uniqueness of the target node). For every solvable configuration, Phase I determines exactly one target Weber Meeting Node m†∈(t)m (t) from the current snapshot. Proof In ℐ1I_1, the single node of (t)W(t) is selected. In ℐ2I_2, the asymmetry of ℳM determines a unique canonical traversal and hence a unique outcome of the prescribed candidate-selection rule. For ℐ31I_31, the rule for the reflection axis, together with the anchor-corner rule when two candidates occur, selects exactly one node. In ℐ41I_41, the algorithm selects the rotation center c as a Weber Meeting Node; however, this does not imply that c is the unique Weber Meeting Node. For ℐ321I_321, ℐ322I_322, and ℐ323I_323, Lemma 1 first provides a unique target half-plane ℬ†B . The set c(t)∩ℬ†W_c(t) is nonempty. If the set contains only one element, that element is selected. If it contains two candidates, the fixed traversal direction of ℬ†B uniquely determines the first candidate encountered. For ℐ4211I_4211, ℐ42121I_42121, and the three subclasses of ℐ42122I_42122, Lemma 1 gives a unique †Q . Candidates in †W are first compared according to their distance from p†p . If a tie remains, their distance from ℒ1++L_1^++ is used, and the conditions of the class ensure that the selected candidate is unique. For ℐ4221I_4221 and ℐ42221I_42221, the selected quadrant and asymmetry determine a unique canonical traversal. Since ¯†≠∅ W ≠ , the first node of this set encountered by that traversal is well defined and unique. These rules depend only on coordinate-invariant distances and canonical strings. Therefore, all robots observing the same snapshot select the same meeting node m†m . Lemma 3 (Invariance of the selected half-plane). Let ℬ†B be the target half-plane selected from a configuration in ℐ321I_321, ℐ322I_322, or ℐ323I_323. If every subsequent move follows MoveToDestination(), every configuration reached during Phase I selects the same half-plane ℬ†B . Proof Let ℬB be the half-plane different from ℬ†B . By MoveToDestination(), a robot in ℬ†B never enters ℬB. A robot in ℬB may cross ℒL only to enter ℬ†B , and once it crosses, it cannot return. Similarly, a robot on ℒL may leave the line only toward ℬ†B . Hence, the occupancy of ℬ†B cannot decrease. Consider the first criterion of Phase I-A that distinguishes the two half-planes. If the comparison is based on occupancy, the monotonicity established above preserves the strict inequality. If it is based on one of the prescribed geometric sums, every allowed move preserves the inequality favoring ℬ†B . Finally, if the selection is based on canonical strings, the restricted paths preserve the first differing entry that favors ℬ†B , or create an earlier differing entry with the same preference. Moreover, no robot moves to an earlier position in the traversal of ℬB. Thus, the first strict comparison cannot reverse after a completed move. Induction over completed moves proves that every subsequent snapshot selects ℬ†B . Lemma 4 (Invariance of the selected quadrant). Let †Q be the target quadrant selected at the beginning of Phase I. Every subsequent configuration reached during Phase I selects the same quadrant †Q . Proof Under the prescribed paths, a robot in †Q remains there. A robot in a quadrant adjacent to †Q can enter it only across their common boundary, whereas a robot in the opposite quadrant must pass through c. Once a robot enters †Q , it remains there. Robots on the bounding lines are treated according to the same convention in every snapshot. Consequently, no move transfers a robot from †Q to a non-selected open quadrant. Fix ≠†Q and consider the first criterion that distinguishes them. For a comparison based on the distribution of candidates, Lemma 8 ensures that no new Weber Meeting Node is created, while m†m remains associated with †Q . Hence, the class-specific pairing of candidates cannot make Q preferable to †Q . For an occupancy comparison, the prescribed transfers do not decrease the occupancy of †Q or increase that of Q. If the first distinction is an α- or β-string, the restricted paths preserve the first unequal entry favoring †Q or replace it with an earlier entry having the same preference. Hence, the first strict criterion cannot reverse. This holds for every non-selected quadrant and after every completed move, so †Q remains selected. Lemma 5 (Invariance of the selected target). Let m†m be selected from ℐ(t)I(t). If every move completed after time t follows MoveToDestination() toward m†m , then every subsequent snapshot selects the same target m†m . Proof By Lemmas 3 and 4, the selected region does not change. These lemmas also preserve every anchor-based comparison used in selecting that region. Furthermore, the symmetry axes, rotation center, pivot corners, boundary half-lines, and meeting-node traversal directions depend only on the fixed meeting-node set ℳM. Every completed move is a shortest-path hop toward m†m . Lemma 8 therefore implies, for every subsequently reached ℐ(t′)I(t ), m†∈(t′)m (t ) and (t′)⊆(t)W(t ) (t). Thus, m†m remains eligible and no new candidate can appear. Under a distance-based rule, deleting other candidates cannot create a candidate preceding m†m in the fixed distance order. Under a traversal-based rule, no earlier node can become a new candidate. The applicable rule consequently selects m†m in every subsequent snapshot. Lemma 6 (Independent progress under crash faults). Let r∉ℱr be a non-faulty robot activated at time t, with r(t)≠m†r(t)≠ m , and let t′>t >t be the time at which it completes the move prescribed by MoveToDestination(). Then d(r(t′),m†)≤d(r(t),m†)−1d(r(t ),m )≤ d(r(t),m )-1. The completion of this move does not require the activation or movement of any other robot. Proof By Lemma 5, every snapshot observed by r yields the same target m†m . The routine MoveToDestination() prescribes a movement contained in a Manhattan shortest path toward m†m . Since a completed movement advances r by at least one grid edge along this path, d(r(t′),m†)≤d(r(t),m†)−1d(r(t ),m )≤ d(r(t),m )-1. The prescribed destination is computed from the snapshot available to r and does not require another robot to move first. A crash-faulty robot remains fixed at its last position. Since a grid node may contain multiple robots, such a stationary robot neither blocks the prescribed path nor prevents r from entering an occupied node. Therefore, r completes its distance-decreasing movement independently of the activation or movement of every other robot. Lemma 7 (Finite-time gathering). Under every fair asynchronous schedule, all non-faulty robots reach m†m after finitely many completed moves and remain there. Proof Let Φ(t)=∑r∉ℱd(r(t),m†) (t)= _r d(r(t),m ), where the sum is over the robots that never crash. Since the number of robots and all grid distances are finite, Φ(t0) (t_0) is a finite non-negative integer. Consider a completed move of a non-faulty robot outside m†m . By Lemma 6, the contribution of that robot to Φ decreases by at least one. Every other completed movement also moves its robot toward m†m and therefore cannot increase Φ . Consequently, after each such completed move from time t to time t′t , Φ(t′)≤Φ(t)−1 (t )≤ (t)-1. Suppose that Φ(t)>0 (t)>0. Then at least one non-faulty robot is outside m†m . By Lemma 6, this robot does not wait for another robot, and fairness ensures that it is activated again and completes another prescribed move. Hence, Φ cannot remain positive after Φ(t0) (t_0) distance-decreasing completed moves. Therefore, every non-faulty robot reaches m†m after finitely many completed moves. Once there, it remains stationary by MoveToDestination().