Deterministic Meeting of Sniffing Agents in the Plane

• Autorzy: Elouasbi S. , Pelc A.

Identyfikatory

DOI

10.3233/FI-2018-1684

• Języki publikacji: EN

Abstrakty

EN

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 t₁ and t₂, whether the distance from the other agent at time t₁ was smaller, equal or larger than at time t₂. 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.

Słowa kluczowe

EN

algorithm; rendezvous; mobile agent; synchronous; deterministic; plane; distance

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 160, nr 3
• Strony: 281--301
• Opis fizyczny: Bibliogr. 20 poz., rys., wykr.

Twórcy

autor

Elouasbi S.

• Département d’informatique et d’ingénierie, Université du Québec en Outaouais, Gatineau, Canada

autor

Pelc A.

• Département d’informatique et d’ingénierie, Université du Québec en Outaouais, Gatineau, Canada

Bibliografia

• [1] Alpern, and Gal S. The theory of search games and rendezvous. Int. Series in Operations research and Management Science, Kluwer Academic Publisher, 2002. doi:10.1007/b100809.
• [2] Anderson E, and Fekete S. Two-dimensional rendezvous search, Operations Research, 2001;49:107-118. URL https://doi.org/10.1287/opre.49.1.107.11191.
• [3] Baba D, Izumi T, Ooshita F, Kakugawa H, Masuzawa T. Space-optimal rendezvous of mobile agents in asynchronous trees. Proc. 17th Int. Colloquium on Structural Information and Comm. Complexity, (SIROCCO 2010), Lecture Notes in Computer Science, vol 6058. Springer, Berlin, Heidelberg, 2010, pp.86-100. doi:10.1007/978-3-642-13284-1_8.
• [4] Bampas E, Czyzowicz J, Gasieniec L, Ilcinkas D, Labourel A. Almost optimal asynchronous rendezvous in infinite multidimensional grids, Proc. 24th International Symposium on Distributed Computing (DISC 2010), Lecture Notes in Computer Science, vol 6343. Springer, Berlin, Heidelberg, 2010, pp. 297-311. doi:10.1007/978-3-642-15763-9_28.
• [5] Chalopin J, Dieudonné Y, Labourel A, Pelc A. Rendezvous in networks in spite of delay faults, Distributed Computing, 2016:29(3):187-205. doi:10.1007/s00446-015-0259-2.
• [6] Cieliebak M, Flocchini P, Prencipe G, Santoro N. Distributed computing by mobile robots: Gathering, SIAM J. Comput., 2012;41(4):829-879. URL https://doi.org/10.1137/100796534.
• [7] Czyzowicz J, Gasieniec L, Pelc A. Gathering few fat mobile robots in the plane, Theoretical Computer Science, 2009;410(6-7):481-499. URL https://doi.org/10.1016/j.tcs.2008.10.005.
• [8] Czyzowicz J, Kosowski A, Pelc A. How to meet when you forget: Log-space rendezvous in arbitrary graphs, Distributed Computing, 2012:25(2):165-178. doi:10.1007/s00446-011-0141-9.
• [9] Das S, Dereniowski D, Kosowski A, Uznanski P. Rendezvous of distance-aware mobile agents in unknown graphs, Proc. 21st Int. Colloquium on Structural Information and Comm. Complexity (SIROCCO 2014), Lecture Notes in Computer Science, vol 8576. Springer, Cham, 2014 pp. 295-310. doi:10.1007/978-3-319-09620-9_23.
• [10] Dessmark A, Fraigniaud P, Kowalski D, Pelc A. Deterministic rendezvous in graphs. Algorithmica, 2006;46(1):69-96. doi:10.1007/s00453-006-0074-2.
• [11] Dieudonné Y, and Pelc A. Deterministic polynomial approach in the plane, Distributed Computing, 2015;28(2):111-129. doi:10.1007/s00446-014-0216-5.
• [12] Dieudonné Y, Pelc A, Villain V. How to meet asynchronously at polynomial cost, SIAM Journal on Computing, 205;44(3):844-867. URL https://doi.org/10.1137/130931990.
• [13] Flocchini P, Prencipe G, Santoro N, Widmayer P. Gathering of asynchronous robots with limited visibility, Theoretical Computer Science, 2005;337(1-3):147-168. URL https://doi.org/10.1016/j.tcs.2005.01.001.
• [14] Flocchini P, Santoro N, Viglietta G, Yamashita M. Rendezvous of two robots with constant memory, Proc. 20th Int. Colloquium on Structural Information and Comm. Complexity (SIROCCO 2013), Lecture Notes in Computer Science, vol 8179. Springer, Cham, 2013 pp. 189-200. doi:10.1007/978-3-319-03578-9_16.
• [15] Fraigniaud P, and Pelc A. Delays induce an exponential memory gap for rendezvous in trees, ACM Transactions on Algorithms, 2013;9(2):171-17:24. doi:10.1145/2438645.2438649.
• [16] Kranakis E, Krizanc D, and Morin P. Randomized Rendez-Vous with Limited Memory, Proc. 8th Latin American Theoretical Informatics (LATIN 2008), Lecture Notes in Computer Science, vol 4957. Springer, Berlin, Heidelberg, 2008 pp. 605-616.
• [17] Kranakis E, Krizanc D, Santoro N, and Sawchuk C. Mobile agent rendezvous in a ring, Proc. 23rd Int. Conf. on Distr. Computing Systems (ICDCS 2003), IEEE, 2003 pp. 592-599. doi:10.1109/ICDCS.2003.1203510.
• [18] Miller A, and Pelc A. Time versus cost tradeoffs for deterministic rendezvous in networks, Distributed Computing, 2016;29(1):51-64. doi:10.1007/s00446-015-0253-8.
• [19] Pelc A. Deterministic rendezvous in networks: A comprehensive survey, Networks 2012;59(3):331-347. doi:10.1002/net.21453.
• [20] Ta-Shma A, and Zwick U. Deterministic rendezvous, treasure hunts and strongly universal exploration sequences, ACM Trans. Algorithms, 2014,10(3):12:1-12:15. doi:10.1145/2601068.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).