Scheduling and routing of autonomous moving objects on a mesh topology

摘要

Autonomous moving objects (AMOs), such as automated guided vehicles (AGVs) and autonomous robots, have been widely used in industry for decades. In an intelligent transport system with a great number of AMOs involved, it is desirable to maintain a smooth traffic flow of AMOs without congestion or deadlocks. Continuing our previous study, in this paper we propose a new algorithm for concurrent scheduling and routing of a great number (i.e., 4n 2) of AMOs on an n×n mesh topology of path network. As a significant improvement compared with the previous algorithm, this new algorithm achieves 3n concurrent rectilinear steps of routing for all 4n 2 AMOs, while no congestion or deadlocks arise from them when all AMOs are moving around on the mesh topology. The theoretical analysis and calculations of the algorithm are verified by randomly generated data in our experiments.