As the use of robots and machines for automation accelerates, the need for algorithms to generate paths for them has emerged. One of the challenges in creating such algorithms is to build paths efficiently while preventing collisions between robots in a shared workspace. In projects like automated warehouse management, the issue of collisions becomes even more significant. Beyond the need to protect cargo while its moving from point to point, the confined space inherently increases the likelihood of collisions between robots.
The objective of this project is to develop a decentralized algorithm that resides within each robot, equipped with a set of rules to avoid collisions and find the most efficient path to the destination. To present the problem and proposed solution, we created a grid network simulation. The user can select starting and ending points for multiple robots, each represented in different colours, and add obstacles along the way – depicted in black. Each robot has a unique colour for its starting point, endpoint, path, and radii. In each simulation step, every robot examines its surroundings using two radii: a search radius and an impact radius, with the search radius necessarily larger than the impact radius.
When a robot detects another robot within its search radius, it begins tracking the other robot’s movement and attempts to predict its direction using a probability table. If the other robot also enters the impact radius, the first robot will determine whether there is a high probability that the second robot will cross its path toward the destination at the same time and space. If so, the robot will adjust its path accordingly, otherwise, it will continue in its current direction and if necessary, recalculate its path in the next step. The robots use a probability table to predict the positions of other robots in the next step. The basic algorithm is based on pathfinding (A* algorithm), which has been modified to prevent collisions both in time and space. Information about the location and timing of other robots is obtained through the mentioned table.
The simulation demonstrated successful results, with no collisions between robots. Each robot moved along the optimal path, given the surrounding robots and the probabilities of their future movements.