New GAMEOPT framework will help future autonomous vehicles safely navigate unsignalized intersections

Intersections without traffic signals are the sites of 40% of all crashes, 50% of serious collisions, and 20% of fatalities. When motorists approach these intersections, which often have “four-way” stop signs, and feature “unprotected” left turns, they must make choices. If two vehicles approach at approximately the same time, or a driver decides not to stop or wait their turn, safety is at issue.

In the future, autonomous vehicles equipped with vehicle-to-infrastructure (V2I) communication may be able to provide solutions for handling these scenarios. Such vehicles, called connected autonomous vehicles (CAVs), will be able to provide multiple sensing and actuation points in the trafﬁc ﬂow.

ISR faculty and students are developing new algorithms that will enable CAVs to handle these scenarios. They have previously successfully demonstrated CAV algorithms that can help smooth highway merging and trafﬁc shock wave situations.

A new paper introduces algorithms focused on the unsignaled intersection problem. GAMEOPT: Optimal Real-time Multi-Agent Planning and Control for Dynamic Intersections was written by Distinguished University Professor John Baras (ECE/ISR) and his Ph.D. student Nilesh Suriyarachchi; and ISR-affiliated Distinguished University Professor Dinesh Manocha (ECE/UMIACS/ CS) and his Ph.D. student Rohan Chandra.

Recent research into leveraging cooperation among CAVs to achieve safe, fair, and efﬁcient intersection control has provided promising results with solutions from many ﬁelds, including game theory, auctions, optimization, and deep learning. While each domain has its own advantages, no single solution has been shown to be able to achieve all the four key considerations of safety, efﬁciency, fairness, and real-time operation. Here, safety involves the prevention of collisions, efﬁciency involves maximizing the capacity of the intersection, and fairness involves treating all agents equitably. Real-time computation is also essential in this scenario, as the system must react to dynamic changes in this fast-paced environment.

GAMEOPT is a novel hybrid approach to cooperative intersection control for dynamic, multi-lane, unsignalized intersections. GAMEOPT ﬁrst uses an auction mechanism to generate a priority entrance sequence for every agent, followed by an optimization-based trajectory planner that computes velocity controls that satisfy the priority sequence. This coupling operates at real-time speeds of less than 10 milliseconds in high density trafﬁc of more than 10, 000 vehicles/hr, 100× faster than other fully optimization-based methods, while providing guarantees in terms of fairness, safety, and efﬁciency. The algorithm improves throughput by at least 25%, time taken to reach the goal by 75%, and fuel consumption by 33% compared to auction-based approaches and signaled approaches using trafﬁc lights and stop signs.

The general multi-agent intersection control problem can be broadly divided into two phases. The planning phase involves the selection of the optimal entrance sequence (order in which vehicles enter the intersection) and the control phase involves generating safe trajectories for all the vehicles in order to achieve the selected sequence. The system then transmits the output target trajectories to each vehicles’ local controller for execution. Here, sequence selection can become very difﬁcult as the number of possibilities grows exponentially with the number of vehicles. This is further complicated in multilane scenarios, which should allow multiple non-conﬂicting vehicles to enter the intersection at the same time to achieve optimal throughput. Additionally, practical intersection scenarios are dynamic, which means that the number of vehicles that request to cross the intersection changes with time.

GAMEOPT is the ﬁrst hybrid planning and control algorithm for navigating unsignalized dynamic intersections by combining auctions with optimal control. The framework’s implications extend beyond intersection control to more general multi-agent systems, due to the challenging nature of dynamic mechanism design.

More information about GameOPT is available on this page.

Published March 7, 2022