Locomotion

This project group focuses on modelling, solving and analyzing formation problems for swarms of mobile robots. Envision a scenario where n mobile robots having a limited viewing range are placed in a 2- or 3-dimensional Euclidean space and are supposed to establish a certain formation. To reach this formation, each robot has to plan and perform its movement based solely on the positions of other robots within its viewing range, which we normalize to one. In particular, no global view, communication, or long-term memory is provided.

 


Within this broad scenario, we want to design strategies for less studied swarm formation problems, for instance dispersion problems. The goal of dispersion is that a swarm of robots somewhat regularly fills a given space. Consider for example a swarm of robots located inside of a square. A nice distribution of the robots inside of a square might be a hexagonal or square grid. The goal of the project group is to find suitable notations for dispersion inside of a shape and to design local strategies that solve the dispersion problem. The analysis of the strategies are supposed to be both theoretically and practically, via the implementation of a simulator based on PADrend.

Further Reading

There already exists a large body of literature on different problems within the scope of swarm formation problems. The following list of papers offers a general overview on the topic and on the techniques we want to apply within this project group.

 

 

Requirements

This project group targets at students that are interested and experienced in the theory of computing.

To participate successfully in the project group, a solid understanding of the basic concepts of theoretical computer science as well as basics from analysis, algebra and stochastics is necessary. We recommend to consult the reading list above to get a first idea of the concepts which are central to the project group.

If you are interested in participating in the project group, please submit the assignment given through the Jupyter system: pg.cs.upb.de

For additional information on the registration for a project group, visit https://cs.uni-paderborn.de/en/studies/study-elements/project-groups/

 

Dates

  1. First Meeting (and distribution of seminar topics): t.b.a.
  2. First Lecture: t.b.a.
  3. Second Lecture: t.b.a.
  4. Third Lecture: t.b.a.
  5. Fourth Lecture: t.b.a.
  6. Seminar: t.b.a.
  7. Kickoff Workshop t.b.a.

 

Seminar Topics

  1. Moving and Computing Models: Robots (Topic for 1 person)
  2. Pattern Formation (Topic for 2 persons)
  3. Uniform Circle Formation  (Topic for 2 persons)
  4. Computation Under Restricted Visibility, (Topic for 2 persons)
  5. Group Search and Evacuation (Topic for 2 persons)
  6. Patrolling (Topic for 2 persons)
  7. Local Algorithms for Autonomous Robot Systems  (Topic for 2 persons)