Abstract: In a populated environment，boundaries of obstacles are complex，and Generalized Voronoi Diagrams（GVDs） are employed to represent the spatial environment.In the motion planning for multiple robots，it must be considered for coordinating these robots according to passage width in the constructed GVDs.Thus an algorithm for computing the passage width in the constructed GVDs according to the populated environment is proposed.A* algorithm is employed for planning paths for multiple robots in the constructed GVDs，and a distributed method is used for coordinating motions of multiple robots.An instance for coordinating two robots is given and simulated.The simulation results show that the multiple robot motion planning can be completed based on the GVDs with passage width.