Multi-agent systems (MAS) have been of interest to many researchers during the last decades. This thesis focuses on multi-robot systems (MRS) and programmable matter as two types of MAS. Regarding MRS, the focus is on the 'mergeable nervous system' (MNS) concept which allows the robots to connect to one another and establish a communication network through self-organization and then use the network to temporarily report sensing events and cede authority to a single robot in the system. Here, in a collective perception scenario, we experimentally evaluate the performance of an MNS-enabled approach and compare it with that of several decentralized benchmark approaches. We show that an MNS-enabled approach is high-performing, fault-tolerant, and scalable, so it is an appropriate approach for MRS. As a goal of the thesis, using an MNS-enabled approach, we present for the first time a comprehensive comparison of control architectures in multi-robot systems, which includes a comparison of accuracy, efficiency, speed, energy consumption, scalability, and fault tolerance. Our comparisons provide designers of multi-robot systems with a better understanding for selecting the best-performing control depending on the system's objectives. Additionally, as a separate goal, we design a high-level leader based programmable matter, which can perform some basic primitive operations in a grid environment, and construct it using lower-level organisms. We design and implement deterministic algorithms for "curl" operation of this high-level matter, an instance of shape formation problem. We prove the correctness of the presented algorithms, analytically determine their complexity, and experimentally evaluate their performance.

abstract: Imagine that we have a piece of matter that can change its physical properties like its shape, density, conductivity, or color in a programmable fashion based on either user input or autonomous sensing. This is the vision behind what is commonly known as programmable matter. Envisioning systems of nano-sensors devices, programmable matter consists of systems of simple computational elements, called particles, that can establish and release bonds, compute, and can actively move in a self-organized way. In this dissertation the feasibility of solving fundamental problems relevant for programmable matter is investigated. As a model for such self-organizing particle systems (SOPS), the geometric amoebot model is introduced. In this model, particles only have local information and have modest computational power. They achieve locomotion by expanding and contracting, which resembles the behavior of amoeba. Under this model, efficient local-control algorithms for the leader election problem in SOPS are presented. As a central problem for programmable matter, shape formation problems are then studied. The limitations of solving the leader election problem and the shape formation problem on a more general version of the amoebot model are also discussed. The \smart paint" problem is also studied which aims at having the particles self-organize in order to uniformly coat the surface of an object of arbitrary shape and size, forming multiple coating layers if necessary. A Universal Coating algorithm is presented and shown to be asymptotically worst-case optimal both in terms of time with high probability and work. In particular, the algorithm always terminates within a linear number of rounds with high probability. A linear lower bound on the competitive gap between fully local coating algorithms and coating algorithms that rely on global information is presented, which implies that the proposed algorithm is also optimal in a competitive sense. Simulation results show that the competitive ratio of the proposed algorithm may be better than linear in practice. Developed algorithms utilize only local control, require only constant-size memory particles, and are asymptotically optimal in terms of the total number of particle movements needed to reach the desired shape configuration. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2017

<div>Self-organization in a multi-robot system is a spontaneous process where some form of overall order arises from local interactions between robots in an initially disordered system. Cooperative coordination strategies for self-organization promote teamwork to complete a task while increasing the total utility of the system. In this dissertation, we apply prosocial behavioral concepts such as altruism and cooperation in multi-robot systems and investigate their effects on overall system performance on given tasks. We stress the significance of this research in long-term applications involving minimal to no human supervision, where self-sustainability of the multi-robot group is of utmost importance for the success of the mission at hand and system re-usability in the future.</div><div><br></div><div>For part of the research, we take bio-inspiration of cooperation from the huddling behavior of Emperor Penguins in the Antarctic which allows them to share body heat and survive one of the harshest environments on Earth as a group. A cyclic energy sharing concept is proposed for a convoying structured multi-robot group inspired from penguin movement dynamics in a huddle with carefully placed induction coils to facilitate directional energy sharing with neighbors and a position shuffling algorithm, allowing long-term survival of the convoy as a group in the field. Simulation results validate that the cyclic process allows individuals an equal opportunity to be at the center of the group identified as the most energy conserving position, and as a result robot groups were able to travel over 4 times the distance during convoying with the proposed method without any robot failing as opposed to without the shuffling and energy sharing process. </div><div><br></div><div>An artificial potential based Adaptive Inter-agent Spacing (AIS) control law is also proposed for efficient energy distribution in an unstructured multi-robot group aimed at long-term survivability goals in the field. By design, as an altruistic behavior higher energy bearing robots are dispersed throughout the group based on their individual energy levels to counter skewed initial distributions for faster group energy equilibrium attainment. Inspired by multi-huddle merging and splitting behavior of Emperor Penguins, a clustering and sequential merging based systematic energy equilibrium attainment method is also proposed as a supplement to the AIS controller. The proposed system ensures that high energy bearing agents are not over crowded by low energy bearing agents. The AIS controller proposed for the unstructured energy sharing and distribution process yielded 55%, 42%, 23% and 33% performance improvements in equilibrium attainment convergence time for skewed, bi-modal, normal and random initial agent resource level distributions respectively on a 2D plane using the proposed energy distribution method over the control method of no adaptive spacing. Scalability analysis for both energy sharing concepts confirmed their application with consistently improved performances different sized groups of robots. Applicability of the AIS controller as a generalized resource distribution method under certain constraints is also discussed to establish its significance in various multi-robot applications.</div><div><br></div><div>A concept of group based survival from damaging directional external stimuli is also adapted from the Emperor Penguin huddling phenomenon where individuals on the damaging stimuli side continuously relocate to the leeward side of the group following the group boundary using Gaussian Processes Machine Learning based global health-loss rate minima estimations in a distributed manner. The method relies on cooperation from all robots where individuals take turns being sheltered by the group from the damaging external stimuli. The distributed global health loss rate minima estimation allowed the development of two settling conditions. The global health loss rate minima settling method yielded 12.6%, 5.3%, 16.7% and 14.2% improvement in average robot health over the control case of no relocation, while an optimized health loss rate minima settling method further improved on the global health loss rate settling method by 3.9%, 1.9%, 1.7% and 0.6% for robot group sizes 26, 35, 70 and 107 respectively.</div><div><br></div><div>As a direct application case study of collaboration in multi-robot systems, a distributed shape formation strategy is proposed where robots act as beacons to help neighbors settle in a prescribed formation by local signaling. The process is completely distributed in nature and does not require any external control due to the cooperation between robots. Beacon robots looking for a robot to settle as a neighbor and continue the shape formation process, generates a surface gradient throughout the formed shape that allow robots to determine the direction of the structure forming frontier along the dynamically changing structure surface and eventually reach the closest beacon. Simulation experiments validate complex shape formation in 2D and 3D using the proposed method. The importance of group collaboration is emphasized in this case study without which the shape formation process would not be possible, without a centralized control scheme directing individual agents to specific positions in the structure. </div><div> </div><div>As the final application case study, a collaborative multi-agent transportation strategy is proposed for unknown objects with irregular shape and uneven weight distribution. Although, the proposed system is robust to single robot object transportation, the proposed methodology of transport is focused on robots regulating their effort while pushing objects from an identified pushing location hoping other robots support the object moment on the other end of the center of mass to prevent unintended rotation and create an efficient path of the object to the goal. The design of the object transportation strategy takes cooperation cues from human behaviors when coordinating pushing of heavy objects from two ends. Collaboration is achieved when pushing agents can regulate their effort with one another to maintain an efficient path for the object towards the set goal. Numerous experiments of pushing simple shapes such as disks and rectangular boxes and complex arbitrary shapes with increasing number of robots validate the significance and effectiveness of the proposed method. Detailed robustness studies of changing weight of objects during transportation portrayed the importance of cooperation in multi-agent systems in countering unintended drift effects of the object and maintain a steady efficient path to the goal. </div><div><br></div><div>Each case study is presented independent of one another with the Penguin huddling based self-organizations in response to internal and external stimuli focused on fundamental self-organization methods, and the structure formation and object transportation strategies focused on cooperation in specific applications. All case studies are validated by relevant simulation and experiments to establish the effectiveness of altruistic and cooperative behaviors in multi-robot systems.</div>