SDY06a

Using Eventually Consistent Compasses to Gather Oblivious Mobile Robots w. Limited Visibility :  Using Eventually Consistent Compasses to Gather Oblivious Mobile Robots w. Limited Visibility Samia Souissi (JAIST) Masafumi Yamashita (Kyushu Univ.) Xavier Défago (JAIST) Context:  Context Coordination of autonomous mobile robots Distributed computing point of view Gathering problem System No infrastructure No direct communication Unreliable sensors Motivation :  Motivation Minimal requirements to robust coordination Identify fundamental limits of coordination Deterministic solutions Weak/weaker/weakest assumptions Gathering possible [FPSW 05] Oblivious robots Limited visibility Share a compass Motivation :  Motivation In practice: Compasses error prone Compasses sensitive to magnetic interference Question: Gathering with unreliable compasses? Problem definition:  Gathering: Robots located arbitrarily  All robots should gather at same location. Advantage: Agreement on a common origin Problem definition Gathering Outline:  Outline System model Eventually Consistent Compasses: definition Gathering w. Eventually Cons. Compasses Correctness Conclusion/ Future works System model [SY99]:  System model [SY99] System model: [Suzuki & Yamashita, SIAM J. Computing, 1999] Environment: Two-dimensional plane No boundary No landmarks No obstacles System model [SY99]:  System model [SY99] Robots: … are points ... Disoriented (no common Coord. Sys.) … Anonymous ... No explicit communication Interactions: Vision: observe positions of others System model [SY99]:  System model [SY99] Cycle of robot: Look- Compute -Move - Idle Semi-synchronous model Activation: Activation schedule Scheduler: Fair & distributed System model:  System model Further assumptions Robots: Oblivious (stateless) Have limited visibility (range V) Unable to detect multiplicity Difficulty of gathering:  Difficulty of gathering Illustration: Two robots Deterministic gathering: impossible [SY99] r r’ Difficulty of gathering:  Difficulty of gathering Scenario 1: each robot moves to the other If always activated together Swap positions endlessly r r’ Difficulty of gathering:  Difficulty of gathering Scenario 2: move to midpoint r r’ Difficulty of gathering:  Difficulty of gathering Scenario 3: move to midpoint r activated infinitely often Convergence r r’ Gathering: Related work:  Gathering: Related work SY99 and CORDA models: Deterministic gathering impossible without additional assumption [Prencipe 05] Non oblivious [SY 99] Multiplicity detection [CFPS 03] Compasses [FPSW 05] Etc. Question:  Question Is gathering possible with unreliable compasses? Outline:  Outline System model Eventually Consistent Compasses: definition Gathering w. Eventually Cons. Compasses Correctness Conclusion/ Future works Compass: definition:  Compass: definition Compass: Function (robot ; time) Output: North direction Perfect Compass: Agreement: agree on the same North Invariance: North never changes Eventually consistent compass:  Eventually consistent compass Eventual agreement: there is a time (unknown) after which compasses become consistent Eventual invariance: after some time compasses stabilize Eventually cons. compass:  Eventually cons. compass time r 1 r 2 r 3 Chaotic period Good period Global Stabilization Time (unknown) Consistent & Stable GST Inconsistent/ Unstable GST: unknown to robots Outline:  Outline System model Eventually Consistent Compasses: definition Gathering w. Eventually Cons. Compasses Correctness Conclusion/ Future works Algorithm: principle:  Algorithm: principle Assumption: Visibility graph connected initially Safety: Visibility graph must remain connected Robots do not loose sight with visible neighbors Liveness: Gather in finite number of steps Algorithm :  Algorithm Case 1: No visible neighbor r Algorithm :  Algorithm Case 2: Neighbors on Left/Top Cr r r Algorithm :  Algorithm General case: No neighbors on Left/Top r Cr r Algorithm:  Algorithm General case: No neighbors on Left/Top Compute two outermost robots Cr r r1 r2 Algorithm:  Algorithm General case: No neighbors on Left/Top Cr r r1 r2 H Algorithm:  Algorithm No neighbors on Left/Top H inside triangle (r,r1,r2) Move to H Cr r1 r2 H r Algorithm:  Algorithm No neighbors on Left/Top H outside triangle (r,r1,r2) Cr r r1 r2 H Algorithm:  Algorithm No neighbors on Left/Top H outside triangle (r,r1,r2) Move to nearest among r1 and r2 Cr r r1 r2 H Algorithm:  Algorithm Collinear case: No neighbors on Left/Top Cr r r Algorithm:  r’ Algorithm Collinear case: No neighbors on Left/Top Move to nearest Cr r r Outline:  Outline System model Eventually Consistent Compasses: definition Gathering w. Eventually Cons. Compasses Correctness Conclusion/ Future works Algorithm: correctness:  Safety: Vision graph connected Liveness: Termination in finite time Algorithm: correctness Preserved connectivity (safety):  Preserved connectivity (safety) Given: To prove: S: set of robots visible to r at time t.  t’>t, r at distance at most V from robots in S. Preserved connectivity:  Preserved connectivity Scenario 1: Robot r does not move Scenario 2: Robot r collinear with robots in S. Scenario 3: Robot r computes outermost robots. Preserved connectivity:  Preserved connectivity Scenario 3: Robot r computes outermost robots. Schedule1: Only robot r active at time t Others inactive at time t Preserved connectivity:  Preserved connectivity Scenario 3/schedule 1: r computes outermost robots; others inactive Cr r Preserved connectivity:  Preserved connectivity Scenario 3/schedule 1: r computes outermost robots; others inactive Cr r A H B Preserved connectivity:  Preserved connectivity Scenario 3: Robot r computes outermost robots. Schedule2: Robot r active at time t All/some robots in S active at time t Robot r’ active at time t Preserved connectivity:  Scenario 3/schedule 2: Example1: r and r’ are active at time t Preserved connectivity Cr r’ r Preserved connectivity:  Preserved connectivity Scenario 3/schedule 2: Example2: r and r’ are active at time t r r’ Cr Conclusion:  Conclusion Gathering solvable: Semi-synchronous model [SY99] Oblivious Limited visibility Eventually consistent compasses Benefits: Tolerates transient failure of compasses. Self-stabilizing Solves gathering in asynchronous model for n3 Future works:  Future works Gathering in Asynchronous model (CORDA) Combine unstable + bounded errors compasses Impossible for some N ≥5 (conjecture) Questions/Comments:  Questions/Comments Algorithm: Discussion:  Chaotic period: Progress: may be Good period: Progress: OK Algorithm: Discussion r 1 r 2 r 3 Gathering Good period Chaotic period GST Algorithm: termination:  Algorithm: termination Termination: Gather at leftmost and bottommost robot Gathering  left  right System model:  System model Two variants: Semi-synchronous model: [SY99] :Suzuki & Yamashita, SIAM J. Comput., 1999. Atomicity of actions Robots: can’t see each other “while moving” Asynchronous model: CORDA [FPSW05], Theor. Comp. Sci. Asynchrony of actions Robots: see each other “while moving” System model [SY99]:  System model [SY99] Activation: illustration Observe each other at beginning of cycle time t0 t1 tn Observe Compute Move Robot 1 Robot 2 Robot 3 System model: CORDA [FPSW05]:  System model: CORDA [FPSW05] Asynchronous model: CORDA [FPSW05], Theor. Comp. Sci. 2005 Cycle: Full asynchrony within a cycle See each other “while moving” Can not anticipate other’s actions Robot 1 Robot 2 Robot 3 time Gathering: Related work:  Gathering: Related work In semi-synchronous model (SY99): Solvable (N3) [SY99] Oblivious robots Unlimited visibility Convergence [Ando et al. 99] Oblivious robots Limited visibility References:  References [SY99]: I. Suzuki and M. Yamashita. Distributed anonymous mobile robots: Formation of geometric patterns. SIAM J. Computing, vol28. number4. Pages.1347-1363, 1999. [Ando et al.99]: H. Ando, Y. Oasa, I. Suzuki and M. Yamashita, Distributed Memoryless Point Convergence Algorithm for Mobile Robots with Limited Visibility, In IEEE Trans. on Robotics and Automation, 15(5): 818-828, 1999. [FPSW05]: P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer. Gathering of Asynchronous Robots With Limited Visibility. Journal of Theoretical Computer Science, 337 (1-3) 147-168, 2005 . [Pre05] G. Prencipe. On the Feasibility of Gathering by Autonomous Mobile Robots. In Proc. of Colloquium on Structural Information and Communication Complexity SIROCCO'05, pages 246-261, 2005. Gathering: Related work:  Gathering: Related work In asynchronous model (CORDA): Solvable [CFPS 03] (N3) Oblivious robots Unlimited visibility Multiplicity detection Solvable [FPSW 05] Oblivious robots Limited visibility Robots: share a compass (common orientation) Problem definition:  Gathering: Robots located arbitrarily  All robots should gather at same location. Advantage: Agreement on a common origin Problem definition Gathering Initial configuration