Multi-Agent Chance-Constrained Stochastic Shortest Path with Application to Risk-Aware Intelligent Intersection
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Autonomous VehiclesMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Dual Formulation for Chance Constrained Stochastic Shortest Path with Application to Autonomous Vehicle Behavior Planning
Autonomous vehicles face the problem of optimizing the expected performance of subsequent maneuvers while bounding the risk of collision with surrounding dynamic obstacles. These obstacles, such as agent vehicles, often …
Autonomous VehiclesA Fully Polynomial Time Approximation Scheme for Constrained MDPs and Stochastic Shortest Path under Local Transitions
The fixed-horizon constrained Markov Decision Process (C-MDP) is a well-known model for planning in stochastic environments under operating constraints. Chance-Constrained MDP (CC-MDP) is a variant that allows bounding t…
Large Language Model-Based Automatic Formulation for Stochastic Optimization Models
This paper presents an integrated systematic study of the performance of large language models (LLMs), specifically ChatGPT, for automatically formulating and solving Stochastic Optimization (SO) problems from natural la…
Stochastic OptimizationChance Constrained Stochastic Optimal Control Based on Sample Statistics With Almost Surely Probabilistic Guarantees
While techniques have been developed for chance constrained stochastic optimal control using sample disturbance data that provide a probabilistic confidence bound for chance constraint satisfaction, far less is known abo…
Collision AvoidanceChance Constrained Stochastic Optimal Control for Arbitrarily Disturbed LTI Systems Via the One-Sided Vysochanskij-Petunin Inequality
While many techniques have been developed for chance constrained stochastic optimal control with Gaussian disturbance processes, far less is known about computationally efficient methods to handle non-Gaussian processes.…
Collision AvoidanceGaussian Processes