Motion planning for multiple robots with multi-mode operations via disjunctive graphs

Abstract

SUMMARY A new approach to motion planning for multiple robots with multi-mode operations is proposed in this paper. Although sharing a common workspace, the robots are assumed to perform periodical tasks independently. The goal is to schedule the motion trajectories of the robots so as to avoid collisions among them. Rather than assigning the robots with different priorities and planning safe motion for only one robot at a time, as is done in most previous studies, an efficient method is developed that can simultaneously generate collision-free motions for the robots with or without priority assignment. Being regarded as a type of job-shop scheduling, the problem is reduced to that of finding a minimaximal path in a disjunctive graph and solved by an extension of the Balas algorithm. The superiority of this approach is demonstrated with various robot operation requirements, including “non-priority”, “with-priority”, and “multicycle” operation modes. Some techniques for speeding up the scheduling process are also presented. The planning results can be described by Gantt charts and executed by a simple “stop-and-go” control scheme. Simulation results on different robot operation modes are also presented to show the feasibility of the proposed approach.