Approach of Agents with Restricted Fuel Tanks

Two mobile agents, modelled as points moving in the plane, have to get at a distance at most 1 from each other. This task is known as approach or rendezvous in the plane and has numerous applications. The final distance, normalized to 1, should be viewed as the distance at which agents can “see” each other, hence the goal of approach is mutual perception. In human interaction, people may want to meet in a large terrain, where meeting means seeing each other. In robotics applications, two mobile robots, independently deployed in a contaminated territory and collecting samples of the ground, may need to meet in order to exchange these sample and coordinate further actions. Robots have limited energy, either a fuel tank or an electric battery, that allows them to travel a certain maximum distance and then has to be replenished at the base.

We consider two mobile agents modelled as points moving in the plane, that have to get at a distance at most 1 from each other. An adversary initially places both agents at distinct points, called their bases, at distance at most $D$, and wakes them up at possibly different times. Both agents execute the same deterministic algorithm. If they were identical then, in the case of simultaneous start and identical compasses, they would move along trajectories that are shifts of each other, and consequently, at any time, their distance would be the same as at the start, thus precluding approach, for any $D>1$. In order to allow approach, this symmetry has to be broken. We do this in the way that is most common in the literature: agents have distinct labels that are integers from a set $\{1,\mathrm{\dots },L\}$, where $L$ is some constant number. This may be viewed as the set of all identifiers used by the manufacturer of the robots. We make an assumption, standard in rendezvous/approach literature (cf. e.g., [4, 10]) that each agent only knows its own label that can be used as a parameter in a common deterministic algorithm they execute. Each agent is equipped with a clock and a compass showing the cardinal directions. Clocks of the agents tick at the same rate and the clock of each agent starts at its wake-up. Compasses may be inaccurate and arbitrarily distorted, i.e., for each agent, its North can point in any (fixed) direction. Each of the agents has a fuel tank that allows them to traverse a trajectory of length $D$, and can be replenished at the base of the agent.¹¹1The discussion of the size of the tank is postponed to Section 5.

The execution of an approach algorithm by an agent consists of a series of actions. An agent can either choose a direction $\alpha$ (according to its compass) and a distance $x$, in which case it travels distance $x$ in direction $\alpha$ with speed 1, or it can stay put at the current point for a chosen time $t$. Whenever agents get at a distance at most 1, the algorithm is interrupted and the goal of approach is achieved. For a given instance of the approach task, the execution time of an approach algorithm is the length of the period between the start of the later agent and the moment of approach.

Our goal is to design approach algorithms with optimal time complexity. We consider two independent coherence assumptions. One of them is time coherence, i.e., agents start simultaneously, and the other is orientation coherence: agents have compatible compasses, showing the same North direction. The presence or absence of these two assumptions yields four possible scenarios. Our main result is establishing optimal time complexity of the approach problem for each of these scenarios. It turns out that this optimal complexity heavily depends on the above coherence assumptions. If both of them are satisfied then approach can be performed in time $O(D^2)$ and we show that this complexity is optimal. If any of the two coherence assumptions is missing then approach can be performed in time $O(D^2\sqrt{D})$ and we prove that this order of magnitude cannot be improved.

Our main technical contribution are lower bounds showing that, for each of the considered scenarios, our fairly natural approach algorithms are, in fact, optimal. In both our $\mathrm{\Omega }(D^2\sqrt{D})$ lower bound proofs, we consider the most difficult instances of the approach problem, when bases of the agents are at a distance exactly $D$. For these instances, approach is only possible in short time periods in which both agents are close to their maximal range, i.e., at distance $D/2$ from their respective bases. We will prove that these time periods must be separated by time segments of length $\mathrm{\Omega }(D)$. Due to lack of simultaneous start or of compass compatibility, any of these time periods may be necessary for approach, depending on the instance. In view of the above, the main difficulty is proving that the number of these time periods is $\mathrm{\Omega }(D\sqrt{D})$, which will imply the lower bound $\mathrm{\Omega }(D^2\sqrt{D})$ on the time of approach.

The task of rendezvous of mobile agents has been extensively studied, both when agents move in graphs, and when they move in the plane. For a survey of randomized rendezvous algorithms, see the classic book [1], amd for a survey of deterministic rendezvous, see [16].

Deterministic rendezvous in networks modelled as graphs has been studied under two scenarios. In the synchronous scenario, agents move in synchronous rounds, in each round deciding either to stay put at the current node or to move to an adjacent neighbor. The goal is to get both agents at the same node in the same round. The time of rendezvous is the number of rounds used. A time-efficient synchronous rendezvous algorithm was designed in [17], although the problem of optimal synchronous rendezvous is still open. In the asynchronous scenario, an agent chooses the edge along which it wants to go but the adversary chooses the speed of the agent during the move. The goal is to meet at a node or inside an edge, and the cost is the number of traversed edges. A polynomial-cost algorithm for asynchronous rendezvous in arbitrary graphs was designed in [10].

Rendezvous in the plane, often called approach, has also been studied both under the synchronous and asynchronous scenarios. In [8, 9], this task was investigated under various assumptions concerning attributes of agents, such as orientation, chirality and speed. An asynchronous approach algorithm in the plane working at cost polynomial in the initial distance and in the lengths of agents’ labels was designed in [4]. The more general task of gathering many agents in the plane was studied in [6, 7, 12], under various assumptions concerning perception capabilities of the agents.

A special, well researched variation of rendezvous, both in graphs and in the plane, is treasure hunt. An inert treasure is hidden at a node of the graph or in a point in the plane, and a mobile agent starting at some other node or point in the plane has to find it. Thus, treasure hunt can be viewed as rendezvous in which one of the agents is permanently inert. Treasure hunt in the plane was considered, e.g., in [3, 15], see also surveys [13, 14]. Treasure hunt in graphs was investigated, e.g., in [2, 5, 11], under some constraints imposed on the mobile agent: in [2], the mobile agent had a restricted fuel tank that could be replenished at the base (as in the present paper), and in [11], the agent was tethered, i.e., attached to the base with a rope of fixed length. To the best of our knowledge, the general task of approach in the plane of agents with restricted fuel tanks has never been studied before.

In this section, we design Algorithm Faster working in the strongest scenario where both coherence assumptions are satisfied. We prove that this algorithm has complexity $O(D^2)$.

Let $O_1$ be the base of agent Blue and $O_2$ the base of agent Red. Let $C_1$ be the circle of radius $D/2$ centered at $O_1$ and let $C_2$ be the circle of radius $D/2$ centered at $O_2$. Let $n=4\lceil \pi D\rceil$. Let $A_0,\mathrm{\dots },A_{n-1}$ (resp. $B_0,\mathrm{\dots },B_{n-1}$) be points on $C_1$ (resp. on $C_2$) in clockwise order, such that $A_0$ is North of $O_1$ $B_0$ is North of $O_2$, and all distances between points $A_i$ and $A_{(i+1)modn}$ and points $B_i$ and $B_{(i+1)modn}$ are equal. Each agent visits consecutive points on its circle but they start from antipodal points.

Algorithm Faster for agent Blue (Red, resp.): the algorithm works in $n$ phases. In phase $i=0,1,\mathrm{\dots }n-1$, agent Blue (Red, resp.) goes from its base straight to $A_i$ ($B_{(i+n/2)modn}$, resp.) and comes back straight to its base.
The following theorem establishes the correctness and complexity of Algorithm Faster. Its proof is in the Appendix, Section B.

In this section, we design Algorithm Slower working even in the weakest scenario where none of the coherence assumptions is satisfied. We prove that this algorithm has complexity $O(D^2\sqrt{D})$. Let $O_1$ be the base of agent Blue and $O_2$ the base of agent Red. Let $C_1$ be the circle of radius $D/2$ centered at $O_1$ and let $C_2$ be the circle of radius $D/2$ centered at $O_2$. Let $n=\lceil 2\pi \sqrt{D}\rceil$ and let $m=\lceil 4\pi D\rceil$. Let $A_0,\mathrm{\dots },A_{n-1}$ (resp. $B_0,\mathrm{\dots },B_{m-1}$) be points on $C_1$ (resp. on $C_2$) in clockwise order, such that $A_0$ is North of $O_1$ according to agent’s Blue compass, $B_0$ is North of $O_2$ according to agent’s Red compass, and all distances between points $A_i$ and $A_{(i+1)modn}$ and points $B_i$ and $B_{(i+1)modn}$ are equal. Each agent visits consecutive points on its circle. However, agent Blue visits only $\mathrm{\Theta }(\sqrt{D})$ points on $C$, waiting in each of them for time $\mathrm{\Theta }(D^2)$, while agent Red visits $\mathrm{\Theta }(D)$ points on $C$ without any waiting.

Algorithm Slower for agent Blue: The algorithm works in phases. In phase $i\ge 0$, agent Blue goes from its base straight to $A_{imodn}$, waits there for time $4\lceil 4\pi D^2\rceil$, and comes back straight to its base.
Algorithm Slower for agent Red: The algorithm works in phases. In phase $i\ge 0$, agent Red goes from its base straight to $B_{imodm}$ and comes back straight to its base.

The following result establishes the correctness and complexity of Algorithm Slower. Its proof is in the Appendix, Section C.

The algorithms presented so far assume that each agent knows in advance whether it is Blue or Red, and therefore it can execute the appropriate version of the algorithm. However, in our model we assume that the agents do not have prior knowledge of their roles. The only way to break symmetry is provided by distinct labels of agents from the set of natural numbers $\{1,\mathrm{\dots },L\}$, where the value of $L$ is a constant not known to the agents. Each agent knows only its own label that can be used as a parameter in their common deterministic algorithm.

It turns out that our algorithms can be adjusted to the above scenario at the multiplicative cost in time complexity of the order of $O(\log L)$. Since we assume that $L$ is a constant, this does not change the previously established complexities. The idea behind the generalizations is that the original algorithms presented earlier are executed by each agent several times, until the approach happens. The agent uses an appropriate binary encoding of its label in order to decide whether to act as Blue or Red in its $i$th execution. More precisely, the agent $X$ with the binary encoding of its label equal to $l(X)$ executes the algorithm for Blue in the $i$th execution if the $i$th bit of $l(X)$ is equal to 0 and it executes the algorithm for Red otherwise. Using fairly standard encodings of size $O(\log L)$ and appropriate proof techniques one can prove that there will appear simultaneously a period in which one of the agents acts as Blue and the other one acts as Red in the first $O(\log L)$ executions of the original algorithm designed for agents Blue and Red. These facts will lead to the following result.

As a warm-up, in this section, we prove the lower bound $\mathrm{\Omega }(D^2)$ on the time of approach that holds even for the strongest scenario with simultaneous start and common orientation. In fact we will show the following stronger lower bound implying our result: it turns out that this lower bound holds even for unbounded fuel tanks. Its proof is in the Appendix, Section D.

In this section we define the common notions and prove geometric properties useful in lower bounds from Sections 4.4 and 4.5. Some missing proofs will be provided in the full version of the paper.

Consider an arbitrary approach algorithm for two agents $A$ and $B$. Each agent’s range disc is the disc with radius $D/2$ centered at the base of the agent. Each agent’s range circle is the boundary of its range disc. We assume that the bases of the agents are at distance $D$, i.e., their range discs are tangent. Consider the trajectory of an agent between its wake-up and the approach. This trajectory can be partitioned into a sequence of sub-trajectories between consecutive visits of the base, and the final sub-trajectory finishing at the approach. These sub-trajectories are called walks. For each walk, we distinguish its meeting part between the first and last points of the walk at distance at least $D/2-1$ from the source. The bisector of the angle between these points is called the walk bisector. The angle between North and the walk bisector of agent $A$ is called the walk angle of agent $A$. The angle between South and the walk bisector of agent $B$ is called the walk angle of agent $B$. We define the angle $\delta =\arcsin (\frac{1}{D/2-1})$. The meeting area of a walk is the part of the plane bounded by two half-lines with origin at the base, forming angle $\delta$ with the walk bisector, and circles of radii $D/2$ and $D/2-1$ centered at the base (see Fig. 2).

In this section we describe the ideas of the lower bounds $\mathrm{\Omega }(D^2\sqrt{D})$ presented in Sect. 4.4 and 4.5.

In this section, we prove the lower bound $\mathrm{\Omega }(D^2\sqrt{D})$ on the time of approach that holds if arbitrary start delay is permitted, even if agents have the same orientation. Some missing proofs of lemmas will be provided in the full version of the paper.

Consider an instance $I$ of the approach problem consisting of bases $a$ of agent $A$ and $b$ of agent $B$, and of a delay between the starting times of the agents. As $I$ is a geometric instance with an additional delay parameter we will call it a time-shifted instance. We say that a pair of walks $W$ of agents $A$ and $B$ supports the time-shifted instance $I$ if $W$ supports the geometric part of the instance $I$.

Let $z=2\lfloor \sqrt{D}\rfloor$, and let $g_i=[(2i-1)\frac{2\pi }{z},2i\frac{2\pi }{z})$ for $i=1,2,\mathrm{\dots },z/2$.
The following corollary is implied directly by Lemma 6.

For any $i=1,2,\mathrm{\dots },z/2$, we define the set $P_i$ of walks of agent $A$ and the set $Q_i$ of walks of agent $B$ as follows.

We say that $w\in P_i$ (resp. $w\in Q_i$), if there exists a walk $w^{\prime }$ of agent $B$ (resp. of agent $A$), such that the pair of walks $\{w,w^{\prime }\}$ supports a time-shifted instance $I$ with $\gamma (I)\in g_i$. Note that, due to Corollary 9, sets $P_i$, for different indices $i$, and sets $Q_i$, for different indices $i$, are pairwise disjoint.

Without loss of generality, we will assume that agent $A$ starts first. Let $0$ be the time when agent $A$ starts, and $t\ge 0$ be the time when agent $B$ starts. The local time of each agent is the time counted since its start. Assume that $T$ is the approach time counted from the start of agent $B$, for a worst-case instance.

Denote by $p_i$ the fraction of time spent by agent $A$ in walks from set $P_i$ in the period $[0,11T]$. Denote by $q_i$ the fraction of time spent by agent $B$ in walks from set $Q_i$ in the period $[0,T]$. (Recall that, we measure time for agent $B$ according to its local time. In particular time $0$ for agent $B$ is equal to time $t$ at which $B$ starts the execution of the algorithm.) By definition, ${\sum }_i{p}_i\le 1$ and ${\sum }_i{q}_i\le 1.$

We define the indicator function ${𝕀}_A^i(s)$ as follows: ${𝕀}_A^i(s)=1$, if at time $s$, agent $A$ performs a walk from the set $P_i$ and ${𝕀}_A^i(s)=1$ otherwise. Analogously, ${𝕀}_B^i(s)=1$ if at its local time $s$, agent $B$ performs a walk from the set $Q_i$ and ${𝕀}_B^i(s)=0$ otherwise.

Note that $p_i=\frac{1}{11T}{\int }_0^{11T}{𝕀}_A^i(s)𝑑s$ and $q_i=\frac{1}{T}{\int }_0^T{𝕀}_B^i(s)𝑑s$. The common period of walks in $P_i$ and $Q_i$ is defined as the set of time points when agent $A$ performs a walk from $P_i$ while agent $B$ performs a walk from $Q_i$. The attempt period of walks in $P_i$ and $Q_i$ is the subset of the common period of walks in $P_i$ and $Q_i$ consisting of time points such that both walks are in their meeting parts. This set of time points depends on the starting time of agent $B$. Moreover define $r_i(t)=\frac{1}{T}{\int }_0^T{𝕀}_A^i(t+s){𝕀}_B^i(t)𝑑s$. This is the fraction of the time segment $[t,t+T]$ occupied by the common period of walks in $P_i$ and $Q_i$.

In this section, we prove the lower bound $\mathrm{\Omega }(D^2\sqrt{D})$ on the time of approach that holds if orientations of agents may be different and arbitrary, even if they start simultaneously.

We will call the orientation of agent $A$ the global orientation. Consider an instance $I$ of the approach problem consisting of bases $a$ of agent $A$ and $b$ of agent $B$, and of the orientation of agent $B$. As it is a geometric instance with an additional rotation parameter we will call it an orientation-shifted instance. Let $\varphi (I)$ be a the angle between the half-line indicating north according to the local orientation of agent $B$ and the halfline indicating north in the global orientation. Thus, an orientation-shifted instance $I$ is determined by the locations $a$ and $b$ of the bases of agents and the angle $\varphi (I)$. Let $\{w_A,w_B\}$ be a pair of walks, where $w_A$, $w_B$ are walks of agent $A$ and agent $B$, respectively. Let $w_B(I)$ be the walk $w_B$ of agent $B$ rotated around the base of agent $B$ by $\varphi (I)$, i.e., the walk $w_B$ expressed according to the global orientation in the orientation-shifted instance $I$. We say that the pair of walks $\{w_A,w_B\}$ supports the orientation-shifted instance $I$ if $\{w_A,w_B(I)\}$ supports the part of the instance $I$ determined by the locations of the bases.

Let $ℐ$ be a set of orientation-shifted instances $I_{i,j}$ for $i\in \{0,\mathrm{\dots },\lfloor 2\pi \frac{\sqrt{D}}{6}\rfloor -1\}$ and $j\in \{0,\mathrm{\dots },\lfloor 2\pi \frac{D}{30}\rfloor -1\}$ such that:

• $\mathrm{■}$

  the distance between the bases of agents $A$ and $B$ is exactly $D$.

• $\mathrm{■}$

  $\gamma (I_{i,j})=\frac{6i}{\sqrt{D}}$,

• $\mathrm{■}$

  $\varphi (I_{i,j})=\frac{30j}{D}$.