(Press-News.org) To understand how driverless vehicles can navigate the complexities of the road, researchers often use game theory — mathematical models representing the way rational agents behave strategically to meet their goals.
Dejan Milutinovic, professor of electrical and computer engineering at UC Santa Cruz, has long worked with colleagues on the complex subset of game theory called differential games, which have to do with game players in motion. 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. But now, Milutinovic and his colleagues have proved in a new paper published in the journal IEEE Transactions on Automatic Control that this long-standing dilemma does not actually exist, and 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 that exist within the field of differential games, and enables better reasoning about autonomous systems such as driverless vehicles.
Game theory is used to reason about behavior across a wide range of fields, such as economics, political science, computer science and engineering. Within game theory, the Nash equilibrium is one of the most commonly recognized concepts. The concept was introduced by mathematician John Nash and it defines game optimal strategies for all players in the game to finish the game with the least regret. Any player who chooses not to play their game optimal strategy will end up with more regret, therefore, rational players are all motivated to play their equilibrium strategy.
This concept applies to the wall pursuit game — a classical Nash equilibrium strategy pair for the two players, the pursuer and 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 came up with a new way to approach the problem, using a mathematical concept that was not in existence when the wall pursuit game was originally conceived. By using the viscosity solution of the Hamilton–Jacobi–Isaacs equation and introducing a rate of loss analysis for solving the singular surface they were able to find that a game optimal solution can be determined in all circumstances of the game and resolve the dilemma.
The viscosity solution of partial differential equations is a mathematical concept that was non-existent until the 1980s and offers a unique line of reasoning about the solution of the Hamilton-Jacobi-Isaacs equation. It is now well known that the concept is relevant for reasoning about optimal control and game theory problems.
Using viscosity solutions, which are functions, to solve game theory problems involves using calculus to find the derivatives of these functions. It is relatively easy to find game optimal solutions when the viscosity solution associated with a game has well-defined derivatives. This is not the case for the wall-pursuit game, and this lack of well-defined derivatives creates the dilemma.
Typically when a dilemma exists, a practical approach is that players randomly choose one of possible actions and accept losses resulting from these decisions. But here lies the catch: if there is a loss, each rational player will want 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 found that not only does this rate of loss minimization define the game optimal actions for the singular surface, but it is also in agreement with the game optimal actions in every possible state where the classical analysis is also able to 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 said. “We take the classical theory and we augment it with the rate of loss analysis, so a solution exists everywhere. This is an important result showing that the augmentation is not just a fix to find a solution on the singular surface, but a fundamental contribution to game theory.
Milutinovic and his coauthors are interested in exploring other game theory problems with singular surfaces where their new method could be applied. The paper is also an open call to the research community to similarly examine other dilemmas.
“Now the question is, what kind of other dilemmas can we solve?” Milutinovic said.
Researcher solves nearly 60-year-old game theory dilemma
ELSE PRESS RELEASES FROM THIS DATE:
Mediterranean diet cuts women’s cardiovascular disease and death risk by nearly 25%
Sticking closely to a Mediterranean diet cuts a woman’s risks of cardiovascular disease and death by nearly 25%, finds a pooled data analysis of the available evidence—the first of its kind—published online in the journal Heart. The findings prompt the researchers to call for more sex specific research to guide clinical practice in heart health. Cardiovascular disease accounts for more than a third of all deaths in women around the world. While a healthy diet is a key plank of prevention, most relevant clinical trials have included relatively few women or haven’t reported the results by sex, say the researchers. And current guidelines ...
High blood caffeine level might curb amount of body fat and type 2 diabetes risk
A high blood caffeine level might curb the amount of body fat a person carries and their risk of type 2 diabetes, suggests research published in the open access journal BMJ Medicine. In light of their findings, the potential role of calorie free caffeinated drinks for lowering the risks of obesity and type 2 diabetes is probably now worth exploring, say the researchers. Previously published research indicates that drinking 3-5 daily cups of coffee, a rich source of caffeine, is associated with a lower risk ...
TikTok health information videos on Mpox often inaccurate and of poor quality
Health information on M(onkey)pox, posted on the social media platform TikTok, is often inaccurate, incomplete, and of poor quality, finds a recent analysis of relevant videos, published in the open access journal BMJ Global Health. The findings highlight the potential risks of using social media for health information, particularly during public health emergencies, warn the researchers. Mpox, formerly called monkeypox, usually describes fever, swollen lymph glands (lymphadenopathy), and painful skin pustules all over the body ...
Altered “neuronal avalanches” in brains of epilepsy patients tied to cognitive performance
New research by the Human Brain Project has found that in the brains of patients with epilepsy, changes in large scale neuronal activations can be detected in the brain’s resting state activity, even when no seizure is ongoing. The non-invasive approach could lead to a new method to aid epilepsy diagnostics. Diagnosing epilepsy can be problematic for patients, who sometimes have to wear helmets and electrodes for prolonged periods of time waiting for an epileptic episode to happen, so that the clinicians can document it with EEG. Alternatively, the seizure is artificially induced, causing discomfort. The new ...
Neolithic ceramics reveal dairy processing from milk of multiple species
A new study has found evidence of cheesemaking, using milk from multiple animals in Late Neolithic Poland. The research suggests that early farmers reduced the lactose content in milk by making it into cheese or other dairy products like yoghurt, and used dairy products from a number of different animals, such as cows, sheep or goats. Lactose intolerance was a common condition in almost everyone in Europe during the Neolithic and until the Late Bronze Age when the genetic mutation became widespread, enabling adults to produce lactase, the enzyme which breaks down lactose in the body. Researchers looked at the practice of dairy processing ...
Community health workers can help protect pregnant women and their babies from malaria
Community health workers can make a great difference in increasing the number of pregnant women who receive life-saving preventive antimalarial treatment, according to a study conducted in four sub-Saharan African countries and led by the Barcelona Institute for Global Health (ISGlobal), an institution supported by “la Caixa” Foundation. The findings, published in The Lancet Global Health, will help to guide malaria control strategies in pregnant women and improve maternal and infant health in malaria-endemic ...
Robots can help improve mental wellbeing at work – as long as they look right
Robots can be useful as mental wellbeing coaches in the workplace – but perception of their effectiveness depends in large part on what the robot looks like. Researchers from the University of Cambridge carried out a study in a tech consultancy firm using two different robot wellbeing coaches, where 26 employees participated in weekly robot-led wellbeing sessions for four weeks. Although the robots had identical voices, facial expressions, and scripts for the sessions, the robots’ physical appearance affected how participants interacted with it. Participants who did their wellbeing exercises with a toy-like robot said that they felt more of a connection ...
Knowing your ants from your anteaters: are wildlife documentaries showing us the ‘real’ natural world?
Wildlife documentaries miss an opportunity to highlight the diversity of nature by focusing too much on mammals and birds, according to a new study. In a new study published in People and Nature, researchers from the University of Cambridge have shown that while the production of wildlife documentaries has exploded over recent decades, they portray a biased view of the natural world around us. Our natural world is under threat, from habitat and biodiversity loss, to high extinction rates. At the same time, there is a growing disconnect between people and nature, with children’s opportunities to experience the natural world diminishing. Now more ...
Propeller advance paves way for quiet, efficient electric aviation
Electrification is seen as having an important role to play in the fossil-free aviation of tomorrow. But electric aviation is battling a trade-off dilemma: the more energy-efficient an electric aircraft is, the noisier it gets. Now, researchers at Chalmers University of Technology, Sweden, have developed a propeller design optimisation method that paves the way for quiet, efficient electric aviation. In recent years, electrification has been described as having an important role in reducing emissions from future aviation. Due to the challenges posed by longer ranges, interest is chiefly focused on electric propeller planes covering shorter distances. Propellers connected to ...
People of color have been largely underrepresented among authors published in the American Journal of Archaeology
A new demographic survey of authorship in the American Journal of Archaeology (AJA) reveals that people of color have been largely underrepresented among the scholars published in the journal. The results of the survey, which also found that authors who are the children of people without advanced degrees were also underrepresented in the journal’s pages, are published in the paper “Demographic Dynamics of Publishing in the American Journal of Archaeology.” The study was conducted ...