Skip to content

Commit a4b2e7d

Browse files
author
Matthew Daws
committed
Patrol plans added
1 parent 83a5019 commit a4b2e7d

3 files changed

Lines changed: 169 additions & 0 deletions

File tree

‎examples/Patrol Plans/Literature review.ipynb‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
{
2+
"cells": [
3+
{
4+
"cell_type": "markdown",
5+
"metadata": {},
6+
"source": [
7+
"# Literature review\n",
8+
"\n",
9+
"## Daily patrol planning\n",
10+
"\n",
11+
"1. Chen, H.; Cheng, T.; Wise, S. \"Designing Daily Patrol Routes for Policing Based on ANT Colony Algorithm\" ISPRS Ann. Photogramm. Remote Sens. Spatial Inf. Sci., II-4/W2, 103-109, https://doi.org/10.5194/isprsannals-II-4-W2-103-2015, 2015. \n",
12+
"\n",
13+
"See this (open access) paper for further literature.\n",
14+
"\n",
15+
"Here the task is that we are _already given_ hotspots, and we wish to (dynamically) route patrols to these hotspots, in an efficient way. This is a different task to that which we're interested in."
16+
]
17+
},
18+
{
19+
"cell_type": "markdown",
20+
"metadata": {},
21+
"source": [
22+
"## Forming hotspots\n",
23+
"\n",
24+
"1. Chawathe, S. S. \"Organizing Hot-Spot Police Patrol Routes\" DOI: 10.1109/ISI.2007.379538 \n",
25+
"\n",
26+
"This does address our problem, but makes a (large) number of simplifications before presenting a solution, making it not directly applicable."
27+
]
28+
},
29+
{
30+
"cell_type": "code",
31+
"execution_count": null,
32+
"metadata": {
33+
"collapsed": true
34+
},
35+
"outputs": [],
36+
"source": []
37+
}
38+
],
39+
"metadata": {
40+
"kernelspec": {
41+
"display_name": "Python 3",
42+
"language": "python",
43+
"name": "python3"
44+
},
45+
"language_info": {
46+
"codemirror_mode": {
47+
"name": "ipython",
48+
"version": 3
49+
},
50+
"file_extension": ".py",
51+
"mimetype": "text/x-python",
52+
"name": "python",
53+
"nbconvert_exporter": "python",
54+
"pygments_lexer": "ipython3",
55+
"version": "3.6.0"
56+
}
57+
},
58+
"nbformat": 4,
59+
"nbformat_minor": 2
60+
}

‎examples/Patrol Plans/Problem statement.ipynb‎

Lines changed: 99 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,99 @@
1+
{
2+
"cells": [
3+
{
4+
"cell_type": "markdown",
5+
"metadata": {},
6+
"source": [
7+
"# Statement of the problem\n",
8+
"\n",
9+
"## On a grid\n",
10+
"\n",
11+
"We are given a grid of risks.\n",
12+
"\n",
13+
"- We wish to find $N$ hotspots (typically $N$ is fixed, say $N=5$, or at least bounded above, say $N<=8$).\n",
14+
"- Each hotspot is of a maxmimum size (number of grid cells). Or the total coverage is limited.\n",
15+
"- At the very least, a \"hotspot\" must be a contiguous selections of cells.\n",
16+
"- We might wish to further constrain what we mean by a \"hotspot\".\n",
17+
"\n",
18+
"This thus becomes an optimisation problem, not really connected to criminology. I wonder if it has been studied in computer science?\n",
19+
"\n",
20+
"## On a network\n",
21+
"\n",
22+
"We are given an assignment of risk to each edge of the network.\n",
23+
"\n",
24+
"- We wish to find $N$ hotspots (typically $N$ is fixed, say $N=5$, or at least bounded above, say $N<=8$).\n",
25+
"- Each hotspot is of a maxmimum size (shortest _walk_ which covers all edges in the hotspot). Or the total coverage is limited.\n",
26+
"- At the very least, a \"hotspot\" must be a contiguous selections of edges.\n",
27+
"- We might wish to further constrain what we mean by a \"hotspot\".\n",
28+
"\n",
29+
"## Maximisation\n",
30+
"\n",
31+
"In either case, our goal is to find the selection of cells (or edges) which satisfies the above constraints, and subject to this constraint, maximises the sum of risks. This is probably computationally intractible, and so algorithms which get close to the maximum will be sought."
32+
]
33+
},
34+
{
35+
"cell_type": "markdown",
36+
"metadata": {},
37+
"source": [
38+
"# Goals\n",
39+
"\n",
40+
"- Can we find simple sets of additional constraints which give rise to \"nice\" hotspots?\n",
41+
"- E.g. we might bias in favour of \"compact\" hotspots (meaning the ratio of the perimeter to area is low).\n",
42+
"- Can we find efficient algorithms?\n",
43+
"- What sort of \"hit rate\" do the different methods / different risk algorithms give?"
44+
]
45+
},
46+
{
47+
"cell_type": "markdown",
48+
"metadata": {},
49+
"source": [
50+
"# Simple example: \"greedy grid\"\n",
51+
"\n",
52+
"Grid based, will produce $\\leq N$ hotspots of a certain total size $M$. Only constraint is that each \"hotspot\" is a connected collection of cells. Iterative:\n",
53+
"\n",
54+
"- If the current number of hotspots is $<N$, select the cell with the highest risk.\n",
55+
"- Otherwise, select the cell with the highest risk which is adjacent to a current hotspot.\n",
56+
"- Stop if we have selected $M$ cells, otherwise continue.\n",
57+
"\n",
58+
"Advantages:\n",
59+
"\n",
60+
"- $\\mathcal O(nM)$ where $n$ is the number of grid cells, in the naivest implementation.\n",
61+
"\n",
62+
"Problems:\n",
63+
"\n",
64+
"- No guarantee of producing \"compact\" hotspots.\n",
65+
"- No guarantee of solving the maximisation problem: this can happen if there are say $N$ isolated cells with high risk, surrounds by very low risk cells, and disjoint to these a large number of medium risk cells, with $M$ much larger than $N$ (so an optimal solution is to choose many medium risk cells; the algorithm chooses the high risk cells and then add very low risk cells)."
66+
]
67+
},
68+
{
69+
"cell_type": "code",
70+
"execution_count": null,
71+
"metadata": {
72+
"collapsed": true
73+
},
74+
"outputs": [],
75+
"source": []
76+
}
77+
],
78+
"metadata": {
79+
"kernelspec": {
80+
"display_name": "Python 3",
81+
"language": "python",
82+
"name": "python3"
83+
},
84+
"language_info": {
85+
"codemirror_mode": {
86+
"name": "ipython",
87+
"version": 3
88+
},
89+
"file_extension": ".py",
90+
"mimetype": "text/x-python",
91+
"name": "python",
92+
"nbconvert_exporter": "python",
93+
"pygments_lexer": "ipython3",
94+
"version": "3.6.0"
95+
}
96+
},
97+
"nbformat": 4,
98+
"nbformat_minor": 2
99+
}

‎examples/Patrol Plans/readme.md‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
# Patrol plans
2+
3+
A traditional approach to forming "hotspots" is via "coverage levels":
4+
5+
1. Produce, using a prediction algorithm, an estimate of "risk" in each grid cell.
6+
2. Decide upon a "coverage level", say 10%, and take simply the top 10% of grid cells by risk.
7+
8+
This may form a pattern of spatial locations which look like "hot spots", or it may not. (For network based prediction techniques, the same applies, with "grid cell" replaced by "edge of network").
9+
10+
Alternatively, we might replace the 2nd step by an algorithm which seeks always to form "hotspots" (according to some criteria) using the risk of each grid cell (or network edge) merely as a guide. We believe this is more likely to lead to usable hotspots, from a police operational viewpoint.

0 commit comments

Comments
 (0)