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.
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.
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.
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.
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.
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.
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.
Papers
Books
Other
Reports