We introduce a variant of the deterministic rendezvous problem for a pair of heterogeneous agents operating in an undirected graph, which differ in the time they require to traverse particular edges of the graph. Each agent knows the complete topology of the graph and the initial positions of both agents. The agent also knows its own traversal times for all of the edges of the graph, but is unaware of the corresponding traversal times for the other agent. The goal of the agents is to meet on an edge or a node of the graph. In this scenario, we study the time required by the agents to meet, compared to the meeting time @math in the offline scenario in which the agents have complete knowledge about each others speed characteristics. When no additional assumptions are made, we show that rendezvous in our model can be achieved after time @math in a @math -node graph, and that such time is essentially in some cases the best possible. However, we prove that the rendezvous time can be reduced to @math when the agents are allowed to exchange @math bits of information at the start of the rendezvous process. We then show that under some natural assumption about the traversal times of edges, the hardness of the heterogeneous rendezvous problem can be substantially decreased, both in terms of time required for rendezvous without communication, and the communication complexity of achieving rendezvous in time @math .
Scenarios with agents having different capabilities have been also studied. In @cite_4 the authors considered multiple colliding robots with different velocities traveling along a ring with a goal to determine their initial positions and velocities. Mobile agents with different speeds were also studied in the context of patrolling a boundary, see e.g. @cite_18 @cite_27 . In @cite_5 agents capable of traveling in two different modes that differ with maximal speeds were considered in the context of searching a line segment. We also mention that speed, although very natural, is not the only attribute that can be used to differentiate the agents. For example, authors in @cite_11 studied robots with different ranges or, in other words, with different battery sizes limiting the distance that a robot can travel.
@cite_18 @cite_4 @cite_27 @cite_5 @cite_11
1728603878 1981392728 2035206572 1833254390 1459833043
A set of k mobile agents are placed on the boundary of a simply connected planar object represented by a cycle of unit length. Each agent has its own predefined maximal speed, and is capable of moving around this boundary without exceeding its maximal speed. The agents are required to protect the boundary from an intruder which attempts to penetrate to the interior of the object through a point of the boundary, unknown to the agents. The intruder needs some time interval of length τ to accomplish the intrusion. Will the intruder be able to penetrate into the object, or is there an algorithm allowing the agents to move perpetually along the boundary, so that no point of the boundary remains unprotected for a time period τ? Such a problem may be solved by designing an algorithm which defines the motion of agents so as to minimize the idle time I, i.e., the longest time interval during which any fixed boundary point remains unvisited by some agent, with the obvious goal of achieving I < τ. Depending on the type of the environment, this problem is known as either boundary patrolling or fence patrolling in the robotics literature. The most common heuristics adopted in the past include the cyclic strategy, where agents move in one direction around the cycle covering the environment, and the partition strategy, in which the environment is partitioned into sections patrolled separately by individual agents. This paper is, to our knowledge, the first study of the fundamental problem of boundary patrolling by agents with distinct maximal speeds. In this scenario, we give special attention to the performance of the cyclic strategy and the partition strategy. We propose general bounds and methods for analyzing these strategies, obtaining exact results for cases with 2, 3, and 4 agents. We show that there are cases when the cyclic strategy is optimal, cases when the partition strategy is optimal and, perhaps more surprisingly, novel, alternative methods have to be used to achieve optimality. We study the localization problem in the ring: a collection of @math n anonymous mobile robots are deployed in a continuous ring of perimeter one. All robots start moving at the same time with arbitrary velocities, starting in clockwise or counterclockwise direction around the ring. The robots bounce against each other according to the principles of conservation of energy and momentum. The task of each robot is to find out, in finite time, the initial position and the initial velocity of every deployed robot. The only way that robots perceive the information about the environment is by colliding with their neighbors; robots have no control of their walks or velocities moreover any type of communication among them is not possible. The configuration of initial positions of robots and their speeds is considered feasible, if there is a finite time, after which every robot starting at this configuration knows initial positions and velocities of all other robots. It was conjectured in (2012) that if the principles of conservation of energy and momentum were assumed and the robots had arbitrary velocities, the localization problem might be solvable. We prove that this conjecture is false. We show that if @math v0,v1,?,vn-1 are the velocities of a given robot configuration @math S, then @math S is feasible if and only if @math vi?v¯ for all @math 0≤i≤n-1, where @math v¯=v0+?+vn-1n. To figure out the initial positions of all robots no more than @math 2min0≤i≤n-1|vi-v¯| time is required. Suppose we want to patrol a fence (line segment) using k mobile agents with speeds v 1, …, v k so that every point on the fence is visited by an agent at least once in every unit time period. conjectured that the maximum length of the fence that can be patrolled is (v 1 + … + v k ) 2, which is achieved by the simple strategy where each agent i moves back and forth in a segment of length v i 2. We disprove this conjecture by a counterexample involving k = 6 agents. We also show that the conjecture is true for k ≤ 3. We introduce and study a new problem concerning the exploration of a geometric domain by mobile robots. Consider a line segment [0,I] and a set of n mobile robots r 1,r 2,…, r n placed at one of its endpoints. Each robot has a searching speed s i and a walking speed w i , where s i < w i . We assume that every robot is aware of the number of robots of the collection and their corresponding speeds. We consider mobile agents of limited energy, which have to collaboratively deliver data from specified sources of a network to a central repository. Every move consumes energy that is proportional to the travelled distance. Thus, every agent is limited in the total distance it can travel. We ask whether there is a schedule of agents’ movements that accomplishes the delivery. We provide hardness results, as well as exact, approximation, and resource-augmented algorithms for several variants of the problem. Among others, we show that the decision problem is NP-hard already for a single source, and we present a 2-approximation algorithm for the problem of finding the minimum energy that can be assigned to each agent such that the agents can deliver the data.