An Autonomous Distributed Route Planning Method for Multiple Mobile Robots

Abstract

Route planning of multiple AGVs (Automated Guided Vehicles) is expected to minimize the transportation time without collision and deadlock among the AGVs in many transportation systems. In this paper, we propose an autonomous distributed route planning method for multiple mobile robots. The proposed method has a characteristic that each mobile robot individually creates a near optimal route through the repetitive data exchange among the robots and the local search of route using Dijkstra's algorithm. The proposed method is applied to several transportation route planning problems. The optimality of the solution generated by the proposed method is evaluated using the duality gap derived by Lagrangian relaxation method. A near optimal route plan within 5% of duality gap for a large scale transportation system consisting of 143 nodes and 15 AGVs can be obtained with five seconds of computation time by using Pentium III (1GHz) processor. Moreover, it is shown that the proposed method is effective for various types of problems despite the fact that each route for AGV is created without optimizing the entire objective function even when the velocity of each AGV is different.