Brief Announcement: Anonymous Distributed Localisation via Spatial Population Protocols

Location services are vital for modern computing paradigms like pervasive computing and sensor networks. Manual configuration and GPS, though effective for determining node locations, are impractical in large-scale or obstructed environments. Recent network localisation approaches use beacon nodes with known positions to help other nodes estimate their locations via distance measurements. Key challenges include ensuring unique localisability, managing computational complexity, and addressing deployment issues. In the distributed localisation problem (DLP), $n$ anonymous robots (agents) $A_0,\mathrm{\dots },A_{n-1}$ begin at arbitrary positions $p_0,\mathrm{\dots },p_{n-1}\in S$, where $S$ is an Euclidean space. Initially, each agent $A_i$ operates within its own coordinate system in $S$, which may be inconsistent with those of other agents. The primary goal in DLP is for agents to reach a consensus on a unified coordinate system that accurately reflects the relative positions of all points, $p_0,\mathrm{\dots },p_{n-1}$, in $S$.

A network of agents’ unique localisability is determined by specific combinatorial properties of its graph and the number of anchors (agents aware of their real location). For example, graph rigidity theory [2, 5, 6] provides a necessary and sufficient condition for unique localisability [2]. Specifically, a network of agents located in the plane is uniquely localisable if and only if it has at least three anchors and the network graph is globally rigid. However, unless a network is dense and regular, global rigidity is unlikely. Even without global rigidity, large portions of a network may still be globally rigid, though the positions of remaining nodes will remain indeterminate due to multiple feasible solutions. The decision version of this problem, often referred to as the graph embedding or graph realisation problem, requires determining whether a weighted graph can be embedded in the plane so that distances between adjacent vertices match the edge weights, a problem known to be strongly NP-hard [14]. Furthermore, this complexity holds even when the graph is globally rigid [2]. In sensor networks, where nodes measure distances only within a communication range $r$, the network is best represented as a unit disk graph. Here, two nodes are adjacent if and only if their distance is $\le r$. The corresponding decision problem, known as unit disk graph reconstruction, requires determining whether a graph can be embedded in the plane such that distances between adjacent nodes match edge weights, while distances between non-adjacent nodes exceed $r$. This problem is also NP-hard [1], indicating that no efficient algorithm can solve localisation in the worst case unless $P=NP$. Furthermore, even for instances with unique reconstructions, no efficient randomised algorithm exists to solve this problem unless $RP=NP$ [1].

Distributed localisation is also crucial in robotic systems, enabling robots to autonomously determine their spatial position within an environment – a fundamental requirement for applications such as navigation, mapping, and multi-robot coordination [18]. Accurate localisation allows robots to interact more effectively with their surroundings and with each other, facilitating tasks from autonomous driving to warehouse automation and search-and-rescue operations [10, 12]. Localisation approaches generally fall into two broad categories: centralised and distributed systems [19]. Centralised localisation systems offer high accuracy but may struggle with scalability and robustness [9]. In contrast, distributed localisation systems allow each robot to perform localisation computations independently or in collaboration with neighbouring robots, enhancing adaptability and resilience, although this may come at the cost of increased complexity [7, 8]. Within distributed systems, leader-based localisation mechanisms involve one or more designated robots that serve as reference points or coordinators for localisation [3], which can streamline computations but may create single points of failure. Leaderless localisation, where all robots contribute equally to position estimation without relying on specific leader nodes, is advantageous in decentralised applications where flexibility and fault tolerance are paramount [7, 15]. Both methods have been explored using probabilistic [17], geometric [11], and graph-based models [7], with leaderless approaches gaining traction due to their robustness in large-scale and dynamically changing settings. Various methods leverage tools such as Kalman filters [13], particle filters [9], and graph rigidity theory [16] to enhance localisation accuracy and efficiency in complex environments.

In this section, we discuss a localisation protocol with predefined input stabilising in $o(n)$ time, i.e., after this time labels of all agents become stable. This protocol is non-self-stabilising. We assume that one of the agents starts as the leader of the population. If the identity of the leader is not known, the localisation protocol can be preceded by one of the leader election protocols discussed in the introduction. The agents’ positions $p_0,\mathrm{\dots },p_{n-1}$ are distributed in a $k$-dimensional Euclidean space $S$, where $k$ is a fixed integer. It is assumed that any $k+1$ agents’ positions span the entire space. For example, in two-dimensional space, this assumption guarantees that no three points are collinear. Although our algorithms can be adapted to handle an arbitrary distribution of agents’ positions, the time guarantees of such adaptations would be weaker. The state of an agent can accommodate a fixed number of agent positions and distances.

We adopt a symmetric model of communication, which means that when agents $A_u$ and $A_v$ interact, they both gain access to each other’s states as well as the distance $d_{uv}$. The transitions assigned to the leader are distinct from those of the other agents, and the leader also serves as the initiator of the entire process. Initially, the state of each agent $A_u$ stores a label $x_u$ (representing a hypothetical position in $S$) and its color $C[A_u]$. We assume that at the beginning, the leader is coloured green, and each non-leader’s colour is set to blue. Finally, the leader’s label (position in $S$) is set at the origin of the coordinate system, i.e., this label is used as the anchor in the localisation process.

In this paper, we introduce a novel variant of spatial population protocols and explore its applicability to the distributed localization problem. In the full version of this paper [4], we explore faster leader-based localisation in one-dimensional space using the model with distance queries, alongside superfast localisation in the model with vector queries. Any meaningful advances in this problem could pave the way for developing faster and more robust lightweight communication protocols suitable for real-world applications. It could also provide insights into the limitations of what can be achieved in such systems.