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/

 

Course Achievement (Studienleistung)

The Course Achievement (Studienleistung) will be given based on

  • The performance on the talk in the introductory phase
  • The active participation in the Kick-off meeting
  • Successful participation during the rest of the project group. We are going to evaluate this in per person interviews at the end of the summer semester 2020.

 

Dates

07.04. Distribution of introductory talk topics
21.04. 4pm - 5pm First Lecture: Algorithmic Foundations of Swarm Robotics – The Discrete Case
22.04. 4pm - 5pm Second Lecture: Algorithmic Foundations of Swarm Robotics – The Continuous Case
28.04. 4pm - 5pm Third Lecture : Towards Dispersing Robots properly: The Max-Chain-Formation Problem
29.04. 4pm - 5pm Fourth Lecture : PadRend
07.05. 9am - 1pm Presentation of introductory talks
11.05. starting 3pm Kick-off Workshop (may be continued on the 12.05.)

 

Introductory Talks

In order to exercise reading and presenting research papers, each participant is assigned a paper from the list of topics below. We expect you to understand and present the main focus of the paper, the models considered, the main results (algorithms, theorems about the algorithms), and ideas of the proofs. Each presentation is based on slides (.pptx, pdf), which have to be uploaded to the PANDA site of the project group by May 6th at 2pm. The presentation should last 20min and will be given via Jitsi. Please contact your topic advisor if you have questions.

 

Topics

  1. Fault-Tolerant Mobile Robots (Advisor: Friedhelm Meyer auf der Heide)
  2. Pattern Formation (Advisor: Friedhelm Meyer auf der Heide)
  3. Uniform Circle Formation  (Advisor: Till Knollmann)
  4. Computation Under Restricted Visibility, (Advisor: Till Knollmann)
  5. Group Search and Evacuation (Advisor: Jannik Castenow)
  6. Patrolling (Advisor: Jannik Castenow)
  7. Local Algorithms for Autonomous Robot Systems  (Advisor: Jannik Castenow)