A researcher has solved a 60-year-old game theory dilemma, the wall pursuit game, with implications for autonomous systems such as driverless vehicles, providing a breakthrough in reasoning for these systems. Dejan Milutinovic, professor of electrical and computer engineering at UC Santa Cruz, uses game theory to help driverless vehicles navigate the complexities of the road. Differential games, a subset of game theory, are used to model situations in which a faster pursuer attempts to catch a slower evader. One of these games is the wall pursuit game, a model for a situation in which an evader is confined to a wall and a pursuer attempts to catch them. This game is used to help researchers understand how driverless vehicles can navigate the complexities of the road.
For nearly 60 years, the wall pursuit game has posed a dilemma: it was thought that no game optimal solution existed. However, a new paper published in the journal IEEE Transactions on Automatic Control by Milutinovic and his colleagues has proven that this long-standing dilemma does not actually exist. The paper introduces a new method of analysis that proves there is always a deterministic solution to the wall pursuit game. This discovery has the potential to resolve other similar challenges in the field of differential games and can be used to improve autonomous systems such as driverless vehicles.
Game theory is used to analyze behavior in various fields, such as economics, political science, computer science, and engineering. The Nash equilibrium is a concept introduced by mathematician John Nash that defines optimal strategies for all players in a game to minimize regret. This concept applies to the wall pursuit game, where two players, the pursuer and evader, must find the best strategy to finish the game. However, there is a set of positions between the pursuer and evader for which the classical analysis fails to yield the game optimal strategies, known as a singular surface. This has been accepted as a dilemma for years, but recent research has provided a solution to this problem.
In a study published in the journal Nature Communications, researchers from the University of California, Berkeley, and the University of Belgrade have challenged the notion that a singular surface is the optimal strategy for an evader in a game of pursuit-evasion. The researchers argue that if the evader knows there is a singular surface, they can exploit it to their advantage, forcing the pursuer to go to a surface where they don’t know how to act optimally. The researchers suggest that a more complex strategy, such as a combination of multiple surfaces, may be more effective in pursuit-evasion games.
Milutinovic and his coauthors developed a new approach to the wall pursuit game, a mathematical concept that was not available when the game was first conceived. By using the viscosity solution of the Hamilton-Jacobi-Isaacs equation and introducing a rate of loss analysis, they were able to determine a game optimal solution in all circumstances. This mathematical concept, which was not available until the 1980s, is now widely used to reason about optimal control and game theory problems.
Viscosity solutions are functions used to solve game theory problems. However, when it comes to the wall-pursuit game, the lack of well-defined derivatives creates a dilemma. In this case, players typically randomly choose one of the possible actions and accept the losses that come with it. But, since each player wants to minimize their losses, a practical approach is needed to find the optimal solution.
This study analyzed the viscosity solution of the Hamilton-Jacobi-Isaacs equation around singular surfaces, where derivatives are not well-defined, to determine how players can minimize their losses. The authors found that when each actor minimizes their rate of losses, there are well-defined game strategies for their actions on the singular surface. Furthermore, these strategies are in agreement with the game’s optimal actions in every possible state where the classical analysis is also able to find these actions. This research provides a useful tool for players to minimize their losses in games with singular surfaces, and can be applied to a variety of game scenarios.”
In a new paper, researchers from the University of Belgrade have developed a new method for solving game theory problems with singular surfaces. The new method, called rate of loss analysis, augments the classical theory of game theory and can be applied to any game theory problem with a singular surface. The researchers found that the game’s optimal actions from the classical analysis are not impacted by the rate of loss analysis. The paper is an open call to the research community to similarly examine other dilemmas and explore how the rate of loss analysis can be applied. The new method could be a fundamental contribution to game theory and could help solve a variety of game theory problems.
