Selected Topics in Algorithmics of Mobile Robots
Lecturer:
Jerzy Czyżowicz
(Université du Québec en Outaouais).
About the lecturer | Course Summary | Slides | Assignment
About the lecturer:
Jerzy Czyżowicz is a Professor at the Department of Informatics and Engineering of UniversitŽ du QuŽbec en Outaouais (Canada). He works on algorithmics, escpecially related to mobile robots.
Course summary: Many questions may be solved by collections of collaborating processors distributed in the network environment. Several of these problems require processors to move along the network and the distance travelled by such mobile entities is a principal measure of the efficiency of the solutions. For several decades the tasks for mobile agents and robots has been fundamental in numerous domains of mathematics and computer science. These include robotics, operations research, network searching and exploration, web crawling, vehicle routing, cops-and-robber games and many others. Most often mobile entities represent either physical objects (e.g. robots, humans, animals) or software robots (agents, bots).
The course presents selected algorithms involving mobile robots. Some of them concern the central problems in algorithms and distributed computing like searching/exploration and rendez-vous. More thoroughly we look at some more specific questions:
- The problem of boundary patrolling involves a perpetual searching of the environment in order to minimize its idleness Ð the time when points of the environment remain unvisited.
- Two-speed robots attempt to optimize the time of the environment exploration when each robot searching speed is smaller than its inadvertent walking speed.
- Bouncing robots simulate uncontrolled movement of particles subject to laws of physics. Message transfer between bouncing robots and localization (learning existence and the positions of all other robots of the collection) are analyzed.
- Evacuation concerns exiting the environment by an a priori unknown exit point. The exit time of the last robot of the collection is sought to be minimized.
Slides: Lecture slides can be found at the departmental Moodle. If you cannot access that site, please contact Bartek Klin for the slides.
Assignment: You can find the problem set here, or at the departmental Moodle. Please send the solutions to prof. Czyżowicz by Thursday, January 15.