Critical Patrolling Schedules for Two Robots on a Line

Typ
Examensarbete för masterexamen
Program
Publicerad
2021
Författare
Gustafsson, Anton
Radjavi, Iman
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
Patrolling with unbalanced frequencies (PUF) involves scheduling mobile robots that continuously visit a finite number of fixed stations, with known individual maximal waiting times, placed on a line. Recent work demonstrates that PUF is a remarkably challenging problem. To advance current research in the best-known solution, we searched for critical instances of the integer patrolling problem (IntPUF). A solvable instance is critical if it becomes impossible to schedule the visits when any station’s waiting time is decremented. Formulating IntPUF as a specific graph problem enabled several algorithms and heuristics to be developed, mainly for solving any instance of IntPUF and searching for critical instances. The algorithms were proved to be correct and implemented in a Java program to collect the critical instances. Benchmarking the implementation shows that solving instances work well when the number of stations is relatively small while searching for critical instances turned out to be extremely difficult. However, numerous critical instances were found, which reveal interesting patterns that may be further analyzed and utilized to improve the search for additional critical instances.
Beskrivning
Ämne/nyckelord
Patrolling with unbalanced frequencies , scheduling , robots , graph , algorithms , heuristics , Java
Citation
Arkitekt (konstruktör)
Geografisk plats
Byggnad (typ)
Byggår
Modelltyp
Skala
Teknik / material
Index