Improved Algorithm for Constructing Collision-Free Route for Multi-Agent Swarm Robotic Systems

Abstract

Formulation of the problem in general. It is noted that to increase the efficiency of performing targeted tasks, groups (swarms) of robots, called multi-agent systems, are used. Such systems move in a complex environment with obstacles, which requires algorithmization of the process of building collision-free routes for the movement of robotic vehicles for safe movement in space. An analysis of existing algorithms for planning routes for mobile robotic vehicles is carried out. It is shown that to solve the problem of finding the optimal collision-free route for a group (swarm) of unmanned aerial vehicles, it is proposed to use a joint matrix-grid (graph) of the space with obstacles and the movement plan.

Analysis of recent researches and publications. The Dijkstra algorithm, fast random tree search, and search algorithms for building a route from one point to another are used to plan the route of mobile robotic vehicles. However, they solve the problems of route planning for individual robotic systems in various fields of activity and are not well adapted to the problems of group control of moving objects in a complex environment with obstacles.

Presenting the main material. The algorithm for constructing a route for a multi-agent system of robotic vehicles has been improved to ensure collision-free movement of agents in space performing common tasks as part of groups (swarms). The improvement is made by adding a heuristic function for estimating the complexity of movement between cells. It is proposed to build a collision-free route using a modified algorithm with a modified function of heuristic evaluation of movement between the vertices of a graph, which is an element of a cubic cell. It is shown that the main stages of the algorithm for constructing a collision-free route for a swarm of unmanned aerial vehicles are: determining the main element (leader), constructing a common grid matrix (graph) and determining the occupancy of each cell (vertex) depending on the route and time, forming an attraction/repulsion function that determines the criterion for critical convergence of group elements.

Conclusion. The algorithm for constructing a collision-free route for swarming multiagent systems allows us to keep the group elements in a cluster or as part of the swarm as a whole while moving in a space with obstacles. The proposed algorithm is based on the approach of constructing a grid matrix (graph) that divides the space into cells. The occupancy of each cell is determined depending on the UAV's route and travel time. The criterion for critical convergence of group elements is determined by the attraction/repulsion function, and the difficulty of moving to the next cell is determined by a heuristic function for estimating the movement between the vertices of the graph.

The perspectives of future researches. Further research should include the improvement of mathematical methods based on the use of reinforcement learning of agents and modeling the processes of building collision-free routes for multi-agent systems.