REVIEW 5 major objections 9 minor 28 references
Cooperative Patrol Routing: Optimizing Urban Crime Surveillance through Multi-Agent Reinforcement Learning
T0 review · 5 major / 9 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read Trained on real crime data from three Malaga districts, a cooperative multi-agent reinforcement learning model plans single-shift patrol routes that cover over 90% of the highest-crime cells.
desk verdict Real applied-MARL work with a useful greedy baseline, but the coverage index is ill-defined and the abstract's 90%/65% numbers are contradicted by Table 7. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is VDPPO (Value Decomposition Proximal Policy Optimization), a multi-agent PPO variant that decomposes the joint value function to handle credit assignment among homogeneous agents. Observations are filtered through an agent line of sight, and the reward function $R'_t(a_i)$ combines a node-value term with an exploration term $\tau_t$ and a coverage penalty, summed with the joint reward to discourage free-riding. The paper's evaluation metric is the coverage index $|W_\psi|$, which counts how many of the $\psi$% highest-crime nodes in the area are visited by any patrol; $\psi$ is typically 3% to 20%.
What would settle it
Recompute the coverage index for any reported configuration using the full set of nodes in the zone as the denominator; if the fraction of top-3% nodes visited does not reproduce the table values (for example, 0.999 for zone 3 with five patrols, line of sight 3, best starting positions), then the formal definition of G as the route-visited subset is the one being used and the headline percentages describe something weaker than district-wide coverage.
Extended reading notes
Core claim
The central discovery is that route design for urban police patrols can be posed as a decentralized partially observable Markov decision process and solved with a cooperative multi-agent reinforcement learning algorithm, Value Decomposition PPO, without preselecting which nodes to visit. Agents share a policy, observe patrol positions, recent visit counts, and target values within a limited line of sight, and are rewarded through a combination of individual and joint coverage terms designed to prevent lazy agents and encourage exploration. Evaluated on 50-meter grid graphs built from real street maps and 304,125 geolocated crimes in Malaga, the trained policies generate routes that concentrate on high-crime cells. The authors report that the best configurations cover essentially all of the top 3% highest-crime nodes in the denser districts and still cover roughly 65% of the top 20% in the larger, sparser district.
Load-bearing premise
The headline coverage numbers assume that the metric's denominator is the full set of monitorable cells in the district, whereas the paper's formal definition says the denominator is only the cells the patrols actually visited, which would make the index trivially 1.
Editorial extensions
If this is right
- Cities can estimate the right number of patrols: in the two denser districts, five patrols achieve coverage nearly equal to ten, so the extra five mostly add cost without adding surveillance.
- Agents do not need full information: a line of sight of 3 performs about as well as 6, which supports deployment with limited reconnaissance.
- Randomizing starting positions buys little: it raises route entropy by less than 10% and generally lowers coverage compared with starting patrols at the highest-crime nodes.
- The learned routes beat the greedy nearest-high-value-cell baseline in almost every configuration, and clearly so in the two smaller districts.
- Sparse, large districts are harder: zone 10 needed stronger exploration rewards and still achieved lower coverage, indicating that per-area parameter tuning is required when the model is transferred.
Reading between the lines
- An implication left implicit is that the model could serve as a pre-shift planning tool rather than real-time dispatch, since the paper assumes patrols will not deviate from their route for incidents.
- The same coordinated-route machinery should transfer to other spatially heterogeneous surveillance tasks, such as drone inspection or environmental monitoring, but the reward parameters would need to be re-tuned for each new target function, as the paper itself notes.
- A concrete extension would be to couple the trained policy with a fast local replanner that handles emergency deviations, which the authors list as future work and which the current model explicitly does not support.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper addresses the problem of planning coordinated patrol routes in urban environments using multi-agent reinforcement learning. The authors model the problem as a decentralized partially observable Markov decision process (dec-POMDP) on an undirected graph and train a shared policy with the VDPPO algorithm. The approach is evaluated on three districts of Málaga using historical crime data, and a new 'coverage index' inspired by the predictive accuracy index (PAI) is introduced to measure how well the generated routes visit the highest-crime nodes. The authors also compare against a greedy baseline and analyze the effects of the number of patrols, line of sight, and initial deployment strategy. The abstract claims that the coordinated routes achieve more than 90% coverage of the top 3% highest-crime nodes and 65% coverage of the top 20%, for the tested scenarios.
Significance. If the results are validated, the paper would be a relevant contribution to MARL-based patrol planning, offering a real-world testbed, a reproducible codebase (public repository), and a practical resource-allocation question about the required number of patrols. The motivation for a coverage metric suited to finite-horizon, non-cyclical routes is reasonable. However, the current significance is limited by the fact that the coverage index is not consistently defined in the text, the headline claim is contradicted by the results for zone 10, the reported point estimates lack uncertainty quantification, and the evaluation metric and training reward share the same target function, making the results largely a measure of optimization success rather than an independent assessment. With substantial revision, the approach could be of interest to both the applied reinforcement learning and crime-prevention communities.
major comments (5)
- [Section 5, Eqs. (7)-(9)] The definition of the coverage index is ambiguous and inconsistent with the reported tables. The text defines G as 'the subset of nodes ... covered in the routes of the agents'; if this is interpreted literally, every node of Z (a subset of G) is visited by construction, so Wψ = Z and the index is trivially 1 after any reasonable normalization. The tables report fractional values between 0.141 and 1.000, which cannot be cardinalities of a subset of nodes. The only reading consistent with the numbers is that G is the full set of candidate nodes in each zone and the reported value is |Wψ| / (ψ|G|/100) (or an equivalent proportion of the top-ψ nodes that are visited), but this denominator and normalization are not stated anywhere. Because every headline claim is expressed through this index, the paper must define it unambiguously and consistently with the tables.
- [Abstract vs. Table 7] The abstract's claim of 'more than 90% of the 3% of graph nodes with the highest crime incidence' is not supported by the results for zone 10, where the largest |W3| value is 0.712 (Table 7, line of sight 6, random initial positions, 5 patrols). Even under the charitable reading of the coverage index, this claim holds only for zones 3 and 9, and only for certain configurations. The abstract should be revised to state the claim as zone-specific (e.g., 'for zones 3 and 9') or to describe the range of results, such as 'up to more than 90%'.
- [Tables 5-7] The tables report a single point estimate per configuration with no standard deviation, confidence interval, or statistical test, despite the text mentioning '100 runs' in Section 5. Without measures of variability, the reader cannot assess whether the observed differences across line-of-sight values, numbers of patrols, and initial positions are meaningful, nor whether the model's improvements over the greedy baseline are significant. The paper should provide error bars or the full distribution of outcomes, and where relevant, apply significance tests or report effect sizes.
- [Section 3.5 and Section 5] The evaluation metric and the training reward both rely on the same target function σ (crime incidence): the reward function (Eq. 5) directly rewards visiting nodes with high σ, and the coverage index (Eqs. 7-9) measures the fraction of high-σ nodes visited. In addition, the 'best' initial placement selects nodes with the highest σ. Consequently, the reported coverage largely reflects the agents' ability to optimize the training objective rather than an independent measure of surveillance effectiveness. The greedy baseline is a useful external reference, but it is also defined in terms of σ. To support the broader claim of 'optimizing urban crime surveillance,' the paper should provide out-of-sample or temporal validation (e.g., training on earlier years and evaluating on later crime data) or explicitly limit the claim to coverage of known historical hotspots.
- [Section 4.1] The paper reports that only 304,125 of 376,737 crimes (about 19%) were successfully geolocated and used for the target function σ, but it does not discuss whether the omitted crimes are spatially biased. If the geocoding failures are not spatially random, σ will be a distorted representation of crime density, and all coverage results will inherit that distortion. The paper should analyze geocoding completeness by zone, discuss the potential for spatial bias, or apply an appropriate correction, and in any case should state this as a limitation explicitly.
minor comments (9)
- [Section 7] The Conclusions section contains several typographical errors and garbled passages, such as 'we counted with rreliedaonthe crimes comed in the city' and 'WFurthermore,e have also introduced'; this section needs a careful copyedit.
- [Section 6] The subsection heading 'umber of patrols' in the Discussion is missing the initial 'N'; it should read 'Number of patrols'.
- [Eq. (1)] Equation (1) contains an apparent typo in the recursive case: the condition 'vk∈V,vk,vi' should likely be 'vk ≠ vi' to correctly express the shortest-path recurrence.
- [Section 5] The notation |Wψ| implies a cardinality, but the reported values are normalized fractions. Once the coverage index is formally redefined, the authors should use a distinct notation (e.g., Cψ or a fractional coverage) to avoid confusion.
- [Tables 5-7] The paper does not specify whether the reported coverage values are means, medians, or maxima over the 100 runs; please clarify this for both the coverage and entropy columns.
- [Section 3.5 and 5] The concept of 'line of sight' is not formally defined; the paper should specify the exact geometry (e.g., a square of side 2k+1 cells centered on the agent) and whether the range is measured in grid cells.
- [Table 1] The column 'Preselected or homogeneous nodes' is ambiguous; consider splitting it into 'Preselected nodes' and 'Homogeneous node weights' for clarity.
- [Figure 9] The caption says 'Three of the five routes' but does not identify the configuration (zone, number of patrols, line of sight); please specify these details.
- [Section 5] The paper states that for zone 10 'the results with 10 patrols surpass those with 2 and 5 patrols' after changing the reward parameters, which makes cross-zone comparisons of the 'optimal number of patrols' conclusion difficult; this sensitivity should be acknowledged in the Discussion.
Circularity Check
Coverage-index definition makes the headline 90%/65% claim either trivially 1 or dependent on an unstated denominator; the evaluation also reuses the training target function.
-
self definitional
[Section 5, 'Coverage index (|Wψ|)', Equations 7-9]
"Let G be the subset of nodes, G⊆ C, to be monitored, covered in the routes of the agents, and Z⊆ G, a subset that fulfills the following conditions ... Finally, the coverage index, which depends on the value of ψ, is the cardinality of the subset Wψ with the nodes in Z visited by any agent in any simulation episode (Equation 9)."
Under the paper's own definition, G is the set of nodes 'covered in the routes of the agents.' Since Z⊆G, every node in Z is by construction visited by at least one route, so Wψ=Z and the index is identically 1 (or 100%) — yet Tables 5-7 report values from 0.141 to 1.000. The reported fractions are possible only if G is instead the full candidate set C and the table actually lists |Wψ|/|Z|, a normalization that is never stated. Thus the headline 'coverage of more than 90%' is either a tautology or rests on an unstated denominator; the central quantitative claim reduces to the metric's definition.
-
fitted input called prediction
[Sections 3.2/3.5 (target function and reward) and Section 5 (coverage index)]
"σ : V → R a target function. The higher the value of the target function for a node, the more important it is for agents to transit through it. Therefore, the goal of the model will be to maximize the coverage of those nodes with higher target values. ... Since we have information about crimes that have occurred in these areas, we rank all nodes in the area to be covered by the number of crimes and extract the number of nodes that represent the chosen percentage, ψ."
The same historical crime data define both the reward signal (through σ in Eq. 5, with α± granted when σ meets a relevance threshold φ) and the evaluation metric (ranking nodes 'by the number of crimes'). The routes are optimized to maximize σ-weighted coverage, and then the coverage index measures coverage of the top-σ nodes. There is no held-out or temporally separated crime sample; the reported 'results' describe how well the optimized policy performs on the very function it was trained to optimize. This is a fitted input presented as an independent evaluation, not a prediction validated against data outside the training objective.
full rationale
The central empirical claim is not supported by an independent derivation chain. The formal definition of the coverage index (Eqs. 7-9) makes the measured set equal to the target set by construction if G is the route-covered set, so the index would be trivially 1; the fractional table values require an unstated reinterpretation of G and an unstated normalization. Independently of that ambiguity, the evaluation reuses the same crime-derived target function σ that drives the reward function, so the reported coverage is an in-sample measure of the training objective rather than an external validation. The algorithm comparisons against greedy, IPPO, and MAPPO are legitimate and not circular, and I found no load-bearing self-citation chain; the circularity is concentrated in the metric definition and the same-data evaluation. For these reasons the paper receives a partial-circularity score of 6 rather than a higher score, since the greedy baseline and the algorithm comparisons retain independent content.
Assumptions & free parameters
free parameters (9)
- coverage factor nu =
-25 for zones 3/9; -10 for zone 10
- exploration reward alpha_minus =
5 for zones 3/9; 10 for zone 10
- optimal exploration reward alpha_plus =
50 for zones 3/9; 100 for zone 10
- normalization factor eta =
10
- relevance threshold phi =
10
- VDPPO learning rate =
0.0005
- VDPPO lambda =
0.95
- entropy coefficient =
0.01
- KL coefficient =
0.3
assumptions (7)
- domain assumption Dec-POMDP with cooperative homogeneous agents sharing a single policy is an adequate model for police patrol routing.
- domain assumption Grid-to-graph skeletonization with 50 m cells captures patrol-relevant mobility and crime distribution.
- ad hoc to paper An 8-hour shift maps to 50 discrete steps of approximately 10 minutes each.
- domain assumption Continuous over-surveillance reduces patrol effectiveness and should be penalized.
- domain assumption Patrols will not dynamically deviate from the planned route to handle incidents.
- ad hoc to paper Only 304,125 of 376,737 crimes were successfully geolocated and used without spatial-bias correction.
- domain assumption Historical crime counts from 2010-2018 are an appropriate target function for future patrol planning.
Cite this review
Pith. "Pith review of Cooperative Patrol Routing: Optimizing Urban Crime Surveillance through Multi-Agent Reinforcement Learning." pith.science (2026). https://pith.science/paper/6KKUDZDP
@misc{pith2026250108020,
author = {Pith},
title = {Pith review of: Cooperative Patrol Routing: Optimizing Urban Crime Surveillance through Multi-Agent Reinforcement Learning},
year = {2026},
howpublished = {\url{https://pith.science/paper/6KKUDZDP}},
note = {Machine review of arXiv:2501.08020}
}
abstract
The effective design of patrol strategies is a difficult and complex problem, especially in medium and large areas. The objective is to plan, in a coordinated manner, the optimal routes for a set of patrols in a given area, in order to achieve maximum coverage of the area, while also trying to minimize the number of patrols. In this paper, we propose a multi-agent reinforcement learning (MARL) model, based on a decentralized partially observable Markov decision process, to plan unpredictable patrol routes within an urban environment represented as an undirected graph. The model attempts to maximize a target function that characterizes the environment within a given time frame. Our model has been tested to optimize police patrol routes in three medium-sized districts of the city of Malaga. The aim was to maximize surveillance coverage of the most crime-prone areas, based on actual crime data in the city. To address this problem, several MARL algorithms have been studied, and among these the Value Decomposition Proximal Policy Optimization (VDPPO) algorithm exhibited the best performance. We also introduce a novel metric, the coverage index, for the evaluation of the coverage performance of the routes generated by our model. This metric is inspired by the predictive accuracy index (PAI), which is commonly used in criminology to detect hotspots. Using this metric, we have evaluated the model under various scenarios in which the number of agents (or patrols), their starting positions, and the level of information they can observe in the environment have been modified. Results show that the coordinated routes generated by our model achieve a coverage of more than $90\%$ of the $3\%$ of graph nodes with the highest crime incidence, and $65\%$ for $20\%$ of these nodes; $3\%$ and $20\%$ represent the coverage standards for police resource allocation.
Figures
Figures from the paper (6 more)
Reference graph
Works this paper leans on
-
[5]
Balancing e fficiency and unpredictability in multi-robot patrolling: A marl- based approach, in: 2023 IEEE International Conference on Robotics and Automation (ICRA), IEEE. pp. 3504–3509. Hari, S.K.K., Rathinam, S., Darbha, S., Kalyanam, K., Manyam, S.G., Casbeer, D.,
work page 2023
-
[9]
European Journal of Operational Research 291, 296–308
Multi-agent reinforcement learning algorithm to solve a partially-observable multi-agent problem in disaster response. European Journal of Operational Research 291, 296–308. doi:https://doi.org/10. 1016/j.ejor.2020.09.018. Lee, Y ., SooHyun, O., Eck, J.E.,
work page 2020
-
[16]
Lstm path-maker: a new lstm-based strategy for the multi- agent patrolling, in: HAW AII INTERNATIONAL CONFERENCE ON SYSTEM SCIENCES 2019 (HICSS-52). doi:10.24251/HICSS.2019.076. Parker, J., Nunes, E., Godoy, J., Gini, M.,
-
[19]
The use of predictive analysis in spatiotemporal crime forecasting: Building and testing a model in an urban context. Applied Geography 86, 255–261. doi: https://doi.org/10. 1016/j.apgeog.2017.06.011. Samanta, S., Sen, G., Ghosh, S.K.,
work page 2017
-
[20]
The gravitational strategy for the timed patrolling, in: 2010 22nd IEEE International Conference on Tools with Artificial Intelligence, IEEE. pp. 113–120. Samvelyan, M., Rashid, T., De Witt, C.S., Farquhar, G., Nardelli, N., Rudner, T.G., Hung, C.M., Torr, P.H., Foerster, J., Whiteson, S.,
work page 2010
-
[21]
arXiv preprint arXiv:1902.04043
The starcraft multi-agent challenge. arXiv preprint arXiv:1902.04043 . Santana, H., Ramalho, G., Corruble, V ., Ratitch, B.,
arXiv 1902
-
[23]
arXiv preprint arXiv:1707.06347
Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 . Sea, V ., Sugiyama, A., Sugawara, T.,
-
[24]
Frequency-based multi-agent patrolling model and its area partitioning solu- tion method for balanced workload, in: Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26–29, 2018, Proceedings 15, Springer. pp. 530–545. Shalev-Shwartz, S., Shammah...
work page 2018
Show all 28 references
-
[25]
arXiv preprint arXiv:1610.03295
Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.03295 . Sherman, L.W., Williams, S., Ariel, B., Strang, L.R., Wain, N., Slothower, M., Norton, A.,
-
[26]
Artificial Intelligence 195, 63–105
Near-optimal continuous patrolling with teams of mobile information gathering agents. Artificial Intelligence 195, 63–105. doi: https://doi.org/10.1016/j. artint.2012.10.006. Su, J., Adams, S., Beling, P.,
2012 doi
-
[27]
Multiagent system development for cooperative multiplayer video game using deep q-network, in: 2019 International Conference of Advanced Informatics: Concepts, Theory and Applications (ICAICTA), IEEE. pp. 1–5. Yan, C., Zhang, T.,
2019
-
[28]
arXiv preprint arXiv:2107.06434
Centralized model and exploration policy for multi-agent rl. arXiv preprint arXiv:2107.06434 . 28
-
[1129]
Trust region policy optimization, in: International conference on machine learning, PMLR
Schulman, J., Levine, S., Abbeel, P., Jordan, M., Moritz, P., 2015a. Trust region policy optimization, in: International conference on machine learning, PMLR. pp. 1889–1897. Schulman, J., Moritz, P., Levine, S., Jordan, M., Abbeel, P., 2015b. High-dimensional continuous contro...
-
[2004]
IEEE /WIC/ACM International Conference on Intelligent Agent Technology, 2004.(IAT 2004)., IEEE
Theoretical analysis of the multi-agent patrolling problem, in: Proceedings. IEEE /WIC/ACM International Conference on Intelligent Agent Technology, 2004.(IAT 2004)., IEEE. pp. 302–308. Cho, K., Van Merri ¨enboer, B., Gulcehre, C., Bahdanau, D., Bougares, F., Schwenk, H., Bengio, Y .,
2004
-
[2009]
Cooperative patrol planning of multi-robot systems by a competitive auction system, in: 2009 ICCAS-SICE, IEEE. pp. 4359–4363. Iqbal, S., Sha, F.,
2009
-
[2010]
1271–1276
Msp algorithm: multi-robot patrolling based on territory allocation using balanced graph partitioning, in: Proceedings of the 2010 ACM symposium on applied computing, pp. 1271–1276. Portugal, D., Rocha, R.P.,
2010
-
[2013]
Applying bayesian learning to multi-robot patrol, in: 2013 IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR), IEEE. pp. 1–6. Portugal, D., Rocha, R.,
2013
-
[2014]
arXiv preprint arXiv:1406.1078
Learning phrase representations using rnn encoder-decoder for statistical machine translation. arXiv preprint arXiv:1406.1078 . De Witt, C.S., Gupta, T., Makoviichuk, D., Makoviychuk, V ., Torr, P.H., Sun, M., Whiteson, S.,
-
[2015]
arXiv preprint arXiv:1509.02971
Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.02971 . Lowe, R., Wu, Y .I., Tamar, A., Harb, J., Pieter Abbeel, O., Mordatch, I.,
-
[2016]
Asynchronous methods for deep reinforcement learning, in: International conference on machine learning, PMLR. pp. 1928–1937. Mnih, V ., Kavukcuoglu, K., Silver, D., Rusu, A.A., Veness, J., Bellemare, M.G., Graves, A., Riedmiller, M., Fidjeland, A.K., Ostrovski, G., et al.,
1928
-
[2017]
Multi-agent patrolling in dynamic environments, in: 2017 IEEE international conference on agents (ICA), IEEE. pp. 72–77. Othmani-Guibourg, M., Farges, J.L., Seghrouchni, A.,
2017
-
[2018]
Path generation with lstm recurrent neural net- works in the context of the multi-agent patrolling, in: 2018 IEEE 30th International Conference on Tools with Artifi- cial Intelligence (ICTAI), pp. 430–437. doi:10.1109/ICTAI.2018.00073. Othmani-Guibourg, M., El Fallah-Seghrouch...
2018
-
[2019]
Decision Support Systems 119, 107–117
Public decision support for low population density areas: An imbalance- aware hyper-ensemble for spatio-temporal crime prediction. Decision Support Systems 119, 107–117. doi: https: //doi.org/10.1016/j.dss.2019.03.001. Kuba, J.G., Chen, R., Wen, M., Wen, Y ., Sun, F., Wang, J....
2019 doi
-
[2020]
Devia, N., Weber, R.,
Is independent learning all you need in the starcraft multi-agent challenge? arXiv preprint arXiv:2011.09533 . Devia, N., Weber, R.,
2011 arXiv
-
[2021]
arXiv preprint arXiv:2109.11251
Trust region policy optimisation in multi-agent reinforcement learning. arXiv preprint arXiv:2109.11251 . Lee, H.R., Lee, T.,
-
[2022]
Value-decomposition multi-agent proximal policy optimization, in: 2022 China Automation Congress (CAC), IEEE. pp. 3460–3464. Machado, A., Almeida, A., Ramalho, G., Zucker, J.D., Drogoul, A., 2002a. Multi-agent movement coordination in patrolling, in: Proceedings of the 3rd Int...
2022
-
[2023]
A risk-aware multi-objective patrolling route optimiza- tion method using reinforcement learning, in: 2023 IEEE 29th International Conference on Parallel and Distributed Systems (ICPADS), IEEE. pp. 1637–1644. Chevaleyre, Y .,
2023
-
[2024]
M ´alaga — datosa- biertos.malaga.eu
Sistema de Informaci ´on Cartogr´afica - Callejero - Datos abiertos Ayto. M ´alaga — datosa- biertos.malaga.eu. [Accessed 08-04-2024]. Oliehoek, F.A., Amato, C., et al.,
2024
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.