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.