Critical Patrolling Schedules for Two Robots on a Line

Potential supervisors: 
Description: 

In patrolling problems, some mobile entities called "robots" must repeatedly visit certain points with prescribed frequencies. Constructing patrolling schedules is amazingly difficult. It is like solving many intertwined shortest-path problems simultaneously. Already for two robots patrolling on a line we neither have a polynomial-time algorithm nor do we know NP-completeness. The only known results are approximations.

The project builds on paper [1]. Thee goal is to solve problem instances with equidistant points on the line and with integer waiting times. In particular, we wish to find, characterize the "critical" instances that are solvable but become infeasible when some waiting time is further reduced. Small examples done by hand suggest that the necessary schedules can have surprising and diverse structures.

To be precise, the goal of the project is to collect all critical instances and the solutions to them, up to some number of points (as large as possible).  This will most likely be achieved with the help of a computer program to be developed, probably based on some branch-and-bound heuristics combined with elements of dynamic programming. The solutions shall be nicely displayed as well.

The project shall be done by two students that, preferably, have taken the Advanced Algorithms course, enjoy graph problems and algorithms, and are decent programmers.

[1] P. Damaschke: Two robots patrolling on a line: Integer version and approximability. 31st International Workshop on Combinatorial Algorithms IWOCA 2020, LNCS 12126, 211-223 (available on the author's homepage)

Date range: 
September, 2020 to September, 2025