Deterministic Meeting of Sniffing Agents in the Plane^*

Article type: Research Article

Authors: Elouasbi, Samir | Pelc, Andrzej^{; †}

Affiliations: Département d’informatique et d’ingénierie, Université du Québec en Outaouais, Gatineau, Canada. elos02@uqo.ca, pelc@uqo.ca

Correspondence: [†] Partially supported by NSERC discovery grant 8136 – 2013 and by the Research Chair in Distributed Computing at the Université du Québec en Outaouais. Address for correspondence: Département d’informatique et d’ingénierie, Université du Québec en Outaouais, Gatineau, Canada.

Note: [*] A preliminary version of this paper appeared in the Proc. 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO 2016), LNCS 9988.

Abstract: Two mobile agents, starting at arbitrary, possibly different times from arbitrary locations in the plane, have to meet. Agents are modeled as discs of diameter 1, and meeting occurs when these discs touch. Agents have different labels which are positive integers. Each agent knows its own label, but not the label of the other agent. Agents are equipped with compasses and have synchronized clocks. They make a series of moves. Each move specifies the direction and the duration of moving. This includes a null move which consists in staying inert for some time, or forever. In a non-null move agents travel at the same constant speed, normalized to 1. We assume that agents have sensors enabling them to estimate the distance from the other agent (defined as the distance between centers of discs), but not the direction towards it. We consider two models of estimation. In both models an agent reads its sensor at the moment of its appearance in the plane and then at the end of each move. This reading (together with the previous ones) determines the decision concerning the next move. In both models the reading of the sensor tells the agent if the other agent is already present. Moreover, in the monotone model, each agent can find out, for any two readings in moments t1 and t2, whether the distance from the other agent at time t1 was smaller, equal or larger than at time t2. In the weaker binary model, each agent can find out, at any reading, whether it is at distance less than ρ or at distance at least ρ from the other agent, for some real ρ > 1 unknown to them. Such distance estimation mechanism can be implemented, e.g., using chemical sensors. Each agent emits some chemical substance (scent), and the sensor of the other agent detects it, i.e., sniffs. The intensity of the scent decreases with the distance. In the monotone model it is assumed that the sensor is ideally accurate and can measure any change of intensity. In the binary model it is only assumed that the sensor can detect the scent below some distance (without being able to measure intensity) above which the scent is too weak to be detected. We show the impact of the two ways of sensing on the cost of meeting, defined as the total distance travelled by both agents until the meeting. For the monotone model we show an algorithm achieving meeting at cost O(D), where D is the initial distance between the agents. This complexity is optimal. For the binary model we show that, if agents start at distance smaller than ρ (i.e., when they sense each other initially) then meeting can be guaranteed at cost O(ρ log λ), where λ is the larger label, and that this cost cannot be improved in general. Finally we observe that, if agents start at distance αρ, for some constant α > 1 in the binary model, then sniffing does not help, i.e., the worst-case optimal meeting cost is of the same order of magnitude as without any sniffing ability.

Keywords: algorithm, rendezvous, mobile agent, synchronous, deterministic, plane, distance

DOI: 10.3233/FI-2018-1684

Journal: Fundamenta Informaticae, vol. 160, no. 3, pp. 281-301, 2018