Analysis, design and implementation of cooperative control strategies for multi-robot systems under communication constraints is the topic of this thesis. Motivated by a rapidly growing number of applications with networked robots and other vehicles, fundamental limits on the achievable collaborative behavior are studied for large teams of autonomous agents. In particular, a problem is researched in detail in which the group of agents is supposed to agree on a common state without any centralized coordination. Due to the dynamics of the individual agents and their varying connectivity, this problemis an extension of the classical consensus problemin computer science. It captures a crucial component of many desirable features of multi-robot systems, such as formation, flocking, rendezvous, synchronizing and covering. Analytical bounds on the convergence rate to consensus are derived for several systemconfigurations. It is shown that static communication networks that exhibit particular symmetries yield slow convergence, if the connectivity of each agent does not scale with the total number of agents. On the other hand, some randomly varying networks allow fast convergence even if the connectivity is low. It is furthermore argued that if the data being exchanged between the agents are quantized, it may heavily degrade the performance. The extent to which certain quantization schemes are more suitable than others is quantified through relations between the number of agents and the required total network bit rate. The design of distributed coordination and estimation schemes based on the consensus algorithm is presented. A receding horizon coordination strategy utilizing subgradient optimization is developed. Robustness and implementation aspects are discussed. A new collaborative estimation method is also proposed. The implementation of multi-robot control systems is difficult due to the high systemcomplexity. In the final part of this thesis, a hierarchical control architecture appropriate for a class of coordination tasks is therefore suggested. It allows a formal verification of the correctness of the implemented control algorithms. / QC 20100920

Controlling systems with multiple robots is quickly becoming the next large hurdle that must be overcome for groups of robots to successfully function as a team. An agent oriented approach for this problem is presented in this thesis. By using an agent oriented method, the robots can act independently yet still work together. To be able to establish communities of robots, a basic agent oriented control system for each robot must first be implemented. This thesis introduces a novel method to create Physical Robot Agents, promoting a separation of cognitive and reactive behaviours into a two layer system. These layers are further abstracted into key subsections that are required for the Physical Robot Agents to function. To test this architecture, experiments are performed with physical robots to determine the feasibility of this approach. <br /><br /> A real-time implementation of a Physical Robot Agent would greatly expand its field of use. The speed of internal communication is analyzed to validate the application of this architecture to real-time tasks. <br /><br /> It is concluded that the Physical Robot Agents are well suited for multiple robot systems and that real-time applications are feasible.

Teams of mobile robots have numerous applications, such as space exploration, underground mining, warehousing, and building security. Multi-robot teams can provide a number of practical benefits in such applications, including simultaneous presence in multiple locations, improved system performance, and greater robustness and redundancy compared to individual robots. This thesis addresses three aspects of coordination and navigation for teams of mobile robots: localization, the estimation of the position of each robot in the environment; motion planning, the process of finding collision-free trajectories through the environment; and task allocation, the selection of appropriate goals to be assigned to each robot. Each of these topics are investigated in the context of many robots working in a common environment. A particle-filter based system for cooperative global localization is presented. The system combines the sensor data from three robots, including measurements of the distances between robots, to cooperatively estimate the global position of each robot in the environment. The method is developed for a single triad of robots, then extended to larger groups of robots. The algorithm is demonstrated in a simulation of robots equipped with only simple range sensors, and is shown to successfully achieve global localization of robots that are unable to localize using only their own local sensor data. Motion planning is investigated for large teams of robots operating in tunnel and corridor environments, where coordinated planning is often required to avoid collision or deadlock conditions. A complete and scalable motion planning algorithm is presented and evaluated in simulation with up to 150 robots. In contrast to popular decoupled approaches to motion planning (which cannot guarantee a solution), this algorithm uses a multi-phase approach to create and maintain obstacle-free paths through a graph representation of the environment. The resulting plan is a set of collision-free trajectories, guaranteeing that every robot will reach its goal. The problem of task allocation is considered in the same type of tunnel and corridor environments, where tasks are defined as locations in the environment that must be visited by one of the robots in the team. To find efficient solutions to the task allocation problem, an optimization approach is used to generate potential task assignments, and select the best solution. The multi-phase motion planner is applied within this system as an efficient method of evaluating potential task assignments for many robots in a large environment. The algorithm is evaluated in simulations with up to 20 robots in a map of large underground mine. A real-world implementation of 3 physical robots was used to demonstrate the implementation of the multi-phase motion planning and task allocation systems. A centralized motion planning and task allocation system was developed, incorporating localization and time-dependent trajectory tracking on the robot processors, enabling cooperative navigation in a shared hallway environment.

This research addresses the problem of allocating closely spaced targets to multiple autonomous underwater vehicles (AUV) in the presence of constant ocean currents. The main difficulty of this problem is that the non-holonomic vehicles are constrained to move along forward paths with bounded curvatures. The Dubins model is a simple but effective way to handle the kinematic characteristics of AUVs. It gives complete characterization of the optimal paths between two configurations for a vehicle with limited turning radius moving in a plane at constant speed. In the proposed algorithm, Dubins paths are modified to include ocean currents, resulting in paths defined by curves whose radius of curvature is not constant. To determine the time required to follow such paths, an approximate dynamic model of the AUV is queried due to the computational complexity of the full model. The lower order model is built from data obtained from sampling the full model. The full model is used in evaluating the final tour times of the sequences generated by the proposed algorithm to validate the results. The proposed algorithm solves the task allocation problem with market-based auctions that minimize the total travel time to complete the mission. The novelty of the research is the path cost calculation that combines a Dubins model, an AUV dynamic model, and a model of the ocean current. Simulations were conducted in Matlab to illustrate the performance of the proposed algorithm using various number of task points and AUVs. The task points were generated randomly and uniformly close together to highlight the necessity for considering the curvature constraints. For a sufficiently dense set of points, it becomes clear that the ordering of the Euclidean tours are not optimal in the case of the Dubins multiple travelling salesmen problem. This is due to the fact that there is little relationship between the Euclidean and Dubins metrics, especially when the Euclidean distances are small with respect to the turning radius. An algorithm for the Euclidean problem will tend to schedule very close points in a successive order, which can imply long maneuvers for the AUV. This is clearly demonstrated by the numerous loops that become problematic with dense sets of points. The algorithm proposed in this thesis does not rely on the Euclidean solution and therefore, even in the presence of ocean currents, can create paths that are feasible for curvature bound vehicles. Field tests were also conducted on an Iver2 AUV at the Avila Pier in California to validate the performance of the proposed algorithm in real world environments. Missions created based on the sequences generated by the proposed algorithm were conducted to observe the ability of an AUV to follow paths of bounded curvature in the presence of ocean currents. Results show that the proposed algorithm generated paths that were feasible for an AUV to track closely, even in the presence of ocean current.

Controlling systems with multiple robots is quickly becoming the next large hurdle that must be overcome for groups of robots to successfully function as a team. An agent oriented approach for this problem is presented in this thesis. By using an agent oriented method, the robots can act independently yet still work together. To be able to establish communities of robots, a basic agent oriented control system for each robot must first be implemented. This thesis introduces a novel method to create Physical Robot Agents, promoting a separation of cognitive and reactive behaviours into a two layer system. These layers are further abstracted into key subsections that are required for the Physical Robot Agents to function. To test this architecture, experiments are performed with physical robots to determine the feasibility of this approach. <br /><br /> A real-time implementation of a Physical Robot Agent would greatly expand its field of use. The speed of internal communication is analyzed to validate the application of this architecture to real-time tasks. <br /><br /> It is concluded that the Physical Robot Agents are well suited for multiple robot systems and that real-time applications are feasible.

Teams of mobile robots have numerous applications, such as space exploration, underground mining, warehousing, and building security. Multi-robot teams can provide a number of practical benefits in such applications, including simultaneous presence in multiple locations, improved system performance, and greater robustness and redundancy compared to individual robots. This thesis addresses three aspects of coordination and navigation for teams of mobile robots: localization, the estimation of the position of each robot in the environment; motion planning, the process of finding collision-free trajectories through the environment; and task allocation, the selection of appropriate goals to be assigned to each robot. Each of these topics are investigated in the context of many robots working in a common environment. A particle-filter based system for cooperative global localization is presented. The system combines the sensor data from three robots, including measurements of the distances between robots, to cooperatively estimate the global position of each robot in the environment. The method is developed for a single triad of robots, then extended to larger groups of robots. The algorithm is demonstrated in a simulation of robots equipped with only simple range sensors, and is shown to successfully achieve global localization of robots that are unable to localize using only their own local sensor data. Motion planning is investigated for large teams of robots operating in tunnel and corridor environments, where coordinated planning is often required to avoid collision or deadlock conditions. A complete and scalable motion planning algorithm is presented and evaluated in simulation with up to 150 robots. In contrast to popular decoupled approaches to motion planning (which cannot guarantee a solution), this algorithm uses a multi-phase approach to create and maintain obstacle-free paths through a graph representation of the environment. The resulting plan is a set of collision-free trajectories, guaranteeing that every robot will reach its goal. The problem of task allocation is considered in the same type of tunnel and corridor environments, where tasks are defined as locations in the environment that must be visited by one of the robots in the team. To find efficient solutions to the task allocation problem, an optimization approach is used to generate potential task assignments, and select the best solution. The multi-phase motion planner is applied within this system as an efficient method of evaluating potential task assignments for many robots in a large environment. The algorithm is evaluated in simulations with up to 20 robots in a map of large underground mine. A real-world implementation of 3 physical robots was used to demonstrate the implementation of the multi-phase motion planning and task allocation systems. A centralized motion planning and task allocation system was developed, incorporating localization and time-dependent trajectory tracking on the robot processors, enabling cooperative navigation in a shared hallway environment.

This research addresses the problem of allocating closely spaced targets to multiple autonomous underwater vehicles (AUV) in the presence of constant ocean currents. The main difficulty of this problem is that the non-holonomic vehicles are constrained to move along forward paths with bounded curvatures. The Dubins model is a simple but effective way to handle the kinematic characteristics of AUVs. It gives complete characterization of the optimal paths between two configurations for a vehicle with limited turning radius moving in a plane at constant speed. In the proposed algorithm, Dubins paths are modified to include ocean currents, resulting in paths defined by curves whose radius of curvature is not constant. To determine the time required to follow such paths, an approximate dynamic model of the AUV is queried due to the computational complexity of the full model. The lower order model is built from data obtained from sampling the full model. The full model is used in evaluating the final tour times of the sequences generated by the proposed algorithm to validate the results. The proposed algorithm solves the task allocation problem with market-based auctions that minimize the total travel time to complete the mission. The novelty of the research is the path cost calculation that combines a Dubins model, an AUV dynamic model, and a model of the ocean current. Simulations were conducted in Matlab to illustrate the performance of the proposed algorithm using various number of task points and AUVs. The task points were generated randomly and uniformly close together to highlight the necessity for considering the curvature constraints. For a sufficiently dense set of points, it becomes clear that the ordering of the Euclidean tours are not optimal in the case of the Dubins multiple travelling salesmen problem. This is due to the fact that there is little relationship between the Euclidean and Dubins metrics, especially when the Euclidean distances are small with respect to the turning radius. An algorithm for the Euclidean problem will tend to schedule very close points in a successive order, which can imply long maneuvers for the AUV. This is clearly demonstrated by the numerous loops that become problematic with dense sets of points. The algorithm proposed in this thesis does not rely on the Euclidean solution and therefore, even in the presence of ocean currents, can create paths that are feasible for curvature bound vehicles. Field tests were also conducted on an Iver2 AUV at the Avila Pier in California to validate the performance of the proposed algorithm in real world environments. Missions created based on the sequences generated by the proposed algorithm were conducted to observe the ability of an AUV to follow paths of bounded curvature in the presence of ocean currents. Results show that the proposed algorithm generated paths that were feasible for an AUV to track closely, even in the presence of ocean current.

Considered in this research is a framework for effective formation control of multirobot systems in dynamic environments. The basic formation control involves two important considerations: (1) Real-time trajectory generation algorithms for distributed control based on nominal agent models, and (2) robust tracking of reference trajectories under model uncertainties. Proposed is a two-layer hierarchical architecture for collectivemotion control ofmultirobot nonholonomic systems. It endows robotic systems with the ability to simultaneously deal with multiple tasks and achieve typical complex formation missions, such as collisionfree maneuvers in dynamic environments, tracking certain desired trajectories, forming suitable patterns or geometrical shapes, and/or varying the pattern when necessary. The study also addresses real-time formation tracking of reference trajectories under the presence of model uncertainties and proposes robust control laws such that over each time interval any tracking errors due to system uncertainties are driven down to zero prior to the commencement of the subsequent computation segment. By considering a class of nonlinear systems with favorable finite-time convergence characteristics, sufficient conditions for exponential finite-time stability are established and then applied to distributed formation tracking controls. This manifests in the settling time of the controlled system being finite and no longer than the predefined reference trajectory segment computing time interval, thus making tracking errors go to zero by the end of the time horizon over which a segment of the reference trajectory is generated. This way the next segment of the reference trajectory is properly initialized to go into the trajectory computation algorithm. Consequently this could lead to a guarantee of desired multi-robot motion evolution in spite of system uncertainties. To facilitate practical implementation, communication among multi-agent systems is considered to enable the construction of distributed formation control. Instead of requiring global communication among all robots, a distributed communication algorithm is employed to eliminate redundant data propagation, thus reducing energy consumption and improving network efficiency while maintaining connectivity to ensure the convergence of formation control.

Our research focuses on one of the more fundamental issues in multi-agent, mobile robotics: the formation control problem. The idea is to create controllers that cause robots to move into a predefined formation shape. This is a well studied problem for the scenario in which the robots know in advance to which point in the formation they are assigned. In our case, we assume this information is not given in advance, but must be determined dynamically. This thesis presents an algorithm that can be used by a network of mobile robots to simultaneously determine efficient robot assignments and formation pose for rotationally and translationally invariant formations. This allows simultaneous role assignment and formation sysnthesis without the need for additional control laws. The thesis begins by introducing some general concepts regarding multi-agent robotics. Next, previous work and background information specific to the formation control and assignment problems are reviewed. Then the proposed assignment al- gorithm for role assignment and formation control is introduced and its theoretical properties are examined. This is followed by a discussion of simulation results. Lastly, experimental results are presented based on the implementation of the assignment al- gorithm on actual robots.

Like computer architects, robot designers must address multiple, possibly competing, requirements by balancing trade-offs in terms of processing, memory, communication, and energy to satisfy design objectives. However, robot architects currently lack the design guidelines, organizing principles, rules of thumb, and tools that computer architects rely upon. This thesis takes a step in this direction, by analyzing the roles of heterogeneity and distribution in robot systems architecture. This thesis takes a systems architecture approach to the design of robot systems, and in particular, investigates the use of distributed, heterogeneous platforms to exploit locality in robot systems design. We show how multiple, distributed heterogeneous platforms can serve as general purpose robot systems for three distinct domains with different design objectives: increasing availability in a search and rescue mission, increasing flexibility and ease-of-use for a personal educational robot, and decreasing the computation and sensing resources necessary for navigation and foraging tasks.