Roozbehani, HajirD'Andrea, Raffaello2013-02-272013-02-272013-02-27201110.1007/978-3-642-19457-3_39https://infoscience.epfl.ch/handle/20.500.14299/89837WOS:000309893200039The 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.text::conference output::conference proceedings::conference paper