Piracy Risk-Minimizing Transit and Patrol Routing

Our approach is centered on optimizing the movement of transiting and patrolling vessels through better coordination and planning, in order to minimize the chance of successful pirate attack. For modeling the adversarial aspects of the problem, namely the interaction between the pirates and the transiting and patrolling vessels, we employ the framework of game theory, specifically that of security games which have been recently successfully applied to similar problems. We are able to evaluate the effectiveness of computed solutions directly in our platform. The results show a substantial improvement compared to existing transit and patrolling schemes.

The situation in the Gulf of Aden is depicted on the following picture. The transiting vessels are following the IRTC corridor patrolled by a number of naval forces. The pirates roams the area trying to find an unprotected vessel to attack.

Transit Scheme in the Gulf of Aden

The situation can be seen as a game between three types of players – the first type of players represent transport vessels (further termed T player) trying to safely cross the area, the second type represents armed patrols operating in the area (further termed P player) protecting transporters and trying to find and capture pirate vessels, and finally the third type of players represents pirate vessels (further termed A player) performing attacks on transport vessels and trying to capture them. We further refer to this game-theoretic model as the Patroller-Attacker-Transit (PAT) game.

Top

Patroller-Attacker-Transit (PAT) Game

Based on the goals of the individual types of players, we can explicitly model their interactions as a game between many agents (multiple players of each type – many transport vessels, several armed patrols and pirate vessels). This game, however, would be too complex to solve optimally. Moreover, the game would remain highly complex even if we assumed only three players (one for each type of players and controlling possibly multiple units) because of the asymmetry of players’ goals. Even though there is a clear adversarial element represented by the A player, the P and T players have only slightly different goals and utility functions, which makes the game asymmetric and hard to solve on large scenarios.

PAT Game

Rather than modeling the interactions between players explicitely, we can follow an implicit interaction model. In this approach, we model relation between each pair of player types as a distinct two-player game and assume fixed strategy for the third type of players who act as part of the environment. Following this concept, we can more accurately model simpler two-player-type games and we are able to compute an optimal solution in these smaller games. Unfortunately, such a piecewise approach does not guarantee that a solution which is optimal in some of the smaller games would be optimal in the complete PAT game. On the other hand, it can be still a reasonable strategy.

Top

Transit Game

The first game is the Transit Game. It is a two-player-type game between transport players and pirate players. We assume that transport players are travelling together and their goal is to transit an area without being captured by some of the pirates. The action of transport players is some selected path through the area that has the lowest probability of the encounter. Moreover, the selection of the path should be randomized; otherwise the pirates can learn the strategy of transport players and capture them more easily. Hence, we seek mixed strategies for transport players – i.e. some probabilistic distribution over all possible paths between a starting and ending point of the area – and we minimize the expected probability of the encounter.

The actions of the pirate vessels are represented as closed walks through the area that originate in their base. The player omitted in this game, naval forces, can be represented as part of the environment by a probabilistic distribution over the area specifying the probability that a pirate attack would be successful in a given location. Other games (i.e. Transit Grouping or Patrolling Game) can use the resulting probability distributions of paths of transport vessels.

Transit Game

Top

Transit Grouping

The second game is the Transit Grouping game, which is played between T players and P players. We consider this situation as a cooperative game, where transport players are trying to create optimal groups (i.e. form optimal coalitions) based on their characteristics (e.g. speed) and their preferences (e.g. deadlines for cargo delivery). Moreover, transport players form a group with respect to the available naval patrols (i.e. the number and selected speed of specific groups can depend on the overall number and capabilities of available armed patrols).

At present, we have developed a preliminary approach to solving this game. As the result of solving the transit grouping game, we obtain the information about which transport vessels belong to which group and we can use this knowledge in other games. Note that groups of transport vessels always move together, and we can thus view them as a single player. The optimization techniques are in detail described here.

securetransit

Top

Patrolling Game

Finally, there is the Patrolling Game, which is a game between player types P and A. The goal of the armed patrols is to protect transiting transport vessels. We captured this scenario as a patrolling game, where a single patroller is trying to protect several valuable targets that are moving across the area – i.e. periodically visit them and minimize maximal probability that some target would be left unvisited more than some given time. As a part of the environment, there are the movement schedules of the transiting vessels that are being protected.

We assume that these schedules are known to both types of players and we do not model pirate vessels explicitly in the game (e.g. as in the Transit Game) but we assume the worst case – i.e. that the pirate vessel can attack any transiting transport at any time. As the outcome of the Patrolling Game, we obtain a time-dependent policy for the patroller representing randomized movement in the area.

Patrolling Graph

Publications

Papers

  • Ondrej Vanek and Ondrej Hrstka and Michal Pechoucek: Improving Group Transit Schemes to Minimize Negative Effects of Maritime Piracy. IEEE Intelligent Transportation Systems (to appear). 2014.
    BiBTeX | PDF (430)
  • Ondrej Vanek and Michal Pechoucek: Dynamic Group Transit Scheme for Corridor Transit. In Proceedings of the 5th International Conference on Modeling, Simulation and Applied Optimization (ICMSAO). IEEE Press, 2013.
    BiBTeX | PDF (388)
  • Ondrej Vanek and Michal Jakob and Ondrej Hrstka and Michal Pechoucek: Agent-based Model of Mariime Traffic in Piracy-affected Waters. Transportation Research Part C: Emerging Technologies.. 2013, vol. 36, p. 157–176. ISSN 0968-090X.
    BiBTeX | PDF (422)
  • Michal Jakob and Ondrej Vanek and Ondrej Hrstka and Michal Pechoucek: Agents vs. Pirates: Multi-Agent Simulation and Optimization to Fight Maritime Piracy. In 12th International Conference on Autonomous Agents and Multiagent Systems. 2012.
    BiBTeX | PDF (345)
  • Ondrej Vanek: Security Games with Mobile Patrollers (Extended Abstract). In Proceedings of 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). 2011.
    BiBTeX | PDF (7)
  • Ondrej Vanek, Michal Pechoucek, Michal Jakob, Branislav Bosansky a Viliam Lisy: Agentni simulaci proti somalskym piratum. Scientific American, Czech Edition. 2011.
    BiBTeX | PDF (5)
  • Ondrej Vanek, Michal Jakob, Ondrej Hrstka, and Michal Pechoucek: AgentC: Agent-based System for Securing Maritime Transit (Demonstration). In Proceedings of The 10th International Conference on Autonomous Agents and Multiagent Systems. 2011.
    BiBTeX | PDF (10)
  • Ondrej Vanek and Michal Jakob and Viliam Lisy and Branislav Bosansky and Michal Pechoucek: Iterative Game-theoretic Route Selection for Hostile Area Transit and Patrolling. In Tenth International Conference on Autonomous Agents and Multiagent Systems. 2011.
    BiBTeX | PDF (14)
  • Michal Jakob and Ondrej Vanek and Michal Pechoucek: Using Agents to Improve International Maritime Transport Security. IEEE Intelligent Systems. 2011, vol. 26, p. 90-96. ISSN 1541-1672.
    BiBTeX | PDF (13)
  • Ondrej Hrstka and Ondrej Vanek: Optimizing Group Transit in the Gulf of Aden. In Proceedings of 15th International Student Conference on Electrical Engineering (POSTER). 2011.
    BiBTeX | PDF (6)
  • Branislav Bosansky, Viliam Lisy, Michal Jakob and Michal Pechoucek: Computing Time-Dependent Policies for Patrolling Games with Mobile Targets. Tenth International Conference on Autonomous Agents and Multiagent Systems. 2011.
    BiBTeX | PDF (12)
  • Ondrej Vanek and Branislav Bosansky and Michal Jakob and Michal Pechoucek: Transiting Areas Patrolled by a Mobile Adversary. In Proceedings of 2010 IEEE Conference on Compuattional Intelligence and Games. 2010.
    BiBTeX | PDF (51)
  • Michal Jakob and Ondrej Vanek and Stepan Urban and Petr Benda and Michal Pechoucek: Employing Agents to Improve the Security of International Maritime Transport. In Proceedings of AAMAS 2010 Workshop on Agents In Traffic and Transportation. 2010.
    BiBTeX | PDF (59)
  • Stepan Urban and Michal Jakob and Michal Pechoucek: Probabilistic modeling of mobile agents' trajectories. In Proceedings of the International Workshop on Agents and Data Mining Interaction (ADMI 2010). 2010.
    BiBTeX | PDF (50)
  • Michal Jakob and Ondrej Vanek and Stepan Urban and Petr Benda and Michal Pechoucek: AgentC: Agent-based Testbed for Adversarial Modeling and Reasoning in the Maritime Domain (Demo). In Proceedings of The Ninth International Conference on Autonomous Agents and Multiagent Systems. 2010.
    BiBTeX | PDF (58)
  • Ondrej Vanek: Agent-based Simulation of the Maritime Domain. In POSTER 2010, 14th International Student Conference on Electrical Engineering. CVUT, Fakulta elektrotechnicka, 2010.
    BiBTeX | PDF (53)
  • Ondrej Vanek: Agent-based Simulation of the Maritime Domain. Acta Polytechnica. 2010, vol. 50, p. 94-99.
    BiBTeX | PDF (44)
Top

Books

  • Ondrej Vanek and Michal Jakob and Michal Pechoucek: Using Data-Driven Simulation for Analysis of Maritime Piracy. In Prediction and Recognition of Piracy Efforts Using Collaborative Human-Centric Information Systems. IOS Press, 2013, p. 109-116.
    BiBTeX | DOCX (316)
Top

Other

  • Ondrej Vanek: Computational Methods for Transportation Security. . 2013.
    BiBTeX | PDF (431)
  • Ondrej Vanek, Michal Jakob, Ondrej Hrstka, and Michal Pechoucek: Agent-based System for Securing Maritime Transit (May 2011). . 2011.
    BiBTeX | PDF (313)
Top

Reports

  • Michal Jakob and Ondrej Vanek and Branislav Bosansky and Ondrej Hrstka and Vojtech Krizek and Stepan Urban and Petr Benda and Michal Pechoucek: Adversarial Modeling and Reasoning in the Maritime Domain - Year 2 Report. . 2010.
    BiBTeX | PDF (26)
  • Michal Jakob and Ondrej Vanek and Stepan Urban and Petr Benda and Michal Pechoucek: Adversarial Modeling and Reasoning in the Maritime Domain (Year 1 Report). . 2009.
    BiBTeX | PDF (57)
Top