Key points are not available for this paper at this time.
We present an algorithm that solves the following motion- planning problem that arises in robotics: Given several two-dimensional circular bodies B 1 , B 2 , ..., and a region bounded by a collection of "walls, " either find a continuous motion connecting two given configurations of these bodies during which they avoid collision with the walls and with each other, or else establish that no such motion exists. This paper continues other studies by the authors on motion- planning algorithms for other kinds of moving objects. The algorithms presented are polynomial in the number of walls for each fixed number of moving circles (for two moving circles the algorithm is shown to run in time O(n 3 ) if n is the number of walls), but with exponents increasing with the number of moving circles.
Schwartz et al. (Thu,) studied this question.