A researcher has solved the wall pursuit game, a nearly 60-year-old game theory quandary with implications for better reasoning about autonomous systems such as driverless vehicles. Researchers frequently use game theory to understand how driverless vehicles can navigate the complexities of the road. Game theory is a mathematical model that represents how rational agents behave strategically to achieve their goals.
Dejan Milutinovic, a professor of electrical and computer engineering at UC Santa Cruz, has long collaborated with colleagues on differential games, a complex subset of game theory that deals with moving game players. One of these games is called the wall pursuit game, a relatively simple model for a situation in which a faster pursuer has the goal to catch a slower evader who is confined to moving along a wall.
Since this game was first described nearly 60 years ago, there has been a dilemma within the game – a set of positions where it was thought that no game optimal solution existed. However, Milutinovic and his colleagues have demonstrated in a new paper published in the journal IEEE Transactions on Automatic Control that this long-standing quandary does not exist, and have introduced a new method of analysis that proves there is always a deterministic solution to the wall pursuit game. This discovery opens the door to resolving other similar challenges in the field of differential games, as well as better reasoning about autonomous systems such as driverless vehicles.
When we take the rate of loss analysis and apply it elsewhere, the game optimal actions from the classical analysis are not impacted. We take the classical theory and augment it with rate of loss analysis, so there is a solution everywhere.
Dejan Milutinovic
Game theory is used to explain behavior in a variety of disciplines, including economics, political science, computer science, and engineering. The Nash equilibrium is a well-known concept in game theory. The concept was developed by mathematician John Nash and defines game optimal strategies for all players in order to finish the game with the least amount of regret. Any player who does not play their game optimal strategy will have more regret; thus, rational players are all motivated to play their equilibrium strategy.
This concept is applicable to the wall pursuit game, which has a classical Nash equilibrium strategy pair for the two players, the pursuer and the evader, that describes their best strategy in almost all of their positions. However, there are a set of positions between the pursuer and evader for which the classical analysis fails to yield the game optimal strategies and concludes with the existence of the dilemma. This set of positions are known as a singular surface and for years, the research community has accepted the dilemma as fact.
But Milutinovic and his co-authors were unwilling to accept this.
“This bothered us because we thought, if the evader knows there is a singular surface, there is a threat that the evader can go to the singular surface and misuse it,” Milutinovic said. “The evader can force you to go to the singular surface where you don’t know how to act optimally and then we just don’t know what the implication of that would be in much more complicated games.”
So Milutinovic and his coauthors devised a novel approach to the problem, employing a mathematical concept that did not exist when the wall pursuit game was first imagined. They discovered that a game optimal solution can be determined in all circumstances of the game and resolve the dilemma by using the viscosity solution of the Hamilton-Jacobi-Isaacs equation and introducing a rate of loss analysis for solving the singular surface.
The viscosity solution of partial differential equations is a mathematical concept that existed prior to the 1980s and provides a unique line of reasoning for the solution of the Hamilton-Jacobi-Isaacs equation. The concept is now well understood to be relevant for reasoning about optimal control and game theory problems.
Calculus is used to find the derivatives of viscosity solutions, which are functions, used to solve game theory problems. When the viscosity solution associated with a game has well-defined derivatives, it is relatively simple to find game-optimal solutions. This is not the case in the wall-pursuit game, and the lack of well-defined derivatives causes the quandary.
When faced with a dilemma, it is common practice for players to choose one of several possible actions at random and accept the losses that result from these decisions. But here’s the catch: if a loss occurs, each rational player will seek to minimize it.
So to find how players might minimize their losses, the authors analyzed the viscosity solution of the Hamilton-Jacobi-Isaacs equation around the singular surface where the derivatives are not well-defined. Then, they introduced a rate of loss analysis across these singular surface states of the equation. They found that when each actor minimizes its rate of losses, there are well-defined game strategies for their actions on the singular surface.
The authors discovered that this rate of loss minimization not only defines the game optimal actions for the singular surface, but it also agrees with the game optimal actions in every possible state where the classical analysis can also find these actions.
“When we take the rate of loss analysis and apply it elsewhere, the game optimal actions from the classical analysis are not impacted,” Milutinovic explained. “We take the classical theory and augment it with rate of loss analysis, so there is a solution everywhere.” This is a significant result demonstrating that the augmentation is more than just a quick fix for finding a solution on the singular surface; it is a fundamental contribution to game theory.
