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 n3 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 (N3) [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] (N3) 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
.'SDy06a*DJ on6as afinpuò sona 91 :pnuo D*ono aJqnpo ap Dlpay unaqed • q 00'6L e OE'LL ap :OUDJOH -lod :SDZD1d ap ON 09 soutunp
Read more
上海端懿电气科技有限公司专业生产(供应)销售泄漏电流测量仪校准仪产品,公司具有良好的市场信誉,专业的销售和 ...
Read more
摘要:sdy06a数字式泄漏电流测量仪校准仪,是依据相关国家规程设计制造的,具有五位数字显示,...
Read more
Add a comment