Brickner2

50 %
50 %
Information about Brickner2
Science-Technology

Published on May 2, 2008

Author: Malden

Source: authorstream.com

The Populating Problem:  The Populating Problem Erez Brickner 21/12/04 It all began in a very small scale…:  It all began in a very small scale… Nanorobotics Controlled manipulation of atoms and molecules Many applications – inside the human body Multi-nanorobotics Can nanorobots have an effect in the macro-scale? Only in large teams! Yet, there is hardly any published work in this regard… Small Scale – Great Limitations:  Small Scale – Great Limitations Size Limited memory and computational capabilities Simple algorithms Environment Mostly inside the human body Wireless communication might prove lethal Short distance communication Multiplicity Thousands or millions of nanorobots A tiny bandwidth for each robot Too many computations for a central controller Reliability… Populating Problems:  Populating Problems Place a robot in every “sector” of an unknown environment Place a nanorobot in every tissue cell of the human body (and then – shut it down…) Place a virus in every computer of the enemy’s network (and than – shut it down) Place a robot in every room of an unknown building (and then – listen to the enemy) What’s the problem? Where should I go? Are we done yet? The Model:  The Model Environment  Connected graph - G(V,E) Sectors to populate  the nodes - V Initially - the robots are randomly scattered The robots are identical and autonomous A robot may move only along the edges A robot may sense only its neighborhood Random Walk Populating (RWP):  Random Walk Populating (RWP) For each robot: If current node is not populated Settle Else Move randomly to one of its neighbors RWP – a Short Analysis:  RWP – a Short Analysis Completion time – unbounded Mean completion time – may be not less than O(|V|3) Termination (knowledge of completion) – never achieved Impossibility of Termination:  Impossibility of Termination There is no populating algorithm that promises termination! Still, if the completion time is bounded… An outside viewer may decide on termination after crossing the time bound RWP is not good enough! Directed Walk Populating (DWP):  Directed Walk Populating (DWP) Accelerated version of RWP Robots (try to) direct each other towards empty nodes Two layers of algorithm: The already settled robots learn where the empty nodes are The unsettled robots are directed by the settled robots towards the empty nodes Directed Walk Populating (DWP):  Directed Walk Populating (DWP) For each unsettled robot: If current node is not populated Settle Else Move randomly to one of its lowest neighbors For each settled robot: Set its height to that of its lowest neighbor, plus 1 Why Does It Work?:  Why Does It Work? The height function is like a blanket over the graph Each robot tries to push this blanket higher, but is restrained by its neighbors The edges of the blanket are grounded by the empty nodes The blanket tends to stretch up, sloping towards the empty nodes The unsettled robots slide down these slopes Once a robot settles – it “unstretches” the blanket DWP – Time Complexity:  DWP – Time Complexity The lower layer of the algorithm is performed as long as “the blanket is not stretched” The total time in which the blanket is not stretched is O(|V|2) The total time spent on the second layer – while the blanket is stretched is – O(|V|2) Hence, completion time is O(|V|2) in the worse case DWP – Memory Complexity:  DWP – Memory Complexity The state of each robot is determined by its height The height may rise up to |V|-1, hence the described DWP requires O(log(|V|)) memory bits to store the state of each robot At any time, the height of a robot differs from that of its neighbor by at most 1 Therefore, it is enough to use height(mod3) as a state, hence 2 bits of memory are sufficient

Add a comment

Related presentations

Related pages

Bernd Bruckner - Vertriebsleiter National Consumer ...

Vertriebsleiter National Consumer ... XING ist Deutschlands größtes berufliches Netzwerk: Mit XING finden Sie Ihren Traumjob, knüpfen wertvolle Kontakte ...
Read more

Jürgen Bruckner - Head of Sales & Marketing - Franz Barta ...

Head of Sales & Marketing ... XING ist Deutschlands größtes berufliches Netzwerk: Mit XING finden Sie Ihren Traumjob, knüpfen wertvolle Kontakte ...
Read more

Bruckner – CDs, Noten, Bücher und mehr – jpc.de

... Moni Bruckner (2) Wolfgang Zeitler (2) Reinhard Bruckner (2) Susanne Bruckner (2) Oskar Loerke (2) Martin Bruckner (2) Constantin Floros (2) Otto Bruckner
Read more

Suchergebnis auf Amazon.de für: bruckner 2: Musik-CDs & Vinyl

"bruckner 2" Abbrechen. Sinfonie 2 2006. von Davies,Dennis Russell und Bruckner Orchester Linz. Audio CD. EUR 6,99 Prime. Nur noch 8 Stück auf ...
Read more

Michael Brickner | Facebook

Michael Brickner is on Facebook. Join Facebook to connect with Michael Brickner and others you may know. Facebook gives people the power to share and...
Read more

Bruckner. 2 Bände.: Amazon.de: Bücher

- Bruckner. 2 Bände. jetzt kaufen. Kundrezensionen und 0.0 Sterne. …
Read more

Jens Bruckner | LinkedIn

Jens Bruckners berufliches Profil anzeigen LinkedIn ist das weltweit größte professionelle Netzwerk, das Fach- und Führungskräften wie Jens Bruckner ...
Read more

Anton Bruckner

jpc Online-Shop - wählen Sie aus mehr als 4 Millionen CDs, DVDs, Blu-rays und Büchern. Portofrei ab 20 Euro und bei Bestellungen mit Buch.
Read more

Symphonieorchester des BR - BLOMSTEDT/Nielsen, Bruckner/2 ...

Tickets für Symphonieorchester des BR - BLOMSTEDT/Nielsen, Bruckner/2. Abo S in Gasteig, Philharmonie, München am Samstag, 09.02.2013 um 19:00 Uhr bei ...
Read more

Symphonieorchester des BR 2013/14 - NOTT/Berg, Bruckner/2 ...

Tickets für Symphonieorchester des BR 2013/14 - NOTT/Berg, Bruckner/2. Abo S in Gasteig, Philharmonie, München am Samstag, 22.02.2014 um 19:00 Uhr bei ...
Read more