Asynchronous Rendezvous of Anonymous Deterministic Mobile Automata in the Plane

Meeting of mobile agents in some point of the environment is a classic task, called rendezvous or gathering, studied in distributed mobile agents computing. Agents are mobile entities that may represent software agents or mobile robots, and the environment may be a communication network or a terrain in the plane. The aim of rendezvous may be exchanging information between the agents, or planning future collaborative actions. Since mobile agents are often relatively simple devices, it is natural to model them computationally as deterministic finite automata.

There are two mobile agents, modeled as points moving in the plane, and starting at two different points, chosen by the adversary. The actions of the agents are modeled by the same deterministic finite automaton, i.e., agents are anonymous and identical. Each agent has a compass showing the cardinal directions. Each agent makes a series of steps. At the beginning of each step, it takes a snapshot, which is the disc of radius 1 centered at the current position of the agent. Intuitively, the agent “sees” the part of the plane at distance 1 from its current position. The information contained in the snapshot (to be specified below) is an input that causes the automaton to possibly change state and make the next move in a chosen direction at a chosen distance. Moves of the agents are asynchronous: the adversary controls the possibly variable speed of an agent during each move. Without the possibility of leaving marks, meeting is often impossible, even if agents were modeled by identical Turing machines. Indeed, if agents start simultaneously at a distance larger than 1 and move at the same speed, then their trajectories are shifts of each other, and they could never meet. Hence we allow the agents to use movable pebbles. All pebbles used by an agent are identical and they differ between the agents. A pebble of an agent can be dropped by it, and later possibly picked again. In each snapshot $\mathrm{\Sigma }$ taken by an agent, the location of all pebbles of the agent (called domestic pebbles) in $\mathrm{\Sigma }$, all pebbles of the other agent (called foreign pebbles) in $\mathrm{\Sigma }$, and (possibly) the location of the other agent in $\mathrm{\Sigma }$ are the input of the agent in the current step.

In any step, the agent is in some state $S$, and it is located in some point $v$ of the plane. The snapshot $\mathrm{\Sigma }$ taken by the agent gives it the input $I=(D,F,A)$, where $D$ is the set of coordinates of the domestic pebbles within $\mathrm{\Sigma }$, $F$ is the set of coordinates of the foreign pebbles within $\mathrm{\Sigma }$, and $A$ is the at most one-element set of coordinates of the other agent within $\mathrm{\Sigma }$, with respect to the current position of the agent. Each of the sets $D$, $F$, and $A$ may be empty. In particular, if there is a (domestic or foreign) pebble at the current position of the agent, we say that the agent hits this pebble. The input $I$ causes the agent to transit from state $S$ to some state $S^{\prime }$. Also, an agent in state $S$ with input $I$ produces an output $(\alpha ,\delta ,\varphi )$, where $\alpha \in \{pick,drop,leave\}$ is a pebble action, $\delta >0$ is a distance, and is an angle. This output causes the following behavior of the agent in the given step.

First we describe the pebble action $\alpha$. If the agent hits a domestic pebble then it may either pick it or perform the action leave, not changing the pebble configuration. If the agent hits a foreign pebble then it must perform the action leave, not changing the pebble configuration. If the agent does not hit a pebble at its current position $v$, it may either drop a pebble in point $v$, or perform the action leave, not changing the pebble configuration. (The agent cannot drop a pebble if there is already a pebble at its current position, and it cannot pick up a foreign pebble). The other two parameters of the output describe the move of the agent in the current step. The agent goes to the point $v^{\prime }$ at distance $\delta$ in the direction given by angle $\varphi$ with respect to North. At the beginning of the next step, the agent is at point $v^{\prime }$ in state $S^{\prime }$. The trajectory of the agent is the sequence of above described steps until rendezvous.

It should be stressed that the output of the agent and the state to which it transits depend both on the current input and the current state. It is important to explain the dependence on the input, i.e., on the current snapshot. Suppose that the agent is at a point $v$ and there is a single foreign pebble in the snapshot, located at point $v^{\prime }$. Then the agent can get to point $v^{\prime }$ by measuring the distance $\delta$ between $v$ and $v^{\prime }$, the angle between North and the vector $(z,z^{\prime })$ and outputting $(\cdot ,\delta ,\varphi )$. Now suppose that the agent wants to return to point $v$. However, if it didn’t drop any pebble at $v$, such a return is not possible, as the agent does not have any way to specify point $v$ standing at $v^{\prime }$: there is nothing in its current snapshot to distinguish $v$, and, in general, the position of $v$ cannot be “remembered” in some state to which the agent might transit. Of course, a finite number of vectors can be “remembered” using prepared states but, as the location of the foreign pebble at $v^{\prime }$ could not be predicted at the time of the automaton design, there may be no state of the automaton allowing it to return from $v^{\prime }$ to $v$. Thus, in order to guarantee a return to $v$, the agent should drop a pebble at $v$ and then use the snapshot at $v^{\prime }$ to get back to $v$.

We now formalize the above intuitive description. Let $Inputs$ be the family of all possible inputs which are triples $(D,F,A)$, where $D$ and $F$ are finite sets of points and $A$ is a set of points of size at most 1, within a disc of radius 1. Each of these points is represented by cartesian coordinates of the respective points in the system of coordinates with origin at the current position of the agent. Let $\{e,d,f\}$ be the set of three possibilities for the current position $v$ of the agent: $e$ indicates that there is no pebble in $v$ ($v$ is empty), $d$ indicates that there is a domestic pebble in $v$, and $f$ indicates that there is a foreign pebble in $v$. Let $PebbleActions=\{pick,drop,leave\}$.

The actions of the mobile agent are formalized as a finite deterministic Mealy automaton $𝒜=(X,Y,Q,\delta ,\lambda ,S_0)$. $X=Inputs$ is the input alphabet, $Y=PebbleActions\times R^{+}\times [0,2\pi )$ is the output alphabet, where $R^{+}$ denotes the set of positive reals. $Q$ is a finite set of states with two special states: $S_0$ called initial and $S_f$ called final. The automaton starts in state $S_0$. $\sigma :Q\times X\to Q$ is the state transition function, and $\lambda :Q\times X\to Y$ is the output function.

The meaning of the input and output symbols is the following. In each step of its functioning, the agent is in some point $v$ of the plane, in some state $S$. It gets the input $I\in Inputs$, from the snapshot at the current point. In particular, from this input $I$, it learns the value $b\in \{e,d,f\}$, concerning the presence or absence of a (domestic or foreign) pebble in $v$. Given the state $S$ and the input $I$, the agent outputs the symbol $\lambda (S,I)\in PebbleActions\times R^{+}\times [0,2\pi )$ with the following meaning. The first term indicates the pebble action performed by the agent in the current step. The second and third term indicate the distance at which the agent should go and the angle between North and the move direction, respectively.

Since we imposed restrictions on pebble actions, we have the following restrictions on the possible values of the output function $\lambda$. Let $I\in Inputs$, let $b\in \{e,d,f\}$ be the value learned from $I$, and let $\lambda (S,I)=(\alpha ,\delta ,\varphi )$.

• $\mathrm{■}$

  if $b\ne e$ (there is a pebble at the current position of the agent) then $\alpha \ne drop$ (the agent cannot drop a pebble if there is already a pebble at its current position);

• $\mathrm{■}$

  if $b=e$ (there is no pebble at the current position of the agent) then $\alpha \ne pick$ (the agent cannot pick up a pebble from an empty point);

• $\mathrm{■}$

  if $b=f$ (there is a foreign pebble at the current position of the agent) then $\alpha \ne pick$ (the agent cannot pick up a foreign pebble);

Given the input symbol $I$ and being in a current state $S$, the agent makes the changes indicated by the output function (it possibly drops or picks up a pebble as indicated, and goes to the indicated point of the terrain), and transits to state $\sigma (S,I)$. The agent starts in the initial state $S_0$, and its starting point is empty. In some step, the agent transits to the final state $S_f$, halts and remains in this state forever. If rendezvous occurs “accidentally” before at least one of the agents transits to the final step, both agents instantly recognize this event, and they stop.

Our main result shows that, using finitely many pebbles, asynchronous rendezvous of identical anonymous agents modeled by a deterministic finite automaton is always possible, regardless of the actions of the adversary. While we did not try to minimize the number of pebbles used, in our solution each agent uses at most 8 pebbles. The cost of a rendezvous algorithm executed by the agents is the worst-case length of the trajectory of both agents, over all adversary’s decisions. We show that our rendezvous algorithm has cost $O(D^2)$, if the initial positions of the agents are at distance at most $D$. We observe in Section 5 that this cost is optimal.

As a by-product, we obtain the solution of the leader election problem between two anonymous agents modeled as automata asynchronously navigating in the plane. In this problem, one of the identical agents must become a leader, and the other a non-leader.

The fundamental task of getting several mobile agents to the same place in some environment, called rendezvous or gathering, has been thoroughly investigated in distributed computing literature. The environment where agents operate may be either a network modeled as a graph, or a terrain in the plane. In the graph scenario, it is often assumed that nodes do not have distinct identities, and agents cannot mark nodes, although rendezvous was also considered in labeled graphs [7, 15], or when agents can mark nodes using tokens [13, 14]. A survey of randomized rendezvous in various models of the environment is provided in [1], while deterministic rendezvous in graphs has been surveyed in [16].

A large part of the literature on rendezvous in graphs assumed the synchronous scenario, where agents move in rounds. In [17], the authors presented rendezvous algorithms with time polynomial in the size of the graph and the length of agents’ labels. The amount of memory required by the agents to achieve deterministic rendezvous was investigated in [8] for arbitrary finite graphs. The authors showed that $\mathrm{\Theta }(\log n)$ memory is necessary and sufficient to meet in all graphs with at most $n$ nodes.

Synchronous rendezvous was also studied in infinite graphs. Under this scenario, it was usually assumed that agents have distinct identities but cannot mark the visited nodes. In [7], the authors considered rendezvous in infinite trees and grids, assuming that the agents know their location in the environment. In [4], the authors presented a rendezvous algorithm working for arbitrary, even infinite, graphs. In the above papers, agents were modeled as Turing machines, without any memory limitations. Gathering several agents modeled as deterministic finite automata navigating in an infinite line was studied in [11].

Rendezvous in the infinite oriented grid is particularly important because it is closely related to the problem of approach in the plane, in which agents equipped with compasses start in arbitrary points of the plane, and have to get at a distance at most 1. Rendezvous in the grid implies approach in the plane, hence it was studied by many authors under various scenarios [3, 5, 12]. In [12], the authors assumed that agents are anonymous but they leave a trace after visiting each previously not visited node.

Asynchronous rendezvous was considered both in graphs and in the plane. In graphs, the agent chooses the edge to traverse, but the adversary controls the speed of the agent, and agents are permitted to meet inside an edge. In [3], the authors proposed almost optimal algorithms for asynchronous rendezvous in infinite multidimensional grids, under a strong assumption that an agent knows its position in the grid. In [5, 9] the authors used a much weaker assumption that agents have distinct identities. In [5], a polynomial-cost algorithm was designed for the infinite oriented two-dimensional grid, and in [9] – for arbitrary finite graphs.

The problem of gathering and of approach in the plane was considered under various scenarios. In [5], approach was considered under the assumption of total asynchrony. Agents could not mark nodes but they had distinct labels. In [6, 10] the authors considered asynchronous gathering of many mobile agents in the plane, according to the Look-Compute-Move model, where decisions of the agents may depend only on the current snapshot. In [10], the agents have limited visibility, and in [6] they can see all other agents. In the above cited papers, the computational capacity of the agent was not limited. To the best of our knowledge, the problem of asynchronous rendezvous in the plane of anonymous agents modeled as deterministic finite automata, has never been investigated before.

Consider the squares that are traversed by the agent in the first parts of two consecutive phases of the algorithm. Define a frame to be the subset of the plane between those squares. The frame consists of four corner squares with diagonals joining, respectively, the northern, eastern, southern and western corners of the squares forming the frame, and of four side rectangles between consecutive corner squares (see Fig. 3). Thus any stick $s$ satisfies at least one of the following conditions:

1. 1.

   $s$ intersects one of the corner squares of a frame $f$,

2. 2.

   $s$ is included in some side rectangle $R$ of a frame $f$,

3. 3.

   $s$ crosses a side of a side rectangle $R$ that $R$ does not share with any corner square.

Fix a stick $s$. First note that if $s$ intersects a corner square then $s$ is in the snapshot of the agent when this agent is at one of the vertices of this square. Hence, we may assume that either condition 2 or 3 is satisfied. There are two cases. If $R$ is the southwestern or the northeastern side rectangle then $s$ is perpendicular to the southwestern and northeastern sides of $R$, and if $R$ is the northwestern or the southeastern side rectangle then $s$ is parallel to the northwestern and southeastern sides of $R$. We will consider these cases separately and prove that, in each of them, the stick $s$ will be in some snapshot of the agent during its traversal of one of the squares limiting the frame $f$.

$R$ is the southwestern or the northeastern side rectangle.

Without loss of generality, suppose that $R$ is the southwestern side rectangle. $s$ is perpendicular to the southwestern and northeastern sides of $R$. Either $s$ is included in $R$ or $s$ crosses the southwestern or the northeastern side of $R$. In the first case, let $\mathrm{\ell }$ be the southwestern side of the smaller square limiting the frame $f$, and in the second case let $\mathrm{\ell }$ be the side of $R$ crossed by $s$. Suppose that $s$ is not included in any snapshot of the agent during its traversal of $\mathrm{\ell }$.

Let $w$ be the endpoint of $s$ farther from $\mathrm{\ell }$. Let $w^{\prime }$ be intersection of $\mathrm{\ell }$ with the line perpendicular to $\mathrm{\ell }$, passing through $w$. Then there are two consecutive steps in the traversal of $\mathrm{\ell }$ by the agent, such that, in those steps, the agent is on different sides of $w^{\prime }$, in points $v_1$ and $v_2$, respectively, and both distances $a_1=dist(v_1,w)$ and $a_2=dist(v_2,w)$ are larger than 1 (the agent cannot see the point $w$). Let $b_1=dist(v_1,w^{\prime })$ and $b_2=dist(v_2,w^{\prime })$. We have: $b_1+b_2=2\sqrt{2}/3$ (the length of one step on $\mathrm{\ell }$). The inequality $dist(w,w^{\prime })\le \sqrt{2}/3$ ($\sqrt{2}/3$ is the width of the frame) implies: $a_1=\sqrt{b_1^2+dist{(w,w^{\prime })}^2}\le \sqrt{b_1^2+2/9}$, and $a_2=\sqrt{b_2^2+dist{(w,w^{\prime })}^2}\le \sqrt{b_2^2+2/9}$. Hence,

which is a contradiction.

$R$ is the northwestern or the southeastern side rectangle.

Without loss of generality, suppose that $R$ is the northwestern side rectangle. Now $s$ is parallel to the northwestern and the southeastern sides of $R$. Let $t$ be the northwestern side of the smaller square limiting the frame $f$, and let $w$ and $w^{\prime }$ be, respectively, the southwestern and northeastern endpoints of $s$. Let $u$ and $u^{\prime }$ be the intersections of $t$ with the lines perpendicular to $t$, passing through $w$ and $w^{\prime }$, respectively.

Two subcases are possible.

There are two consecutive steps in the traversal of $t$ by the agent, such that, in those steps, the agent is on different sides of the segment $u{u}^{\prime }$, in points $v_1$ and $v_2$, respectively (cf. Fig. 4 (A)).

Suppose that both distances $a_1=dist(v_1,w^{\prime })$ and $a_2=dist(v_2,w)$ are larger than 1 (the agent cannot see the respective points). Let $b_1=dist(v_1,u^{\prime })$ and $b_2=dist(v_2,u)$. We have (the length of one step on $t$ plus the length of the stick). As before, the inequality $dist(u,w)=dist(u^{\prime },w^{\prime })\le \sqrt{2}/3$ ($\sqrt{2}/3$ is the width of the frame) implies: $a_1=\sqrt{b_1^2+dist{(u^{\prime },w^{\prime })}^2}\le \sqrt{b_1^2+2/9}$, and $a_2=\sqrt{b_2^2+dist{(u,w)}^2}\le \sqrt{b_2^2+2/9}$. Hence,

which is a contradiction.

There is a step in the traversal of $t$ by the agent, in which the agent is in a point $v$ in the segment $u{u}^{\prime }$ (cf. Fig. 4 (B)).

Suppose that both distances $a_1=dist(v,w^{\prime })$ and $a_2=dist(v,w)$ are larger than 1 (the agent cannot see the respective points). However, for $i=1,2$ we have , which is a contradiction.

Hence we have shown that during the traversal of the square in the first part of some phase of the algorithm (if the phases were not interrupted before), $s$ is included in some snapshot of the agent. It remains to estimate the phase when this happens. By assumption, the southwestern endpoint of the stick $s$ is at distance at most $D$ from the starting point of the agent executing the algorithm. Since sides of squares traversed in consecutive phases increase by the constant summand $2\sqrt{2}/3$, and they are all centered at the starting point of the agent, it follows that the stick $s$ is included in the square traversed in some phase $p\in O(D)$, and hence $s$ is included in some snapshot of the agent by the end of phase $p$. $◀$

Using Lemma 1 we can now prove the main result of this section.

Consider either of the two agents, call it $a$. Let $b$ be the other agent. Let $z$ be the starting point of $a$ and $z^{\prime }$ the starting point of $b$. By the description of the algorithm, agent $a$ iterates procedure Phase until one of the two events, Base or Agent, happens. By Lemma 1, there exists a phase $p\in O(D)$ such that, if phases were not interrupted earlier by one of the above events, the stick $s$ with southwestern endpoint $z^{\prime }$ would be in some snapshot of agent $a$ by the end of phase $p$. At this time, either the base of agent $b$ has been already created, which means that event Base happened, or agent $b$ is in the process of creating its base and is in the snapshot of $a$, which means that event Agent happened. This implies that, by the end of phase $p$, one of the above events must happen (if agents haven’t accidentally met before).

If event Base happened then agent $a$ decides which of the two points, $z$ or $z^{\prime }$ is dominating, goes to the dominating point and stops. In any case, the remaining part of the trajectory of agent $a$ has length $O(D)$. If event Agent happened, there are two possibilities. Either agent $a$ discovers the base of $b$ after making some additional constant-length traversal and then acts as in the case of event Base (goes to the dominating starting point and stops after an additional traversal of length $O(D)$), or it discovers that it has not seen the base of $b$ yet, and executes some traversal of length $O(D)$ to get to the current location of its pebble $n$. In the latter case, agent $a$ continues iterating procedure Phase. It can be interrupted again by one of the above events, but eventually the interruption must be because of event Base, and it must happen by the end of phase $p\in O(D)$.

To summarize, event Base must happen by the end of phase $p\in O(D)$, unless agents have met accidentally before. After event Base, agent $a$ goes to the dominating point among $z$ and $z^{\prime }$ and stops. This guarantees the meeting of the agents, as $b$ executes the same algorithm. As for cost, the trajectory of the agent in each phase $i$ has length $O(i)$, hence the length of the trajectory until the end of phase $p$ is $O(p^2)$ which is $O(D^2)$. Thus the total length of the trajectory of agent $a$ is $O(D^2)$. The same is true for agent $b$, which implies cost $O(D^2)$.

Since all actions of an agent prescribed by Algorithm Automata Rendezvous (such as moving in one of the eight directions at a prescribed distance, and moving to a given point in the snapshot) require remembering a bounded number of bits plus using the input provided by the current snapshot, the algorithm can be executed by agents modeled by a deterministic finite automaton. Each agent uses two pebbles to mark its base, four pebbles to perform expansion in phases, and (possibly) two additional pebbles when executing procedure Clarification, if Condition Agent occurs. These two latter pebbles can be reused at each call of procedure Clarification, if Condition Agent occurs, because the agent always picks up these pebbles after using them. Hence the total number of pebbles used by each agent is at most eight. $◀$