# Multi-Agent Chance-Constrained Stochastic Shortest Path with Application to Risk-Aware Intelligent Intersection

arXiv: https://arxiv.org/abs/2210.01766 · HTML: https://mlsanity.com/paper/2210.01766/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 51 references that are in the map.
- First posted on arXiv 3 Oct 2022.

## Builds on (most cited first, 11 of 11)

- [CARLA: An Open Urban Driving Simulator](https://mlsanity.com/paper/1711.03938/) (2017)
- [TrafficPredict: Trajectory Prediction for Heterogeneous Traffic-Agents](https://mlsanity.com/paper/1811.02146/) (2018)
- [Continuous-Time Gaussian Process Motion Planning via Probabilistic Inference](https://mlsanity.com/paper/1707.07383/) (2017)
- [Crocoddyl: An Efficient and Versatile Framework for Multi-Contact Optimal Control](https://mlsanity.com/paper/1909.04947/) (2019)
- [On the Complexity of Solving Markov Decision Problems](https://mlsanity.com/paper/1302.4971/) (2013)
- [Uncertainty-Aware Driver Trajectory Prediction at Urban Intersections](https://mlsanity.com/paper/1901.05105/) (2019)
- [GamePlan: Game-Theoretic Multi-Agent Planning with Human Drivers at Intersections, Roundabouts, and Merging](https://mlsanity.com/paper/2109.01896/) (2021)
- [Provably Safe Robot Navigation with Obstacle Uncertainty](https://mlsanity.com/paper/1705.10907/) (2017)
- [Online Risk-Bounded Motion Planning for Autonomous Vehicles in Dynamic Environments](https://mlsanity.com/paper/1904.02341/) (2019)
- [Solving Transition-Independent Multi-agent MDPs with Sparse Interactions (Extended version)](https://mlsanity.com/paper/1511.09047/) (2015)
- [Semi-autonomous Intersection Collision Avoidance through Job-shop Scheduling](https://mlsanity.com/paper/1510.07026/) (2015)

## Built on by (most cited first, 1 of 1)

- [Scaling Team Coordination on Graphs with Reinforcement Learning](https://mlsanity.com/paper/2403.05787/) (2024)

## Abstract (arXiv)

In transportation networks, where traffic lights have traditionally been used for vehicle coordination, intersections act as natural bottlenecks. A formidable challenge for existing automated intersections lies in detecting and reasoning about uncertainty from the operating environment and human-driven vehicles. In this paper, we propose a risk-aware intelligent intersection system for autonomous vehicles (AVs) as well as human-driven vehicles (HVs). We cast the problem as a novel class of Multi-agent Chance-Constrained Stochastic Shortest Path (MCC-SSP) problems and devise an exact Integer Linear Programming (ILP) formulation that is scalable in the number of agents' interaction points (e.g., potential collision points at the intersection). In particular, when the number of agents within an interaction point is small, which is often the case in intersections, the ILP has a polynomial number of variables and constraints. To further improve the running time performance, we show that the collision risk computation can be performed offline. Additionally, a trajectory optimization workflow is provided to generate risk-aware trajectories for any given intersection. The proposed framework is implemented in CARLA simulator and evaluated under a fully autonomous intersection with AVs only as well as in a hybrid setup with a signalized intersection for HVs and an intelligent scheme for AVs. As verified via simulations, the featured approach improves intersection's efficiency by up to 200% while also conforming to the specified tunable risk threshold.