Researchers frequently use game theory—mathematical models that reflect the
way logical actors conduct tactically to achieve their goals—to better
understand how autonomous vehicles can negotiate the intricacies of the
road.
Dejan Milutinovic, a professor of electrical and computer engineering at UC
Santa Cruz, has long collaborated with others on differential games, a
challenging branch of game theory that deals with moving participants. The
wall chase game is one of these games, which is a fairly straightforward
example for a scenario in which a faster pursuer seeks to capture a slower
evader who is restricted to moving along a wall.
There has been a dilemma within the game ever since it was first defined
nearly 60 years ago—a collection of situations where it was believed that
there was no place for which there was an optimal game play. However,
Milutinovic and his coworkers have now disproved this enduring conundrum in
a new article released in the journal IEEE Transactions on Automatic Control
and presented a new technique of analysis that demonstrates there is always
a deterministic solution to the wall pursuit game. This finding makes it
possible to solve additional problems of a similar nature in the study of
differential games and improves our ability to think about automated systems
like driverless cars.
Many different disciplines, including economics, political science,
computer science, and engineering, use game theory to explain behavior. The
Nash equilibrium is one of the most well-known ideas in game theory.
Mathematician John Nash developed the idea, which outlines the best
game-playing tactics for all participants to use in order to end the game
with the least amount of remorse. Therefore, rational players are all driven
to play their equilibrium strategy because any player who opts not to play
their game-optimal strategy will lament it more in the end.
This idea is relevant to the wall chase game, where the pursuer and evader
each have a best-case strategy pair that covers almost all of their possible
situations. There are some situations between the pursuer and the evader,
though, for which the traditional analysis is unable to produce the winning
strategies and comes to the conclusion that the conundrum exists. The study
community has long accepted the paradox as true because this collection of
locations is known as a singular surface.
Milutinovic and his co-authors, however, did not agree to this.
This concerned Milutinovic and his team because they believed that if the
evader knew there was a unique area, he or she might use it inappropriately.
We simply don't know what the implications of that would be in games that
are much more complex because the evader can compel you to go to the
singular surface where you are unsure of how to behave best.
In order to solve the issue, Milutinovic and his co-authors developed a
novel method that made use of a mathematical idea that had not yet been
invented when the wall chase game was first imagined. They were able to
discover that a game optimal solution can be found in all game conditions by
using the viscosity solution of the Hamilton-Jacobi-Isaacs equation and
adding a rate of loss analysis for solving the singular surface.
The Hamilton-Jacobi-Isaacs equation can be solved in a novel way thanks to
the 1980s invention of the mathematical idea known as the viscous solution
of partial differential equations. The idea's applicability to
problem-solving in game theory and optimum management is now widely
acknowledged.
Calculus is used to locate the derivatives of the viscous solutions, which
are functions used to handle game theory issues. When a game's related
viscosity solution has well-defined derivatives, it is comparatively simple
to locate the game's optimal solutions. The wall-pursuit game is an
exception to this, and the conundrum is brought on by the absence of clearly
specified variants.
Usually, when faced with a choice, participants will take the least
advantageous course of action and tolerate losses as a consequence of their
choice. The problem is that each reasonable participant will try to limit
any losses if there are any.
In order to determine how participants could reduce their loses, the
writers examined the Hamilton-Jacobi-Isaacs equation's viscosity solution
near the singular surface where the derivatives are ill-defined. Then they
added a rate of loss study over these singular equation surface states. They
discovered that there are clearly specified game tactics for their actions
on the single surface when each player minimizes its rate of losses.
In addition to defining the game-optimal actions for the single surface,
the authors discovered that this rate of loss reduction agrees with the
game-optimal actions in every scenario in which the classical analysis is
also capable of identifying these actions.
The game-optimal behaviors from the conventional analysis are unaffected
when we implement the rate of loss analysis elsewhere, according to
Milutinovic. There is an answer everywhere because we take the traditional
theory and add the rate of loss analysis to it. This significant finding
demonstrates that the enhancement is a fundamental advancement in game
theory rather than merely a workaround to locate a solution on the solitary
surface.
Milutinovic and his co-authors are eager to investigate additional single
surface game theory issues that could benefit from the use of their novel
methodology. The article serves as a free invitation to the study community
to investigate other conundrums in a similar manner.
The next query is, "What other conundrums can we resolve?" said
Milutinovic.
Provided by
University of California - Santa Cruz
