Numerical methods for game-theoretic joint trajectory prediction and planning

Conventional multiplayer motion planning approaches are often proven to not be sufficient models for the highly interactive nature of the autonomous driving scheme. Using the concepts of game-theoretic joint motion prediction and planning to find a solution for the Generalized Nash Equilibrium Problem (GNEP), allows for the shared responsibility for collision avoidance and symmetry among drivers on the road, and results in trajectories that no player wishes to deviate from. This work expands on the purely mathematical Interior Point Method (IPM) used to solve GNEPs, by proposing an IPM approach that explicitly satisfies dynamic and equality constraints and is adapted to the autonomous driving in both urban and racing scenarios. Extensive numerical testing is done by comparing the proposed algorithm with a custom implementation of an Augmented Lagrange Game Solver (ALGAMES) in MATLAB environment. The problem formulation was enhanced for both algorithms with the introduction of exact collision detection, obstacle avoidance, regularization techniques for the ALGAMES algorithm to increase stability, Iterative Best Response (IBR) algorithms and an autonomous racing formulation. The proposed algorithm, while limited in scalability and computational effort, proved to be stable under the highly complex and highly non-linear environments, showing 99.77% success rate in a 3 player lane merge Monte Carlo simulation, and 84.54% in a hyper-symmetric intersection crossing.

Gli approcci convenzionali alla pianificazione del movimento multigiocatore si sono spesso rivelati modelli insufficienti per la natura altamente interattiva dello schema di guida autonoma. L'utilizzo dei concetti di previsione e pianificazione congiunta del movimento, basati sulla teoria dei giochi, per trovare una soluzione al problema dell'equilibrio di Nash generalizzato (GNEP), consente di condividere la responsabilità di evitare le collisioni e la simmetria tra i conducenti sulla strada e di ottenere traiettorie da cui nessun giocatore desidera deviare. Questo lavoro amplia il Metodo dei Punti Interni (IPM) puramente matematico utilizzato per risolvere i GNEP, proponendo un approccio IPM che soddisfa esplicitamente i vincoli dinamici e di uguaglianza e si adatta alla guida autonoma in scenari sia urbani che di gara. L'algoritmo proposto viene confrontato con un'implementazione personalizzata di un risolutore di giochi di Lagrange aumentati (ALGAMES) in ambiente MATLAB. La formulazione del problema è stata migliorata per entrambi gli algoritmi con l'introduzione del rilevamento esatto delle collisioni, dell'evitamento degli ostacoli, di tecniche di regolarizzazione per l'algoritmo ALGAMES per aumentare la stabilità, di algoritmi di risposta migliore iterativi (IBR) e di una formulazione autonoma per le corse. L'algoritmo proposto, pur essendo limitato nella scalabilità e nello sforzo computazionale, si è dimostrato stabile in ambienti molto complessi e altamente non lineari, mostrando un tasso di successo del 99,77% in una simulazione Monte Carlo di unione di corsie a tre giocatori e dell' 84,54% in un incrocio iper-simmetrico.