Network defense and attack problems can be modeled as network interdictions. In this paper, we consider a new version of the network interdiction problem that optimizes the interdictor’s resource consumption while limiting network capacities (e.g., the shortest path) to a specified threshold. Interdictors would balance the interdiction performance and resource consumption when maximizing the performance costs too much. The most frequently-used technique is to relax the maximization restraint to certain specified threshold; however, the known algorithms provide little help in calculating the threshold restraint. We present a novel model named Minimizing the Interdiction Resource with Goal Threshold (MIRGT) based on the shortest path interdiction problem and propose two basic algorithms to solve it based on Benders decomposition and Lagrange duality, respectively. To consider the situation of complete interdiction and that of a large threshold, a corresponding set-covering algorithm and a Lagrange approximate algorithm are presented. Computational experiments show that decomposition-based algorithms generally perform better on small-world networks while duality based algorithms perform better on regular grid networks. Analyses on network property sensitivity show that the decomposition-based algorithms are sensitive to the threshold value while the duality based algorithms become weaker as the interdiction increment grows. Furthermore, we evaluate the performance of these two basic algorithms on a real-world Chicago transportation network. The result illustrates a significant advance; both algorithms can compute an optimal strategy for problems that scale up to real-world sizes.

Network interdiction game is a class of Stackelberg games on networks. In this paper, we consider a extended shortest path network interdiction game in which the interdiction focuses on nodes. In this problem, the evader attempts to traverse the shortest path from the origin to destination, while the interdictor attempts to maximize the shortest path length by interdicting some nodes of the network with limited resources. we define the nodal shortest path network interdiction problem as a bilevel program and formulate it as a mixed integer program. A novel interdiction subgraph decomposition algorithm is proposed to solve this program. We use both simulated grid network and real transportation network data in the computational experiments, and the results show that the efficiency of proposed algorithm is improved a lot comparing with the existing algorithm. And the proposed algorithm can be used to solve general shortest path network interdiction problem with large scale.

Multiagent goal recognition is a tough yet important problem in many real time strategy games or simulation systems. Traditional modeling methods either are in great demand of detailed agents’ domain knowledge and training dataset for policy estimation or lack clear definition of action duration. To solve the above problems, we propose a novel Dec-POMDM-T model, combining the classic Dec-POMDP, an observation model for recognizer, joint goal with its termination indicator, and time duration variables for actions with action termination variables. In this paper, a model-free algorithm named cooperative colearning based on Sarsa is used. Considering that Dec-POMDM-T usually encounters multiagent goal recognition problems with different sorts of noises, partially missing data, and unknown action durations, the paper exploits the SIS PF with resampling for inference under the dynamic Bayesian network structure of Dec-POMDM-T. In experiments, a modified predator-prey scenario is adopted to study multiagent joint goal recognition problem, which is the recognition of the joint target shared among cooperative predators. Experiment results show that (a) Dec-POMDM-T works effectively in multiagent goal recognition and adapts well to dynamic changing goals within agent group; (b) Dec-POMDM-T outperforms traditional Dec-MDP-based methods in terms of precision, recall, andF-measure.

Shortest-path network interdiction, where a defender strategically allocates interdiction resource on the arcs or nodes in a network and an attacker traverses the capacitated network along a shortest s-t path from a source to a terminus, is an important research problem with potential real-world impact. In this paper, based on game-theoretic methodologies, we consider a novel stochastic extension of the shortest-path network interdiction problem with goal threshold, abbreviated as SSPIT. The attacker attempts to minimize the length of the shortest path, while the defender attempts to force it to exceed a specific threshold with the least resource consumption. In our model, threshold constraint is introduced as a trade-off between utility maximization and resource consumption, and stochastic cases with some known probability p of successful interdiction are considered. Existing algorithms do not perform well when dealing with threshold and stochastic constraints. To address the NP-hard problem, SSPIT-D, a decomposition approach based on Benders decomposition, was adopted. To optimize the master problem and subproblem iteration, an efficient dual subgraph interdiction algorithm SSPIT-S and a local research based better-response algorithm SSPIT-DL were designed, adding to the SSPIT-D. Numerical experiments on networks of different sizes and attributes were used to illustrate and validate the decomposition approach. The results showed that the dual subgraph and better-response procedure can significantly improve the efficiency and scalability of the decomposition algorithm. In addition, the improved enhancement algorithms are less sensitive and robust to parameters. Furthermore, the application in a real-world road network demonstrates the scalability of our decomposition approach.

Important network attack and defense problems can be modeled as network interdiction. In this paper we propose a new threshold shortest-path network interdiction model (MIRGT) based on maximization shortest path problem, which minimizes the resources consumption while limiting the rival's network capacity to meet goal threshold. We then select a representative feedback dependency relation of multi-layer network, and propose the novel MIRGT-B bi-layer network interdiction model using logic constraint to replace the nonlinear constraint. Based on Benders decomposition and dual method, we give out two basic solution algorithms, and verify them on small-scale bi-layer networks.

Critical network defense and attack problems, usually modeled as network interdiction, is of great significance. It is of great interest from the interdictor’s view to study saturation property of resource allocations. This paper presents a bi-objective shortest path network interdiction model with node interdiction, in which the interdictor seeks to interdict a set of nodes in the network that is Pareto-optimal with respect to two objectives, i.e., maximization of shortest path length and minimization of resources cost. A novel subgraph sequence algorithm is developed to identify the efficient frontier through a sequence of single-objective problems. Novel subgraph decomposition algorithms are proposed to solve single-objective problems. Features and time complexity of those problems and algorithms are analyzed. Moreover, to make a trade-off between the resource investment and the interdiction performance, the definition and the computing method of saturation point are introduced in this paper. Both simulated grid network and real-world transportation network data are used to evaluate the performance of algorithms in numerical experiments. The results show that the subgraph sequence algorithm can achieve the optimal Pareto-frontier of this bi-objective problem effectively.