8 Search Results for "Bouchard, Sébastien"

Document
DOI: 10.4230/LIPIcs.DISC.2025.33
Approach of Agents with Restricted Fuel Tanks

Authors: Adam Ganczorz, Tomasz Jurdzinski, Andrzej Pelc, and Grzegorz Stachowiak

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Two mobile agents, modelled 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²) 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²√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.
Cite as

Adam Ganczorz, Tomasz Jurdzinski, Andrzej Pelc, and Grzegorz Stachowiak. Approach of Agents with Restricted Fuel Tanks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 33:1-33:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ganczorz_et_al:LIPIcs.DISC.2025.33,
  author =	{Ganczorz, Adam and Jurdzinski, Tomasz and Pelc, Andrzej and Stachowiak, Grzegorz},
  title =	{{Approach of Agents with Restricted Fuel Tanks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{33:1--33:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.33},
  URN =		{urn:nbn:de:0030-drops-248506},
  doi =		{10.4230/LIPIcs.DISC.2025.33},
  annote =	{Keywords: mobile agent, approach, rendezvous, plane, restricted energy}
}
Document
Survey
DOI: 10.4230/TGDK.3.1.3
Uncertainty Management in the Construction of Knowledge Graphs: A Survey

Authors: Lucas Jarnac, Yoan Chabot, and Miguel Couceiro

Published in: TGDK, Volume 3, Issue 1 (2025). Transactions on Graph Data and Knowledge, Volume 3, Issue 1

Abstract
Knowledge Graphs (KGs) are a major asset for companies thanks to their great flexibility in data representation and their numerous applications, e.g., vocabulary sharing, Q&A or recommendation systems. To build a KG, it is a common practice to rely on automatic methods for extracting knowledge from various heterogeneous sources. However, in a noisy and uncertain world, knowledge may not be reliable and conflicts between data sources may occur. Integrating unreliable data would directly impact the use of the KG, therefore such conflicts must be resolved. This could be done manually by selecting the best data to integrate. This first approach is highly accurate, but costly and time-consuming. That is why recent efforts focus on automatic approaches, which represent a challenging task since it requires handling the uncertainty of extracted knowledge throughout its integration into the KG. We survey state-of-the-art approaches in this direction and present constructions of both open and enterprise KGs. We then describe different knowledge extraction methods and discuss downstream tasks after knowledge acquisition, including KG completion using embedding models, knowledge alignment, and knowledge fusion in order to address the problem of knowledge uncertainty in KG construction. We conclude with a discussion on the remaining challenges and perspectives when constructing a KG taking into account uncertainty.
Cite as

Lucas Jarnac, Yoan Chabot, and Miguel Couceiro. Uncertainty Management in the Construction of Knowledge Graphs: A Survey. In Transactions on Graph Data and Knowledge (TGDK), Volume 3, Issue 1, pp. 3:1-3:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{jarnac_et_al:TGDK.3.1.3,
  author =	{Jarnac, Lucas and Chabot, Yoan and Couceiro, Miguel},
  title =	{{Uncertainty Management in the Construction of Knowledge Graphs: A Survey}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{3:1--3:48},
  ISSN =	{2942-7517},
  year =	{2025},
  volume =	{3},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.3.1.3},
  URN =		{urn:nbn:de:0030-drops-233733},
  doi =		{10.4230/TGDK.3.1.3},
  annote =	{Keywords: Knowledge reconciliation, Uncertainty, Heterogeneous sources, Knowledge graph construction}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.13
Self-Stabilizing Weakly Byzantine Perpetual Gathering of Mobile Agents

Authors: Jion Hirose, Ryota Eguchi, and Yuichi Sudo

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
We study the Byzantine gathering problem involving k mobile agents with unique identifiers (IDs), f of which are Byzantine. These agents start the execution of a common algorithm from (possibly different) nodes in an n-node network, potentially starting at different times. Once started, the agents operate in synchronous rounds. We focus on weakly Byzantine environments, where Byzantine agents can behave arbitrarily but cannot falsify their IDs. The goal is for all non-Byzantine agents to eventually terminate at a single node simultaneously. In this paper, we first prove two impossibility results: (1) for any number of non-Byzantine agents, no algorithm can solve this problem without global knowledge of the network size or the number of agents, and (2) no self-stabilizing algorithm exists if k ≤ 2f even with n, k, f, and the length Λ_g of the largest ID among IDs of non-Byzantine agents, where the self-stabilizing algorithm enables agents to gather starting from arbitrary (inconsistent) initial states. Next, based on these results, we introduce a perpetual gathering problem and propose a self-stabilizing algorithm for this problem. This problem requires that all non-Byzantine agents always be co-located from a certain time onwards. If the agents know Λ_g and upper bounds N, K, F on n, k, f, the proposed algorithm works in O(K⋅ F⋅ Λ_g⋅ X(N)) rounds, where X(n) is the time required to visit all nodes in a n-nodes network. Our results indicate that while no algorithm can solve the original self-stabilizing gathering problem for any k and f even with exact global knowledge of the network size and the number of agents, the self-stabilizing perpetual gathering problem can always be solved with just upper bounds on this knowledge.
Cite as

Jion Hirose, Ryota Eguchi, and Yuichi Sudo. Self-Stabilizing Weakly Byzantine Perpetual Gathering of Mobile Agents. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hirose_et_al:LIPIcs.SAND.2025.13,
  author =	{Hirose, Jion and Eguchi, Ryota and Sudo, Yuichi},
  title =	{{Self-Stabilizing Weakly Byzantine Perpetual Gathering of Mobile Agents}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.13},
  URN =		{urn:nbn:de:0030-drops-230662},
  doi =		{10.4230/LIPIcs.SAND.2025.13},
  annote =	{Keywords: Distributed algorithms, Byzantine environments, Gathering}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.11
Gathering Teams of Deterministic Finite Automata on a Line

Authors: Younan Gao and Andrzej Pelc

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
Several mobile agents, modelled as deterministic finite automata, navigate in an infinite line in synchronous rounds. All agents start in the same round. In each round, an agent can move to one of the two neighboring nodes, or stay idle. Agents have distinct labels which are integers from the set {1,…,L}. They start in teams, each of which consists of x agents, for some fixed integer x. Agents in a team have the same starting node. The adversary decides the compositions of teams, and their starting nodes. Whenever an agent enters a node, it sees the entry port number and the states of all collocated agents; this information forms the input of the agent on the basis of which it transits to the next state and decides the current action. The aim is for all agents to gather at the same node and stop. Gathering is feasible, if this task can be accomplished for any decisions of the adversary, and its time is the worst-case number of rounds from the start till gathering. We consider the feasibility and time complexity of gathering teams of agents, and give a complete solution of this problem. It turns out that both feasibility and complexity of gathering depend on the crucial parameter x which is the size of teams. For the oriented line, gathering is impossible if x = 1, and it can be accomplished in time O(D), for x > 1, where D is the distance between the starting nodes of the most distant teams. This complexity is of course optimal. For the unoriented line, the situation is different. For x = 1, gathering is also impossible, but for x = 2, the optimal time of gathering is Θ(Dlog L), and for x ≥ 3 the optimal time of gathering is Θ(D). Solving the gathering problem for agents that are finite automata navigating in an infinite environment requires new methodological tools. Traditional gathering techniques in graphs are count driven: agents make decisions based on counting steps. Since distances between agents may be unbounded, agents have to count unbounded numbers of steps. When agents are finite automata, counting unbounded numbers of steps is impossible, hence we must use different methods. In all our gathering algorithms, changes of the agents' behavior are triggered not by counting steps but by events which are meetings between agents during which they interact. Hence our new technique is event driven. Designing the behavior of the agents based on meeting events, so as to guarantee gathering regardless of the adversary’s decisions is our main methodological contribution.
Cite as

Younan Gao and Andrzej Pelc. Gathering Teams of Deterministic Finite Automata on a Line. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.OPODIS.2024.11,
  author =	{Gao, Younan and Pelc, Andrzej},
  title =	{{Gathering Teams of Deterministic Finite Automata on a Line}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.11},
  URN =		{urn:nbn:de:0030-drops-225478},
  doi =		{10.4230/LIPIcs.OPODIS.2024.11},
  annote =	{Keywords: Gathering, deterministic finite automaton, mobile agent, team of agents, line, time}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.36
Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs

Authors: Sébastien Bouchard, Yoann Dieudonné, Arnaud Labourel, and Andrzej Pelc

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
A mobile agent navigating along edges of a simple connected graph, either finite or countably infinite, has to find an inert target (treasure) hidden in one of the nodes. This task is known as treasure hunt. The agent has no a priori knowledge of the graph, of the location of the treasure or of the initial distance to it. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure. Awerbuch, Betke, Rivest and Singh [Baruch Awerbuch et al., 1999] considered graph exploration and treasure hunt for finite graphs in a restricted model where the agent has a fuel tank that can be replenished only at the starting node s. The size of the tank is B = 2(1+α)r, for some positive real constant α, where r, called the radius of the graph, is the maximum distance from s to any other node. The tank of size B allows the agent to make at most {⌊ B⌋} edge traversals between two consecutive visits at node s. Let e(d) be the number of edges whose at least one extremity is at distance less than d from s. Awerbuch, Betke, Rivest and Singh [Baruch Awerbuch et al., 1999] conjectured that it is impossible to find a treasure hidden in a node at distance at most d at cost nearly linear in e(d). We first design a deterministic treasure hunt algorithm working in the model without any restrictions on the moves of the agent at cost 𝒪(e(d) log d), and then show how to modify this algorithm to work in the model from [Baruch Awerbuch et al., 1999] with the same complexity. Thus we refute the above twenty-year-old conjecture. We observe that no treasure hunt algorithm can beat cost Θ(e(d)) for all graphs and thus our algorithms are also almost optimal.
Cite as

Sébastien Bouchard, Yoann Dieudonné, Arnaud Labourel, and Andrzej Pelc. Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bouchard_et_al:LIPIcs.ICALP.2021.36,
  author =	{Bouchard, S\'{e}bastien and Dieudonn\'{e}, Yoann and Labourel, Arnaud and Pelc, Andrzej},
  title =	{{Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.36},
  URN =		{urn:nbn:de:0030-drops-141051},
  doi =		{10.4230/LIPIcs.ICALP.2021.36},
  annote =	{Keywords: treasure hunt, graph, mobile agent}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.48
Deterministic Treasure Hunt in the Plane with Angular Hints

Authors: Sébastien Bouchard, Yoann Dieudonné, Andrzej Pelc, and Franck Petit

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
A mobile agent equipped with a compass and a measure of length has to find an inert treasure in the Euclidean plane. Both the agent and the treasure are modeled as points. In the beginning, the agent is at a distance at most D>0 from the treasure, but knows neither the distance nor any bound on it. Finding the treasure means getting at distance at most 1 from it. The agent makes a series of moves. Each of them consists in moving straight in a chosen direction at a chosen distance. In the beginning and after each move the agent gets a hint consisting of a positive angle smaller than 2 pi whose vertex is at the current position of the agent and within which the treasure is contained. We investigate the problem of how these hints permit the agent to lower the cost of finding the treasure, using a deterministic algorithm, where the cost is the worst-case total length of the agent's trajectory. It is well known that without any hint the optimal (worst case) cost is Theta(D^2). We show that if all angles given as hints are at most pi, then the cost can be lowered to O(D), which is optimal. If all angles are at most beta, where beta<2 pi is a constant unknown to the agent, then the cost is at most O(D^{2-epsilon}), for some epsilon>0. For both these positive results we present deterministic algorithms achieving the above costs. Finally, if angles given as hints can be arbitrary, smaller than 2 pi, then we show that cost Theta(D^2) cannot be beaten.
Cite as

Sébastien Bouchard, Yoann Dieudonné, Andrzej Pelc, and Franck Petit. Deterministic Treasure Hunt in the Plane with Angular Hints. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 48:1-48:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bouchard_et_al:LIPIcs.ISAAC.2018.48,
  author =	{Bouchard, S\'{e}bastien and Dieudonn\'{e}, Yoann and Pelc, Andrzej and Petit, Franck},
  title =	{{Deterministic Treasure Hunt in the Plane with Angular Hints}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{48:1--48:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.48},
  URN =		{urn:nbn:de:0030-drops-99964},
  doi =		{10.4230/LIPIcs.ISAAC.2018.48},
  annote =	{Keywords: treasure hunt, deterministic algorithm, mobile agent, hint, plane}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.147
Byzantine Gathering in Polynomial Time

Authors: Sébastien Bouchard, Yoann Dieudonné, and Anissa Lamani

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
Gathering a group of mobile agents is a fundamental task in the field of distributed and mobile systems. This can be made drastically more difficult to achieve when some agents are subject to faults, especially the Byzantine ones that are known as being the worst faults to handle. In this paper we study, from a deterministic point of view, the task of Byzantine gathering in a network modeled as a graph. In other words, despite the presence of Byzantine agents, all the other (good) agents, starting from {possibly} different nodes and applying the same deterministic algorithm, have to meet at the same node in finite time and stop moving. An adversary chooses the initial nodes of the agents (the number of agents may be larger than the number of nodes) and assigns a different positive integer (called label) to each of them. Initially, each agent knows its label. The agents move in synchronous rounds and can communicate with each other only when located at the same node. Within the team, f of the agents are Byzantine. A Byzantine agent acts in an unpredictable and arbitrary way. For example, it can choose an arbitrary port when it moves, can convey arbitrary information to other agents and can change its label in every round, in particular by forging the label of another agent or by creating a completely new one. Besides its label, which corresponds to a local knowledge, an agent is assigned some global knowledge denoted by GK that is common to all agents. In literature, the Byzantine gathering problem has been analyzed in arbitrary n-node graphs by considering the scenario when GK=(n,f) and the scenario when GK=f. In the first (resp. second) scenario, it has been shown that the minimum number of good agents guaranteeing deterministic gathering of all of them is f+1 (resp. f+2). However, for both these scenarios, all the existing deterministic algorithms, whether or not they are optimal in terms of required number of good agents, have the major disadvantage of having a time complexity that is exponential in n and L, where L is the value of the largest label belonging to a good agent. In this paper, we seek to design a deterministic solution for Byzantine gathering that makes a concession on the proportion of Byzantine agents within the team, but that offers a significantly lower complexity. We also seek to use a global knowledge whose the length of the binary representation (that we also call size) is small. In this respect, assuming that the agents are in a strong team i.e., a team in which the number of good agents is at least some prescribed value that is quadratic in f, we give positive and negative results. On the positive side, we show an algorithm that solves Byzantine gathering with all strong teams in all graphs of size at most n, for any integers n and f, in a time polynomial in n and the length |l_{min}| of the binary representation of the smallest label of a good agent. The algorithm works using a global knowledge of size O(log log log n), which is of optimal order of magnitude in our context to reach a time complexity that is polynomial in n and |l_{min}|. Indeed, on the negative side, we show that there is no deterministic algorithm solving Byzantine gathering with all strong teams, in all graphs of size at most n, in a time polynomial in n and |l_{min}| and using a global knowledge of size o(log log log n).
Cite as

Sébastien Bouchard, Yoann Dieudonné, and Anissa Lamani. Byzantine Gathering in Polynomial Time. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 147:1-147:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bouchard_et_al:LIPIcs.ICALP.2018.147,
  author =	{Bouchard, S\'{e}bastien and Dieudonn\'{e}, Yoann and Lamani, Anissa},
  title =	{{Byzantine Gathering in Polynomial Time}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{147:1--147:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.147},
  URN =		{urn:nbn:de:0030-drops-91511},
  doi =		{10.4230/LIPIcs.ICALP.2018.147},
  annote =	{Keywords: gathering, deterministic algorithm, mobile agent, Byzantine fault, polynomial time}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.8
Asynchronous Approach in the Plane: A Deterministic Polynomial Algorithm

Authors: Sébastien Bouchard, Marjorie Bournat, Yoann Dieudonné, Swan Dubois, and Franck Petit

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
In this paper we study the task of approach of two mobile agents having the same limited range of vision and moving asynchronously in the plane. This task consists in getting them in finite time within each other's range of vision. The agents execute the same deterministic algorithm and are assumed to have a compass showing the cardinal directions as well as a unit measure. On the other hand, they do not share any global coordinates system (like GPS), cannot communicate and have distinct labels. Each agent knows its label but does not know the label of the other agent or the initial position of the other agent relative to its own. The route of an agent is a sequence of segments that are subsequently traversed in order to achieve approach. For each agent, the computation of its route depends only on its algorithm and its label. An adversary chooses the initial positions of both agents in the plane and controls the way each of them moves along every segment of the routes, in particular by arbitrarily varying the speeds of the agents. Roughly speaking, the goal of the adversary is to prevent the agents from solving the task, or at least to ensure that the agents have covered as much distance as possible before seeing each other. A deterministic approach algorithm is a deterministic algorithm that always allows two agents with any distinct labels to solve the task of approach regardless of the choices and the behavior of the adversary. The cost of a complete execution of an approach algorithm is the length of both parts of route travelled by the agents until approach is completed. Let Delta and l be the initial distance separating the agents and the length of (the binary representation of) the shortest label, respectively. Assuming that Delta and l are unknown to both agents, does there exist a deterministic approach algorithm whose cost is polynomial in Delta and l? Actually the problem of approach in the plane reduces to the network problem of rendezvous in an infinite oriented grid, which consists in ensuring that both agents end up meeting at the same time at a node or on an edge of the grid. By designing such a rendezvous algorithm with appropriate properties, as we do in this paper, we provide a positive answer to the above question. Our result turns out to be an important step forward from a computational point of view, as the other algorithms allowing to solve the same problem either have an exponential cost in the initial separating distance and in the labels of the agents, or require each agent to know its starting position in a global system of coordinates, or only work under a much less powerful adversary.
Cite as

Sébastien Bouchard, Marjorie Bournat, Yoann Dieudonné, Swan Dubois, and Franck Petit. Asynchronous Approach in the Plane: A Deterministic Polynomial Algorithm. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bouchard_et_al:LIPIcs.DISC.2017.8,
  author =	{Bouchard, S\'{e}bastien and Bournat, Marjorie and Dieudonn\'{e}, Yoann and Dubois, Swan and Petit, Franck},
  title =	{{Asynchronous Approach in the Plane: A Deterministic Polynomial Algorithm}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.8},
  URN =		{urn:nbn:de:0030-drops-79631},
  doi =		{10.4230/LIPIcs.DISC.2017.8},
  annote =	{Keywords: mobile agents, asynchronous rendezvous, plane, infinite grid, deterministic algorithm, polynomial cost}
}
  • Refine by Type
  • 8 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 4 2025
  • 1 2021
  • 2 2018
  • 1 2017

  • Refine by Author
  • 4 Bouchard, Sébastien
  • 4 Dieudonné, Yoann
  • 4 Pelc, Andrzej
  • 2 Petit, Franck
  • 1 Bournat, Marjorie
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs
  • 1 TGDK

  • Refine by Classification
  • 4 Theory of computation → Distributed algorithms
  • 2 Computing methodologies → Mobile agents
  • 2 Theory of computation → Design and analysis of algorithms
  • 1 Information systems → Graph-based database models
  • 1 Information systems → Information integration
  • Show More...

  • Refine by Keyword
  • 5 mobile agent
  • 3 deterministic algorithm
  • 3 plane
  • 2 Gathering
  • 2 treasure hunt
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact