Scheduling autonomous vehicle platoons through an unregulated intersection

DOI10.4230/OASICS.ATMOS.2016.5MaRDI QIDQ5240224zbMATH OpenOpenAlexFDO

Authors Vial Juan José Besa, William E. Devanny, David Eppstein, Michael T. Goodrich

Publication date 24 October 2019

Full work available at URL https://arxiv.org/abs/1609.04512

zbMATH Keywords

autonomous vehiclesplatoonsscheduling

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Traffic problems in operations research (90B20) Deterministic scheduling theory in operations research (90B35)

Abstract: We study various versions of the problem of scheduling platoons of autonomous vehicles through an unregulated intersection, where an algorithm must schedule which platoons should wait so that others can go through, so as to minimize the maximum delay for any vehicle. We provide polynomial-time algorithms for constructing such schedules for a $k$-way merge intersection, for constant $k$, and for a crossing intersection involving two-way traffic. We also show that the more general problem of scheduling autonomous platoons through an intersection that includes both a $k$-way merge, for non-constant $k$, and a crossing of two-way traffic is NP-complete.

Recommendations

• On the complexity of an unregulated traffic crossing
• Contention-resolving model predictive control for an intelligent intersection traffic model
• A repeated route-then-schedule approach to coordinated vehicle platooning: algorithms, valid inequalities and computation
• Efficient algorithms for collision avoidance at intersections
• Semi-autonomous intersection collision avoidance through job-shop scheduling

Cites work

• A traveller's problem
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• On the complexity of an unregulated traffic crossing
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation

Cited in

(7)

• Contention-resolving model predictive control for an intelligent intersection traffic model
• An autonomous vehicle sequencing problem at intersections: a genetic algorithm approach
• Least Restrictive Supervisors for Intersection Collision Avoidance: A Scheduling Approach
• Semi-autonomous intersection collision avoidance through job-shop scheduling
• On the complexity of an unregulated traffic crossing
• A repeated route-then-schedule approach to coordinated vehicle platooning: algorithms, valid inequalities and computation
• Modular circulation and applications to traffic management

This page was built for publication: Scheduling autonomous vehicle platoons through an unregulated intersection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5240224)