To understand the ability of autonomous vehicles to navigate complex paths, scientists often turn to game theory, a branch of mathematics that deals with modeling the rational behavior of agents as they try to achieve their goals. Dejan Milutinovic, a professor of electrical and computer engineering at the University of California at Santa Cruz, has collaborated with research colleagues for years on a complex subset of game theory known as differential games. This area is available for players on the move. Among these games is the wall chase game, which offers a relatively simple framework for a scenario where a faster chaser tries to catch a slower escapee who is limited to moving along a wall.

Ever since the game was first described nearly 60 years ago, the game has been a dilemma – a set of locations where the optimal game solution is believed to not exist. But now Milutinovich and his colleagues have proven it in a new article in the journal. IEEE Transactions in Automatic Control, introduced a new method of analysis that proved that this age-old dilemma does not really exist and that there is always a deterministic solution to the wall. chase game This discovery opens the door to solving other similar problems that exist in the field of differential games and makes us think better about autonomous systems such as self-driving cars.

It is used to think about behavior in many fields such as game theory, economics, political science, computer science, and engineering. In game theory, the Nash equilibrium is one of the most recognized concepts. The concept was introduced by mathematician John Nash and identifies optimal game strategies for all players in a game to finish the game with the least regret. Any player who chooses not to play the optimal game strategy will ultimately regret more, so all rational players are motivated to play their balance strategy.

This concept applies to the wall chase game, a classic Nash equilibrium strategy pair for two players, one chasing and the other escaping, describing their best strategy in nearly all their positions. However, there are a number of positions between the chaser and the fleeing, where classical analysis fails to provide optimal game strategies and leads to the conclusion that a dilemma exists. This set of locations is known as a singular surface, and for years the research community has accepted this dilemma as a reality.

“This was a concern for us because we thought that if the escaped person knew there was a separate surface, there was a threat to go to the separate surface and abuse it,” Milutinovic said. “A dodger can force you to go to a certain surface where you don’t know how best to act – and then we don’t know what the consequences will be in much more complex games.”

So Milutinovic and his co-authors found a new way of approaching the problem, using a mathematical concept that didn’t exist when the wall chase game was originally designed. By using the viscosity solution of the Hamilton-Jacobi-Isaacs equation and introducing the loss ratio analysis to solve the singular surface, they were able to find that the optimal game solution can be determined under any game condition and solve the dilemma.

Solving partial differential equations by viscosity is a mathematical concept that didn’t exist until the 1980s, and it offers a unique reasoning method for solving the Hamilton-Jacobi-Isaacs equation. It is now well known that this concept relates to optimal control and game theory problems.

Using viscosity solutions, which are functions, to solve game theory problems involves using analysis to find derivatives of these functions. Finding optimal game solutions is relatively easy when there are well-defined derivatives of the viscosity solution associated with the game. This does not apply to the chase game, and the lack of well-defined derivatives creates a dilemma. In general, the practical approach when faced with a dilemma is for players to randomly choose one of the possible actions and accept losses as a result of those decisions. But here is the trick: If there is a loss, every sensible player will want to minimize it.

Therefore, to find out how players can minimize their losses, the authors analyzed the solution of the viscosity of the Hamilton-Jacobi-Isaacs equation around a singular surface where the derivatives are not well defined. Next, they did an analysis of the rate of loss in these special surface states of Equation (1). They discovered that when each player minimized the casualty rate, there were well-defined game strategies for their actions on a given surface.

The authors found that this loss minimization rate not only determines the optimal game actions for the singular surface, but is also consistent with the optimal game actions in every possible situation where classical analysis can find these actions.

“When we take the loss rate analysis and apply it elsewhere, optimal game actions are not affected by the classical analysis,” Milutinovic said. said. “We take the classical theory and supplement it with loss-rate analysis so that the solution exists everywhere. This is an important result that shows that the extension is not just a fix for finding solutions on a singular surface, but a fundamental contribution to game theory.

Milutinovic and his co-authors are interested in exploring other game theory problems related to singular surfaces to which their new method can be applied. The article is also an open call to the research community to explore other dilemmas alike.

“Now the question is, what other dilemmas can we solve?” – said Milutinovich.