INTRODUCTION
In the past 2 decades, swarm robotics research has demonstrated that it is possible to coordinate a large group of autonomous robots without any central coordinating entity. Elegant collective solutions have been developed for tasks such as environmental monitoring (1), navigation and transport (2), self-assembly (3), construction (4, 5), and biohybrid interaction (6, 7). Using strictly self-organized control within flat (single-level and fully decentralized) system architectures, swarm robotics behaviors have leveraged redundancy and parallelism to consistently achieve the hallmark advantages of a robot swarm—scalability, flexibility, the absence of single points of failure, and some degree of inherent fault tolerance.
Despite notable progress and advantages, the swarm behaviors developed in abstract laboratory experiments are persistently slow to be adopted in real applications (8). This slow adoption rate can be attributed to the fact that, although there are advantages to self-organized swarm behaviors, there are also inherent limitations. One crucial limitation is swarm behaviors occurring at the macroscale but arising from self-organization among robots programmed at the microscale. Some approaches for global-to-local programming have been developed (9, 10), but self-organized swarm behaviors are still difficult (and, in some cases, potentially impossible) to design analytically (11). Even experienced researchers in the field often conduct a long trial-and-error design process to develop an incrementally new behavior, and it is not trivial to combine these behaviors once developed. Furthermore, self-organized swarms can take an undesirably long time to complete a task or converge on a decision, and, if an environment occupied by a swarm changes, it can be difficult to predict the influence of the change on the swarm’s collective behavior.
In centralized robot systems, it is much more straightforward to design and combine behaviors. We already know how to execute many centrally coordinated behaviors that we currently do not know how to accomplish with many robots in a strictly self-organized way, such as simultaneous localization and mapping (12) or online routing optimization (13). However, bottlenecks and single points of failure are unavoidable in strictly centralized systems, bringing inherent scalability and fault tolerance limitations that are typically absent in self-organized swarms. Here, we propose that key impediments to rapid progress in swarm robotics can be overcome by partially integrating centralized control into an otherwise self-organized system through the introduction of a reconfigurable multilevel architecture: in other words, a self-organized hierarchy.
A self-organized hierarchy has been identified as a key challenge for swarm robotics (8), along with other approaches such as automatic design (14–16) and behavioral heterogeneity (17). A hierarchy can offer swarm robotics easier and faster behavior design and management as well as more flexibility when combining behaviors. However, not just any hierarchy is suitable. To still behave like a swarm and retain the oft-cited benefits of scalability, flexibility, and fault tolerance, the swarm members must autonomously establish an ad hoc hierarchy among themselves and be able to comprehensively manage it in a self-organized way.
In existing multirobot systems, the overall architecture is normally set before deployment. In other words, the communication structure (organization of communication links and the system levels they can span), control distribution (degree of decentralization), and behavior structure of the system (for example, which sensor information influences which actions) are predefined, and the robots coordinate within this static architecture. Traditionally, the architecture of most robot swarms is strict self-organized heterarchy (unranked elements), as seen, for example, in self-organized flocking (18, 19). This trend is expected, given that both swarm robotics (8, 11, 20–23) and artificial swarm intelligence (21) have been heavily inspired by biological systems with unranked members, such as social insects (24–26).
Still, some mechanisms relevant to hierarchy have been demonstrated in robot swarms, such as behavioral heterogeneity that results in implicit leadership by members that are more informed (27), more communicative (28), more persistent (29), or partially human controlled (30, 31). However, this behavioral heterogeneity has normally been implemented with unranked members (single-level system). Some robot swarms have also incorporated explicit leaders (double-level system) into behaviors that are otherwise self-organized and based on local information (32–36), but this leadership allocation has been static after deployment and is usually defined manually. In some other robot swarms, interactions are one way and can therefore be interpreted as a hierarchy of many temporary leader-follower pairs (37–40), but any ranking among these pairs is emergent and cannot be explicitly controlled. Last, many high-performing approaches to collective navigation are partly centralized and partly decentralized—notably, the recent trajectory planner for drone swarms by Zhou et al. (41)—but they use fixed collaboration structures because configuring and reconfiguring swarm architectures is not the focus of these studies. In short, no existing approach has provided a comprehensive way to self-organize dynamic and highly reconfigurable multilevel system architectures.
To undertake this challenge, we present self-organizing nervous systems (SoNSs) for robot swarms. A SoNS is a robot swarm architecture that uses self-organized hierarchy to allow robots acting as “brains” to coordinate sensing, actuation, and decision-making in temporarily centralized subswarms without sacrificing the scalability, flexibility, and fault tolerance of self-organization. For our development of SoNSs, we have taken inspiration from our mergeable nervous systems (MNSs) (42), an approach for physically connected robots, and conducted preliminary simulation-only studies on extending the MNS (43–47). Here, we present SoNSs and provide a proof of concept using real robots.
SoNS concept
In the SoNS concept, robots self-organize into dynamic multilevel system architectures using ad hoc remote bidirectional connections. The result is a swarm composed of a number of reconfigurable SoNSs (Fig. 1 and Movie 1). In each SoNS instance, each “child” robot has chosen to temporarily grant explicit supervisory powers to a parent robot in the level above it, culminating in a single “brain” robot that acts as a temporary coordinating entity. The structure of a SoNS instance is defined both by the topology of its connections and the relative robot poses associated with those connections. Thus, the underlying graph of a SoNS is a rooted tree with bidirectional edges and a set of attributes.
Fig. 1. The SoNS concept.
Robots self-organize reconfigurable multilevel system architectures using communication only with nearby robots. (A) In a SoNS, each child robot has chosen to temporarily grant explicit supervisory powers to a parent robot in the level above it, culminating in a single brain robot that acts as a temporary coordinating entity. At each bidirectional connection, the child robot sends sensor information upstream, and the parent robot sends actuation instructions downstream. (B) Any robot at any level of the hierarchy can be interchanged with another robot—even the brain. (C and D) At initialization, each robot is the brain of its own single-robot SoNS and has a target graph. If it encounters another SoNS, it can choose to accept recruitment and merge with it, thereby abdicating its brain status. (E) The process by which the robots establish and maintain SoNS connections is self-organized, and SoNS topologies can be reconfigured by reallocating robots (i.e., removing and adding connections within the same SoNS), merging two or more SoNSs, or splitting a SoNS. Here, we see a 5-robot SoNS (right) that merges with a 20-robot SoNS (left). (F) The SoNS topology is used to organize supervisory powers and send actuation instructions downstream, but the child robots are still semiautonomous and can adjust the interlevel control distribution in the SoNS, adapting the effective degree of centralization or decentralization in the decision-making processes of the SoNS.
One aim of the SoNS concept is to maintain the key benefits of self-organization: The SoNS architecture should be scalable (for instance, connections should not become more difficult to establish if a SoNS has more members) and should be fault tolerant. To maintain scalability, each connection in a SoNS is managed solely by the two robots sharing the connection, and each robot (even the brain) communicates only with robots nearby. To maintain fault tolerance, every robot in a SoNS is replaceable (even the brain). If any robot fails or is lost, another robot can replace it automatically, or, if no extra robots are available, the SoNS can reconfigure and try to continue its mission with the robots it already has.
Another aim of the SoNS concept is that the members of one SoNS should be capable of seamless shared behaviors and agile reactions. For the aim of seamless shared behaviors, each robot in a SoNS sends sensor information upstream and actuation instructions downstream, allowing the brain to indirectly steer the SoNS as a whole. To maintain agility, the interlevel control distribution in a SoNS is not strictly determined by the connection topology. Rather, any robot in a SoNS can set its own local actuation goals, trigger temporary SoNS-wide reactions, and adjust the weighting of its self-defined goals with those it receives.
The final aim of the SoNS concept is that a user should be able to program the whole robot swarm as if it were a single robot with a reconfigurable morphology and program multi-SoNS behaviors as if they were multirobot behaviors. For this aim, a program that runs on every robot manages how the brain can supervise and reconfigure its SoNS on demand, and this program can be used to directly specify the actuation goals of both the brain and the SoNS as a whole.
SoNS control algorithm and multirobot behaviors
At initialization, each robot is an independent single-robot SoNS, of which it is the brain by default. A multirobot SoNS can be established by merging two or more SoNSs, through communication between nearby robots. Each robot starts with mission-specific goals, the target graph of the SoNS that it would like to build, and a local copy of the SoNS control algorithm. The key components of this algorithm (Fig. 2) are as follows: update target graphs, update node attributes, manage connections to neighbors, transform input vectors (i.e., reference vectors received from neighbors) to the robot’s coordinate frame, classify sensor information, and update actuation instructions. Using these components, robots self-organize the following multirobot behaviors: merging, node allocation, splitting, collective sensing, and collective actuation.
Fig. 2. The key components of the SoNS control algorithm.
Each robot (A) updates its target graph (i.e., the target connection topology and target relative poses) and those of its children, (B) updates its node attributes, (C) manages its connections to neighbors, (D) transforms its input vectors into its own coordinate frame, (E) classifies sensor information, and (F) updates its actuation instructions. These components receive inputs from and send outputs to other components of the SoNS algorithm (black arrows between components), the robot’s other software layers (green), parent (blue) and/or children (pink), and other robots appearing in its FoV (yellow). See Materials and Methods for details.
Open in viewer
The foundation of the merging behavior is that every robot, whether a brain or the child of another robot, tries to recruit nearby robots. When two robots appear in each other’s field of view (FoV), they send each other messages to compete for recruitment. A robot rejects recruitment if it is or recently was in the same SoNS as the competitor or if the quality (which by default is randomly generated but can be redefined in mission-specific ways) of the competitor’s SoNS is lower than its own; otherwise, it accepts. If a robot accepts recruitment, it becomes the child of its competitor, splitting from its previous parent (if it had one) and merging into the SoNS of the new parent, bringing all its downstream robots (if it had any). For a recruited child to be assigned to a node in its parent’s target graph, it needs to undergo node allocation.
The node allocation behavior is based on each robot’s graph of the targets downstream from it, including graph attributes such as target relative poses. During node allocation, a robot can assign any child it has to a node in its target graph or pass it upstream or downstream to be handled by its parent or another of its children, if it has any. To decide, the robot tries to match its children with nodes in its and its parent’s target graphs on the basis of their (current versus target) relative poses and downstream vertex cardinalities. Children can be (re)allocated at every time step even if already assigned to a node. Thus, a parent can replace an already assigned child with one that is currently a better match, potentially demoting the formerly assigned child to an unassigned status. Using these node allocation operations, robots in a SoNS can be redistributed continuously within the various robots’ target graphs.
For collective sensing, a robot can gather feature-level sensor information itself (e.g., symbolic representations of detected objects’ types and relative poses) or receive it from any children it has. Each robot with a parent can classify features it has detected or received as features to react to locally, to forward to its parent, or to forward in all directions to trigger SoNS-wide reactions. If a robot has no parent, it instead inputs the features to a mission-specific BrainProgram (see Materials and Methods).
For collective actuation, if a robot is a brain, it uses the BrainProgram to define its own actuation instructions, including target velocities and target graph. If a robot has a parent, it acts as a semiautonomous follower using three types of reference vectors: local, based on locally defined goals and features detected nearby; hierarchical, received from its parent and based on the parent’s target graph; and “global,” based on goals or features that require SoNS-wide action, such as goals defined by the brain or detected features that present emergencies. Global reference vectors can be self-generated or received from any connected robot (parent or child) and are likewise forwarded to any connected robot that does not already have the respective reference. Nonbrain robots weight their various local, hierarchical, and global reference vectors to define their own target velocities.
The foundation of the splitting behavior is that, if a parent robot chooses to expel or is unintentionally disconnected from its child, the SoNS splits into two. The disconnected child will automatically resume being the brain of its own SoNS and will update its target graph accordingly. If the disconnected robot had any children, all its downstream connections are maintained, and the downstream robots can then be redistributed according to the updated target graphs.
Unique features of a SoNS
The primary contribution of the SoNS robot swarm architecture is that a robot system can integrate the manageability advantages of centralized systems without sacrificing the scalability, flexibility, and fault-tolerance advantages of self-organized systems. This contribution is based on four unique features (Fig. 1): self-organized controllable hierarchy, interchangeable leadership, explicit intersystem reconfiguration, and reconfigurable swarm behavior structures. Together, these features enable robot swarms to self-organize reconfigurable multilevel system architectures, including their communication structures, control distributions, and system behaviors.
The self-organized controllable hierarchy in a SoNS is built and maintained using communication only with nearby robots, not imposed from the outside, and comprehensively controllable (that is, the SoNS-wide multilevel structure can move from any initial state to any desired state in its configuration space of directed acyclic graphs). In other words, a SoNS hierarchy can be explicitly defined and redefined by the brain, and the desired changes occur through robots configuring and reconfiguring their local connections in a self-organized way. Existing robot swarms have shown emergent hierarchy (27) but not controllable hierarchy.
The interchangeable leadership in a SoNS means that all robots occupy an explicitly defined position in a hierarchy, but any robot, at any level of hierarchy, can be interchanged autonomously and on demand. The robots self-organize this interchange using communication only with nearby robots. For example, if the brain fails, the SoNS self-organizes to automatically and immediately substitute it with the nearest robot, which continues to specify the same SoNS structure and mission goals as the previous leader. Existing robot systems have included static explicit leaders or indiscriminate followers but not an explicit hierarchy of interchangeable leadership that is self-organized using communication only with nearby robots.
The explicit intersystem reconfiguration in the SoNS approach means that several SoNSs can split and merge themselves in a self-organized way that is coordinated by the brains of the SoNSs and uses communication only with nearby robots, without losing the existing substructures that could be retained. For example, several independent SoNSs could agree to merge simultaneously, and the robots would reorganize themselves around the new shared brain, retaining subsections of the old structures when possible. Existing robot systems have demonstrated splitting and merging of groups with unranked nonleader members (48, 49) but not splitting and merging of explicit substructures.
Reconfigurable swarm behavior structures in the SoNS approach mean that the interlevel control distribution and system behaviors (for example, which information sources influence which actions) can be explicitly reconfigured without breaking the system architecture. Reconfiguration can occur locally and temporarily to balance conflicting global and local goals; SoNS-wide for global sensing, actuation, and decision-making goals set by the brain; or locally for robot redistribution, for instance, to compensate for a failed robot. Existing robot swarms have included coordination networks that are fully dynamic but not explicitly reconfigurable across a multilevel system architecture.
RESULTS
To demonstrate the SoNS approach, we used real aerial-ground robot swarms (Movie 2) consisting of differential drive e-puck robots (50, 51) and our custom-developed S-drone quadrotors (52). To demonstrate the SoNS in swarms larger than our real arena allows, we also ran experiments in the simulator ARGoS (53), cross-verified against the behavior of the real robots (see Supplementary Results). Within each experiment, all robots ran local copies of the same SoNS algorithm and operated fully autonomously, without any global positioning system, remote control, or off-board sensing. The robots used vision-based relative positioning and were allowed to communicate wirelessly only if one robot was in the other’s FoV. Actuation was confined to motion.
We conducted four proof-of-concept robot missions that together demonstrated the key capabilities and unique features of the SoNS approach (see Supplementary Results and movie S1 for additional SoNS establishment experiments). We also conducted experiments to test scalability and fault tolerance in SoNSs. Accompanying online repositories provide all software used, all experimental data, and theoretical convergence and stability analyses.
Robot missions
All missions demonstrated self-organized controllable hierarchy, the first feature of the SoNS approach: Hierarchy was maintained despite external disturbances in the balancing global and local goals mission and was shown to be comprehensively controllable in the rest of the missions. The next features, interchangeable leadership and explicit intersystem reconfiguration, were demonstrated in the splitting and merging mission as robots reconfigured into different SoNSs and reconfigured their leadership allocations. Interchangeable leadership was further demonstrated in the fault tolerance results presented after the missions. The last feature, reconfigurable swarm behavior structures, was demonstrated in all missions: Reconfiguration was shown locally and temporarily in the balancing global and local goals mission and locally for internal redistribution in the rest of the missions, as well as SoNS-wide in the global sensing and actuation and binary decision-making missions. Together, the four missions demonstrated the ability to self-organize multilevel system architectures, including their communication structures, interlevel control distributions, and system behaviors.
For each mission, we report at least 5 trials with real robots (with 8 robots, up to 12 robots in the Supplementary Materials) and 50 trials in simulation (with up to 65 robots), with a maximum run time of 15 min (constrained by the battery capacity of the quadrotor platform). The goals and scope of possible behaviors for each mission were designed offline (Materials and Methods). We give the mission schematics, show that the qualitative goals of the mission were achieved, and assess the results in terms of mean actuation error E with respect to a lower bound B (Eqs. 2 and 4 in Materials and Methods). The mean error E with respect to lower bound B is meant to be a comprehensive metric that encapsulates all types of actuation error that can originate in the SoNS, such as errors in sensing and in decision-making, during reconfiguration, or while converging on a single shared SoNS.
Balancing global and local goals
The first mission shows obstacle avoidance (Fig. 3), in which robots in a SoNS negotiated the interlevel control distribution on the fly (i.e., adapting the degree of centralization or decentralization in the decision-making of the SoNS). The robots needed to balance the global goals of an overall motion trajectory and target topology, supervised by the brain, with the local goals of circumventing small obstacles. The obstacles were scattered in one section of the arena, and their positions and types were not known by the robots beforehand. In the two mission variants, either obstacles were larger than the ground robots, so that circumventing the obstacles was challenging (see Supplementary Results), or obstacles were roughly the same size as the ground robots and were positioned more densely, so that navigating through the gaps was challenging (Fig. 3A).
Fig. 3. Balancing global and local goals.
In this experiment, robots needed to navigate a field of obstacles scattered in one section of the arena while maintaining the bidirectional connections of the target graph. (A) Mission schematic: (1) The robots in the SoNS began moving across an environment with an unknown field of obstacles, searching for an object marking the final destination. (2) The robots moved through the obstacle field until (3) the SoNS surpassed the obstacle field and sensed the final destination object. (B to E) Results of the real robot experiments, in trials with eight robots. [(B) and (C)] In a real robot example trial (movie S2): (B) trajectories of robots over time, with the initial robot positions indicated in color and with an early (left) and the final (right) SoNS indicated in black, and (C) mean actuation error E (Eq. 2) with lower bound B (Eq. 4) plotted for reference. [(D) and (E)] Violin plots of E (Eq. 2) minus B (Eq. 4) in all real robot trials: (D) smaller and denser obstacles, five trials, and (E) larger and less dense obstacles, five trials. (F to I) Results of the simulated experiments, in trials with 50 robots, given in the same format: (F) trajectories and (G) error E with lower bound B in an example trial, with [(H) and (I)] violin plots of E – B in all simulated trials, 50 trials per variant.
Open in viewer
Robots began as members of a single SoNS, and the brain began with a straight trajectory in a given direction, searching for an object at an unknown position that marked the final destination. As the SoNS navigated the obstacle field, each ground robot that encountered an obstacle locally calculated its own reference vectors to avoid that obstacle. The robot then balanced the local goals it generated with the external goals it received, weighing them according to the relative position of the detected obstacle. When a robot that was not the brain detected the final destination object, it forwarded the sensor information upstream—once this information reached the brain, the brain stopped moving, and, as a result, the robots in the SoNS approached the target relative poses defined in the brain’s target graph.
In all trials, the robots completed the mission. In a typical experiment (Fig. 3, C and G), the actuation error dropped as the robots reached their initial target relative positions and then rose slightly and became more unsteady as the SoNS passed through the obstacle field; after exiting the obstacle field, the SoNS returned to negligible steady-state error. All trials reached a low steady-state error, in both reality and simulation, with the smaller, denser obstacle variant displaying slightly higher average error than the larger, less dense variant (Fig. 3, D, E, H, and I).
Collective sensing and actuation
The next mission shows sweeping (Fig. 4), in which a SoNS sensed and reacted to walls at unknown positions to keep the SoNS shape as wide as would fit until finding an object that marked the final destination. In this setup, the space between the walls got narrower as the SoNS progressed (Fig. 4A). Like in the previous mission, the robots began as members of one SoNS, and the brain began with a straight trajectory in a given direction. As robots at the extremities of the SoNS started to detect objects, they determined that the objects needed to be avoided locally in the short term and that this sensor information needed to be forwarded upstream. When a brain received information from its children about two walls on opposing sides, it triggered a change in the target graph. This resulted in a reorganization of the SoNS as the brain continued to move forward, and thus, while the robots in the SoNS were reconfiguring their connections, they also continued to encounter and react to new objects.
Fig. 4. Collective sensing and actuation.
In this experiment, robots needed to sweep the environment while collectively reacting to the width between two walls. (A) Mission schematic: (1) The robots in the SoNS began moving across an environment, searching for an object marking the final destination. (2) The robots sensed walls and reconfigured to a slightly narrower target graph (3) and then a much narrower target graph. (4) After sensing that the walls ended, the robots returned to their original target graph and sensed the final destination object. (B to D) Results of the real robot experiments, in trials with eight robots. [(B) and (C)] In a real robot example trial (movie S3): (B) trajectories of robots over time, with the initial robot positions indicated in color and with an early (left), an example intermediate (center), and the final (right) SoNS indicated in black, and (C) mean actuation error E (Eq. 2) with lower bound B (Eq. 4) plotted for reference. (D) Violin plot of E (Eq. 2) minus B (Eq. 4) in all five real robot trials. (E to G) Results of the simulated experiments, in trials with 65 robots, given in the same format: (E) trajectories and (F) error E with lower bound B in an example trial, with (G) a violin plot of E − B in all 50 simulated trials.
Open in viewer
In all trials, the robots completed the mission. The actuation error became low as the robots reached their initial target relative positions, spiking each time the brain initialized a new target graph and then declining gradually until the subsequent reorganization, with many small spikes occurring as robots at the edges of the formation detected the walls and robots in the SoNS adjusted their positions accordingly. The largest spikes occurred when both the target relative positions and the target topology changed (e.g., in Fig. 4C, compare the change involving only positions at approximately 115 s with the other two changes, at approximately 150 s and 220 s, which involved both topology and positions). In the simulated example trial, the same progression can be observed but with only two changes to the target graph (Fig. 4F). After the SoNS reorganized and reached the final destination object, it returned to low steady-state error in every trial.
Binary decision-making
The next mission showed reactive path planning (Fig. 5), in which a SoNS made a binary choice between possible paths and updated its trajectory accordingly, while also reconfiguring itself when obstacles were detected, until reaching an object that marked the final destination (Fig. 5A). As in the previous mission, the robots began as members of one SoNS, and the brain began with a straight trajectory in a given direction. When robots encountered small scattered obstacles, they responded in the same way as in the balancing global and local goals mission. When a robot detected one side of an opening in a wall, but not the other side, it sent this sensor information upstream. When a robot at any level in the hierarchy received sensor information that included both sides of an opening, it split from its parent and updated its quality according to the width of that opening to improve its chances in recruitment competitions. In this way, robots “bid” to become the new brain, and the swarm reached consensus by reorganizing around the robot that first detected the widest opening. The new brain then switched to a target graph that fit through the opening, and the SoNS continued forward until one of the robots detected the final destination object. When the brain received information about this object, it switched to a target graph that encircled the object.
Fig. 5. Binary decision-making.
In this experiment, robots needed to sweep the environment, making a binary choice between two possible paths. (A) Mission schematic: (1) The robots in the SoNS began moving across an environment, searching for an object marking the final destination. (2) After surpassing an obstacle field, the robots sensed a wall, collaboratively chose the widest opening, and adjusted the path of the SoNS to pass through it. (3) The robots sensed that the walls ended and then sensed the final destination object and changed their target graph to surround it. (B to D) Results of the real robot experiments, in trials with eight robots. [(B) and (C)] In a real robot example trial (movie S4): (B) trajectories of the robots over time, with the initial robot positions indicated in color and with an early (left), an example intermediate (center), and the final (right) SoNS indicated in black, and (C) mean actuation error E (Eq. 2) with lower bound B (see Eq. 4) plotted for reference. (D) Violin plot of E (Eq. 2) minus B (Eq. 4) in all five real robot trials. (E to G) Results of the simulated experiments, in trials with 65 robots, given in the same format: (E) trajectories and (F) error E with lower bound B in an example trial, with (G) a violin plot of E − B in all 50 simulated trials.
Open in viewer
In all trials, the robots completed the mission. Because of the complexity of the mission, the actuation error experienced several spikes (Fig. 5, C and F). However, after these spikes, the robots in every trial converged to a graph encircling the final destination object with low steady-state error.
Splitting and merging
The last mission showed search and rescue (Fig. 6), in which SoNSs split and merged to reunite with missing robots. At initiation, one or more single-robot SoNSs were isolated somewhere in the environment, waiting there to be found by a rescue team. There was also a primary multirobot SoNS somewhere in the environment. After noticing that its SoNS was incomplete, the brain of this SoNS started a rescue mission to find missing robots (Fig. 6A) by issuing instructions downstream for a specific node in its target graph to split away and activate its “rescuer” program. When the robot at that node received the message, it split from its parent and automatically became a brain. It also lowered its quality so that it could resume its old membership upon returning. When robots in the newly split rescuer SoNS detected objects, they responded in the same way as they did in the collective sensing and actuation mission. The brain then used sensor information about these objects to follow them until its SoNS had found and recruited the correct number of robots for its target graph, after which it backtracked along the same objects. When the rescuer SoNS encountered its former SoNS, it got re-recruited, and the two SoNS remerged. In an alternative mission variant (see Supplementary Results), the primary SoNS knew the direction of its missing robot but needed to physically push an obstruction out of the way and then merge with the missing robot and guide it out of a convex barrier.
Fig. 6. Splitting and merging.
In this experiment, robots needed to conduct multi-SoNS search and rescue to reunite with a missing robot(s). (A) Mission schematic: (1) Robots started in a SoNS that was missing a member. (2) The brain instructed one of the robots to split and temporarily form its own multirobot SoNS as a rescue team. The rescue team SoNS searched a passage in the environment until it found the missing robot and merged with it. (3) The rescue team SoNS returned to the initial split location and remerged with the remaining SoNS, reuniting all robots. (B to D) Results of real robot experiments, in trials with eight robots. [(B) and (C)] In a real robot example trial (movie S5): (B) trajectories of robots over time, with the initial (in color) and final (in black) positions indicated, and (C) mean actuation error E (Eq. 2) with lower bound B (Eq. 4) plotted for reference. (D) Violin plot of E (Eq. 2) minus B (Eq. 4) in all five trials.
Open in viewer
In all trials, the robots completed the mission. The actuation error rose during the periods of reorganizations, but all robots remerged into one SoNS, and the system returned to a low steady-state error (Fig. 6, C and D).
Scalability
We demonstrated the scalability of the SoNS architecture in the binary decision-making mission with four different system sizes up to 125 robots (50 trials per system size) and in simple SoNS establishment with 50 different system sizes up to 250 robots (30 trials per system size). Given that the real arena size was limited, we ran the scalability experiments only in simulation. We also disregarded the battery capacity of the quadrotor platform in these experiments.
In the binary decision-making experiments (Fig. 7, A and B; movie S6; and Supplementary Results), the robots completed all parts of the mission successfully, providing proof of concept that the demonstrated capabilities of the SoNS approach do not break down in larger swarms (up to 125 robots): The SoNS can balance global and local goals, collectively sense and react to an environment, make a collective binary decision, and reconfigure when needed, all without breaking the system architecture.
Fig. 7. Scalability study.
Results in simulation with up to 250 robots (20% aerial, 80% ground). (A and B) An example trial of a 125-robot SoNS completing the binary decision-making mission (movie S6): (A) trajectories of robots over time, with the initial robot positions indicated in color and with an early (left) and the final (right) SoNS indicated in black and (B) mean actuation error E (Eq. 2) with lower bound B (Eq. 4) plotted for reference. (C to F) Scalability study when robots simply established a SoNS (example trials in movie S7), with the number of robots increasing from 5 to 250 in steps of 5, 30 trials per system size. (C) Mean actuation error E (Eq. 2) throughout the experiment (purple bars) and after the SoNS converged (red bars); (D) communication: maximum bytes of messages of any robot per step, after the SoNS converged; (E) computation: maximum CPU clock cycles of any robot per step, after the SoNS converged; and (F) convergence time.
Open in viewer
In the SoNS establishment experiments (Fig. 7, C to F, and movie S7), we aimed to test the scalability limits of the SoNS architecture under the current software implementation. We ran experiments with system size n = {5,10,15, …, 250} robots (30 trials for each system size) and a maximum experiment time of t = 500 s for n ≤ 125 robots and t = 4n + 4(n−125) s for 125 < n ≤ 250 robots (see dashed line in Fig. 7F). In system sizes of n ≤ 125 robots, all trials converged before the maximum experiment time. In systems of 125 < n < 220 robots, one or two trials per system size did not converge before the maximum time (approximately 5% of trials, on average). In systems of 220 ≤ n ≤ 250 robots, approximately 20% of trials did not converge before the maximum time. In trials that did converge (Fig. 7F), the mean convergence time rose superlinearly, with the rate of change increasing most noticeably after system sizes of 150 robots. We therefore consider the performance of the current SoNS implementation to be fully reliable in system sizes up to 125 robots, to be somewhat stable until 220 robots, and to degrade substantially in larger systems.
Within SoNS establishment trials that converged, the error increased with the number of robots (see purple bars in Fig. 7C), slowly at first and more substantially in systems larger than 100 robots. This trend can be mostly attributed to the rising Euclidean distance between the starting positions and the target positions in the eventual SoNS—i.e., the greater the number of robots is, the higher the lower bound of the error. After SoNS convergence (see red bars in Fig. 7C), when the starting positions were no longer relevant, error increased only slightly with system size and always remained low (less than E = 0.5 m).
In SoNS establishment trials that converged, we also measured the communication load and the computational work, respectively, in terms of maximum bytes of messages of any robot and maximum CPU clock cycles of any robot, per step. Note that all simulations ran the same software modules as those run on the real robots (see Supplementary Methods), and each simulated trial that was used to assess computational work was a single-threaded program. The results show that, in system sizes of 50 robots or more, the communication load nearly plateaued (Fig. 7D), and the mean CPU cycles rose only slightly, with a moderate increase in variability (Fig. 7E). The rise in communication load that occurred in small swarm sizes (Fig. 7D) is in part a function of the maximum communication range and maximum robot density (due to minimum safety distances). For small swarm sizes, the average number of robots in each robot’s FoV (including both connected robots and unconnected robots that might be candidates for recruitment operations) grew with swarm size until the robot density reached its upper limit, after which the average number of robots in each robot’s FoV plateaued (at approximately 50 robots). The similar rise in computational work that occurred in small swarm sizes (Fig. 7E) is in part a function of the targeted number of connections per robot. For the small swarm sizes, the average targeted connections per robot rose until the swarm size reached 35 robots or more, after which the average targeted connections plateaued (at approximately eight connections per robot). We conclude that the SoNS architecture can be considered scalable in these proof-of-concept missions in terms of overall communication and computation loads.
Fault tolerance
We demonstrated several aspects of fault tolerance in SoNS, in real and simulated swarms. First, using real robots, we showed replacement of a single robot that has failed permanently (see online repository), including a failed brain (movie S8). In these demonstrations, one robot was remotely triggered to fail (for the aerial robots, this included immediately landing in place). Then, a new robot of the same hardware type was manually placed in the arena and switched on, after which it was recruited by the SoNS. When a brain robot or a robot at an inner hierarchy level failed, it was immediately and automatically replaced by another robot already in the SoNS, and the robots redistributed around the change. Then, when a new robot was recruited, it filled the vacancy in the reorganized SoNS.
Using real robots, we also demonstrated reorganization in high-loss conditions (Fig. 8, A to C), i.e., after arbitrary permanent failures when the failed robots cannot be replaced. The collective sensing and actuation mission setup was used, with five trials conducted. The robots started the mission as one SoNS, and, after failure occurred, the SoNS continued the mission with the robots still available. The full set of results (see online repository) shows that when ground robots failed, the rest of the robots were able to stay connected in one SoNS and complete the mission, whereas when an aerial robot failed, some of the ground robots downstream from it were disconnected from the primary SoNS, but the remaining connected robots were able to continue the mission. For example, in the trial shown in Fig. 8 (A and B), one of the aerial robots failed (see purple star in Fig. 8A) at approximately 85 s (see red dotted line in Fig. 8B). The only aerial robot that remained functional recruited the ground robots that remained functional and reachable and continued with the mission, eventually reaching the object marking the final destination. In all trials in which at least one robot of each type remained functional, the SoNS was able to reorganize itself with the remaining robots and continue with the mission, resulting in relatively low overall error for all trials (Fig. 8C).
Fig. 8. Fault tolerance study.
Results are presented with real robots and in simulation, testing both permanent failures (up to two-thirds of the robots) and temporary system-wide failures of communication or vision. (A to C) High-loss conditions with real robots: arbitrary permanent failures of multiple robots in an eight-robot SoNS. [(B) and (C)] In a real robot example trial (movie S9): (A) trajectories of robots over time, with the initial robot positions indicated in color and with an early (left), an example intermediate (center), and final (right) SoNS indicated in black, with the failed robots indicated in purple at their shutdown positions, and (B) mean actuation error E (Eq. 2) with lower bound B (Eq. 4) plotted for reference. (C) Violin plot of E (Eq. 2) minus B (Eq. 4) in all five trials. (D to F) High-loss conditions in simulation: 33.3¯ or 66.6¯% failure probabilities in a 65-robot SoNS. [(B) and (C)] In a simulated example trial with 66.6¯% probability for each robot to fail (movie S10): (D) trajectories of robots over time, with the initial robot positions indicated in color, with an early (left) and final (right) SoNS indicated in black, and with the failed robots indicated in purple at their shutdown positions; and (E) mean actuation error E (Eq. 2) with lower bound B (Eq. 4). (F) Violin plot of E − B in all trials with both 33.3¯ and 66.6¯% failure probabilities, 50 trials per probability. (G and H) System-wide vision failure for 30 s in simulation, in a 65-robot SoNS: (G) E in an example trial (movie S11) and (H) violin plots of E − B in all 50 trials, compared with 50 trials without failure. (I and J) System-wide communication failure for 30 s in simulation, in a 65-robot SoNS: (I) error E with lower bound B in an example trial (movie S12) and (J) violin plots of E − B in all 50 trials, compared with 50 trials without failure.
