Branched Structure Formation in a Decentralized Flock of Wheeled Robots

Abstract

Swarm robotics studies how a large number of relatively simple robots can accomplish various functions collectively and dynamically. Modular robotics concentrates on the design of specialized connected parts to perform precise tasks, while other swarms exhibit more fluid flocking and group adaptation. Here we focus on the process of morphogenesis per se, i.e. the programmable and reliable bottom-up emergence of shapes at a higher level of organization. We show that simple abstract rules of behavior executed by each agent (their “genotype”), involving message passing, virtual link creation, and force-based motion, are sufficient to generate various reproducible and scalable multi-agent branched structures (the “phenotypes”). On this basis, we propose a model of collective robot dynamics based on “morphogenetic engineering” principles, in particular an algorithm of programmable network growth, and how it allows a flock of self-propelled wheeled robots on the ground to coordinate and function together. The model is implemented in simulation and demonstrated in physical experiments with the PsiSwarm platform.

1 Introduction

Swarm robotics studies how multiple relatively simple robots can accomplish various functions collectively and dynamically  [2]. Boosted by recent advances in hardware technologies, the field is expected to bring many benefits as robot swarms can cover vast areas, decentralization is robust against individual failures (allowing replacements), and local communication with neighbors consumes less energy. Its core challenge, however, is to design or rather “meta-design”  [4] the motion control and collective self-assembly of robots to make them operate as a single entity, whether physically connected or loosely aggregated. Meta-designing a complex system consists of finding the rules that each agent should individually follow to interact with others, decide, act, or even evolve new rules.

Background. Some swarm systems contain a large number of simple and cheap mobile robots, creating a dense “herd” such as the Kilobot platform  [19]. On the ground, units cluster together to maintain local communication and possibly display patterns, typically guided by “chemotaxis” based on virtual pheromones. Other works experiment with smaller flocks of unmanned aerial vehicles for indoor exploration  [20], also examining self-reconfiguration in case of faulty rotors  [9], or schools of (sub)marine robots performing synchronous encounters  [23] and cooperative load transport  [12]. At the other end of the spectrum, great effort can be spent on the design of sophisticated parts and actuators capable of physical attachment to achieve “modular robotics”  [1]. In these cases, a limited number of units generally only permit sparse and precise formations, such as chains and T-junctions, typically by recursive attachment.

Historically, the Modular Transformer (m-tran)  [15] was one of the first self-reconfigurable robotic kits. A group of m-trans can be placed in a certain initial state and go through a series of moves to achieve some target shape. Swarm-Bot  [11] is a self-assembling system comprising smaller mobile robots called s-bots, which use mounted grippers and sensors/actuators (LEDs, camera) to cling to each other or static objects, following behavioral rules and local perception. Using the s-bot model, SwarmMorph  [3, 17] is a morphogenetic model based on a script language able to produce small 2D robot formations to achieve certain tasks. As for the symbrion project  [13], it created an intricate piece of hardware in the form a cube that could dock precisely with its peers: the vision was to collectively form “symbiotic” robotic organisms that could move in 3D.

In recent years, modular robot systems have become more commonplace thanks to cheaper and faster hardware. For example, HyMod  [18] is a set of cubic modules with full rotational freedom, which can combine to create 3D lattice structures such as snakes or wheeled vehicles. The Soldercube  [16] is a similar building-block rotational unit equipped with magnetic ties and internal sensors to detect its orientation and occupied faces. Resting on top of a planar lattice of anchors, Soldercubes are able to transform their spatial arrangement by picking up and dropping off each other through attach/turn/detach combinations of moves. The Evo-bot  [8] is another modular concept intended to physically implement the growth of artificial “creatures” as compounds of differentiated robotic modules, each one with a specific function such as resource harvesting or motion control. “Soft robotic” designs  [22] also attempt to mimic cell aggregation with pneumatic and magnetic cubic elements that can shrink and inflate, giving rise to organisms capable of locomotion.

Motivation. The variety of systems briefly reviewed above is only a small sample of what is done in collective and modular robotics. Again, while some works focus on the design of specialized modules to generate super-robots that can perform specific tasks, others are rather inspired by artificial life swarms capable of fluid flocking and group adaptation. Few works, however, seem to pay much attention to the process of morphogenesis per se, i.e. the programmable and reliable bottom-up development of shapes at a higher level of organization. This will be our own focus: we want to show here that simple abstract rules of behavior executed by each agent (their “genotype”), involving message passing, link creation, and force-based motion, are sufficient to generate various reproducible and scalable multi-robot structures (the “phenotypes”) by aggregation. Ideally, agent rules are independent of its physical embodiment—but of course we also present a proof of concept using real robots.

In summary, between swarm and modular robotics, the goal of the present work is to create flexible, yet at the same time highly specific spatial formations within a larger group of small wheeled robots, based on Morphogenetic Engineering (ME) principles. The field of ME  [5, 6] investigates the subclass of complex systems that self-assemble into nontrivial and reproducible structures, such as multicellular organisms built by cells, or the nests built by colonies of social insects. These natural examples can serve as a source of inspiration for the meta-design of self-organizing artificial and techno-social systems. In particular, we will follow here Doursat’s abstract ME algorithm of “programmable network growth”  [7]—which was later modified and hypothetically applied to the autonomous deployment of emergency response teams forming chains of agents using IoT devices  [21].

The rest of the paper is as follows: In Sect. 2, we describe the abstract model of collective robot dynamics based on ME principles applied to network growth. We present the underlying mechanisms allowing a small swarm, or “flock”, of self-propelled robots on the ground to coordinate and function together. Then, we show how the model unfolds in simulation (Sect. 3) and physical experiments (Sect. 4) to generate different structures.

2 Model

The “meta-design” methodology of this project consists of hand-made rules programmed in all agents to foster the development of a multi-robot structure. Given different rules, robots are able to form different target shapes by making local decisions based on what they detect and exchange with their neighbors.

Ambient Space: Neighborhoods and Forces. We consider a distributed, multi-agent system where each agent only relies on local perception of the environment to control its behavior and communicates with the agents that it detects in its vicinity. All the computational logic is embedded in the agents to obtain a fully decentralized system. At an abstract level, each agent represents a single robot potentially equipped with the following limited features and capabilities: a set of proximity sensors (infrared and/or ultrasonic) placed around the robot to detect nearby obstacles, evaluate distances and avoid collisions; a communication module to exchange messages with neighboring robots; a transportation module including wheels and motors to move around autonomously; and a small camera to identify the average position of the other agents (the center of mass of the flock).

The definition and computation of each agent’s neighborhood is central to the cohesiveness of a collective robotic organism, as it ensures the proper coordinated propagation of information across the structure. To this aim, we use a hybrid “topological-metric” type of neighborhood implemented by a modified Delaunay triangulation, chosen for its accurate representation of physical contacts and robustness to change. The modification consists of pruning connections that are longer than a given threshold, set just below the average minimum distance of uniformly distributed agents in space in order to accommodate real-world constraints (Fig. 1a). Since the Delaunay triangulation is not metric-based, far away robots may also be connected and this is why a cutoff length was introduced to prevent unrealistic long-range communication.

Fig. 1.

Neighborhoods and forces. (a) Example of a Delaunay graph among a dozen agents where connections are trimmed (dashed lines) above a given cutoff distance D. (b) Two connected agents i and j at distance d exert virtual and opposite elastic forces of magnitude $F\!=\!k|d - L|$ onto each other (implemented by wheel-based movements, see later sections), where L denotes a free length and k a rigidity coefficient. If $d > L$, i and j move toward each other; otherwise, they pull apart.

Each neighborhood connection also carries a virtual spring creating elastic forces (Fig. 1b), which translates into wheel-based movements by each agent to stay at a certain optimal distance from its neighbors, neither too close to avoid collisions, nor too far to remain within signal range.

Network Components: Ports, Links and Gradients. The morphogenetic core of the model is derived from Doursat’s original algorithm of programmable network growth  [7]. It involves input/output ports on the nodes, links between nodes (on top of their neighborhood connections), and gradients (integer values) sent and received by the nodes over the links through the ports. All agents are endowed with the same set of pairs of input/output ports, denoted by $(X_\mathrm {in}$, $X_\mathrm {out})$, $(Y_\mathrm {in}$, $Y_\mathrm {out})$, etc. A port can be in one of three states: “open”, where it accepts (in input) or creates (in output) links with neighbors; “busy”, where it is already linked to a maximum number of agents (generally one) and cannot accept or create new links; and “closed”, where it is disabled and devoid of links. An open input port on agent i can accept link requests originating only from its mirror output port located on a neighboring agent j, for example: $X_\mathrm {in}^i\leftarrow X_\mathrm {out}^j$ (but not $X_\mathrm {in}^i\leftarrow Y_\mathrm {out}^j$ or $X_\mathrm {in}^i\leftarrow X_\mathrm {in}^j$).

Each type of pair of ports is associated with a gradient field across the network, composed of integer values representing important positional information about the nodes relative to each other within the topology (essentially their hop distance), and denoted by $x^i_g$, $y^i_g$, etc. When a link $i\leftarrow j$ is created between two agents, the gradient associated with the ports is propagated through this link from j to i via an increment, i.e. $x^i_g\!=\!x^j_g + 1$ if it concerns the X ports. Then both agents switch the corresponding ports to the busy state.

Fig. 2.

Simple chain formation among static agents. Each agent executes Algorithm 1 (non-bracketed parts) with $x_N\!=\,4$. Ports are symbolized by thick arrows (inputs as tails, outputs as heads) and color-coded states: open in blue, busy in green, closed in red. Nodes are also colored: recruiting in blue, accepting in gray, integrated in green. Edges can be of two types: neighborhood connections in black, structural links in green. (a) Initial state: gradient $x^1_g$ is set to 0 in a seed Agent 1 and undefined everywhere else. (b) Agents 1 and 3 agree on creating a chain link and propagate the gradient, i.e. $x^3_g\!=\!1$. (c,d) The chain continues to grow, with Agent 3 recruiting 2, and 2 recruiting 4 in turn. This results in $x^2_g\!=\!3$, which reaches the given threshold $x_N$ (the maximum length) prescribed in the genome, therefore shuts the output port $X_\mathrm {out}^2$ and ends the chain. (Color figure online)

In the context of collective robotics, this abstract port-link-gradient framework translates into the self-organization of branched structures made of chains of robots (Figs. 2 and 3). These structures are a subset of the background communication mesh described above. Therefore, at every time step each agent may have two types of neighbors: ones that are simply within signal range, or “connected” (thin black edges), and ones that are formally and durably “linked” to it (thick green edges)—albeit not physically for lack of hooks or magnets.

Within a static connectivity graph, network growth proceeds by peer-to-peer recruitment and aggregation of agents as follows: if agent j is already part of the growing structure and has an open output port $X_\mathrm {out}^j$, it will look if one of its neighbors i has a corresponding open input port $X_\mathrm {in}^i$ (i.e. is not yet in the structure) to request a link creation—which it does by sending requests to each neighbor in turn.

The specifics of the growth process (which ports to open or update, how many links to create in a chain, etc.) are prescribed by an identical set of rules, or “genome”, executed by each agent. The genome dictates how an agent should behave, i.e. the local decisions it should make at every time step, which will vary depending on its current neighborhood configuration and the gradient values it carries. In essence, a genomic ruleset is composed of a list of condition$\rightarrow$action clauses, where conditions are based on gradients and port states, and actions update the ports. Examples of genomes and structures developed from them are shown in the next subsection.

In the beginning, agents are scattered at random across the arena. One agent is chosen to be the seed of the structure and is initialized differently from the others. Typically its input port is closed, its output port open, and its gradient value set to 0. Conversely, all other agents start with open inputs, closed outputs, and undefined gradients at $-1$. Then, each agent repeatedly executes four main steps in a loop: (a) port states are changed according to the genomic rules; (b) links are created where possible; (c) gradient values are propagated and updated; and (d) the robot moves by applying spring forces and/or a search behavior. The latter step is explained below in the subsection about mobile network growth.

Examples of Genomes and Structures. In this section, we give two examples of abstract network growth among static agents on top of their background communication graph, omitting spring forces and motion. The first system involves four agents forming a simple chain based on one pair of X ports (Fig. 2). The genome is described in Algorithm 1 (non-bracketed parts only), where $x_N$ is set to 4. As explained above, at first ($t\!=\!0$) the unique seed agent is initialized differently from the other agents. Then, as soon as an agent is recruited into the structure, its gradient $x_g$ becomes positive by propagation and triggers the opening of the output port $X_\mathrm {out}$, unless $x_g\!=\!x_N - 1$, which means that it found itself at the end of the chain and should close $X_\mathrm {out}$.

The second example shows a slightly more complicated branched structure, or “creature” composed of a “body” chain of five agents and two short “leg” chains of two agents each, sprouting from the even-positioned body agents (Fig. 3). Ports X are used to form the body, while different ports Y support the legs. The genomic rules are described in Algorithm 1, with $x_N\!=\!5$ and $y_N\!=\!3$. Compared to the previous example, the added complication consists of managing ports Y and their associated gradient $y_g$ depending on certain values of $x_g$. Here, if $x_g\!=\!1$ or 3 it means that the agent is second or fourth along the main chain, therefore it should open its other output port $Y_\mathrm {out}$ and set $y_g\!=\!0$ to start a branch by recruiting free agents via $Y_\mathrm {in}$. For branch termination, the same condition is used in Y, i.e. closing $Y_\mathrm {out}$ when $y_g\!=\!y_N-1$.

Fig. 3.

Branched structure formation among static agents. Each agent possesses two pairs of ports, X and Y (not represented), and executes Algorithm 1 with $x_N\!=\!5, y_N\!=\!2$. Color coding is the same as Fig. 2, with red lines symbolizing Y links (leg branches). (a) Seed is Agent 1, which recruited Agent 9 via an X link, thus starting the body chain. Then, Agent 9 applying both $X_\mathrm {out}$ and $Y_\mathrm {out}$ opening rules recruited Agent 3 on X (extending the body) and Agent 4 on Y (starting a leg branch). The main chain then continued with Agent 5, which was also preparing to grow a second le.g. (b) Finished structure, where all agents have satisfied the rules and no more recruitment is attempted. (Color figure online)

Mobile Network Growth in Space. In reality, as robots move around, the background mesh is not static but continually updated (as per Fig. 1a) so that new connections may appear and existing ones disappear. In spite of this, already created structural links will persist: if communication between linked robots is accidentally interrupted, they keep tabs on each other and resume regular gradient exchange whenever possible. This should rarely happen, however, as elastic forces tend to keep them close to each other, as if physically attached.

To maximize matching opportunities, agents not yet recruited navigate toward, and stay close to, the existing structure. If an agent finds itself isolated far away without neighborhood connections, it uses the camera to search for the bulk of the flock and head over there. When its front proximity sensors detect a close obstacle, then two scenarios can happen: ($\alpha$) in simulation (Sect. 3), it initiates a clockwise exploration behavior by turning left and keeping its right-side sensors active until it receives a link request; ($\beta$) in the physical experiments (Sect. 4), it just sticks near the first encountered neighbor(s) by applying default elastic forces. In this last case, an added condition is to receive a “connected-component” flag propagated from the seed agent over the graph connections: if it does not get it, then it moves again toward the flock’s center.

To be more precise, different types of springs are used or not depending on the local state of neighboring nodes. Three cases can be distinguished: (i) if both nodes are integrated into the structure and linked to each other, then a strong attractive elastic force is applied between them with a coefficient $k_\mathrm {att}$ and a length $L_\mathrm {att}$ significantly smaller than the cutoff communication distance D to keep them close; (ii) if both nodes belong to the structure but are not directly linked (yet spatially close, e.g. if the chain is folded), then a weak repulsive force is used to pull them apart, with a coefficient $k_\mathrm {rep}$ and a length $L_\mathrm {rep}$ greater than or about equal to D; (iii) if one or both nodes are outside of the structure, then two variants happen: (iii. $\gamma$) in simulation, no spring force is applied and the free agents rely on proximity sensing for their search behavior (the linked agents ignore them when calculating their forces); (iii. $\delta$) in the physical experiments, the repulsion force $L_\mathrm {rep}, k_\mathrm {rep}$ is used to keep them at an optimal distance.

Altogether, this combination of attractive and repulsive elastic forces leads the robot flock to form a tight chain-like structure visible to the naked eye (although without physical links) while at the same time making this structure unfold in space.

Fig. 4.

Branched structure formation in simulation. Bottom: screenshots of the morse display at time steps $t\!=\!0, 13, 94, 385$. Top: custom 2D visualization tool based on log files at same time steps with color code of Fig. 3. Each virtual robot executes Algorithm 1 with $x_N\!=\!7, y_N\!=\!3$. The 13 robots self-organize into a 7-robot chain body with three 2-robot legs at odd-numbered positions. This network structure also unfolds in space under the influence of the spring forces with parameters $D\!=\!3.56d, L_\mathrm {att}\!=\!1.8d, k_\mathrm {att}\!=\!1, L_\mathrm {rep}\!=\!5.4d, k_\mathrm {rep}\!=\!0.5$, where d is a robot’s diameter and $d\!=\!0.5$ morse unit. The simulation stops at $t\!=\!427$ when robots cannot form new links and elastic forces have reached equilibrium. Videos available at https://tinyurl.com/gaget20.

3 Simulations

Before trying our model with real robots (see Sect. 4), we implemented it in a realistic simulation. This allowed us to test and adjust the model more flexibly, in order to prepare the ground toward bridging the reality gap with the physical experiments. To this aim, we chose the morse simulator environment¹, a platform written in Python and powered by the Blender physics engine. morse offers accurate representations, physics simulation and detailed graphic display of robotic components and external objects. In our case, each agent is instantiated by an autonomous low-height cylindrical robot endowed with its own virtual control and sensorimotor abilities: two wheels and motors, eight infrared proximity sensors on its periphery, and a communication module for short-range broadcast. For simplicity, the turret camera is not simulated but replaced by global information about the center of mass of the flock sent to the robots that needed it. A Python script encoding the behavior of the simulated robots, including their genomic rules of self-assembly, is running in parallel with the morse engine.

The simulated experiment shown here is a flock of 13 robots forming a branched structure based on the complete genome of Algorithm 1 (Fig. 4). In addition to the networking rules, spatial motion relied on the exploration behavior and the spring forces as explained above at the end of Sect. 2 in items ($\alpha$) and (i–iii. $\gamma$) with the parameter values specified in the caption.

Fig. 5.

Formation of linked structures in a flock of wheeled robots. (a) The PsiSwarm platform: i. mother board, ii. lcd screen, iii. infrared sensors, iv. wheels & motors, v. joystick, and vi. battery. (b–g) 20 PsiSwarm robots execute Algorithm 1 (in full) with $x_N=5, y_N=3$ inside a 170 $\times$ 180 cm arena. (b-f) Top views from the ceiling camera at times $t=4, 13, 26, 45, 100$ s. Structural links (thick green & red) and graph connections (thin white) are automatically visualized by ARDebug in real time. (b) Shortly after initialization, the seed robot psw_15 created a first link with a neighbor. (c) Search behavior and spring forces bring robots closer, while two more body links (green) and one leg link (red) appeared. (d–f) The branched structure continued growing until it was complete and stabilized (robots stopped moving) under the attractive/repulsive forces, with parameters $D=43.2$ cm, $L_\mathrm {att}=11$ cm, $k_\mathrm {att}=0.6$, $L_\mathrm {rep}=32.4$ cm, $k_\mathrm {rep}=0.42$. (g) Same final state in perspective view. (h, i) Other examples of “phenotypes” based on Algorithm 1: (h) a simple 9-robot chain and (i) a 3 + 6-robot T-shape. Videos of all three experiments available at https://tinyurl.com/gaget20. (Color figure online)

4 Physical Experiments

The PsiSwarm platform, a disc-shaped robot on wheels, was designed by James Hilder and Jon Timmis at the York Robotics Lab². It runs on Mbed OS, an open-source real-time operating system for the Internet of Things. Its control code in C++ is uploaded to the board via a USB link. PsiSwarms are equipped with the following components (Fig. 5a): an Mbed LPC1768 Rapid Prototyping Board, the heart of the operation containing the code, plus a Micro-USB plug and a Bluetooth emitter/receptor; an LCD screen; eight infrared sensors placed at quasi-regular intervals around the robot; two wheels and motors; a small joystick to input commands into the robot; and a single battery.

To centrally monitor the PsiSwarms in real time, whether to read out their trajectories or intervene in the experiment, we relied on the ARDebug software [14], an augmented-reality tool that can track the robots with ArUco square markers pasted on top of them  [10] (each one carrying a binary pixel matrix that encodes a unique ID number; Fig. 5g–i), and can exchange information with them via Bluetooth. The software uses a top-down bird’s-eye camera (mounted on the ceiling) to evaluate the location of every PsiSwarm and link this information with the right Bluetooth sockets to communicate with them individually. This allowed us to send to/receive from each robot data, both in the beginning (e.g., whether it is the seed) and during the experiment. However, although it is in principle possible to transfer the genomic code Algorithm 1 in that manner, the executable was instead input into each robot by hand using a USB cable.

Toward our goal of flock formation, we faced three technical issues: (1) the IR sensors are not powerful enough to detect the positions of neighboring robots beyond a few cm; (2) PsiSwarms are not equipped to communicate locally with each other; (3) they also lack a turret camera to spot the flock from afar. To compensate for these shortcomings, we had to infringe somewhat the principle of decentralization by resorting to proxy-mediated detection & communication. Thanks to the ceiling camera and ArUco markers, (1) the Delaunay neighborhoods were computed centrally by ARDebug and fed back to the robots (in the form of relative angle-distance pairs); (2) this information also served for ARDebug to broker peer-to-peer requests via the Bluetooth links; and (3) stray robots received from ARDebug the direction back toward the flock.

On the other hand, we also made sure to keep the intervention of ARDebug to a minimum, i.e. only provide the robots with the raw, low-level information from their surroundings that they could have otherwise gathered by themselves with more hardware. In no instance was ARDebug actually controlling the robots and telling them what messages to send and how to move; these calculations and decisions were made by each of them. Based on the relative positions of its neighbors (obtained from its fictive detectors via ARDebug), and its internal table of structural links and graph connections, each robot could compute its total vectorial force and next move, as per items (i–iii. $\delta$) above—or head for the flock and apply protocol ($\beta$) if it was stranded far away. Three resulting formations are shown in Fig. 5b–i.

5 Conclusion

In conclusion, we proposed a morphogenetic engineering model and a demonstration of self-organized branched structure formation among small identical wheeled robots, based on local neighborhood perception and communication only. We showed that it was possible to implement an abstract model of programmable network growth both in simulation and physical experiments.

The technical problems encountered in the experiments were essentially due to limitations in the PsiSwarm’s capabilities. Its lack of hardware for mid-range peer-to-peer detection & communication, and flock recognition, had to be remedied by the central monitoring system ARDebug, which tracked robots and brokered information and message-passing among them. ARDebug’s role, however, remained minimal in the sense that it only emulated the neighborhood data that would otherwise be handled by extra sensors and emitters, while the core computation and decision-making modules remained on board.

Beyond these workarounds, the experiments presented so far are encouraging, although at this point they only constitute a proof of concept. To complete this study, an extended statistical analysis over many trials, whether exploring different genotypes or variable random conditions on the same genotype, should be conducted to adjust parameters and establish the resilience of the model in real-world settings. In addition, simulations and experiments with more robots must be conducted to insure the scalability of our model. For future work, more complex branched chains or loops involving other port types and a larger swarm could be attempted. Last but not least, the loose flocking structures thus created should demonstrate their usefulness by moving across space and behaving as single cohesive “creatures”. Even deprived of physical hooks, they should be able e.g.. to encircle and push bulky objects—or interact in any other way with their environment via specialized differentiated robots and division of labor, similar to multicellular organisms.