I |
n parallel with recent advancements in intelligent robots and their applications, the robot motion planning discipline, which is a major field in robotics, computer science and control engineering, has found increasing importance. This field mainly deals with developing obstacle avoidance and optimal path planning models and approaches. In this Article a novel method is proposed for solving the multi robot motion planning problem on conditions that the robots are permitted to merely move along or stop at the nodes of a connected and planar graph. Also, other issues like lengths, capacities of edges and concurrent movements of robots are considered. The main challenge in a multi robot motion planning problem is the emergence of deadlocks, which are instances when two or more robots intend to occupy a specific place at the same time. This causes the problem to be classified as an NP-hard problem. The proposed method is a combination of centralized and decoupled approaches, and benefits from the advantages of both. The generated solutions are evaluated based on optimality criteria of minimality of processing time. The running time complexity of the algorithm is polynomial. Computational results of solving numerous problems with various sizes and complexities exhibited that the lengths of the produced solution had a relatively small gap compared to the absolute minimum number of moves without resolving the deadlocks.