Why do we need to model patrolling schedules?
Patrolling problems present themselves in many situations, often within our daily lives. When visiting a shopping centre you might see a security guard, or you could see a police patrol car on the motorway. In each case, somebody has to make a decision as to how the patroller moves around their designated area. How this decision is made often depends on the context.
For example, a routine building inspection team could be assigned the schedule that maximises area coverage in the smallest amount of time possible, whereas a military patrol may wish to focus on areas that are most likely to be attacked. Even for the same applications, the scheduling method is often dependent on the organisation, with historical schedules and worker preferences usually playing a role.
How do we model them?
Methods have been developed to automate this scheduling process for arbitrary areas. By breaking down a patrol area into its most crucial points and the connections between these points, a mathematical model can be constructed using graph theory.
Each patrol point is referred to as a node, and the connections between them as edges. Designing the patrol schedule then becomes a question of how to move the patroller from node to node, along the edges. To give the patroller something to do at each node, the idea of potential attacks is introduced. These could be anything from an art thief trying to break into a museum or a cyber attacker attempting to breach a system.
Sometimes these attackers are assumed to have inside knowledge of the system they are trying to attack, and thus knowledge of how the patroller is likely to move. Other times, they are assumed to have no knowledge and so just attack randomly. The patrol designer’s objective is to move the patroller between the nodes in a way that maximises their attack detection (and thus prevention) potential. Mathematical assumptions about the problem can be made to quantify the patroller’s potential to detect attacks, for example by looking at how many attacks are expected to be taking place at a given node.
Uses and limitations
This is arguably the simplest approach, with some approaches taking other factors into account such as how soon we can expect the ongoing attacks at a node to be completed. There is also the question as to how effective the patroller is at detecting attacks. A simple idea would be to assume they have a 100% successful detection rate, however, this may not be realistic; perhaps a shoplifter knows how to act natural in a crowd of patrons. Some authors account for this possibility by instead saying that we can only expect to detect a certain percentage of attacks.
Once all of these ideas have been combined into a mathematical model, we then need to be able to solve these models. It is often the case in practice that, for a large enough patrol area, finding the exact solutions takes an unrealistic amount of time and computing power. To overcome this, heuristic approaches have been developed that result in solutions that are a good approximation of the true optimal patrol schedule. These heuristics are much less costly to compute and so are much more suitable for use in real-world decision making, when time and cost are often important factors.
If you are interested in reading more about this area, there are many papers available to read online. Two I would recommend in particular are;
• A Graph Patrol Problem with Random Attack Times
• Optimal Patrol to Uncover Threats when Detection is Imperfect.