On-Line Collision Avoidance for Multiple Robots Using B-Splines

Real world assembly sequences consists of multiple assembly steps, many of which can be performed in parallel. In practice this parallelism is often not exploited because of the complexity involved in avoiding collisions between all of the robots. In this paper we describe a simplified method of achieving smooth collision free paths for multiple robots within a single assembly workcell. Our method is simple because we exploit properties of B-splines to reduce the problem to path planning without moving robots. We develop a path planner to compute an initial linear path. Using that path as input, a trajectory generation tool creates a collision free path of any desired continuity. We exploit three properties of B-splines: (i) continuity for smooth paths, (ii) convex-hull for collision avoidance, and (iii) locality for dynamic course alteration without loss of continuity. In addition, our system runs in real-time, easily accommodating multiple robots. Finally, we describe a user level visualization tool for this system.
On-line Collision Avoidance for Multiple Robots Using B-Splines
Eric Paulos
(8 Pages PostScript)

Eric Paulos / paulos@robotics.eecs.berkeley.edu / 12 Sept 1994