Graph-Based Collision Avoidance Algorithm Among Swarm Agents

Abstract

More than one homogenous or heterogenous type unmanned vehicle can work in a coordinated manner and perform large-scale swarm tasks (firefighting, search and rescue, mapping, and military operations, etc.) efficiently in a shorter time by sharing tasks. Collision of these vehicles is among the most significant problems encountered during their work. The crash of the vehicles causes the vehicles to be out of duty and, accordingly, to the mission's failure. In this study, Quadrotor-type UAVs used as agents can go to any target point by receiving location, speed, and compass information with GPS and IMU sensors. In the application, the agents' locations were kept and updated in a list in pairs, similar to the traversing process in the Optimized Bubble Sort Algorithm. The projections of the velocity vectors on the agents' axis (local) on a single coordinate plane are taken to determine the collision situation between these two agents that are traveling instantaneously. These global velocity vectors, whose projections are taken, are re-projected to the edge formed by these two agents in the graph and then subtracted from each other. Suppose the size of the vector is greater than the distance between two agents obtained by any GPS distance algorithm (Pythagoras, Haversine, etc.). In this case, collision is detected, and the separation process is activated. Separation is the process of advancing one agent in the opposite direction of the other until a minimum safe distance is achieved, where one agent entered by the user will not affect the other. Once the separation is complete, the agent moves to the final destination point. © 2023 IEEE.