I have another new arXiv preprint: "Scheduling Autonomous Vehicle Platoons Through an Unregulated Intersection", arXiv:1609.04512, with Juan Besa, Will Devanny, and Mike Goodrich. The same paper also appeared at ATMOS 2016; the two versions differ only in formatting and their theorem numbering scheme.

The paper is on how to direct vehicle traffic through a road intersection while minimizing the longest waiting time. We assume that the traffic comes in variable-length platoons, and that we shouldn't try to break up these platoons. We also assume (perhaps less reasonably) that we know about all of the traffic that will cross the intersection in advance. This turns out to be susceptible to dynamic programming, but for a different optimization criterion: minimize the completion time of a given prefix of the schedule, subject to a fixed limit on the waiting time. But then, using the magic of parametric search we can turn this algorithm for the wrong criterion into one for the right criterion.

Some of the time bounds, although polynomial, have high exponents, and we didn't succeed in handling some common types of intersections. For instance, there's one that I walk through most days, which at times of light traffic is a four-way stop and at other times has a human traffic director (one of the student jobs on my campus). In the more major of the two roads that cross there, each direction has a through lane and a separate left turn pocket. On the other road, each direction only has one lane, which combines cross traffic and left-turning traffic. Here's a screenshot from Google Earth; the building at the top is the one I work in, and at the bottom is the edge of the housing complex I live in.

Overhead view of East Peltason Dr and Los Trancos Dr, Irvine, California, from Google Earth

The difficulty is that, for this type of intersection, one can direct traffic in such a way that there is no "synchronization point" when nobody is crossing the intersection, for instance by allowing through traffic in both directions on the main road interleaved with phases where one of those two directions has both through traffic and left-turning traffic. Our dynamic programming algorithm relies on these synchronization points. And of course it would be a better fit to the real-world problem to allow the input to be online instead of known in advance. So I think there's still a lot more to do on these problems.

(G+)