Coordinated motion planning for two independent robots

Abstract

We present an Ο(n2) algorithm for planning a coordinated collision-free motion of two independent robot systems of certain kinds, each having two degrees of freedom, which move in the plane amidst polygonal obstacles having a total of n corners. We exemplify our technique in the case of two “planar Stanford arms”, but also discuss the case of two discs or convex translating objects. The algorithm improves previous algorithms for this kind of problems, and can be extended to a fairly simple general technique for obtaining efficient coordinated motion planning algorithms.