These are my notes on papers and literature reviews I read in swarm robotics, as I begin to familiarize myself with the field! My first pass, at least, is based on "A review of swarm robotics tasks," by Levent Bayindir, published in 2016 in the journal Neurocomputing. It's very well-written, and though it's justifiably dense, it is pretty easy to follow. It can be found here.
Bayindir's work breaks down the literature by the application of the research - what goal the swarm is trying to achieve. I'll present the summary in the same order, and then branch off into other specific works as I come across them. All of the references can be found in the original paper.
Swarm robotics studies large groups of robots. One set of criteria used to distinguish swarm robotics work is as follows:
The main goals of a swarm system are "scalability, flexibility, and robustness." Swarm systems are inspired by behavior found in nature that fulfills these goals: coordination of insects such as bees, ants, or termites, or even larger animals such as beavers. Essentially, researchers want swarm systems to be able to take on challenging problems that would be completely impossible for the individual agents in the swarm.
The principal challenges of swarm robotics include desigining individual robot behavior: it is difficult to choose agent behavior that maximizes the swarm's objective. Different researchers approach this problem through three main methods: simulating swarm systems, modeling them, or performing learning on these systems.
There are many tasks to which swarm systems could effectively be applied. Bayindir breaks these tasks into 10 groups.
Aggregation is the task of gathering swarm agents into one place. Prior work has applied a variety of methods to this problem. Artificial physics, where artificial forces are modeled to determine the movement of agents, is one of them. This has been implemented as an artificial force related to an agent's distance from other agents; the force is attractive down to a specified distance, where it turns repulsive if the robot draws nearer. This approach is limited by the sensing/perception capabilities it requires of its agents.
Other methods include probabilistic methods, where agent control is partially random, and partially influenced by surroundings. This is seen often in nature, and is well-implemented on systems with very minimal robot capabilities. Evolutionary methods are also well-applied on these systems, where parameters of the controllers of robots are determined through an artificial evolutionary process, and these parameters are typically applied to all robots in the swarm.
Algorithms that guide aggregation include "free aggregation," where agents aggregate anywhere in the arena, and individually have no bias towards an area or direction, and "environmentally-mediated aggregation," where environmental factors guide the emergence of an aggregation site. Honeybees, for example, perform this type of aggregation, gathering in areas of optimal temperature. In robot systems, features such as lights can be placed in the environment to guide agents to an aggregation site.
Effectiveness of aggregation methods is measured by identifying discrete groups, and measuring their number, size, and closeness, or by looking at all of the agents in the area, and applying distribution metrics to their positions.
Works have also attempted to model aggregation behaviors in systems. Some success was found by analyzing swarm movement using advection-diffusion equations, and by applying Lyapunov theory to artificial physics approaches.
Flocking is a common phenomenon found in biology, consisting of emergent swarm movements that result from local interactions between agents. Flocking takes the aggregation task and adds the importent feature of alignment of robot movement. This often means that robots must be able to measure the location and relative movement of nearby robots.
Flocking can be implemented simply by allowing robots to know the heading of their neighbors, and enforcing three (global) rules: collision avoidance, velocity matching, and flock centering. However, it can also be achieved without global information. It is possible to perform flocking based on a single globally known target location, using local interactions of robots. Further, if only a few "informed" robots know the target location, this information can be spread locally. Agents can also flock in emergent directions. They begin moving randomly, and using knowledge of their neighbors' movements, gradually converge to a direction.
To quantify and measure the performance of a flocking system, the center of mass of the swarm, its movement, and the swarm density are often tracked. A simple measure of the distance covered by the center of mass can characterize some flocking behavior. Other works use metrics that capture the stability of the group, or the "coherence" of the group based on the difference between agents' headings. Others use the level of order of the group to quantify flocking, relying on measurements of entropy through time, deviation from average direction, and number of outlier robots.
The foraging task in swarm systems is inspired by the ability of ants to find and effectively exploit food sources using local interactions. In robotic swarm systems, an area is typically designated as the "nest," and robots are tasked with finding resources and returning them to the nest. The system's goal is to balance the energy lost searching for resources with the energy gained from bringing them to the nest, maximizing energy income.
For the two sub-tasks involved in foraging - searching for resources, and returning resources to the nest - cooperation is advantageous. It necessitates communication between the agents, which is usually in one of three forms: shared memory, communication through the environment, or direct communication.
In shared memory, robots basically collaborate to build a map of the area, with locations and amounts of resources. This method allows robots to find resources easily and avoid collisions by avoiding paths to other resources, but may have poor scalability.
In communication through the environment, robots leave pheromone trails to resources, or develop static gradients to lead robots back to the nest. These methods are useful when robot sensing and navigation capabilities are poor. In other systems, robots themselves act as markers in the environment to lead to resources.
In direct communication, robots directly send information that can help to avoid collisions in crowded areas, facilitate handoff or collaborative transportation of resources, or help find resources.
The algorithms used to take on foraging tasks can be categorized into path formation algorithms, cooperative transport algorithms, and a few of other types.
Path formation algorithms build representations of good routes through the environment that facilitate agent movement towards resources and back to the nest. Systems that implement path formation algorithms do so typically through a shared memory approach, or through environmental modification. The former systems operate by gradually building a map in the shared memory, based on their experiences finding resources. Other agents make use of the map information and modify it according to their own experiences. The latter camp of approaches uses environmental modification: robots leave pheromones along good paths, or break off "crumbs" of the resources to guide other agents to large sources. Still others use robots themselves as path markers, with robots either retrieving resources, or stopping and acting as a beacon along the path. These systems can also incorporate direct communcation, where robots broadcast integers representing points in a gradient leading to resources.
In cooperative transportation approaches to foraging, agents collaborate to transport resources back to the nest. This can reduce interference in crowded areas, as robots are intentionally interacting, and potentially improves foraging performance by limiting the territory each robot is responsible for. Some systems achieve this behavior by forming "bucket brigades," passing resources down a chain to the nest. Others accomplish this by partitioning the map, and dropping resources at partition borders for the next robot to handle. This work achieved this partitioning in an emergent manner.
Other methods for foraging involve calling nearby robots to a resource by flashing a light, sending (again, light) signals to indicate distance to the nest, effectively increasing agent sensing range, or direct communication to efficiently get resources into the nest when a crowd of robots is present.
Clustering is the task of gathering together items that are scattered throughout an environment. Sorting is a subset of this task, where different types of items must be clustered into distinct groups. These tasks are primarily approached in one of two ways: probabilistically, relying on emergent clustering through random exploration and item deposition, and through more deterministic methods that make use of robot localization and planning.
Probabilistic approaches to clustering are usually advantageous if robots have limited localization, perception, and memory capabilities. The simplest algorithm has robots moving randomly about an arena. They pick up objects of a certain type with probability inversely proportional to the number of these objects previously encountered, and drop objects with probability proportional to the number of the same type of object recently encountered. This results in sorting of objects. Other works take similar approaches, using shovels to push objects into a single cluster, a bulls-eye shaped sorted cluster, or a chain. Some works have approached the algorithm with neural networks, learning control parameters that result in clustering or sorting, relying on the same probabilistic principles.
If robots are better able to localize themselves, sense their surroundings, and can remember the location of clusters, a deterministic approach is more powerful. Approached in a distributed manner, robots can independently build their own clusters in arbitrary locations, and eventually reach a concensus on the best cluster to join with, finally merging into one large cluster. This can help resolve collision issues.
Clustering as a task is well suited for modeling-based approaches, and can be simulated with different types of dynamics. Clustering can be analyzed in terms of feedback mechanisms, and a critical cluster size can be identified above which clusters tend to grow, and below which clusters tend to shrink. There have been several full mathematical models of clustering systems that have these probability-based mechanisms. Using metrics such as average and maximum cluster size, cluster number, time to build clusters, or probabilties to add or remove objects from a cluster, system dynamics can be accurately modelled.
An interesting note about clustering for swarms: for this task, an increase in the number of agents working on the task leads to sub-linear increases in task performance, because robots now have to deal with more possible interference. Collaboration is not particularly helpful!
In this task, a single robot with limited capabilities navigates to a goal location with the help other robots. The task is typically executed by leveraging simple communication with nearby robots, which transmit distance to the goal, the "hop count" to the goal, or other helpful information. This communication can take place directly or through the environment. The navigating robot usually performs some type of random walk until it encounters other robots to help it along its way.
One approach to the task is called "static routing," in which the route from the robot to the goal is defined at the beginning of the task, relative to static landmarks. Some works rely on directly transmitting to the navigating robot the euclidian distance to the target, while others use robots that emit sound, with pitch frequency corresponding inversely to goal distance.
The static routing approach can be effective, but extremely resource intensive, in requiring other robots to remain stationary during navigation. In "dynamic routing," this requirement is not present: other agents in the system can move around freely, and directly communicate with the navigating robot. This can be more flexible, but requires more complex algorithms. One approach is to form a chain from the navigating robot through intermediate robots to the goal. Robots are free to move, and their previous locations in the path are remembered as 'ghost robots.' Another method forms a graph, with the robots as nodes. The graph is continually updated and improved as robots move, with nodes swapped, added, or eliminated. Other works use robots around the goal to propagate a light signal, which essentially moves radially outward like a bulls-eye, guiding the navigating robot.
Performance of navigation algorithms is evaluated relative to some baseline: some works compare to a pessimistic baseline, such as a random walk, while others compare to the upper limit of performance - an optimal path or straight-line path. Because the navigating robot is collaborating with other agents to find the goal, the performance of the system is expected to improve as the number of robots increases: this is confirmed by several studies. This improvement comes at a cost of increased resource consumption of the system, or simply increased cost of the system.
Path formation is distinguished from navigation by the number of robots: in the navigation task, one robot aims to move towards a goal. Here, the system aims to establish a path or chain by which many robots can efficiently move between two points. In some implementations of the foraging task, this paths are formed to facilitate movement of resources to the nest. There are two main approaches to this task: establishing stationary chains of robots, and developing robot flows between two points.
Stationary robot chains are formed between two goal locations, and allow robots to navigate back and forth by simply following the chain. Robots communicate directly or using pheromones to determine the shortest path, and join the chain along this path. Typically, this behavior is accompanied by a probabilistic control approach which encourages robots to break off and rejoin the chain at random to further explore the area. Alternatively, some works establish robot chains that grow in a tree-like fashion from the nest to explore the envioronment.
Robot flows are formed when swarms initiate a positive feedback mechanism to attract other agents to a certain path. Often, pheromones are used: a robot finds a path between two target locations, and dpeosits pheromones along this path. Other robots are attracted to the pheromones, and in turn deposit more pheromones, strengthening the system response. Some works have approached this with machine learning, and found that using direct communication, robots can establish parallel flows going to and from a target location in lanes.
The path formation task illustrates the capability of swarms to accomplish tasks not possible for individual robots: the individuals in these systems cannot localize themselves or perceive globally, but the collective system is able to effectively find goal locations and navigate to and from them efficiently.
In the deployment task, a swarm must deploy itself in an environment to accomplish some goal without centralzed coordination. Typically, the swarm's goal is sensor network coverage or mapping, but it can also be applied to forming geometric patterns and other tasks. Robots typically use direct communication/observation, environmental modification, or artificial physics to coordinate their movements.
Dispersion is one of the most useful applications of swarm robotics, used to develop ocean sensor networks, map an unknown area with quadrotors, or maximally extend mobile communication networks. In dispersion, robots most often use direct communication or observation to sense the location of other agents, and avoid them, resulting in a wide spread. This can be modeled as repulsive forces from other robots, or potential fields, using artificial physics. Other works use pheromones, and employ algorithms that cause robots to seek areas of low pheromone concentration, indicating fewer nearby robots.
In pattern formation, robots move to form a specific shape in the arena. This task is often approached with quadrotors, forming geometric shapes in the air. Patterns can be formed by instituting simple local rules for relative robot positioning. For example, robots may position themselves to form a triangle with two other robot it can detect. One work extends this idea - and the swarms framework - further, to "self-controlled particles," finding that large-scale two- and three-dimensional lattices can be formed using attractive and repulsive forces.
The collaborative manipulation task becomes necessary when an object is too large for a single agent to move - many agents must calloborate to transport it. This behavior is inspired heavily by biology, especially ants, which have been observed cooperating to transport large objects using decentralized control and only local information. Methods of approaching this task most often use probabilistic or pheromone-based control systems. The problems to which this task is applied can be broken into the "box-pushing" task and the "stick-pulling" task.
The box-pushing task is what it sounds like. In most approaches to this task, robots have a few modes, such as "seeking" the box and "following" other robots. The agents probabilistically switch between these modes dependant on local information, while maintaining collision avoidance and other constraints. Additionally, pheromones can be used to attract other agents to the location of an object that cannot be manipulated by a single robot, and then these behavior modes can be used.
The stick-pulling task is one of the largest canonical problems in swarms. There have been many approaches that invoke methods from probabilistic to evolutionary to machine learning. The stick-pulling task consists of "sticks" scattered around an environment, such that they can only be pulled out of the ground by two (or, in the general case, k) robots working in tandem. Although the task itself is not very realistic, it is a convenient toy problem for generally understanding how robots can coordinate collaboration at random unknown sites throughout an arena. Typically, robots are deprived of any communication in this scenario.
The stick pulling task has been used to test different methods for distributed learning across a system; the agents random walk until they find a stick, and then wait for a time determined by a parameter, to see if another robot comes to help them. The parameters involved in this scenario can be tuned by various machine learning methods. Other works use the stick-pulling problem to investigate specialization: robots are divided into groups and their parameters are tuned individually through machine learning.
The stick-pulling problem lends itself well to modeling, which may be why it is so often used with machine learning. The system can be parameterized by the rate at which sticks are discovered on average, the stick density, the number of robots required to pull a stick, and many other parameters. These can predict the success rate of the task.
Task allocation is the final task covered by the Bayindir review paper. It refers to the ability of agents to switch the task they are working on dynamically according to external factors perceived locally. Task allocation is applied to several of the swarms tasks we've reviewed already, most notably foraging. The two main approaches to task allocation are thresholding and probabilistic.
In thresholding, robots change the task they are working on when an environmental variable crosses a threshold. An example of this is in the foraging task: robots by default wait in the nest, so as not to expend unnecessary energy. However, if the "energy" level of the nest falls below a threshold, they will enter into the environment to try to track down resources. Another implementation of this method is using success rates of a behavior; a robot performs a behavior, and if the success rate of the behavior falls below a threshold, it changes behavior. In foraging, this has been applied to the search for food: a robot searches for food, but if it is continually failing, then it is wasting energy, and it gives up. This dynamic task switching applied to a swarm results in many robots searching for food in resource-dense areas, and few robots searching for food in resource-scarce areas.
Probabilistic approaches to task switching are largely similar to thresholding, but they are less absolute. Instead of changing behavior at a specific threshold, each robot acts according to a probability distribution, and this probability distribution changes according to environmental variables. Probabilistic task switching can be used in much the same way as thresholding, and can be used to partition robots into specialized groups to better perform a task. Both of the above approaches are often implemented with machine learning, to best learn thresholds or probability distributions for system performance.
Task allocation is a key component of many of the above swarm tasks, but primarily the foraging behavior. In foraging, task allocation is the mechanism that decides when robots switch behaviors, often between a resting and foraging behavior, or between a resource-finding behavior and returning resources to the nest. Approaches to task allocation within forgaging include learning-based methods, energy-based modeling appraoches, and analytical modeling. Dr. Wenguo Liu has performed in-depth studies on the performance effects of task allocation approaches.
Swarm robotics has been applied to many other tasks. Among the most important are object assembly and construction, self-assembly, collective decision-making, and human-swarm interaction.
Autonomous construction and object assembly is the field I've primarily worked in for the last few years, and swarm robotics is an integral approach to it. Swarms of insects have inspired many of the algorithms and approaches that guide construction, including stigmergy and some local-rule based methods. With swarms, autonomous construction is typically decentralized, and guided by the agents' local observations or a shared template.
Self-assembly refers to robot swarms that can connect to one another to form larger structures/robots - basically swarm robotics' take on modular robots. These modular robot systems have been used to traverse holes and other challenging environments, and are typically controlled in a decentralized manner using local sensing and local communication.
Autonomous construction and object assembly is the field I've primarily worked in for the last few years, and swarm robotics is an integral approach to it. Swarms of insects have inspired many of the algorithms and approaches that guide construction, including stigmergy and some local-rule based methods. With swarms, autonomous construction is typically decentralized, and guided by the agents' local observations or a shared template.
Collective decision making encompasses a challenging class of problems, and shares a strong instersection with network system research. There are many approaches that systems can take to achieve collective decision making - some of the most common are an auction-based approach or a polling-based approach. Alternatively, researchers have applied a dynamic systems framework to swarm decision making, looking at the convergence properties of the system. Other researchers, such as Dr. Naomi Leonard at Princeton, have been looking at how inects (bees) make collective decision, taking inspiration from biology into swarm systems.
Human-swarm interaction is an important task for swarms, and may be an important direction for future development. Task specification for swarms is a challenging problem, especially in a setting where dynamic direction is required. Some work has investigated how humans can locally interact with agents to produce global behaviors. Dynamic selection of leader robots and their direction has also been investigated.