A distributed route planning method for multiple mobile robots using Lagrangian decomposition technique

For the transportation in semiconductor fabricating bay, route planning of multiple AGVs (Automated Guided Vehicles) is expected to minimize the total transportation time without collision and deadlock among AGVs. In this paper, we propose a distributed route planning method for multiple mobile robots using Lagrangian decomposition technique. The proposed method has a characteristic that each mobile robot individually creates a near optimal route through the repetitive data exchange among the AGVs and the local optimization of its route using Dijkstra's algorithm. The proposed method is successively applied to transportation route planning problem in semiconductor fabricating bay. The optimality of the solution generated by the proposed method is evaluated by using the duality gap derived by using Lagrangian relaxation method. A near optimal solution within 5% of duality gap for a large scale transportation system consisting of 143 nodes and 15 AGVs can be obtained only within five seconds of computation time. The proposed method is implemented on 3 AGVs system and the route plan is derived taking the size of AGV into account. It is experimentally shown that the proposed method can be found to be effective for various types of problems despite the fact that each route for AGV is created without considering the entire objective function.