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