Critical Patrolling Schedules for Two Robots on a Line

Examensarbete för masterexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/304106
Download file(s):
File Description SizeFormat 
CSE 21-102 Radjavi Gustafsson.pdf1.49 MBAdobe PDFView/Open
Bibliographical item details
FieldValue
Type: Examensarbete för masterexamen
Title: Critical Patrolling Schedules for Two Robots on a Line
Authors: Gustafsson, Anton
Radjavi, Iman
Abstract: 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.
Keywords: Patrolling with unbalanced frequencies;scheduling;robots;graph;algorithms;heuristics;Java
Issue Date: 2021
Publisher: Chalmers tekniska högskola / Institutionen för data och informationsteknik
URI: https://hdl.handle.net/20.500.12380/304106
Collection:Examensarbeten för masterexamen // Master Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.