Abstract: The undirected Petri net is used to model the AGV system layout problem. A time-based reachable state graph is constructed by the time-window combined with the reachable state graph. The scheduling method is used to route the bidirectional AGV system, and the multiple AGVs routing problem is transformed into the single AGV routing problem in order to reduce problem complexity. A shortest time routing algorithm is proposed based on Best-first search, which determines the present state depending on the information of its next step path. By using this method, the shortest time route for each AGV can be found while avoiding deadlock, blocking and collision. Example results indicate that the algorithm can achieve a better optimal solution. This method can be used to deal with large scale systems.

Key words: automated guided vehicle (AGV), Petri net, routing, time-window