A recursive algorithm of obstacles clustering for reducing complexity of collision detection in 2D environment

Abstract

In applications of industrial robots, the robot manipulator must traverse a pre-specified Cartesian curve (path) with its hand tip while links of the robot safely move among obstacles. In order to reduce the costs of collision detection, the number of collision checks can be reduced by enclosing a few obstacles (a cluster) with a larger (artificial) bounding volume, e.g. by their convex hull, without cutting the specified curve. In the paper, an efficient and convergent recursive algorithm for refining an initial randomly generated set of clusters is proposed to tackle the problem of clustering convex polygonal obstacles in a 2D robot's scene. Simulation results show that the proposed algorithm acquires less number of clusters and computationally more efficient. In addition, the algorithm can be easily applied to dynamic environment based on the idea of seeds in clusters.