A Finite State Approach to Vehicle Merging

Abstract

A state space approach is taken to vehicle merging on high speed highways. The vehicles are assumed to be traveling in equal sized “slots” which move at the group velocity. At points where two or more lanes merge, some vehicles must be moved forward or backward to other slots to accomplish the merge. The state of a group of vehicles to be merged is defined in terms of the slots occupied at any time. A finite set of admissible terminal states, representing possible merged configurations, is easily determined. The sequence of moves required to obtain a merge is found as a shortest path in the space of all states, running from the initial state to the terminal manifold. Various costs may be applied to moves in this space, such as time consumed, or number of vehicles being moved simultaneously. Costs may also be assigned to the terminal arrangements, reflecting, for example, the size of platoons in the resulting merge. Estimates are made of required computing load and the method is compared with other approaches.