An approach for collaborative path planning in multi-robot systems

This paper presents a reactive algorithm for multi-robot cooperative path planning. The algorithm integrates the real-time collision detection process with linear navigation functions. The collision detection strategy is based on an improved version of the swept volumes method that uses the relative kinematics of the robots in addition to the geometric considerations of the paths. The swept volumes determine the collision conditions, which are written in terms of the relative velocities and orientations. Speed and orientation collision intervals are then derived based on the swept volumes. A collision histogram is then constructed as a collection of the speed and orientation collision intervals. The collision histograms show the free directions and the direction corresponding to collision. The desired orientation and speed are chosen using the collision histograms. The strategy is illustrated using an extensive simulation study.