Hierarchical Game-Based Multi-Agent Decision-Making for Autonomous Vehicles

Mushuang Liu, Yan Wan, Frank Lewis, Subramanya Nageshrao, H. Eric Tseng, Dimitar Filev · 2025

Read Hierarchical Game-Based Multi-Agent Decision-Making for Autonomous Vehicles by Mushuang Liu, Yan Wan, Frank Lewis, Subramanya Nageshrao, H. Eric Tseng, Dimitar Filev (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-21941.txt.

Introduction

Mushuang Liu and co-authors build a game based decision system in 2025 for self driving cars in mixed traffic. A lone car must plan around other cars, human drivers, cyclists, and people on foot, and treating all of them as full game players is costly. Pairwise games are cheaper but can make the car wait and yield too much.

Their layered game first draws a graph of which nearby agents truly interact with the ego car. Only a picked few become game players, cutting computing cost while keeping joint planning. A refined form splits that game into sub games to cut cost further. Safety and efficiency are analyzed for both forms. Simulations of crossing an intersection test the design, showing a path to firmer decisions in crowded scenes.

Catalog record

CREATORMushuang Liu, Yan Wan, Frank Lewis, Subramanya Nageshrao, H. Eric Tseng, Dimitar Filev
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-21941

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Hierarchical Game-Based Multi-Agent Decision-Making for Autonomous Vehicles Mushuang Liu, Yan Wan, Frank Lewis, Subramanya Nageshrao, H. Eric Tseng, Dimitar Filev Abstract This paper develops a game-theoretic decision-making framework for autonomous driving in multi-agent scenarios. A novel hierarchical game -based decision framework is developed for the ego vehicle. This framework features an interaction graph, which characterizes the interaction relationships between the ego and its surrounding traffic agents (including AVs, human driven vehicles, pedestrians, and bicycles, and others), and enables the ego to smartly select a limited number of agents as its game players. Compared to the standard multi-player games, where all surrounding agents are considered as game players, the hierarchical game significantly reduces the computational complexity. In addition, compared to pairwise games, the most popular approach in the literature, the hierarchical game promises more efficient decisions for the ego (in terms of less unnecessary waiting and yielding). To further reduce the computational cost, we then propose an improved hierarchical game, which decomposes the hierarchical game into a set of sub-games. Decision safety and efficiency are analyzed in both hierarchical games. Comprehensive simulation studies are conducted to verify the effectiveness of the proposed frameworks, with an intersection-crossing scenario as a case study. I Introduction Autonomous vehicles (AVs) are expected to produce significant societal benefits, such as reduced accidents, reduced energy consumption, enhanced ride comfort, improved travel efficiency, and improved equity for children, elderly and disables [ 1 , 2 ] . One of the biggest technical challenges in autonomous driving is the design of decision-making algorithms to generate safe and efficient decisions for AVs in diverse traffic scenarios [ 3 , 4 , 5 ] . Such designs for the ego vehicle must take into consideration the interactions between the ego and other traffic agents, including AVs, human driven vehicles, pedestrians, and bicycles, and others [ 6 , 7 , 8 ] . These interactions can be heterogeneous (i.e., agents affect the ego in different ways), time-varying (i.e., the interactions change with the motion of agents), and highly correlated (i.e., the interaction between one agent pair may affect the interactions between other agent pairs). The game-theoretic approaches have recently been developed as the mathematical framework to capture the interactions among traffic agents for the decision-making of AVs [ 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 ] . In a game theoretic formulation, each agent aims to optimize its own payoff/interest, which is mutually affected by other agents’ actions. Of our interest, paper [ 9 ] formulates a two-player non-zero-sum game to model the merging-giveaway interaction between a through vehicle and a merging vehicle. To capture the vehicles’ interactions in lane-changing scenarios, a two-player Stackelberg game and a two-player normal-form game were developed, respectively, in papers [ 11 , 16 ] . To address the intersection-crossing problems in uncontrolled intersections, a leader-follower game was designed in paper [ 10 ] . To model autonomous racing between two vehicles, paper [ 12 ] investigated and compared two non-cooperative games including the Nash equilibrium game and the Stackelberg game. To deal with the coordination of vehicles on highways, a mixed-integer potential game was developed in paper [ 13 ] . Although the above game-theoretic approaches provide us promising solutions in modeling the interactions among agents, they are computationally intensive with the increase of the number of agents. As such, most of the existing game-theoretic studies focus on the two-agent scenarios only. To generalize the two-agent games to multi-agent scenarios, pairwise games have been recently developed [ 16 , 11 ] . In pairwise games, the ego plays a two-player game with each of its surrounding agents and selects the most conservative decision from the game outcomes as its final decision. Although pairwise game is computationally scalable, it ignores the interaction correlations between different agent pairs. To be more specific, pairwise games assume that the ego is affected by each of its surrounding agents independently. However, this is usually not true because the surrounding agents also have interactions among themselves, and they often act as a coherent whole to the ego. In pairwise games, the ”local” interaction between the ego and one surrounding agent is captured, while the ”global” interaction among multiple agents is ignored. To take into account multi-agent interactions while remaining the tractability of the solution, we propose a novel hierarchical game framework in this paper. This framework features a game player selection step based on an interaction graph that captures the interactions among agents. With this hierarchical game, the ego is able to select a subset of agents as game players such that the number of players are limited while the important interaction information is also captured. Compared to pairwise games, the proposed hierarchical game is able to generate more efficient decisions for the ego (in terms of less unnecessary waiting or yielding), while guaranteeing the decision safety. This paper is organized as follows. Section II briefly reviews a two-agent game-theoretic framework developed in [ 17 ] , which serves as a basis in this paper. Section III introduces the novel hierarchical game that generalizes from the two-agent scenarios to multi-agent scenarios. An improved hierarchical game approach is also proposed in this section to further reduce the computational complexity. Section IV designs game payoffs in the proposed games. Section V shows simulation studies, and Section VI concludes the paper. II Preliminaries and Review of Two-Agent Game-Theoretic Decision-Making Framework In this section, we first briefly review our prior work on the game-theoretic decision-making framework for two agents [ 17 ] . This framework serves as a basis for the development in this paper. The normal-form games are also reviewed in this section to facilitate the analysis in this paper. II-A Decision-making framework in two-agent scenarios A three-level decision-making framework (shown in Figure 1 ) was proposed in [ 17 ] to generate safe and efficient decisions for the ego when it interacts with one other agent. Here is a brief description of each level. The first level is an action space filter, which determines the action space of the ego and filters out the actions that violate ”hard” traffic rules, e.g., driving through a red traffic light. The second level is a normal-form game based decision-making, where the Nash solution is generated. The third level is a final safety check to prevent an unsafe action from being implemented. To better illustrate the role of each level, let us consider the intersection-crossing scenario as a case study. Figure 1: Three-level decision-making framework Consider a four-way stop sign intersection shown in Figure 2 . The ego is labeled with the number ”1” and aims to go straight. Meanwhile, the vehicle 2 is also approaching the intersection and aims to cross it. The action space for the two vehicles is A_{i}=\{\text{yield, go}\} for i=1,2 . To generate appropriate decisions, the ego needs to consider 1) the rules associated with the stop sign, and 2) the interactions with vehicle 2. Using the three-level framework in Figure 1 , the ego determines its action space in the first level by considering the hard rule that all vehicles must come to a complete stop before they cross the stop sign.

Read the complete text