Abstract: M-TdPN, an improved search algorithm, was presented in this paper in view of the shortage of traditional solutions of maze problem. Redundancy points were eliminated to reduce the space complexity. The timed Petri net was applied to simulate the maze. Using the concurrency, every token has its own traces. The flags attached on tokens in the end place arc the feasible paths of maze problem. hhe searching efficiency is improved effectively. Results of experimental showed that the M-TdPN algorithm has better search results in case of more complicated maze or more impasse vertexes specially.

Key words: Limed petri nets, Maze problem, Concurrency, Token flag