REVIEW 5 major objections 5 minor 6 references
Design of A* based heuristic algorithm for efficient interdiction in multi-Layer networks
T0 review · 5 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read A* on a layered graph finds near-optimal defender routes for escape interdiction.
desk verdict A narrow A*-flavored heuristic that is presented as a probability-maximizing method but whose core construction can yield negative edge weights and utilities above 1, on the strength of a single six-node example. 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 load-bearing device is the multi-layer time-expanded network: a copy of the road graph for each discrete time step, with inter-layer edges representing travel along an original edge over its time length. On this graph, A* scores each node by f(n)=g(n)+h(n), where g(n) is the sum of attacker mixed probabilities of strategies that visit that node at that time, and h(n) is the heuristic estimate of future interception probability reachable from that node. The node weight (1−f(n)) is assigned to all incoming edges, and Dijkstra's algorithm finds the minimum-cost defender plan, with defender utility defined as 1−P, where P is the total probability of successful interdiction.
What would settle it
Run both algorithms on a larger network where no single defender route can cover all attacker paths and the MILP-optimal utility is known; if the A* planner returns a utility below the MILP optimum or fails to find any feasible route, the near-optimality claim fails. A second falsifier is sensitivity: perturb one attacker path's probability and check whether the A* route changes in the way the f(n) scoring predicts.
Extended reading notes
Core claim
The central claim is that applying A* to a multi-layer time-expanded graph produces a near-optimal defender strategy for the escape interdiction problem with far less computation than an exact MILP solver. In the layered graph, each time step is a copy of the transportation network, and the attacker's mixed strategy assigns probabilities to a set of escape paths. For each node, the A* score f(n)=g(n)+h(n) adds the exact accumulated probability mass of attacker strategies that reach that node (g) to a heuristic estimate of future interception probability reachable from it (h); the node weight 1−f(n) is placed on incoming edges, and Dijkstra's algorithm then extracts the defender route with maximum interdiction probability. On the reported six-node instance, both A* and MILP return the same route, (6,0,0), (3,2,2), (5,4,6), with utility 1.0, while A* needs about 0.04 seconds and MILP about 0.33 seconds. The paper takes these results as evidence that the heuristic is an efficient and scalable alternative to exact methods.
Load-bearing premise
The entire algorithm is handed the complete attacker mixed strategy—every escape path and its exact probability—as input, even though the paper's problem statement says defenders only know the crime location.
Editorial extensions
If this is right
- On any instance where the full attacker mixed strategy is supplied, the layered-graph formulation converts defender planning into a single shortest-path problem on the expanded network.
- On the tested six-node network, the heuristic obtains the same optimal interdiction probability as the MILP solver in roughly one-eighth of the runtime.
- If the runtime advantage persists on larger networks, defenders could replan quickly as new information about attacker probabilities arrives.
- The MILP baseline remains the exact benchmark, and the paper positions A* as the practical alternative when exact solving becomes too slow.
- The method outputs a concrete timed route schedule for each defender, not just a probability value.
Reading between the lines
- The method's dependence on the complete attacker mixed strategy is the main gate: if only the crime location is known, one would first need to estimate or learn the strategy set, and the paper does not show how to do that.
- A natural extension is to replace the fixed attacker distribution with a robust or adversarial set of distributions, testing whether the A* score f(n) still yields good defender routes under distributional uncertainty.
- The heuristic cost h(n) is built from the same probability data as g(n), so the algorithm is really a deterministic-policy search rather than a statistical estimator; a randomized defender schedule could be a follow-up.
- Running the same comparison on larger networks where MILP cannot finish would separate the scalability claim from the favourable small instance shown.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a layered time-expanded network representation of an escape interdiction problem and an 'A*' algorithm that assigns node values f(n)=g(n)+h(n) from attacker mixed-strategy probabilities, converts them to edge weights 1−f(n), runs Dijkstra's algorithm, and reports defender utility as Ud=1−P. It compares this method with a MILP baseline on a six-node network, reporting identical defender strategies and utility 1.0 in all ten test cases, with lower runtime for the proposed method. The central claims are that the approach is near-optimal and significantly outperforms the MILP-based defender strategy in computational efficiency and solution quality.
Significance. If the central claims were correct, a fast heuristic for interdiction on layered transportation networks would be a useful practical contribution, and the choice of a MILP baseline is a reasonable benchmark. The layered-network modeling idea is sensible, but the paper provides no correctness proof, no admissibility or consistency proof for the heuristic, and no bound on the edge weights used by Dijkstra. The experimental section is a single six-node instance repeated ten times, which cannot support the claimed efficiency or scalability advantages. The work therefore does not currently meet the standard for a publishable contribution.
major comments (5)
- [Section 3, Algorithm 1] The method is not actually A*. Step 3 computes f(n) for each node and then assigns edge weights 1−f(n) before applying Dijkstra's algorithm. The heuristic h(n) is used only to define static edge weights, not to guide an A* search with an open list and priority queue. The paper should either rename the method or present a genuine A* search in which f(n) is the priority key.
- [Section 3, Algorithm 1, Step 3] Nothing guarantees that the edge weights 1−f(n) are nonnegative. Since g(n) sums the mixed probabilities of all attacker strategies that visit n, and h(n) is a backward-propagated probability mass of future exits, the same attacker strategy can be counted in both terms. For example, if two attacker strategies each have probability 0.5, both visit node v at time 2, and exit at times 3 and 4, then Step 1 gives g(v)=1.0, Step 2 gives h(v)=0.5, so f(v)=1.5 and the incoming edge weight is −0.5. Dijkstra's algorithm is not valid with negative edge weights, and the resulting Ud=1−P can exceed 1, so the reported utility is not guaranteed to be a probability. No theorem bounds f(n) or proves that the Dijkstra cost P equals an interdiction probability.
- [Section 3, Step 2] The heuristic h(n) is not an admissible heuristic in the A* sense. It is a backward-propagated attacker-exit probability mass, not a lower bound on the remaining cost from node n to a goal. Without admissibility or consistency, the claimed near-optimality of the defender strategy is unsupported. The paper needs a formal statement of what h(n) estimates and a proof that the resulting path cost corresponds to the actual defender utility.
- [Section 5, Table 1] The experimental evaluation consists of a single six-node network instance repeated ten times with identical attacker strategies, identical defender strategy, identical utility, and nearly identical runtimes. This is one data point, not ten. It cannot establish that the proposed method 'significantly outperforms' the MILP approach or that it scales to large transportation networks. The paper needs experiments on multiple network sizes, time horizons, and attacker strategy sets, preferably with statistical summaries over randomized instances.
- [Section 1 and Algorithm 1 Input] The introduction states that defenders 'are only informed about the crime location within a large transportation network,' but Algorithm 1 requires as input the complete set of attacker strategies with assigned mixed probabilities. If the attacker's full mixed strategy is assumed available to the defender for planning, this should be stated explicitly in the problem definition; otherwise the proposed method is inapplicable to the declared scenario. This mismatch affects the applicability claim of the paper.
minor comments (5)
- [Table 1 and Fig. 2] The notation '0 6' and '01' for node-time pairs is ambiguous and inconsistent; use a clear notation such as (node, time) throughout.
- [Throughout] The paper alternates between 'A-Star' and 'A*'; choose one term and use it consistently.
- [Section 4, Eq. (2)] The MILP objective 'max −Σ(1−zA)yA' is equivalent to minimizing failure probability, but it is easily misread; consider writing 'max Σ zA yA' to make the objective clearer.
- [Fig. 2] The caption should explain the red and blue labels within the figure itself; the text refers to exact and heuristic costs in red and blue, but the figure is not self-contained.
- [References] Reference [5] is about influence propagation in social networks and does not appear to be the source of the layered time-expanded graph idea; a transportation time-expanded network reference would be more appropriate.
Circularity Check
No significant circularity: the A* scores and the reported utility are constructed from the input attacker distribution by design, which is the optimization objective rather than a circular reduction.
full rationale
The claimed derivation chain is not circular. The input is a fully specified attacker mixed strategy y; Eq. (1) defines the defender utility as the expectation over y, and Algorithm 1 constructs g, h, and edge weights from the same y. Using the input distribution both to optimize and to evaluate is the standard objective of the game-theoretic problem, not a hidden self-referential reduction. No free parameter is fitted to the reported outcomes; the single 6-node experiment reports the same strategy for MILP and A* with utility 1.0, and the runtime comparison is independent of the scoring construction. The author's self-citations [1,4,6] are background/literature and are not load-bearing for the A* construction or the comparison. The MILP benchmark [2] is external. The paper does contain a serious correctness risk: Algorithm 1 can assign negative edge weights when f(n)>1 and can return Ud=1-P>1, because g and h can double-count the same attacker strategy. That is an invalid probability model, but it is not circularity under the definition used here. Therefore no circular step is identified.
Assumptions & free parameters
assumptions (3)
- domain assumption The defender knows the complete attacker mixed strategy, including all attacker paths and their exact probabilities.
- ad hoc to paper The heuristic h(n), computed by backward propagation of goal exact costs, is an admissible or otherwise valid estimate for A* search.
- ad hoc to paper The edge weights (1 - f(n)) are nonnegative, so Dijkstra's algorithm is valid.
Cite this review
Pith. "Pith review of Design of A* based heuristic algorithm for efficient interdiction in multi-Layer networks." pith.science (2026). https://pith.science/paper/6USOMKB4
@misc{pith2026250610017,
author = {Pith},
title = {Pith review of: Design of A* based heuristic algorithm for efficient interdiction in multi-Layer networks},
year = {2026},
howpublished = {\url{https://pith.science/paper/6USOMKB4}},
note = {Machine review of arXiv:2506.10017}
}
read the original abstract
Intercepting a criminal using limited police resources presents a significant challenge in dynamic crime environments, where the criminal's location continuously changes over time. The complexity is further heightened by the vastness of the transportation network. To tackle this problem, we propose a layered graph representation, in which each time step is associated with a duplicate of the transportation network. For any given set of attacker strategies, a near-optimal defender strategy is computed using the A-Star heuristic algorithm applied to the layered graph. The defender's goal is to maximize the probability of successful interdiction. We evaluate the performance of the proposed method by comparing it with a Mixed-Integer Linear Programming (MILP) approach used for the defender. The comparison considers both computational efficiency and solution quality. The results demonstrate that our approach effectively addresses the complexity of the problem and delivers high-quality solutions within a short computation time.
Figures
Reference graph
Works this paper leans on
-
[5]
Discovering influential nodes for SIS models in social networks
Saito, Kazumi, Kimura Masahiro, and Motoda Hiroshi. “Discovering influential nodes for SIS models in social networks.” International Conference on Discovery Science (2009): 302-316
2009
-
[1]
Vehicle Interdiction Strategy in Complex Road Networks-A Simulation Based Approach
Samanta, Sukanya, Sen Goutam, and Ghosh Soumya Kanti. “Vehicle Interdiction Strategy in Complex Road Networks-A Simulation Based Approach.” 2021 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM) (2021): 1299-1302
2021
-
[2]
Optimal escape interdiction on transportation networks
Zhang, Youzhi, An Bo, Tran-Thanh Long, Wang Zhen, Gan Jiarui, and Jennings, Nicholas R. “Optimal escape interdiction on transportation networks.” Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (2017): 3936-3944. 16
work page 2017
-
[3]
Computing the optimal strategy to com- mit to
Conitzer, Vincent and Sandholm Tuomas. “Computing the optimal strategy to com- mit to.” Proceedings of the 7th ACM conference on Electronic commerce (2006): 82-90
2006
-
[4]
A literature review on police patrolling problems
Samanta, Sukanya, Sen Goutam, and Ghosh Soumya Kanti. “A literature review on police patrolling problems.” Annals of Operations Research 316, no. 2 (2022): 1063-1106
work page 2022
-
[6]
Samanta, Sukanya, Sen Goutam, and Ghosh Soumya Kanti. “Assessing vehicle interdiction strategies on a complex transportation network: A simulation-based study.” Socio-Economic Planning Sciences 95, (2024): 102035. 17
work page 2024
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.