Approach of agents with restricted fuel tanks

Abstract Two mobile agents, modeled as points in the plane moving at speed 1, have to get at a distance at most 1 from each other. This task is known as approach or rendezvous in the plane. 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. 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. The algorithm of each agent consists of a series of actions which are either moves at a chosen distance in a chosen direction or staying idle for a chosen period of time. 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. Our main result is establishing optimal time complexity of the approach problem with restricted fuel tanks. 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 contributions are lower bounds showing that, for each of the considered scenarios, our fairly natural approach algorithms are, in fact, optimal. Similar content being viewed by others 1 Introduction 1.1 The background 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 samples 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. 1.2 The model and the problem 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 follow the standard approach in the literature: agents have distinct labels that are integers from a set \(\{1,\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 assume that each agent only knows its own label that can be used as a parameter in the 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.Footnote 1 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. When an agent runs out of fuel, i.e., it traverses distance D after a visit at the base, its execution of the algorithm is interrupted as well. The execution time of an algorithm for a given instance (determined by the locations of the bases, times of awakenings of the agents, and their orientations of the direction North) consist of the time of execution of both agents according to the algorithm until they get at a distance at most 1 or finish their own executions of the algorithm. For a given instance of the approach task, the execution time of an algorithm is the length of the period between the start of the later agent and the moment of approach. The approach time of an algorithm is the maximum of its execution times over all instances of the approach task. 1.3 Our results 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 contributions are lower bounds showing that, for each of the considered scenarios, our fairly natural approach algorithms are, in fact, optimal. 1.4 Related work 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], and 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 rendeazvous 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. 2 Preliminaries We will use the following geometric lemma which informally says that two points on tangent circles \(C_1\) and \(C_2\) of radius r located roughly symmetrically with respect to the tangent line of \(C_1\) and \(C_2\) are at a distance at most 1, provided that they are in arc-distance \(O(\sqrt{r})\) from the common point of \(C_1\) and \(C_2\). Lemma 1 Let \(C_1\) and \(C_2\) be tangent circles of the same radius r, centered at \(O_1\) and \(O_2\), respectively. Let S be the common point of \(C_1\) and \(C_2\). For \(i=1,2\), and for any point P on \(C_i\), let \(\alpha _i(P)\) be the length of the arc PS on \(C_i\). Let \(y=\sqrt{r}/4\). Let \(P_1\) be a point on \(C_1\) such that \(\alpha _1(P_1) \le y\), and let \(P_2\) be a point on \(C_2\) such that \(\alpha _1(P_1)-1/2 \le \alpha _2(P_2) \le \alpha _1(P_1)+1/2 \). Suppose that either \(P_1\) on \(C_1\) is counterclockwise from S and \(P_2\) on \(C_2\) is clockwise from S, or \(P_1\) on \(C_1\) is clockwise from S and \(P_2\) on \(C_2\) is counterclockwise from S. Then \(|P_1P_2|< 1\). Proof Without loss of generality, let \(P_1\) be counterclockwise from S. Let l be the line tangent to \(C_1\) in point S and let \(O_1, O_2\) be the centres of \(C_1\) and \(C_2\), respectively. Let H be the common point of l and of the line parallel to the radius \(O_1S\), passing through the point \(P_1\). Let Q be the common point of the bisector of the angle \(SO_1P_1\) and of the segment \(P_1S\). As the triangle \(SO_1P_1\) is an isosceles triangle, \(O_1QP_1\) is a right triangle, and thus the triangles \(O_1QP_1\) and \(SHP_1\) are similar, because \(|\angle QO_1P_1|=|\angle HSP_1|\) (cf. Fig. 1). As \(\alpha _1(P_1)\le y=\frac{1}{4}\sqrt{r}\), the length x of the segment \(P_1Q\) satisfies By similarity of the triangles \(O_1 QP_1\) and \(SHP_1\), we have and thus Let \(P_1'\) be the point axial symmetric to \(P_1\) with respect to axis l. As l is also tangent to circle \(C_2\), and \(C_2\) has the same radius as \(C_1\), the point \(P_1'\) lies on \(C_2\). In view of the assumption \(\alpha _1(P_1)-1/2 \le \alpha _2(P_2) \le \alpha _1(P_1)+1/2 \) we have By the triangle inequality, (1), and (2) we have \(\square \) 3 Algorithms This section is devoted to our positive results. We design two approach algorithms: an algorithm with time complexity \(O(D^2)\) for the strongest scenario where both coherence assumptions are satisfied, and an algorithm with time complexity \(O(D^2\sqrt{D})\) working even in the weakest scenario where none of the coherence assumptions is satisfied. For both algorithms, two variations are presented: one for agent Blue and the other for agent Red. This corresponds to a simplified version of our model, in which agents have labels 1 and 2, i.e., they know from the outset how symmetry between them is broken (they know which of them is Blue and which is Red). In Sect. 3.3, we show how these algorithms can be modified in order to conform with our model, where agents have distinct labels from the set \(\{1,\dots ,L\}\) and each agent only knows its label, i.e., it does not know if it is Blue or Red. 3.1 Time \(O(D^2)\) for simultaneous start and common orientation In this section, we design and analyze Algorithm Guess Angle working in the strongest scenario where both coherence assumptions are satisfied. We prove that this algorithm has complexity \(O(D^2)\). The idea of the algorithm Guess Angle is as follows. Let us assume that the distance between the agents is equal to D, as the distance \(d0\) the infinite strings \(l^f_1[i,\infty ]\) and \(l^f_2\) differ at a prefix of length \(O(\log L)\). We now show that this sufficient condition is satisfied. Note that, for any label l(X), the prefix of \(l^f(X)\) before adding the suffix consisting of the infinite string of 1’s is of length \(O(\log L)\). Consider three cases. Case 1. \(|l_1|=|l_2|\). If \(i=0\) then \(l_1[j]\ne l_2[j]\) for some \(j\le 1+\lceil \log L \rceil \) by the assumption that the labels are distinct. And thus \(l_1^f[5+2(j-1)+1]\ne l_2^f[5+2(j-1)+1]\) which gives the claimed inequality. If \(i>1\) than the suffix \(1^\infty \) of \(l_1^f[i,\infty ]\) matches with the segment of \(l_2^f\) containing at least one occurrence of 0. Finally, if \(i=1\) then the fourth 1 of the prefix of \(l_2^f\) matches with 0 in \(l_1^f[1,\infty ]\). Case 2. \(|l_1|>|l_2|\). If \(i=0\) then the suffix \(1^\infty \) of \(l_2^f\) matches a suffix of \(l_1\) which contains at least one occurrence of 0. If \(i\ge 2\) then the prefix 0000 of \(l_1\) matches with the segment of \(l_2^f\) with at least one occurrence of 1. Finally, if \(i=1\) then the fourth 1 of the prefix of \(l_2^f\) matches with 0 in \(l_1^f[1,\infty ]\). Case 3. \(|l_1|<|l_2|\). In this case, regardless of the value of i, the suffix \(1^\infty \) of \(l_1^f[i,\infty ]\) matches with a suffix of \(l_2^f\) containing at least one occurrence of 0. Hence we have Theorem 4 Algorithm Generalized Adjust and Search for agents with unique labels from the set \(\{1,\ldots ,L\}\) guarantees approach in time \(O(D^2\sqrt{D}\log L)\) in the model without simultaneous start and without common orientation. 4 Lower bounds This section is devoted to our negative results. We present three lower bounds. The first is the lower bound \(\Omega (D^2)\) on the time approach that holds for the strongest scenario with simultaneous start and common orientation. This lower bound shows that our algorithm for this scenario has optimal time complexity. The two other lower bounds concern scenarios when one of the coherence assumptions is not satisfied. If either arbitrary delay between starting times is permitted or different orientations of agents are allowed, we prove that approach requires time \(\Omega (D^2\sqrt{D})\). This result, combined with the complexity \(O(D^2\sqrt{D})\) of our algorithm working even in the weakest scenario shows that \(\Theta (D^2\sqrt{D})\) is the optimal complexity of approach in all the scenarios except the strongest one. 4.1 Time \(\Omega (D^2)\) for simultaneous start and common orientation As a warm-up, in this section, we prove the lower bound \(\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. Theorem 5 The time of approach for two agents simultaneously starting at a distance at most D, with common orientation and unbounded tanks is \(\Omega (D^2)\). Proof Consider an arbitrary approach algorithm for two agents A and B. Let a(t) (resp. b(t)) be a vector describing the position of agent A (resp. B) relative to its starting point in time t. Let \(d(t) = a(t)-b(t)\). Let T be the approach time of the algorithm. For \(i,j \in [-\lfloor \frac{D}{4} \rfloor , \lfloor \frac{D}{4} \rfloor -2]\) let \(r_{i,j}\) be the rectangle with vertices in points \((2i, 2j),(2i+2, 2j), (2i, 2j+2), (2i+2, 2j+2)\). We will consider only even rectangles, that is the rectangles \(r_{i,j}\) where both i and j are even. We say that the algorithm marks the rectangle \(r_{i,j}\) if there is a moment t of the execution of the algorithm such that the point d(t) is inside \(r_{i,j}\). As for any \(t_1, t_2\) such that, \(|t_1-t_2| \le 1 \) the length of the vector \(d(t_1)-d(t_2)\) is at most 2, the algorithm can mark at most \(T + 1\) even rectangles. Assume that the time of approach T is less than \(\frac{D^2}{16}\). The algorithm can mark at most \(\frac{D^2}{16} + 1\) even rectangles, and thus there exists an unmarked even rectangle \(r_{i,j}\). By fixing the base of agent A at point (0, 0) and the base of B at point \((2i+1, 2j+1)\) the adversary can guarantee that the approach does not occur. This contradiction concludes the proof. \(\square \) 4.2 Geometric preliminaries for \(\Omega (D^2\sqrt{D})\) lower bounds In this section we define the common notions and prove geometric properties useful in lower bounds from Sects. 4.4 and 4.5. 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. 4). Fact 1 If an agent goes back to its base at the end of a walk w, the intersection of w with the annulus between circles of radii \(D/2-1\) and D/2 centered at the base of this agent is included in the meeting area of the walk w. Proof In order to get back to the base after leaving the disk \(\Delta \) with the radius \(D/2-1\) centered at the base, an agent can only move at distance at most 1 before getting back to the disc \(\Delta \). A possible part of the trajectory outside of \(\Delta \) corresponds to an angle \(\arcsin (\frac{1}{D/2-1})\). \(\square \) Note that approach can occur only when an agent is in the meeting area of its walk. Consider a geometric instance I of the approach problem consisting of bases a of agent A and b of agent B. The angle between the segment ab and the half-line with direction North, originating at a is denoted by \(\gamma (I)\). This is also the angle between the segment ab and the half-line with direction South, originating at b. We define a pair of walks as a two-element set containing a walk of agent Blue and a walk of agent Red. We say that a pair of walks \(\{w_1,w_2\}\) supports the geometric instance I if these walks are at distance at most 1. Now, we provide some properties regarding “usefulness” of walks and pairs of walks (i.e., two-element sets containing a walk of agent Blue and a walk of agent Red) with respect to the success of approach (cf. Fig. 5). In the following lemma we focus on a single walk. We show that, a given walk w can belong to a pair of walks assuring approach for an instance I, only if the walk bisector of w is \(O(1/\sqrt{D})\)-close to \(\gamma (I)\). In other words, the angle between the segment connecting the bases and the walk bisector of w should be \(O(1/\sqrt{D})\). Otherwise, the agent is at distance greater than 1 from any point reachable by the other agent during the walk w of the first agent. Lemma 2 If \(|\alpha -\gamma (I)|\ge 3/\sqrt{D}\), for \(D>256\), then no pair of walks \(\{w_1,w_2\}\) of agents A and B, such that \(\alpha \) is the walk angle of one of the agents, supports the geometric instance I. Proof Let S be the tangent point of range circles of the agents. Let l be the line tangent to the range circle C of agent A at point S. Let P be the point of the meeting area of the walk \(w_A\), closest to line l (see Fig. 6). Without loss of generality, suppose that \(\alpha \) is the walk angle of agent A. Denote by \(\sigma \) the angle SaP. Thus, \(\sigma = |\alpha -\gamma |-\delta \). Let H be the intersection of l with the line containing P, parallel to the segment aS. Let Q be the midpoint of segment PS. Due to similarity of triangles PHS and PQa we have and thus Hence \(|PH|>1\) if and only if \(|PQ|>\sqrt{D}/2\). Suppose that \(D>256\). If \(\sigma <2\), then If \(\sigma \ge 2\), then Hence \(|PH|>1\). This implies that the range circle of agent B must be at distance larger than 1 from the meeting area of \(w_A\), which proves the lemma. \(\square \) Now, we analyze additional requirements which have to be satisfied for a pair of walks in order to make approach feasible, provided that walks from the pair are appropriately synchronized in time and both of them are close to the tangency point of their circles with radius D/2, as expressed in Lemma 2. In Lemma 3 we show that, apart from the requirements of Lemma 2, a pair of walks \(\{w_1, w_2\}\) might lead to approach only if their walk bisectors are O(1/D)-close. More precisely, if \(\alpha \) and \(\beta \) are the angles of bisectors of these walks (clockwise from Blue and counterclockwise from Red) then approach might be possible only if \(|\alpha -\beta |\in \) O(1/D). Let \(X_i\) be the common point of \(C_i\) and the bisector of the walk \(w_i\), for \(i\in \{1,2\}\), where \(w_1\) is the walk of Blue and \(w_2\) is the walk of Red. Then, the lemma says that, in order to make approach feasible, \(X_1\) and \(X_2\) should be located almost symmetrically with respect to the line tangent to \(C_1\) and \(C_2\). By moving one of these points on its circle by a distance the positions of those points would be ideally symmetric. Lemma 3 Consider the set \(\mathcal{I}\) of geometric instances supported by a set \(\{w_A,w_B\}\) of walks. Let \(\alpha \) be the walk angle of agent A, and \(\beta \) the walk angle of agent B. Then, for \(D>100\) and for any \(I \in \mathcal {I}\), \(\gamma (I)\in \left[ \frac{\alpha +\beta }{2}-\frac{6}{D},\frac{\alpha +\beta }{2}+\frac{6}{D}\right] \). Proof Let P and Q denote the intersection points of the bisectors of walks \(w_A\) and \(w_B\) with the range circles of agents A and B respectively. Let S be the tangent point of range circles of the agents. (Recall also that a and b are the centers of the range circles of the agents A and B, respectively.) Let l be the line tangent to the range circle C of agent A at point S. For any instance \(I \in \mathcal {I}\), the meeting area of walk \(w_A\) must be at a distance at most 1 from the meeting area of walk \(w_B\). Hence, projections of these meeting areas on line l must also be at a distance at most 1. Let \(P'\) and \(Q'\) be the projections of points P and Q, respectively, on line l. We show that the distance from \(P'\) to the border of the projection of the meeting area of \(w_A\) does not exceed 1.5. An analogous argument can be carried out for point \(Q'\) and the meeting area of \(w_B\). Let \(P_1\) be the intersection point of the bisector of walk \(w_A\) with the circle of radius \(D/2-1\) centered at a. Let m be one of the half-lines originating at \( a \) and forming the angle \( \delta =\arcsin (\frac{1}{D/2-1}) \) with the bisector of \(w_A\). Let \( P_2 \) and \( P_3 \) be the points of intersection of m with the circles of radius \( \frac{D}{2} \) and \( \frac{D}{2} - 1 \) centered at \( a \), respectively. Let \(P_2'\) and \(P_3'\) be the projections of points \(P_2\) and \(P_3\), respectively, on line l (see Fig. 7). Our goal is to show that both the point \(P_2'\) and the point \(P_3'\) are at a distance at most 1.5 from \(P'\). For any real positive \(x<0.5\), we have \(\arcsin (x)<1.1x\). So, for \(D>100\), we can estimate On the other hand, if \(|P'P_2'|<|P'P_3'|\), then we have \(|P_2'P_3'|<3/\sqrt{D}\) by Lemma 2. Indeed, let the angle \(aP_2\) be \(\eta \). By Lemma 2, \(\eta \) is at most \(3/\sqrt{D}\). Thus, - \(\frac{|SP'_3|}{D/2-1}=\sin \eta \), - \(\frac{|SP'_2|}{D/2}=\sin \eta \) and therefore Thus \(|P'P_2'|<|P'P_3'|\) implies, for \(D>100\) By Lemma 2, we have \(|\alpha -\gamma (I)| < \frac{3}{\sqrt{D}}\) and \(|\beta -\gamma (I)| < \frac{3}{\sqrt{D}}\). Thus This implies and hence \(\gamma (I)\in \left[ \frac{\alpha +\beta }{2}-\frac{6}{D},\frac{\alpha +\beta }{2}+\frac{6}{D}\right] \). \(\square \) Lemma 3 gives us the following corollary Corollary 1 Consider the set \(\mathcal{I}\) of geometric instances supported by a set \((w_A,w_B)\) of walks. Then all angles \(\gamma (I)\), for \(I \in \mathcal {I}\), belong to an interval of length at most 12/D, for \(D>100\). 4.3 High-level ideas of lower bounds for scenarios without simultaneous start or without common orientation In this section we describe the ideas of the lower bounds \(\Omega (D^2\sqrt{D})\) formally presented in Sects. 4.4 and 4.5. Time-shifted instances In order for a pair of walks \(\{w_1,w_2\}\) to yield approach, both walks have to be sufficiently close geometrically (i.e., their trajectories should be close to each other). These requirements, combined with the assumption that the distance between the bases of agents is the largest still allowing approach, lead to Lemmas 2 and 3. Additionally, the walks \(w_1\) and \(w_2\) assuring approach should be somehow synchronized. This synchronization is necessary in order to assure that the agents get to the closest parts of the pair of walks at the same time. This property should be satisfied regardless of the delay of starting times of agents, chosen by the adversary. Lemma 4 formalizes the above intuition and expresses some conclusions regarding time T needed for approach in the following way. First, we restrict attention to such instances I that the angle \(\gamma (I)\) belongs to one of the pairwise disjoint angle-intervals from the set \(\{g_i\}_{i=1}^{z}\) for \(z=\Theta (\sqrt{D})\) such that: - the length of each interval is \(\Theta (1/\sqrt{D})\), - the intervals \(g_i\) and \(g_{1+i\mod z}\) are separated by an interval of length \(\Theta (1/\sqrt{D})\). Then, by Lemma 2, for all instances \(I, I'\) such that \(\gamma (I)\in g_i\), \(\gamma (I')\in g_{i'}\) for \(i\ne i'\), there is no pair of walks which simultaneously supports I and \(I'\). Actually, Lemma 2 implies even a stronger property that no walk \(w_1\) belongs to the sets \(\{w_1, w_2\}\), \(\{w_1, w'_2\}\) such that the former set supports an instance I and the latter supports \(I'\) such that \(I\in g_i\), \(I'\in g_{i'}\), \(i\ne i'\). Now, assume that one agent starts at time 0 and the start of the other agent is chosen uniformly at random in the period [0, cT] for some constant c, where T is the time of approach of an analyzed algorithm. For this distribution, let \(p_i\) and \(q_i\) be random variables corresponding to the fractions of time serving the interval \(g_i\) by the agents Blue and Red, respectively. Let \(r_i(t)\) be the expected fraction of time in which both agents simultaneously are in their walks that could support instances from \(g_i\) in some pairs, for time shift t. In Lemma 5, we prove a lower bound on the time which agents need to spend in parallel in their walks designated for any interval \(g_i\) of length \(\Omega (1/\sqrt{D})\), in order to achieve the approach for those time-shifted instances I for which the angle \(\gamma (I)\) belongs to \(g_i\). It turns out that this time has to be \(\Omega \left( D\sqrt{D}\right) \). An intuition behind this bound is that an interval of size \(\Omega (1/\sqrt{D})\) requires \(\Omega \left( \frac{1/\sqrt{D}}{1/D}\right) =\) \(\Omega (\sqrt{D})\) separate pairs of walks due to Lemma 3 and each change of a pair of walks takes \(\Omega (D)\) time. Importantly, walks of both agents cannot help with approach for \(\gamma (I)\in g_{i'}\) and \(i'\ne i\), since \(g_i\) is separated from \(g_{i-1}\) and \(g_{i+1}\) by intervals of lengths \(\Omega (1/\sqrt{D})\) as well – cf. Lemma 2. In Lemmas 5 and 6 we take advantage of the fact that time shift is an appropriately chosen random variable and each walk can support instances from only one of the intervals \(g_i\): - In Lemma 5 we show that, for randomly chosen time-shift in \([ 0,10T]\subset \) \(\mathbb {R}\) with uniform distribution, the expected value of time fraction when both agents perform walks supporting approach for the value of \(\gamma (I)\) in \(g_i\), for each i, is at least \(1.1 c p_i q_i\). - Using purely algebraic arguments we show in Lemma 6 that the minimum of \(p_i q_i\) is \(\Omega (1/D)\). This fact holds by substituting the maximum value of i which is \(O(\sqrt{D})\) in the place of n in the lemma. In Theorem 6 we combine the above observations (Lemmas 5 and 6) with Lemma 4, proving a lower bound on the time spent performing walks in the interval \(g_i\), for each i and for each starting time of agent B. Orientation-shifted instances For the model without common orientation, we carefully choose the set \(\mathcal {I}\) of orientation-shifted instances of size \(\Theta (D\sqrt{D})\) such that no pair of walks can support more than one instance from \(\mathcal {I}\). Let \(\phi (I)\) be the angle between the half-line indicating north according to the local orientation of agent B and the half-line indicating north in the global orientation. The set \(\mathcal {I}\) consists of instances \(I_{i,j}\) for natural i and j, such that the largest i is \(O(\sqrt{D})\), the largest j is O(D), \(\gamma (I_{i,j})\) is i times an appropriate value of the order \(\Theta (1/\sqrt{D})\) and \(\phi (I_{i,j})\) is equal to j times an appropriate value of the order \(\Theta (1/\sqrt{D})\). Thus, - If \(i_1\ne i_2\) then the instances \(I_{i_1,j_1}\), \(I_{i_2,j_2}\) cannot be supported by the same pair of walks due to the purely geometric argument regarding distance between tangency points of different geometric instances, see Lemma 2. - If \(i_1=i_2\) and \(j_1\ne j_2\) then the instances \(I_{i_1,j_1}\), \(I_{i_2,j_2}\) cannot be supported by the same pair of walks due to the fact that the differences between orientation shifts of those instances contradict the geometric argument regarding relative locations of walks bisectors of the walks from the set if both instances are supported by the considered pair of walks (see Lemma 3). The above observations imply that \(\Omega (D\sqrt{D})\) pairs (two-element sets) of walks have to be scheduled in such a way that both agents performing walks of a pair have to be in the meeting parts of their walks at the same time. However, as an agent is at distance \(\ge D/2\) from its base in a meeting part of its walk, there is time \(\ge D\) between two consecutive pairs of walks supporting some instances from \(\mathcal {I}\). This observation leads to the lower bound expressed in Theorem 7. However, some extra consideration is needed in order to tackle the case that an agent may move away by distance \(>D/2\) from its base which prevents it from getting back to the base. This can happen in the final walk, at the end of which the agent does not return to the base. This special case is tackled in the final part of the proof of Theorem 7. 4.4 Time \(\Omega (D^2\sqrt{D})\) for arbitrary start delay In this section, we prove the lower bound \(\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. 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,\ldots ,z/2\). The following corollary is implied directly by Lemma 2. Corollary 2 Consider any walk w of one of the agents, and any walks \(w_1\), \(w_2\) of the other agent. Let \(I_1\) and \(I_2\) be time-shifted instances supported by pairs of walks \(\{w,w_1\}\) and \(\{w,w_2\}\), respectively. Then \(\gamma (I_1)\) and \(\gamma (I_2)\) cannot belong to different segments \(g_i\). For any \(i=1,2,\ldots ,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'\) of agent B (resp. of agent A), such that the pair of walks \(\{w,w'\}\) supports a time-shifted instance I with \(\gamma (I)\in g_i\). Note that, due to Corollary 2, 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 and disjointness of sets \(P_i, P_j\) (\(Q_i\), respectively) for \(i\ne j\), we have \( \sum _i p_i \le 1 \) and \( \sum _i q_i \le 1. \) We define the indicator functions \(\mathbb {I}_A^i(s)\) and \(\mathbb {I}_B^i(s)\) Note that \(p_i = \frac{1}{11T} \int _0^{11T} \mathbb {I}_A^i(s) \,ds\) and \(q_i = \frac{1}{T} \int _0^T \mathbb {I}_B^i(s) \,ds\). 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 \mathbb {I}_A^i(t + s) \mathbb {I}_B^i(s) \,ds\). This is the fraction of the time segment \([t,t+T]\) occupied by the common period of walks in \(P_i\) and \(Q_i\). Lemma 4 Suppose that, for some \(i=1,2,\ldots ,z/2\) and some starting time t of agent B, the inequality \(r_i(t) \cdot T<\left( \frac{\pi \sqrt{D}}{12}-1\right) (D-2)\) holds. Then there exists a time-shifted instance I such that \(\gamma (I) \in g_i\) and t is the starting time of agent B, for which approach does not happen. Proof Fix a starting time t of agent B and fix \(i\in \{1,2,\ldots ,z/2\}\). We prove the lemma by contradiction. Suppose that, for all instances I such that \(\gamma (I) \in g_i\) and t is the starting time of agent B, the approach happens. Observe that the approach can only occur in the attempt period of walks in \(P_i\) and \(Q_i\). The attempt period of walks in \(P_i\) and \(Q_i\) is a union of \(\tau \) disjoint time intervals. To each of these intervals assign exactly one pair of walks \(\{w_A,w_B\}\): those that are performed during this interval. For an instance I, the approach can occur during a given interval of the attempt period, if I is supported by the pair of walks \(\{w_A,w_B\}\) assigned to it. For all instances I s.t. \(\gamma (I)\in g_i\), the approach occurs in the attempt period of walks in \(P_i\) and \(Q_i\). By Corollary 1, the pair of walks \(\{w_A,w_B\}\) supports instances I s.t. \(\gamma (I)\) is in a segment of length smaller than 12/D. Thus, in one time interval of the attempt period, the approach can only occur for instances I s.t. \(\gamma (I)\) belongs to a segment of length smaller than 12/D. Since the length of \(g_i\) is \(2\pi /z \ge \pi /\sqrt{D}\), one needs at least \(\pi \sqrt{D}/12\) segments of length 12/D to cover \(g_i\). Thus the attempt period of walks in \(P_i\) and \(Q_i\) has to consist of \(\tau \ge \pi \sqrt{D}/12\) pairwise disjoint time intervals. The time between consecutive time intervals in an attempt period must be at least \(D-2\), due to the need of refueling at the base. Hence, if we extend each but the last interval of the attempt period adding time intervals of length \(D/2-1\) on both of its sides, we will still have a set of disjoint time intervals. The union of these enlarged time intervals of lengths at least \(D-2\) is included in the common period of walks in \(P_i\) and \(Q_i\). Therefore the length of the common period of walks in \(P_i\) and \(Q_i\) is \(r_i(t)T\ge \tau (D-2)\ge \left( \frac{\pi \sqrt{D}}{12}-1\right) (D-2)\). This contradiction proves the lemma. \(\square \) Lemma 5 Assume that agent B starts in time taken uniformly at random from the range [0, 10T]. The expected value of \(r_i\) is not greater than \(1.1 p_i q_i\). Proof The expected value of \(r_i\) is \(\square \) To complete our considerations, we will also need the following algebraic lemma. Lemma 6 Consider real numbers \(p_i, q_i \in [0,1]\), for \(i=1,\dots ,n\), such that \(\sum _{i=1}^{n} p_i \le 1\) and \(\sum _{i=1}^{n} q_i \le 1\). Then \(\min \{ p_i q_i:i\le n\} \le \frac{1}{n^2}\). Proof The proof is by induction on n. The base case for \(n=1\) is trivial. Assume that the lemma holds for some value n. We consider two cases. If \(p_{n+1} q_{n+1} \le \frac{1}{(n+1)^2}\), the conclusion follows. Otherwise, define, for \(i=1,\dots , n\), As \(p'_i\) and \(q'_i\) satisfy the assumptions of the lemma, in view of the inductive hypothesis, there exists some j such that Also, by the inequality between arithmetic and geometric means, we have Thus, This concludes the proof of the lemma. \(\square \) Theorem 6 The time of approach for two agents with arbitrary start delay, starting at a distance at most D, is \(\Omega (D^2\sqrt{D})\). Proof We apply Lemma 6 for \(n=z/2=\lfloor \sqrt{D} \rfloor \) and for \(p_i,q_i\) defined before in this section. By Lemma 6, there exists an i for which \(p_iq_i\le 1/n^2\le 4/D\). By Lemma 5, the expected value of \(r_i\) is at most \(1.1 p_i q_i \). Thus there exists an argument t for which \(r_i(t) \le 1.1 p_i q_i\). Suppose that the approach occurs for an instance I for which \(\gamma (I)\in g_i\) and the delay between starting times of the agents is t. By Lemma 4, we have \(r_i(t) \cdot T\ge \left( \frac{\pi \sqrt{D}}{12}-1\right) (D-2)\), where T is the length of time between the start of agent B and the approach. Hence Thus we get \(T\ge \frac{D}{5}\left( \frac{\pi \sqrt{D}}{12}-1\right) (D-2)\in \Omega (D^2\sqrt{D})\) which proves the theorem. \(\square \) 4.5 Time \(\Omega (D^2\sqrt{D})\) for arbitrary orientations In this section, we prove the lower bound \(\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. Recall that \(\phi (I)\) denotes the angle between the half-line indicating north according to the local orientation of agent B and the half-line 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 \(\phi (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 \(\phi (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 \(\mathcal {I}\) be a set of orientation-shifted instances \(I_{i,j}\) for \(i \in \{0,\dots ,\lfloor 2\pi \frac{\sqrt{D}}{6}\rfloor - 1\}\) and \(j \in \{0,\dots ,\lfloor 2\pi \frac{D}{30}\rfloor - 1\}\) such that: - the distance between the bases of agents A and B is exactly D. - \(\gamma (I_{i,j}) = \frac{6i}{\sqrt{D}}\), - \(\phi (I_{i,j}) = \frac{30j}{D}\). Lemma 7 Let \(\mathcal {S}\) be a collection of pairs of walks. If each instance \(I\in \mathcal {I}\) is supported by a pair of walks from \(\mathcal {S}\) then \(|\mathcal {S}| \ge |\mathcal {I}|\). Proof It is sufficient to prove that each pair of walks can support only one instance from the set \(\mathcal {I}\). For the sake of contradiction assume that there exists a pair of walks \(S\in \mathcal {S}\) supporting two different instances \(I_{i_1,j_1}, I_{i_2,j_2} \in \mathcal {I}\) for \(i_1,i_2\in \{0,\dots ,\lfloor 2\pi \frac{\sqrt{D}}{6}\rfloor - 1\}\) and \(j_1,j_2\in \{0,\dots ,\lfloor 2\pi \frac{D}{30}\rfloor - 1\}\). Let us analyze two cases. - \(i_1\ne i_2\). Let \(\alpha \) be the walk bisector of the walk of agent A. By Lemma 2, we need both inequalities \(|\alpha -\gamma (I_{i_1,j_1})| \le 3/\sqrt{D}\) and \(|\alpha -\gamma (I_{i_2,j_2})| \le 3/\sqrt{D}\) in order to assure that S supports \(I_{i_1,j_1}\) and \(I_{i_2,j_2}\). However, these inequalities imply that \(|\gamma (I_{i_1,j_1})-\gamma (I_{i_2,j_2})| \le 6/\sqrt{D}\) and, by the definition of \(\mathcal {I}\), \(|\gamma (I_{i_1,j_1})-\gamma (I_{i_2,j_2})|> 6/\sqrt{D}\) which gives a contradiction. - \(i_1=i_2\) and \(j_1\ne j_2\). Let \(\alpha \) be the walk bisector of the walk of agent A and let \(\beta (I_{i_k,j_k})\) be the walk bisector of the walk of agent B with respect to the global orientation for the instance \(I_{i_k,j_k}\) where \(k\in \{1,2\}\). By Lemma 3, we need that both \(\gamma (I_{i_1,j_1})\in \left[ \frac{\alpha +\beta (I_{i_1,j_1})}{2}-\frac{6}{D},\frac{\alpha +\beta (I_{i_1,j_1})}{2}+\frac{6}{D}\right] \) and \(\gamma (I_{i_2,j_2})\in \left[ \frac{\alpha +\beta (I_{i_2,j_2})}{2}-\frac{6}{D},\frac{\alpha +\beta (I_{i_2,j_2})}{2}+\frac{6}{D}\right] \) hold, in order to assure that S supports both \(I_{i_1,j_1}\) and \(I_{i_2,j_2}\). However, as \(\gamma (I_{i_1,j_1})=\gamma (I_{i_2,j_2})\), \(\beta (I_{i_1,j_1})=\beta (I_{i_2,j_2})+\phi (I_{i_1,j_1})-\phi (I_{i_2,j_2})\), and, given that \(|\phi (I_{i_1,j_1})-\phi (I_{i_2,j_2})| \ge \frac{30}{D}\), the segments $$\begin{aligned} \left[ \frac{\alpha +\beta (I_{i_1,j_1})}{2}-\frac{6}{D},\frac{\alpha +\beta (I_{i_1,j_1})}{2}+\frac{6}{D}\right] \end{aligned}$$and $$\begin{aligned}&\left[ \frac{\alpha +\beta (I_{i_2,j_2})}{2}-\frac{6}{D},\frac{\alpha +\beta (I_{i_2,j_2})}{2}+\frac{6}{D}\right] \\ =&\left[ \frac{\alpha +\beta (I_{i_1,j_1})}{2} + \frac{\phi (I_{i_1,j_1})-\phi (I_{i_2,j_2})}{2}-\frac{6}{D}\right. ,\\&\left. \frac{\alpha +\beta (I_{i_1,j_1})}{2}+ \frac{\phi (I_{i_1,j_1})-\phi (I_{i_2,j_2})}{2}+\frac{6}{D}\right] \end{aligned}$$are disjoint, which gives a contradiction.\(\square \) Using Lemma 7, we can prove the main theorem of this section. Theorem 7 The time of approach for two agents with arbitrary orientations, starting at a distance at most D is \(\Omega (D^2\sqrt{D})\), even if agents start simultaneously. Proof The proof is by contradiction. Assume that there is an approach algorithm for two agents with arbitrary orientations, starting at a distance D, which completes the approach task in time at most \(\frac{1}{32}\left( \frac{\sqrt{D}}{6}\cdot \frac{D}{30} - 1\right) (D-2) + D\) for all instances in \(\mathcal {I}\). First, consider only walks wholly contained inside the range circles of radius D/2 of the respective agents. We say that a pair of walks \(\{w_1,w_2\}\) is useful if there exists a time t such that both \(w_1\) and \(w_2\) are in their meeting areas at time t.Footnote 2 The pair of walks \(\{w_1,w_2\}\) cannot lead to approach in any instance, if it is not useful. (The reason is that, in such a case, at each time t the actual distance between the agents is larger than 1, regardless of the current instance.) A usefulness witness of a useful set \(\{w_1,w_2\}\) is the smallest time t such that both walks are in their meeting areas at time t. Consider the sequence \(t_10\), such that A is at \(C_1\) before approach happens for any of the instances from \(\mathcal {I}_{i,j}\) (recall that approach cannot happen as long as both agents are inside their range discs, according to the definition of \(\mathcal {I}_{i,j}\)). Observe that, by choosing different values of \(a\in [0,3]\), we can change the location of \(C_1\) with respect to the base \(O_B\) of B in the instances \(I'_{a,j}\) for all \(j\in [0,3]\). Indeed, as we assume that the orientation of A corresponds to the global orientation, the value of \(\gamma (I'_{a,b})\) determines relative location of \(C_1\) and \(O_B\) as illustrated on Fig. 8. The value of \(\gamma (I'_{a,b})\) is determined by the value of a. Let \(a \in [0,3]\) be such that the base \(O_B\) of B is furthest from the point \(C_1\) in \(I'_{a,b'}\), for \(b'\in [0,3]\). Let l be the line tangent to the range circles of both agents, let \(l_A\) and \(l_B\) be the lines parallel to l, going through the bases \(O_A\) and \(O_B\) of the agents, respectively – see Fig. 8. Then, in the instance \(I'_{a, b}\) for \(b\in [0,3]\), the point \(C_1\) is on the opposite side of \(l_A\) than the tangency point of the range circles of the agents. And therefore \(C_1\) is further from the tangency point of the range circles of the agents than from the base of the agent A and so it is further from the base of B than \(D + 1\). Indeed, as \(|C_1 O_A|>D/2\), \(|O_A O_B|=D\) and the angle \(\angle C_1 O_A O_B\) is obtuse, the Pythagorean Theorem implies that for \(D>5\). As A has at this point only \(D/2 - \varepsilon _1\) fuel left, the agent B must in this case travel further from its base than D/2 in order to ensure approach of the agents. But this fact contradicts our assumption that only one of the agents leaves its range disk during the execution of the algorithm. Let \(C_2\) be any point in the special walk of B at distance \(D/2+\varepsilon _2>0\) from the base of agent B. Again, let b be such that the greatest distance between \(C_1\) and \(C_2\) amongst all the instances \(I'_{a,b'}\) for \(b'\in [0,3]\) is obtained for \(I'_{a,b}\). Then, the point \(C_2\) is located on the opposite side of \(l_B\) than \(C_1\) in \(I'_{a,b}\) – see Fig. 9. Inspecting the triangle \(\Delta C_1 O_A C_2\) with the obtuse angle \(\angle C_1 O_A C_2\), we obtain the following lower bound on the distance between \(C_1\) and \(C_2\) for \(D>5\), by the Pythagorean Theorem. On the other hand, the amount of fuel left in the tank of A at the point \(C_1\) and the amount of fuel left in the tank of B at the point \(C_2\) are smaller than D/2 since the agents are outside of their range discs at these points. Thus, the approach cannot occur for the instance \(I'_{a,b}\). As our assumption led to an occurrence of an instance without approach, the algorithm working in time \(\frac{1}{32}\cdot \left( \frac{\sqrt{D}}{6} \frac{D}{30} - 1\right) (D-2) + D\) cannot ensure the approach for all instances from \(\mathcal {I}\), which concludes the proof. \(\square \) 5 Discussion In this section, we discuss two assumptions of our model. The first is that the size of the tank (i.e., the distance that an agent can travel without replenishing the tank) is D, and the second is that the time of approach is counted from the wake-up of the later agent. Considering the first assumption, it is natural to ask if a smaller tank wouldn’t be enough. First observe that an agent with tank of size x cannot go at distance larger than x/2 from its base, possibly apart from the last trip that does not end at the base, because then it would be unable to get back to the base in order to replenish its tank. This implies that the size of the tank must be strictly larger than \(D-1\). Indeed, consider two agents at distance exactly D. If the size x of the tank were strictly smaller than \(D-1\) then agents could never approach without going farther than x/2 from their bases, as their distance would be always larger than 1. It can also be shown that the adversary can place the bases of agents in such a way that approach could not happen during the final trip, when an agent does not have to get back to the base. If the size of the tank were exactly \(D-1\) then the only way to approach without travelling farther than \((D-1)/2\) from the base would be for both agents to go straight on the segment joining their bases, each at distance exactly \((D-1)/2\). Clearly, for any hypothetical algorithm of approach, the adversary can place the bases in order to avoid such a perfect guess of direction in any finite time. Similarly as before, the adversary can prevent approach during the final trip. The remaining case is that of a tank of size \((D-1)+\epsilon \), for some \(0<\epsilon <1\). By slightly modifying our algorithms, it can be shown that, for each of our models, approach can be guaranteed with the same time complexity, whenever the tanks of the agents have size \((D-1)+\epsilon \), for any constant \(0<\epsilon <1\). The second assumption is that the time of approach is counted from the wake-up of the later agent. An alternative way would be to count time from the wake-up of the earlier agent. However, for any \(D>2\), consider two agents with tanks of size D and bases at distance D. Before the wake-up of the later agent, the earlier agent cannot approach it without traveling farther than D/2 from its base. Since the adversary can make the delay between the wake-up times of the agents arbitrarily long, the time of approach counted from the wake-up of the earlier agent would be unbounded. 6 Conclusion We considered the problem of approach of agents with restricted tanks and designed algorithms of optimal complexity, for any of the four scenarios yielded by the presence or absence of our two coherence assumptions. In this paper, we heavily relied on the synchronous character of the agents: they can stay put for a chosen amount of time and when they travel, they always move at speed 1. It is natural to ask how the problem of approach for agents with restricted tanks changes in the asynchronous setting, where agents can choose the direction and distance of their moves but the adversary decides the speeds of the agents. In this model, agents cannot choose to wait, as the adversary controls waiting times as well. The problem of asynchronous approach for agents with unrestricted tanks has been solved in [4]. What is the solution of it for agents with restricted tanks and how large tanks are needed? As for the synchronous model considered in this paper, one can observe that the tanks with capacity 2D allow for the approach in time \(O(D^2)\) regardless of the time coherence and orientation coherence assumptions. Indeed, given the tank with fuel 2D, agent Blue can for example explore its whole D-neighbourhood until the approach happens, while agent Red does not move at all. Hence, an interesting open questions is what is the minimum value of the size of the tanks to obtain approach time \(O(D^2)\) for all coherence assumptions. Data Availability No datasets were generated or analysed during the current study. Notes The discussion of the size of the tank is postponed to Sect. 5. Note that we work in the model with common start here, so both agents work according to the same time. Recall that the range disc of an agent is the disk with radius D/2 centered at the base of the agent. References Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous. Kluwer Academic Publications, Netherlands (2003) Awerbuch, B., Betke, M., Rivest, R.L., Singh, M.: Piecemeal graph exploration by a mobile robot. Inf. Comput. 152, 155–172 (1999) Baeza-Yates, R., Culberson, J., Rawlins, J.: Searching the plane. Inf. Comput. 106, 234–252 (1993) Bouchard, S., Bournat, M., Dieudonné, Y., Dubois, S., Petit, F.: Asynchronous approach in the plane: a deterministic polynomial algorithm. Distrib. Comput. 32, 317–337 (2019) Bouchard, S., Dieudonné, Y., Labourel, A., Pelc, A.: Almost-optimal deterministic treasure hunt in unweighted graphs. ACM Trans. Algor. 19, 22:1-22:32 (2023) Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Distributed computing by mobile robots: Gathering. SIAM J. Comput. 41, 829–879 (2012) Cohen, R., Peleg, D.: Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM J. Comput. 34, 1516–1528 (2005) Czyzowicz, J., Gasieniec, L., Killick, R., Kranakis, E.: Symmetry breaking in the plane: Rendezvous by robots with unknown attributes, Proc. 38th ACM Symp. on Principles of Distributed Computing (PODC 2019): 4-13 Dieudonné, Y., Pelc, A., Petit, F.: Almost universal anonymous rendezvous in the plane. Algorithmica 85, 3110–3143 (2023) Dieudonné, Y., Pelc, A., Villain, V.: How to meet asynchronously at polynomial cost. SIAM J. Comput. 44, 844–867 (2015) Duncan, C.A., Kobourov, S.G., Kumar, V.S.A.: Optimal constrained graph exploration. ACM Trans. Algor. 2, 380–402 (2006) Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous oblivious robots with limited visibility. Theor. Comput. Sci. 337, 147–168 (2005) Gal, S.: Search Games: A Review. A Game Theoretic Perspective, Search Theory, pp. 3–15 (2013) Ghosh, S.K., Klein, R.: Online algorithms for searching and exploration in the plane. Computer Sci. Rev. 4, 189–201 (2010) Pelc, A.: Reaching a target in the plane with no information. Inf. Process. Lett. 140, 13–17 (2018) Pelc, A.: Deterministic rendezvous algorithms, In: Distributed Computing by Mobile Entities, P. Flocchini, G. Prencipe, N. Santoro, Eds., Springer, LNCS 11340 (2019) Ta-Shma, A., Zwick, U.: Deterministic rendezvous, treasure hunts and strongly universal exploration sequences. ACM Trans. Algor. 10, 12:1-12:15 (2014) Acknowledgements Supported by the National Science Center, Poland (NCN), grant 2020/39/B/ST6/03288. Andrzej Pelc was partially supported by NSERC discovery grant RGPIN 2024-03767 and by the Research Chair in Distributed Computing at the Université du Québec en Outaouais. Author information Authors and Affiliations Contributions Each author has provided equal share in each process of conducting research on the presented results as well as writing the manuscript, preparing figures, reviewing and other ingredients of work on this submission. Corresponding author Ethics declarations Competing interests The authors declare no competing interests. Additional information Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. Rights and permissions Open Access This article is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License, which permits any non-commercial use, sharing, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if you modified the licensed material. You do not have permission under this licence to share adapted material derived from this article or parts of it. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by-nc-nd/4.0/. About this article Cite this article Ganczorz, A., Jurdzinski, T., Pelc, A. et al. Approach of agents with restricted fuel tanks. Distrib. Comput. 39, 26 (2026). https://doi.org/10.1007/s00446-026-00518-x Received: Accepted: Published: Version of record: DOI: https://doi.org/10.1007/s00446-026-00518-x