Simple strategies versus optimal schedules in multi-agent patrolling

Akitoshi Kawamura, Makoto Soejima

Suppose that a set of mobile agents, each with a predefined maximum speed, want to patrol a fence together so as to minimize the longest time interval during which a point on the f…