1 of 25

ICCRTS 2023

Network Flow Interdiction for Graph-based Course of Action Analysis

Jonathan Cawalla, Hans-Christian Schmitz

Formatvorlagen des Textmasters bearbeiten

Zweite Ebene

      • Dritte Ebene
        • Vierte Ebene
          • Fünfte Ebene

2 of 25

Outline

Network Flow Interdiction for Graph-based Course of Action Analysis

  1. Motivation & Scenario
  2. Graph Representation of Military Action Spaces
  3. Network Analysis Methods
  4. Outlook & Summary

© Fraunhofer FKIE

Page 2

Formatvorlagen des Textmasters bearbeiten

Zweite Ebene

      • Dritte Ebene
        • Vierte Ebene
          • Fünfte Ebene

3 of 25

Artificial Intelligence for C2IS: Challenges

[Motivation]

        • The complexity of military scenarios is very high.
        • Environments change rapidly:
          • terrain
          • resources
          • doctrine
          • mission goals
        • Military operations cannot be repeated as often as required for training a system. Training data is not easily available.
        • Therefore:
          • Meaningful reduction of complexity of C2 task definitions.
          • Identification of classes of solvable C2 decision problems.

​

​

​

​

​

​

© Fraunhofer FKIE

Page 3

4 of 25

Scenario

[Motivation]

© Fraunhofer FKIE

Page 4

[O1] Identify the main axis of a red approach.

​

​

[O2] Identity areas where the deployment of own resources has the largest effect on stopping or delaying the red approach.

5 of 25

Graph-based Representation of Action Spaces

[Concept]

© Fraunhofer FKIE

Page 5

6 of 25

Graph Representation of a Delay Operation

[Scenario]

© Fraunhofer FKIE

Page 6

7 of 25

Graph Representation of a Delay Operation

[Scenario]

© Fraunhofer FKIE

Page 7

8 of 25

Analysis Objectives

[Network Analysis Methods]

[O1] Identify the main axis of a red approach.

​

​

[O2] Identity areas where the deployment of own resources has the largest effect on stopping or delaying the red approach.

​

© Fraunhofer FKIE

Page 8

      • Network Flow Analysis
      • Network Interdiction Analysis

9 of 25

Network Flow

[Network Analysis Methods]

© Fraunhofer FKIE

Page 9

1

2

3

3

3

1

3

Capacity = # of companies "side by side" according to doctrine given the terrain (mobility corridor)

​

10 of 25

Network Flow

[Network Analysis Methods]

© Fraunhofer FKIE

Page 10

1/1

2/2

3/3

1/3

0/3

1/1

1/3

Maxmimum flow = Maximum capacity utilization for the approach

11 of 25

Network Flow

[Network Analysis Methods]

© Fraunhofer FKIE

Page 11

 

1/1

2/2

3/3

1/3

0/2

1/1

1/3

12 of 25

Network Flow – Results on example scenario

[Network Analysis Methods]

© Fraunhofer FKIE

Page 12

13 of 25

Network Flow Interdiction

[Network Analysis Methods]

© Fraunhofer FKIE

Page 13

1

2

3

3

3

1

3

Find the best interdiction

​

Interdiction = Reduce the capacity of an edge

14 of 25

Network Flow Interdiction

[Network Analysis Methods]

© Fraunhofer FKIE

Page 14

1/1

2/2

0/3

1/3

3/3

1/1

2/3

Flow can be rerouted and therefore maximum capacity utilization is not reduced

15 of 25

Network Flow Interdiction

[Network Analysis Methods]

© Fraunhofer FKIE

Page 15

1

2

3

3

3

1

3

Different interdiction example

16 of 25

Network Flow Interdiction

[Network Analysis Methods]

© Fraunhofer FKIE

Page 16

1/1

0/2

0/3

1/3

1/3

1/1

0/3

Reduction of maximum capacity utilization by 2

17 of 25

Network Flow Interdiction

[Network Analysis Methods]

© Fraunhofer FKIE

Page 17

1/1

0/2

0/3

1/3

1/2

1/1

0/3

 

Upper level problem: find the best interdiction

Lower level problem: select variables that maximize flow

18 of 25

Network Flow Interdiction

[Network Analysis Methods]

© Fraunhofer FKIE

Page 18

19 of 25

Network Interdiction – Potential Extensions

[Network Analysis Methods]

The simple method can and should be extended:

        • Introduction of different interdiction variables with budget for K different resources (e.g. different units, different mine types)
        • Different optimization function: Currently maximize flow, but could introduce different costs for edges
        • Different vehicles types could be modelled depending on terrain (some are bound to specific edges)

​

​

© Fraunhofer FKIE

Seite 19

12.12.2023

20 of 25

Network Interdiction – Limitations

[Network Analysis Methods]

​

​

© Fraunhofer FKIE

Seite 20

12.12.2023

We used classical optimization approaches, but:

        • Experiments indicate long run times in larger graphs and more options (Bilevel Optimization is computationally expensive)
        • Including multiple vehicle types with different interdiction budgets will further increase run time
        • One possible solution: Develop a heuristic approach.
          • manual coding of heuristic is time consuming
          • may not transfer well to different problem extensions

​

  • Automatic learning of heuristics through Reinforcement Learning using Graph Neural Networks (GRL)

Why Reinforcement Learning?

        • Unsupervised learning through trial and error, no dataset necessary

Why Graph Neural Networks?

        • In contrast to Deep Learning: Can consider topology and features of graphs

21 of 25

Reinforcement Learning Perspective

[Outlook]

Constructive generation of a solution through step-by-step selection of actions

​

© Fraunhofer FKIE

Seite 21

12.12.2023

Agent

Simulation

Observation/ State

Action

Reward

        • Feature extraction via GNN
        • Training with RL algorithm such as REINFORCE, PPO

​

​

Selection of an edge

Based on capacity utilization reduction

22 of 25

Reinforcement Learning Perspective

[Outlook]

© Fraunhofer FKIE

Seite 22

12.12.2023

Agent

Offline training

Synthetic graphs

Training environment

Agent

Deployment to scenario graphs

23 of 25

Network Flow Interdiction for Graph-based Course of Action Analysis

[Summary]

        • Introduction of graph representation for the military action space
        • Use of network analysis methods:
          • Network flow: finding maximum capacity utilization for a likely approach of the opponent
          • Network flow interdiction: finding actions that have the greatest effect on minimizing the opponent's capacity utilization
        • Extensions of the model
        • Future Work: Exploring the application of reinforcement learning to address limitations

© Fraunhofer FKIE

Page 23

24 of 25

Thank you.

25 of 25

Jonathan Cawalla, Hans-Christian Schmitz

Information Technology for Command and Control

{jonathan.Cawalla, hans-christian.schmitz}@fkie.fraunhofer.de

​

Fraunhofer Institute for Communication, �Information Processing and Ergonomics FKIE

Fraunhoferstr. 20 | 53343 Wachtberg | Germany

​

www.fkie.fraunhofer.de/en

Contact

—