M.Sc Thesis

M.Sc StudentBrickner Erez
SubjectThe Populating Problem
A Study in Multi-Nano-Robotics
DepartmentDepartment of Computer Science
Supervisors PROF. Alfred Bruckstein
DR. Israel Wagner
Full Thesis textFull thesis text - English Version


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 Ω(n3). The AWP (ant walk populating) algorithm is based on the VAW search algorithm, and its completion time is bounded by O(n·d).

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.