  This paper presents the design of a supervisory algorithm that monitors
safety at road intersections and overrides drivers with a safe input when
necessary. The design of the supervisor consists of two parts: safety
verification and control design. Safety verification is the problem to
determine if vehicles will be able to cross the intersection without colliding
with current drivers' inputs. We translate this safety verification problem
into a jobshop scheduling problem, which minimizes the maximum lateness and
evaluates if the optimal cost is zero. The zero optimal cost corresponds to the
case in which all vehicles can cross each conflict area without collisions.
Computing the optimal cost requires solving a Mixed Integer Nonlinear
Programming (MINLP) problem due to the nonlinear second-order dynamics of the
vehicles. We therefore estimate this optimal cost by formulating two related
Mixed Integer Linear Programming (MILP) problems that assume simpler vehicle
dynamics. We prove that these two MILP problems yield lower and upper bounds of
the optimal cost. We also quantify the worst case approximation errors of these
MILP problems. We design the supervisor to override the vehicles with a safe
control input if the MILP problem that computes the upper bound yields a
positive optimal cost. We theoretically demonstrate that the supervisor keeps
the intersection safe and is non-blocking. Computer simulations further
validate that the algorithms can run in real time for problems of realistic
size.
