Scheduling Autonomous Vehicle Platoons Through An Intersection

Stephen Valenta, Tufts University COMP 150- Special Topics in Algorithms, Summer 2018

Background

While autonomous vehicles will share the road with human drivers for the foreseeable future, once the road transitions fully to computer drivers, new possibilities will emerge for solving transit problems. A prime example of this is intersection design. The current convention is to block out approximately 30 to 90 seconds during which only cars on certain lanes are allowed to cross. But this approach can be inefficient. We all know the feeling of sitting at a completely empty intersection waiting for an eternal red light to change. In an autonomous future, the intersection computer could know of all approaching vehicles and could stop or allow each to cross in the most efficient order possible. Such complex decisions will require efficient algorithms.

A 2016 paper by Juan José Besa Vial, William E. Devanny, David Eppstein, and Michael T. Goodrich of U.C. Irvine discusses algorithms that can determine the most efficient schedule (i.e. order) for platoons (one or more vehicle travelling as a close group) approaching from different directions to cross an intersection.

Their goal is to find the order that results in the smallest maximum vehicle delay. Previous related work had focused on minimizing the total number of stops or total delay of all vehicles. The authors do not explain why they chose this goal, but they might wish for all platoons to be satisfied with the delay they experience.

The authors model each platoon on each lane by defining a time that it will begin to cross the intersection if it is not delayed ("release time") and the time that it will finish crossing the intersection ("end time"). The length of the platoon is the difference between the release time and the end time. Also, the delay of a platoon is the difference between the release time of a platoon and the time it actually begins to cross.

To further limit the difficulty of the problem, the authors specify that platoons cannot be broken up and that platoons cannot travel backwards. Finally, they only consider one intersection at a time, not interactions between multiple intersections.

Paper: Scheduling Autonomous Vehicle Platoons Through an Unregulated Intersection

Illustration of Intersection Model


Illustrations source: Vial et al. paper pages 4 & 6.

The Algorithm

The paper’s authors consider several situations: where two lanes merge, where a constant number k lanes merge, and a more complicated scenario involving crossing traffic plus the merge of an arbitrary number of lanes.

For a two-way merge, they find that a simple greedy algorithm can be used. For the crossing with an arbitrary number of merges, the problem is NP-hard. However, for a k-way merge where k is constant, a solution can be found in polynomial time. I implement this algorithm, which is described in section 3.3 of the paper.

Further, the paper’s authors show in section 3.1 that each optimization algorithm can be derived from a decision algorithm using a parametric search technique from Megiddo. I will focus on the decision algorithm portion, which answers whether or not a schedule exists whereby all platoons can cross the intersection without any platoons being delayed by more than some amount (parameter d).

For this k-way (constant k) decision algorithm, we model the intersection as a series of states. In each state, some number of platoons from each lane has crossed and some number has not yet crossed. For simplicity, no platoons have partially crossed the intersection. We then determine for each state the earliest time that we could reach that state (td(s)). If we cannot reach the state without incurring more than delay of d, then the td(s) of that state is returned as infinite.

Since the time to reach each state relies on the time to reach the states immediately preceding it, the td(s) of each proceeding state is a subproblem, and we can use dynamic programming to find the td(s) of each state. That is, we start with the td(s) of earliest state (where no platoons have crossed) and then allow platoons from each lane to cross one by one in order to find the td(s) of each successor state.

The algorithm functions as follows: for each state s, we find all of its proceeding states si...sk by simply reversing the crossing of a platoon from each lane k, one by one. As such, the number of proceeding states is equal to or less than the number of lanes. For each proceeding state si, we look up td(si) in our dynamic programming table, and then see what the td(s) of our current state would be if we used that proceeding state and allowed the platoon from that lane to cross to bring us to the current state.

Another way to state this it is that each of the most recent platoons to arrives in current state s crossed at the maximum of its original release time and the td(si) of preceeding state si. We then calculate the delay of that platoon by comparing its crossing time to its original release time. Using this approach, we can report whether or not it is possible to reach state s without incurring delay of d. Further, we can calculate td(s) by choosing the preceding state that results in us reaching state s as soon as possible.

We loop through each state until we reach the final state in which all platoons have crossed. There are O(nk) states and finding the td(s) of each state takes constant time, so the algorithm takes O(nk) time in total.

Recap of Definitions

Platoon: A group of autonomous vehicles travelling in close proximity down a single lane.

Platoon release time: The time at which a platoon will reach and start crossing the intersection (if it is not delayed).

Platoon end time: The time at which a platoon will finish crossing the intersection (if it is not delayed).

Platoon length: The difference between the release time and start time of a platoon.

Platoon delay: The difference between the release time of a platoon and its actual cross time from a given schedule.

Schedule: Some order of platoon crossings. e.g. "Platoon 1 from lane 3 crosses at time of 2, platoon 2 from lane 3 crosses at time of 4, etc."

d: The maximum delay (for any single platoon) that we will tolerate in a schedule.

s: A state of the intersection where some number of platoons from each lane have crossed and some have not.

td(s): The minimum time required to reach state s.

My Implementation of the Algorithm

One of my key challenges was choosing an appropriate way to represent and then loop through states. In my previous study of an AI logistics planning problem, states were represented as a nodes on a planning graph. Each node contained complex information about the state as well as which actions were valid to take in that state.

However, in this autonomous intersection problem, I realized that states can be represented much more concisely: the definition of a state is simply the number of platoons from each lane that have crossed the intersection. The only action to transition from one state to the next is to cross one platoon from one lane. Therefore, we can loop through all states by nesting k for loops, where k is the number of lanes and the length of each loop is the number of platoons in that lane +1 (for state where 0 have crossed).

With three lanes, the time to loop through all states in this way is (i+1) * (j+1) * (m+1), where i, j, and m are the number of platoons in each lane. The total time to loop through all states is O(nk), where n is the total number of platoons and k is the number of lanes. (Note: in my code at the bottom of this page, I call the platoon variables i , j, and k, rather than i , j, and m. This k should not be confused with the number of lanes k).

One limitation of my implementation is that the number of lanes is hard-coded to be three. Allowing the code to handle additional lanes could be an extension in the future.

Demo Instructions

The demo can be run with the default of 3 platoons in each of the 3 lanes (total of 9 platoons). To change the number of platoons in each lane, enter numbers in the boxes below and hit submit.

The release time and length of each platoon is randomly generated and listed below in the Lane Details section.

After hitting the Run Demo button, the State Summary will show the algorithm looping through each state. Once this is complete, after a brief pause, the State Summary will illustrate the optimal order of platoon crossings.

For best results, please refresh the page before re-running the demo.

Input Parameters

Please enter an integer vale for d (max delay):

Please enter an integer vale for number of platoons in lane #1:

Please enter an integer vale for number of platoons in lane #2:

Please enter an integer vale for number of platoons in lane #3:

Uncrossed - Crossed

State Summary

Demo status:

Maximum acceptable delay d: N/A

Current step #: 0

Lane 1- number of platoons crossed: 0 of

Lane 2- number of platoons crossed : 0 of

Lane 3- number of platoons crossed: 0 of

Min. time to reach state without delay of d: N/A

Optimal last lane to cross: N/A

Lane Details

The total number of platoons n is NULL. The number of lanes k is 3. So, nk is NULL.

The number of states is O(nk). The actual number of states for this n and k is: (NULL + 1) * (NULL + 1) * (NULL + 1) = NULL

Lane #1 (NULL platoons):

Lane #2 (NULL platoons):

Lane #3 (NULL platoons):

D3 Resources

Core Scheduling Algorithm