PULSE: an algorithm for multi-agent centralised high-density maritime traffic management based on guidance games

Abstract PULSE is an algorithm for multi-agent centralised maritime traffic management that utilises a novel approach to solve polymatrix games through evolutionary dynamics. Polymatrix games are graph-based, succinct game representations with asymmetric two-player normal-form games defined on the edges. Based on the vessels’ (players’) estimated trajectories, the proposed algorithm outputs sequences of pure strategy profiles in the form of speed and heading setpoint pairs, one for each player. These are pure Nash equilibria or their approximations intended for broadcast by the central coordinator. In maritime traffic management, vessel traffic services can provide navigational assistance and decision support to vessels via route suggestion. Guidance games , in which the payoff entries are bound to one, arise from a custom reward framework designed to govern how players balance the trade-off between externalities and internal preferences. We evaluate two variants of payoff calculations: a traditional one, where payoff vectors are derived using ordered player selection, and a novel one based on a random asymmetric two-player game selection. Given the preset strategy competition time, the latter approach reduces the equilibria search time dependency on the number of players from exponential to polynomial, making it more suitable for real-time applications compared to previous work. The simulations of consecutive guidance games and their 2-simplex visualisations highlight the structural properties of the resulting games, though a complete classification within game theory remains an open challenge. Inspired by distributed consensus-seeking algorithms, PULSE is a game-theoretical, multi-agent simulation-based model predictive control planner.