M.Sc Thesis | |

M.Sc Student | Brickner Erez |
---|---|

Subject | The Populating Problem A Study in Multi-Nano-Robotics |

Department | Department of Computer Science |

Supervisors | PROF. Alfred Bruckstein |

DR. Israel Wagner | |

Full Thesis text |

Nanorobots are tiny robots, only tens or hundreds of nanometer in size, capable of manipulating atoms and molecules. There is a general agreement that in order for nanorobots to have a significant effect in the macro-world, they should act in very large teams. Nevertheless, there is hardly any published work asking questions such as 'How can we control so many robots?', 'How should they split the mission among them?' and so on.

In this work, I show that the most adequate model for nanorobotics is the model of anonymous autonomous multi-agents, acting in an anonymous world.

Analyzing the
variety of nanorobotics applications may give rise to many multirobotics
problems. This work introduces one such problem - the populating problem - the
problem of spreading *n* anonymous robots over an *n*-nodes unknown
graph, so that each node eventually contains a robot. Possible
nano-application, which might give rise for such a problem, is anesthetization,
which may be achieved by placing a nanorobot in each of the destination organ's
cells, and then using it for blocking the molecular machinery of metabolism
inside the cell.

The populating
problem itself divides into two consequent problems. The completion problem is
the problem of spreading *n* robots over an *n*-nodes graph. The
termination problem is the problem of acquiring the knowledge of the fact that
completion has indeed occurred. The termination problem is shown to be
unsolvable under the given model.

The completion
problem is shown to be reducible to the multi-agent on-line search problem, so
that any robust multi-agent on-line search algorithm can be used to solve it.
Two such algorithms are proposed. The RWP (random walk populating) algorithm is
based on a multi-agent random walk search algorithm, and its expected
completion time is shown to be *Ω(n ^{3})*. The AWP (ant walk
populating) algorithm is based on the VAW search algorithm, and its completion
time is bounded by

Next, I propose
the DWP (directed walk populating) algorithm. This algorithm uses the special
characteristics of the populating problem, and utilizes the already settled
robots to enhance the populating process. The completion time of the DWP is
also bounded by *O(n·d)*, and it is shown to be robust, asynchronous and
efficient.

Finally, a wide variety of simulations was conducted and analyzed, enlightening and clarifying various features of the populating algorithms, while comparing between AWP and DWP.