A Feasible Collision Detection Algorithm for Mobile Robot Motion Planning with Moving Obstacles

A new approach to solving the collision detection problem for mobile robots in the presence of moving obstacles is proposed. Both the robot and obstacles in the two-dimensional space are assumed to be polygonal and are composed of a set of convex polygons. Each convex polygon is then represented using half-planes. The half-plane representation uses an algebraic method to describe the object motion including translation and rotation through time. Compared with previous methods, the proposed representation is more general in that obstacles are now allowed to move at nonconstant velocities. To detect collision between polygonal objects, a traversability vector method was developed. Traversability vectors are a simple mechanism used to analyze geometric constraints imposed by polygons. Using these vectors, a simple algorithm for predicting collision is derived. Computer simulations were conducted to show the feasibility of the proposed method.