Rapid formation of multi-agent based on computational geometry algorithm

This paper presents a multi-robot rapid line formation and obstacle avoidance algorithm, which is based on computational geometry algorithm, and this can greatly reduces the computational complexity. The paper studies the multi-robot system which possesses a communicative mechanism and an arbitrarily displaced initial state. The specific research establishes a convex hull of the multi-robot system, which is based on computational geometry algorithm, determines the convex hull diameter and the location of the straight line formation. It introduces the `spring force´ to deal with the coordination of the robots, meanwhile it puts forward the concept of `gully´ to model the line formation problem, and uses tangent method in computational geometry algorithm to determine the path to avoid obstacles. The proposed algorithm allows multi-robots to quickly form in a straight line and complete the obstacle avoidance, and its advantage is the small computational complexity and good real-time efficiency.