20 results on '"Tixeuil, Sébastien"'
Search Results
2. Fault-Tolerant Mobile Robots
- Author
-
Défago, Xavier, Potop-Butucaru, Maria, Tixeuil, Sébastien, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Flocchini, Paola, editor, Prencipe, Giuseppe, editor, and Santoro, Nicola, editor
- Published
- 2019
- Full Text
- View/download PDF
3. Synchronous Gathering without Multiplicity Detection: a Certified Algorithm
- Author
-
Balabonski, Thibaut, Delga, Amélie, Rieg, Lionel, Tixeuil, Sébastien, and Urbain, Xavier
- Published
- 2019
- Full Text
- View/download PDF
4. Semi‐uniform deployment of mobile robots in perfect ℓ$$ \ell $$‐ary trees.
- Author
-
Shibata, Masahiro and Tixeuil, Sébastien
- Subjects
MOBILE robots ,PROBLEM solving ,TREES ,VISIBLE spectra ,ROBOTS - Abstract
Summary: In this paper, we consider the problem of semi‐uniform deployment for mobile robots in perfect ℓ$$ \ell $$‐ary trees. This problem requires robots to spread in the tree so that, for some positive integer d$$ d $$ and some fixed integer s(0≤s≤d−1)$$ s\left(0\le s\le d-1\right) $$, each node of depth s+dj(j≥0)$$ s+ dj\left(j\ge 0\right) $$ is occupied by a robot. Robots have an infinite visibility range but are opaque, and each robot can emit a light color visible to itself and other robots, taken from a set of κ$$ \kappa $$ colors, at each time step. Then, we clarify the solvability of the semi‐uniform deployment problem, focusing on the number of available light colors. First, we consider robots with κ=1$$ \kappa =1 $$. In this setting, we show that there is no collision‐free algorithm to solve the problem. Next, relax the number of available light colors, that is, we consider robots with κ=2$$ \kappa =2 $$. In this setting, we propose a collision‐free algorithm that can solve the problem. From these results, we can show that the semi‐uniform deployment problem can be solved when κ≥2$$ \kappa \ge 2 $$, and our proposed algorithm is optimal with respect to the number of used light colors (i.e., 2). [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
5. Formal verification of mobile robot protocols
- Author
-
Bérard, Béatrice, Lafourcade, Pascal, Millet, Laure, Potop-Butucaru, Maria, Thierry-Mieg, Yann, and Tixeuil, Sébastien
- Published
- 2016
- Full Text
- View/download PDF
6. Mobile Robots with Uncertain Visibility Sensors: Possibility Results and Lower Bounds.
- Author
-
Heriban, Adam and Tixeuil, Sébastien
- Subjects
- *
MOBILE robots , *DETECTORS , *MOBILE computing , *ROBOTS , *POSSIBILITY - Abstract
We consider mobile robotic entities that have to cooperate to solve assigned tasks. In the literature, two models have been used to model their visibility sensors: the full visibility model, where all robots can see all other robots, and the limited visibility model, where there exists a limit λ > 0 such that all robots closer than λ are seen and all robots further than λ are not seen. We introduce the uncertain visibility model, which generalizes both models by considering that a subset of the robots further than λ cannot be seen. An empty subset corresponds to the full visibility model, and a subset containing every such robot corresponds to the limited visibility model. Then, we explore the impact of this new visibility model on the feasibility of benchmarking tasks in mobile robots computing: gathering, uniform circle formation, luminous rendezvous, and leader election. For each task, we determine the weakest visibility adversary that prevents task solvability, and the strongest adversary that allows task solvability. Our work sheds new light on the impact of visibility sensors in the context of mobile robot computing, and paves the way for more realistic algorithms that can cope with uncertain visibility sensors. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
7. Optimally Gathering Two Robots
- Author
-
Heriban, Adam, Defago, Xavier, Défago, Xavier, Tixeuil, Sébastien, Networks and Performance Analysis (NPA), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Tokyo Institute of Technology [Tokyo] (TITECH), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Laboratory of Information, Network and Communication Sciences (LINCS), Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT), UPMC Sorbonne Universités, LIP6, and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
FOS: Computer and information sciences ,[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,optimal ,ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.1: Models of Computation ,gathering ,Computer science ,Real-time computing ,ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Measure (physics) ,0102 computer and information sciences ,02 engineering and technology ,Computational Complexity (cs.CC) ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] ,01 natural sciences ,Computer Science::Robotics ,[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,Computer Science - Robotics ,ACM: D.: Software/D.1: PROGRAMMING TECHNIQUES/D.1.3: Concurrent Programming ,[INFO.INFO-MC]Computer Science [cs]/Mobile Computing ,Computer Science - Data Structures and Algorithms ,0202 electrical engineering, electronic engineering, information engineering ,Mobile robots ,[INFO.INFO-RB]Computer Science [cs]/Robotics [cs.RO] ,Data Structures and Algorithms (cs.DS) ,Impossibility ,Protocol (object-oriented programming) ,ComputingMilieux_MISCELLANEOUS ,ACM: C.: Computer Systems Organization/C.2: COMPUTER-COMMUNICATION NETWORKS/C.2.4: Distributed Systems ,Aside ,Mobile robot ,ACM: C.: Computer Systems Organization/C.2: COMPUTER-COMMUNICATION NETWORKS ,ACM: D.: Software/D.1: PROGRAMMING TECHNIQUES ,Computer Science - Computational Complexity ,robots with lights ,[INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF] ,Computer Science - Distributed, Parallel, and Cluster Computing ,ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems ,010201 computation theory & mathematics ,Asynchronous communication ,Robot ,020201 artificial intelligence & image processing ,[INFO.INFO-ES]Computer Science [cs]/Embedded Systems ,Distributed, Parallel, and Cluster Computing (cs.DC) ,Finite time ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Robotics (cs.RO) - Abstract
We present a self-stabilizing algorithm that ensures in finite time the gathering of two robots in the non-rigid ASYNC model. To circumvent established impossibility results, we assume robots are equipped with 2-colors lights and are able to measure distances between one another. Aside from its light, a robot has no memory of its past actions, and its protocol is deterministic. Since, in the same model, gathering is impossible when lights have a single color, our solution is optimal with respect to the number of used colors.
- Published
- 2017
8. Parameterized verification of algorithms for oblivious robots on a ring.
- Author
-
Sangnier, Arnaud, Sznajder, Nathalie, Potop-Butucaru, Maria, and Tixeuil, Sébastien
- Subjects
MOBILE robots ,ROBOTS ,ALGORITHMS ,ARITHMETIC - Abstract
We study verification problems for autonomous swarms of mobile robots that self-organize and cooperate to solve global objectives. In particular, we focus in this paper on the model proposed by Suzuki and Yamashita of anonymous robots evolving in a discrete space with a finite number of locations (here, a ring). A large number of algorithms have been proposed working for rings whose size is not a priori fixed and can be hence considered as a parameter. Handmade correctness proofs of these algorithms have been shown to be error-prone, and recent attention had been given to the application of formal methods to automatically prove those. Our work is the first to study the verification problem of such algorithms in the parameterized case. We show that safety and reachability problems are undecidable for robots evolving asynchronously. On the positive side, we show that safety properties are decidable in the synchronous case, as well as in the asynchronous case for a particular class of algorithms. Several other properties of the protocol can be decided as well. Decision procedures rely on an encoding in Presburger arithmetics formulae that can be verified by an SMT-solver. Feasibility of our approach is demonstrated by the encoding of several case studies. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
9. Probabilistic Asynchronous Arbitrary Pattern Formation
- Author
-
Bramas, Quentin, Tixeuil, Sébastien, Networks and Performance Analysis (NPA), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Laboratory of Information, Network and Communication Sciences (LINCS), Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), This work was performed within the Labex SMART supported by French state funds managed by the ANR within the Investissementsd’Avenir programme under reference ANR-11-IDEX-0004-02., and Université Pierre et Marie Curie
- Subjects
Mobile Robots ,[INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA] ,Randomized Algorithm ,[INFO.INFO-RB]Computer Science [cs]/Robotics [cs.RO] ,Pattern Formation ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] - Abstract
We propose a new probabilistic pattern formation algorithm for oblivious mobile robots that operates inthe ASYNC model. Unlike previous work, our algorithm makes no assumptions about the local coordinatesystems of robots (the robots do not share a common “North” nor a common “Right”), yet it preserves theability from any initial configuration that contains at least 5 robots to form any general pattern (and not justpatterns that satisfy symmetricity predicates). Our proposal also gets rid of the previous assumption (in thesame model) that robots do not pause while moving (so, our robots really are fully asynchronous), and theamount of randomness is kept low – a single random bit per robot per Look-Compute-Move cycle is used.Our protocol consists in the combination of two phases, a probabilistic leader election phase, and a deterministicpattern formation one. As the deterministic phase does not use chirality, it may be of independentinterest in the deterministic context. A noteworthy feature of our algorithm is the ability to form patternswith multiplicity points (except the gathering case due to impossibility results), a new feature in the contextof pattern formation that we believe is an important asset of our approach.
- Published
- 2015
10. The Random Bit Complexity of Mobile Robots Scattering.
- Author
-
Bramas, Quentin and Tixeuil, Sébastien
- Subjects
- *
MOBILE robots , *COMPUTATIONAL complexity , *TOPOLOGICAL spaces , *COMPUTER algorithms , *SCATTERING (Mathematics) - Abstract
We consider the problem of scattering n robots in a two dimensional continuous space. As this problem is impossible to solve in a deterministic manner, all solutions must be probabilistic. We investigate the amount of randomness (that is, the number of random bits used by the robots) that is required to achieve scattering. We first prove that n log n random bits are necessary to scatter n robots in any setting. Also, we give a sufficient condition for a scattering algorithm to be random bit optimal. As it turns out that previous solutions for scattering satisfy our condition, they are hence proved random bit optimal for the scattering problem. Then, we investigate the time complexity of scattering when strong multiplicity detection is not available. We prove that such algorithms cannot converge in constant time in the general case and in o(log log n) rounds for random bits optimal scattering algorithms. However, we present a family of scattering algorithms that converge as fast as needed without using multiplicity detection. Also, we put forward a specific protocol of this family that is random bit optimal ( O( n log n) random bits are used) and time optimal ( O(log log n) rounds are used). This improves the time complexity of previous results in the same setting by a log n factor. Aside from characterizing the random bit complexity of mobile robot scattering, our study also closes the time complexity gap with and without strong multiplicity detection (that is, O(1) time complexity is only achievable when strong multiplicity detection is available, and it is possible to approach a constant value as desired otherwise). [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
11. On the self-stabilization of mobile oblivious robots in uniform rings.
- Author
-
Ooshita, Fukuhito and Tixeuil, Sébastien
- Subjects
- *
SELF-stabilization (Computer science) , *RING theory , *COMPUTER algorithms , *MOBILE robots , *COMPUTER networks , *PROBABILITY theory - Abstract
We investigate self-stabilizing algorithms for anonymous and oblivious robots in uniform ring networks, that is, we focus on algorithms that can start from any initial configuration (including those with multiplicity points). First, we show that no probabilistic self-stabilizing gathering algorithm exists in the asynchronous (ASYNC) model or if only global-weak and local-strong multiplicity detection is available. This impossibility result implies that a common assumption about initial configurations (no two robots share a node initially) is a very strong one. On the positive side, we give a probabilistic self-stabilizing algorithm for the gathering and orientation problems in the semi-synchronous (SSYNC) model with global-strong multiplicity detection. With respect to impossibility results, those are the weakest system hypotheses. In addition, as an application of the previous algorithm, we provide a self-stabilizing algorithm for the set formation problem. Our results imply that any static set formation can be realized in a self-stabilizing manner in this model. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
12. Ring exploration with myopic luminous robots.
- Author
-
Ooshita, Fukuhito and Tixeuil, Sébastien
- Subjects
- *
AUTONOMOUS robots , *ROBOTS , *MOBILE robots - Abstract
We investigate exploration algorithms for autonomous mobile robots evolving in uniform ring-shaped networks. Unlike previous works, we consider myopia (each robot can only observe its neighboring nodes) and luminosity (each robot can use only two colors for its light) properties for the robots. As a main contribution, we prove that (i) in the FSYNC model, two (resp. three) myopic robots are necessary and sufficient to achieve perpetual (resp. terminating) exploration, and (ii) in the SSYNC and ASYNC models, three (resp. four) myopic robots are necessary and sufficient to achieve perpetual (resp. terminating) exploration. We also show that, in all execution models, our perpetual exploration algorithm is universal. That is, the algorithm solves perpetual exploration from any solvable initial configuration with two (resp. three) myopic robots and two colors in the FSYNC model (resp. the SSYNC and ASYNC models). On the other hand, we provide impossibility results for universal terminating exploration. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
13. Stand up indulgent gathering.
- Author
-
Bramas, Quentin, Lamani, Anissa, and Tixeuil, Sébastien
- Subjects
- *
MOBILE robots , *ROBOTS - Abstract
We consider a swarm of mobile robots evolving in a bidimensional Euclidean space. We study a variant of the crash-tolerant gathering problem: if no robot crashes, robots have to meet at the same arbitrary location, not known beforehand, in finite time; if one or several robots crash at the same location, the remaining correct robots gather at the crash location to rescue them. Motivated by impossibility results in the semi-synchronous setting, we present the first solution to the problem for the fully synchronous setting that operates in the vanilla Look-Compute-Move model with no additional hypotheses: robots are oblivious, disoriented, have no multiplicity detection capacity, and may start from arbitrary positions (including those with multiplicity points). We furthermore show that robots gather in a time that is proportional to the initial maximum distance between robots. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
14. Using model checking to formally verify rendezvous algorithms for robots with lights in Euclidean space.
- Author
-
Défago, Xavier, Heriban, Adam, Tixeuil, Sébastien, and Wada, Koichi
- Subjects
- *
MOBILE robots , *ROBOTS , *DISTRIBUTED algorithms , *ALGORITHMS , *ROBOT programming , *AUTONOMOUS robots , *SYNCHRONIC order - Abstract
The paper details the first successful attempt at using model checking techniques to verify the correctness of distributed algorithms for robots evolving in a continuous environment. The study focuses on the problem of rendezvous of two robots with lights. There exist many different rendezvous algorithms that aim at finding the minimal number of colors needed to solve rendezvous in various synchrony models (e.g. , FSYNC, SSYNC, ASYNC). While these rendezvous algorithms are typically very simple, their analysis and proof of correctness tend to be extremely complex, tedious, and error-prone as impossibility results are based on subtle interactions between the activation schedules of the robots. The paper presents a generic verification model that can be concretely expressed in available software model-checkers. In particular, we explain the subtle design decisions that allow to keep the search space finite and tractable, as well as prove several important theorems that support them. As a sanity check, we use the model to verify several known rendezvous algorithms in six different models of synchrony. In each case, we find that the results obtained from the model checker are consistent with the results known in the literature. The model checker outputs a counter-example execution in every case that is known to fail. In the course of developing and proving the validity of the model, we identified several fundamental theorems, including the ability for a well chosen algorithm and ASYNC scheduler to produce an emerging property of memory in a system of oblivious mobile robots, and why it is not a problem when robots executing the gathering algorithms are equipped with lights. [Display omitted] • We describe a model to verify mobile robot gathering algorithms that evolve in a Euclidean continuous space. • We show that positive results obtained for the model extend to the initial system model. • We model check all known mobile robot gathering algorithms and verify previous pen-and-paper results. • We obtain new insights about key system hypotheses about problem solvability. • We introduce weaker models of consistency (inspired by regular registers). • We derive a new algorithm that solves mobile robot gathering in such a model. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
15. The agreement power of disagreement.
- Author
-
Bramas, Quentin, Lamani, Anissa, and Tixeuil, Sébastien
- Subjects
- *
AUTONOMOUS robots , *MOBILE robots , *ROBOTS - Abstract
We consider the rendezvous problem of two autonomous robots with very weak capacities. This problem is notoriously impossible to solve in the semi-synchronous execution model when robots are deterministic, oblivious, and their ego-centered coordinate system is fully symmetric. We show that if the robots disagree on the unit distance of their coordinate system, it becomes possible to solve rendezvous and agree on a final common location, without additional assumptions. We also generalize our scheme to solve gathering (that is, rendezvous of n ≥ 2 robots) in the same setting, possibly starting from a bivalent configuration. • We introduce new techniques that take advantage of different unit distances. • We design and prove a solution to the rendezvous problem of oblivious and disoriented robots in SSYNC. • We generalize our design to solve gathering from any arbitrary initial configuration. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
16. Gathering fat mobile robots with slim omnidirectional cameras.
- Author
-
Honorat, Anthony, Potop-Butucaru, Maria, and Tixeuil, Sébastien
- Subjects
- *
MOBILE robots , *OMNIRANGE system , *INFORMATION asymmetry , *CAMERAS , *DISTRIBUTED computing , *COMPUTER algorithms - Abstract
Most distributed solutions for swarms of oblivious mobile robots consider that individual robots are represented by points that can overlap, which is physically impossible. A recent trend is to consider “fat” robots, i.e. robots that are represented by unit discs and cannot overlap, but still assume that robots can be seen if there exists a point in the unit disc that has a line of sight with the target robot. Again, this does not match practical sensing devices implementations. We propose a new model for sensing devices that originates from embedded omnidirectional cameras, sonars, or lasers found on real robots. This model opens new algorithmic issues since the visibility relation becomes asymmetric. As a case study, we consider the gathering problem for four volumic robots and provide an algorithm to solve the problem in the fully asynchronous setting in our extended model. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
17. Optimal probabilistic ring exploration by semi-synchronous oblivious robots.
- Author
-
Devismes, Stéphane, Petit, Franck, and Tixeuil, Sébastien
- Subjects
- *
COMBINATORIAL optimization , *PROBABILITY theory , *MOBILE robots , *MATHEMATICAL symmetry , *MATHEMATICAL bounds , *RING theory , *PROBLEM solving - Abstract
Abstract: We consider a team of k identical, oblivious, and semi-synchronous mobile robots that are able to sense (i.e., view) their environment, yet are unable to communicate, and evolve on a constrained path. Previous results in this weak scenario show that initial symmetry yields high lower bounds when problems are to be solved by deterministic robots. In this paper, we initiate research on probabilistic bounds and solutions in this context, and focus on the exploration problem of anonymous unoriented rings of any size n. It is known that deterministic robots are necessary and sufficient to solve the problem, provided that k and n are coprime. By contrast, we show that four identical probabilistic robots are necessary and sufficient to solve the same problem, also removing the coprime constraint. Our positive results are constructive. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
18. On time complexity for connectivity-preserving scattering of mobile robots.
- Author
-
Izumi, Taisuke, Kaino, Daichi, Potop-Butucaru, Maria Gradinariu, and Tixeuil, Sébastien
- Subjects
- *
SCATTERING (Physics) , *MOBILE robots , *ASYNCHRONOUS learning , *SYNCHRONOUS electric motors , *SYNCHRONOUS circuits - Abstract
The scattering problem is a fundamental task for mobile robots, which requires that no two robots share the same position. We investigate the scattering problem in the limited-visibility model. In particular, we focus on the connectivity-preservation property, i.e. , the scattering must be achieved so that the disconnection of the visibility graph never occurs (in the visibility graph nodes are robots and edges are their visibility relationship). This paper shows a new scattering algorithm in the semi-synchronous model, which guarantees the connectivity preservation property, and reaches a scattered configuration within O ( min { n , D 2 + log n } ) asynchronous rounds in expectation, where n is the number of robots and D is the diameter of the initial visibility graph. Note that a part of this complexity analysis is adaptive in the sense that it depends on D . This implies that our algorithm quickly scatters all robots crowded with a small-diameter visibility graph. We also show two matching lower bounds for the connectivity-preserving scattering problem. The first lower bound is Ω ( n ) rounds in the case of D = Ω ( n ) , which is a lower bound applying to any connectivity-preserving algorithm. The second bound applies to a (reasonably) restricted class of algorithms, called conservative algorithms , which provides Ω ( D 2 ) -round lower bound. These two bounds imply that our algorithm achieves the optimal running time (in the sense of both adaptive and non-adaptive analyses) as conservative ones because it is conservative. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
19. Taking Advantage of Symmetries: Gathering of Asynchronous Oblivious Robots on a Ring
- Author
-
Klasing, Ralf, Kosowski, Adrian, Navarra, Alfredo, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Baker, Theodore P., editor, Bui, Alain, editor, and Tixeuil, Sébastien, editor
- Published
- 2008
- Full Text
- View/download PDF
20. The Agreement Power of Disagreement
- Author
-
Quentin Bramas, Anissa Lamani, Sébastien Tixeuil, Tixeuil, Sébastien, Sûreté et preuve de protocoles adaptatifs pour robots oublieux - - SAPPORO2019 - ANR-19-CE25-0005 - AAPG2019 - VALID, Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Les Hôpitaux Universitaires de Strasbourg (HUS)-Centre National de la Recherche Scientifique (CNRS)-Matériaux et Nanosciences Grand-Est (MNGE), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Réseau nanophotonique et optique, Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS), Networks and Performance Analysis (NPA), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Laboratory of Information, Network and Communication Sciences (LINCS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU), ANR-19-CE25-0005,SAPPORO,Sûreté et preuve de protocoles adaptatifs pour robots oublieux(2019), Equipe Réseaux du laboratoire ICUBE (ICUBE-Réseaux), Département Informatique du laboratoire ICUBE (ICUBE-Informatique), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), Université de Strasbourg (UNISTRA), Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Réseau nanophotonique et optique, Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Matériaux et nanosciences d'Alsace (FMNGE), Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), and Bramas, Quentin
- Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,General Computer Science ,Computer science ,Coordinate system ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,0102 computer and information sciences ,02 engineering and technology ,Topology ,[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] ,01 natural sciences ,Theoretical Computer Science ,[INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] ,Computer Science::Robotics ,[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,[INFO.INFO-PF] Computer Science [cs]/Performance [cs.PF] ,0202 electrical engineering, electronic engineering, information engineering ,Mobile robots ,[INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,[INFO.INFO-RB]Computer Science [cs]/Robotics [cs.RO] ,[INFO]Computer Science [cs] ,Unit distance ,Execution model ,Distributed algorithm ,[INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,Rendezvous ,[INFO.INFO-RB] Computer Science [cs]/Robotics [cs.RO] ,16. Peace & justice ,Power (physics) ,Gathering ,[INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF] ,[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG] ,010201 computation theory & mathematics ,Robot ,020201 artificial intelligence & image processing ,[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC] ,Bivalent configuration ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Rendezvous problem - Abstract
International audience; We consider the rendezvous problem of two autonomous robots with very weak capacities. This problem is notoriously impossible to solve in the semi-synchronous execution model when robots are deterministic, oblivious, and their ego-centered coordinate system is fully symmetric.We show that if the robots disagree on the unit distance of their coordinate system, it becomes possible to solve rendezvous and agree on a final common location, without additional assumptions. We also generalize our scheme to solve gathering (that is, rendezvous of n ≥ 2robots) in the same setting, possibly starting from a bivalent configuration.
- Published
- 2021
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.