Critical Patrolling Schedules for Two Robots on a Line

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.