Multi-Robot Path Planning Based on Max–Min Ant Colony Optimization and D* Algorithms in a Dynamic Environment

Abstract

This paper involves a proposition of a new method to find the optimal path for centralized and competitive multirobot in the same dynamic environment. These robots can start from different location(s) and destination to the same goal. The method used to hybrid the pheromone trail updating of MAX– MIN ACO (MMAS) algorithm with D* algorithm strategies to construct a trail of the modified (deposited) pheromone which is updated in each iteration. The robots use tour construction probabilities to choose the best solution to move from the start nodes through the dynamic environment, which contains dynamic obstacles moving in free space, by finding and displaying the optimal path for each robot. A number of experimental results simulated on different dynamic environments for different number of robots indicated that the proposed method performed well. The robots are competitive with each other to reach their targets without colliding with obstacles, and they find the optimal path with minimum iterations and minimum total arc cost. Generally, the increase number of the implemented robots increases the occupy time. However, the amount of that increase varies. It goes from (7%) to (15%) when one to two robots are implemented. It is also noticed that the increase in the time occupy turns to be limited in comparison to the previous ratios, i.e. from (27%) to (30%) when four to five robots are implemented.