Numerical solution of the game of two cars with a neurosimulator and grid computing

authored by: Michael H. Breitner, Hans Jörg von Mettenheim
Abstract: The famous game of two cars is a pursuit-evasion dynamic game. In the extended version presented here, a correct driver (evader) on a freeway detects a wrong-way driver (pursuer in a worst case scenario), i.e., a car driving on the wrong lanes of the road or in the wrong direction. The correct driver must try to avoid collision against all possible maneuvers of the wrong-way driver. Additionally, he must try to stay on the freeway lanes. Analytically, the game is not fully solvable. The state-space is cut by various singular manifolds, e.g., barriers, universal, and dispersal manifolds. Here, discretized Stackelberg games are solved numerically for many positions in the state-space. The resulting trajectories and their adherent information are used to synthesize optimal strategies with artificial neural networks. These networks learn the optimal turn rates and optimal velocity change rates. The networks are trained with the high-end neurosimulator FAUN (Fast Approximation with Universal Neural Networks). A grid computing implementation is used which allows significantly shorter computing times. This implementation runs on low-budget, idle PC clusters and moreover power saving allows to wake up and shut down computers automatically. Parallelization on cheap hardware is one of the key benefits of the presented approach as it leads to fast but nonetheless good results. The computed artificial neural networks approximate the Stackelberg strategies accurately. The approach presented here is applicable to many other complex dynamic games which are not (fully) solvable analytically.
Organisation(s): Institute of Computer Science for Business Administration
Type: Contribution to book/anthology
Pages: 207-230
No. of pages: 24
Publication date: 2009
Publication status: Published
Peer reviewed: Yes
ASJC Scopus subject areas: Statistics and Probability, Statistics, Probability and Uncertainty, Applied Mathematics
Electronic version(s): https://doi.org/10.1007/978-0-8176-4834-3_12 (Access: Unknown)

BibTeX

@inbook{e3a1ef13254e4923a7b99cf3d456983b,
title = "Numerical solution of the game of two cars with a neurosimulator and grid computing",
abstract = "The famous game of two cars is a pursuit-evasion dynamic game. In the extended version presented here, a correct driver (evader) on a freeway detects a wrong-way driver (pursuer in a worst case scenario), i.e., a car driving on the wrong lanes of the road or in the wrong direction. The correct driver must try to avoid collision against all possible maneuvers of the wrong-way driver. Additionally, he must try to stay on the freeway lanes. Analytically, the game is not fully solvable. The state-space is cut by various singular manifolds, e.g., barriers, universal, and dispersal manifolds. Here, discretized Stackelberg games are solved numerically for many positions in the state-space. The resulting trajectories and their adherent information are used to synthesize optimal strategies with artificial neural networks. These networks learn the optimal turn rates and optimal velocity change rates. The networks are trained with the high-end neurosimulator FAUN (Fast Approximation with Universal Neural Networks). A grid computing implementation is used which allows significantly shorter computing times. This implementation runs on low-budget, idle PC clusters and moreover power saving allows to wake up and shut down computers automatically. Parallelization on cheap hardware is one of the key benefits of the presented approach as it leads to fast but nonetheless good results. The computed artificial neural networks approximate the Stackelberg strategies accurately. The approach presented here is applicable to many other complex dynamic games which are not (fully) solvable analytically.",
keywords = "Artificial neural networks, Dynamic game, Game of two cars, Grid computing, Parallel computation, Stackelberg game, Synthesis of optimal strategies",
author = "Breitner, {Michael H.} and {von Mettenheim}, {Hans J{\"o}rg}",
note = "Publisher Copyright: {\textcopyright} Birkh{\"a}user Boston, a part of Springer Science + Business Media, LLC 2009. Copyright: Copyright 2018 Elsevier B.V., All rights reserved.",
year = "2009",
doi = "10.1007/978-0-8176-4834-3_12",
language = "English",
series = "Annals of the International Society of Dynamic Games",
publisher = "Birkhauser Boston",
pages = "207--230",
booktitle = "Annals of the International Society of Dynamic Games",
address = "United States",
}