Institute of Transportation Studies at UC Berkeley

Multi-vehicle systems are naturally encountered in civil and military applications. Cooperation amongst individual "miniaturized" vehicles allows for flexibility to accomplish missions that a single large vehicle may not readily be able to accomplish. While accomplishing a mission, motion planning algorithms are required to efficiently utilize a common resource (such as the total fuel in the collection of vehicles) or to penalize a collective cost function (such as to minimize the maximum time taken by the vehicles to reach their intended target). The objective of this paper is to present a constant factor approximation algorithm for planning the path of each vehicle in a collection of vehicles, where the motion of each vehicle must satisfy non-holonomic constraints.