  Multi-mobile robot systems show great advantages over one single robot in
many applications. However, the robots are required to form desired
task-specified formations, making feasible motions decrease significantly.
Thus, it is challenging to determine whether the robots can pass through an
obstructed environment under formation constraints, especially in an
obstacle-rich environment. Furthermore, is there an optimal path for the
robots? To deal with the two problems, a novel graphbased motion planner is
proposed in this paper. A mapping between workspace and configuration space of
multi-mobile robot systems is first built, where valid configurations can be
acquired to satisfy both formation constraints and collision avoidance. Then,
an undirected graph is generated by verifying connectivity between valid
configurations. The breadth-first search method is employed to answer the
question of whether there is a feasible path on the graph. Finally, an optimal
path will be planned on the updated graph, considering the cost of path length
and formation preference. Simulation results show that the planner can be
applied to get optimal motions of robots under formation constraints in
obstacle-rich environments. Additionally, different constraints are considered.
