Multi-agent Robots Systems (MARS) can be defined as sets of autonomous robots coordinated through a communication system to achieve cooperative tasks. During the last 20 years, MARS have found a wide range of applications in terrestrial, spatial and oceanic explorations emerging as a new research area (Cao et al. (1997)). Some advantages can be obtained from the collective behavior of MARS. For instance, the kind of tasks that can be accomplished are inherently more complex than those a single robot can accomplish. Also, the system becomes more flexible and fault-tolerant (Yamaguchi (2003)). The range of applications includes toxic residues cleaning, transportation and manipulation of large objects, alertness and exploration, searching and rescue tasks and simulation of biological entities behaviors (Arai et al. (2002)). The study ofMARS extends the classical problems of single robotswith new issues likemotion coordination, task decomposition and task assignment, network communications, searching and mapping, etc. Therefore, the study of MARS encompass distributed systems, artificial intelligence, game theory, biology, ethology, economics, control theory, etc. Motion coordination is an important research area of MARS, specifically formation control (Chen & Wang (2005)). The main goal is to coordinate a group of mobile agents or robots to achieve a desired formation pattern avoiding inter-agent collisions at the same time. The formation strategies are decentralized because it is assumed that every agent measures the position of a certain subset of agents and, eventually, it detects the position of other agents when a minimal allowed distance is violated and collision danger appears. Thus, the main intention is to achieve desired global behaviors through local interactions (Francis et al. (2004)). Also, the decentralized approaches offer greater autonomy for the robots, less computational load in control implementations and its applicability to large scale groups (Do (2007)). According to Desai (2002); Muhammad & Egerstedt (2004), the possible inter-agent communications and the desired relative position of every agent with respect to the others can be represented by a FormationGraph (FG). The application of different FG’s to the same group of robots produces different dynamics on the team behavior. In the literature, some special FG topologies are chosen and the convergence to the desired formation and non-collision is analyzed for any number of robots. A decentralized formation strategy must comply with two fundamental requirements: Global convergence to the desired formation and inter-agent collision avoidance (Cao et al. (1997)). 6