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