Funding: DFG project (2018–2022)

Partners involved:
Prof. Dr Christian Scheideler, Paderborn University, Germany
Prof. Shlomi Dolev, Ben Gurion University of the Negev, Israel

The aim of this project is to develop new models and algorithms for swarms of autonomous nanorobots, i.e. groups of tiny active units with very limited individual capabilities that operate as a swarm in physiological environments.

The development of new models will take into account questions that have not been considered in the past, or only incompletely: How can the nanorobots generate, store and utilise energy (energy manager)? Which realistic models (based on physical, biological or chemical processes in nature) can enable non-local communication between a group of nanorobots? Which models allow the failure and repair of faulty nano-robots by intact nano-robots (fault tolerance)?

Algorithmically, the leader selection problem is a key problem, the solution of which makes the solution of other important problems by a swarm of nano-robots possible in the first place. The models developed in the project will be analysed in terms of their ability to solve the leader election problem efficiently. Based on this, solutions for other important tasks will be developed: A swarm of nano-robots should search an environment completely and, if necessary, mark important positions in the environment (exploration). A swarm of nano-robots should envelop an object in its direct environment as quickly as possible (envelopment). A swarm of nano-robots should form a path from a starting point to a destination point in its environment (transport).

For all developed models, the limits of the respective models are shown by lower bounds (and possibly impossibility results).

The algorithmic results are then extended to investigate aspects such as robustness against failures of nano-robots and swarms with different nano-robots as well as the solution of the above problems in three-dimensional environments.