Temporal Network Interdiction Problems
Abstract
Interdiction problems involve two competing entities- a leader and a follower. In these problems, the leader attempts to minimize the maximum objective that can be obtained by the follower, where the leader’s decisions are constrained to lie within some limited range of actions (e.g., by some budget constraints), and the follower s constraints and-or objective are affected by the leader’s decisions. Interdiction problems are particularly important in planning operations, or in games for which at least one of the agents makes a permanent decision. Foundational network interdiction theory regards precisely this situation, usually regarding two-stage games in which the leader commits all decisions in one stage, and the follower operates thereafter. However, there are many defense situations in which games are played with repeated decisions over time. The timing of decisions may be important with respect to the other agent s moves, changing data in the game, and information revealed as to the goals of the other agent. Traditional means of investigating these problems do not extend to such games. To address the lack of technology for efficiently solving temporal network interdiction problems, this research will investigate the creation of a mix of dynamic optimization, relaxation-restriction methods, and mathematical optimization techniques to attack problems for which the timing of agents’ actions is a key strategic decision of the game. The impact of this research is that it will produce fundamentally new ideas for algorithms that can be applied to real-world interdiction problems. These interdiction problems are generally less stylized than those that have been considered in prior research, and involve realistic elements that permit the analysis of defense actions encompassing timing, uncertainty, and repeated strategic decisions.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 22, 2024
- Source ID
- FA95502310018
Entities
People
- J. Cole Smith
Organizations
- Air Force Office of Scientific Research
- Syracuse University
- United States Air Force