Adaptive Highways on a Grid

The primary objective of this paper is to introduce the adaptive highways algorithm, a path planning algorithm for vehicles moving on a grid. We consider a workspace that consists of a symmetric grid and a large number of vehicles that move on the grid to accomplish a certain task. Each vehicle is assigned the task of visiting a set of randomly selected locations, which are updated over time. The dynamics of the vehicles are described by a constrained linear double-integrator model. The objective is to find, in real time, a set of trajectories that maximize the average speed of the vehicles while ensuring safety. The trajectory optimization problem is solved locally, whereas a central entity is employed for distribution of information. Safety guarantees are provided through a space reservation mechanism. Several algorithms are presented and compared in terms of performance.