Estimated time to read: 10 minutes
By Marcus McNabb
Two decades of swarming optimization research lay the groundwork for the development of physical swarming techniques. By applying conceptual lessons learned from applied mathematics to physical swarms in military operations, we can optimize physical swarm activity through effective communication and efficient information management.
Swarming is a hot topic in military circles looking for game-changing technologies (e.g., 3rd offset). However, the military is far from the first group to explore swarming behavior. Computer scientists and mathematicians have been studying swarming behaviors for use in the optimization field for over two decades. Others have already explored the use of particle swarm optimization (PSO) in physical applications such as asset allocation in the electromagnetic spectrum and supply chain management. Although these swarms only exist conceptually and navigate mathematical spatial constructs, this field does provide some lessons and insights the military can adopt to accelerate learning in how to apply swarming tactics in physical spaces. This article examines how some of the common PSO techniques might apply to a swarm of vehicles tasked with a fires mission.
Inspired by the flocking behavior of birds, PSO was first developed in 1995. PSO falls into a category of nature-inspired algorithms. Others include ant colony optimization, genetic algorithms, and neural networks. The basic way a PSO works is that each member of the flock has some information about its location relative to some desired objective. In mathematics, the member of the swarm can calculate the solution to the problem in question based on its current location. The goal is to guide the flock toward areas of the solution space that present better solutions to the problem. However, movement of the flock too quickly to an area will result in premature convergence on a sub-optimal solution. Therefore, the communication and movement of the flock must be regulated via certain parameters. This regulation must balance exploration versus exploitation. The flock must be allowed (or perhaps even forced) to explore the space to search for new, promising areas of the solution space. But the flock must also be allowed to converge and further exploit those promising areas. This requirement has resulted in lessons learned about how the swarms should communicate. These are the lessons we seek.
Two points require attention before proceeding. First, in the case of optimization, why not just “solve” the problem? PSO and the other algorithms mentioned above, and indeed all swarm techniques, are heuristics. A heuristic seeks to achieve good solutions to difficult problems in a reasonable amount of time. Problems to which heuristics are applied are typically difficult and time-consuming to solve to full optimality. Using a heuristic allows the user to balance the quality of the solution against the time required to generate the solution. Generally, longer times yield better solutions and vice versa. Another advantage to a heuristic is that it generates solutions early in the process and then seeks to continually refine that solution and find better solutions. True optimization techniques may not generate a complete solution until the process is completely finished. This means those techniques are “all or nothing,” as in you either have the perfect solution or no solution.
A second question is how should physical swarms communicate? The physical and technical aspects of this communication problem (e.g., communication equipment, electromagnetic spectrum usage, frequency agility, survivability) are reserved for another time. Instead, here we explore the logical aspect of the question and consider parameters that guide what type of information the swarm should share and how the swarm should behave. Each of the following sections provides an explanation of how several parameters impact swarm behavior in optimization and how each applies to a physical swarm.
A neighborhood in optimization is the group with which a particular member may communicate. This parameter essentially defines the level of cooperation across the swarm. The simplest neighborhood is that of all members, meaning every member can communicate with every other member. This strategy quickly becomes cumbersome as the size of the swarm increases. Machines are susceptible to information overload just as humans are. Examples of topologies are often based on distance. For example, a member may communicate with any other members within a specified distance. Or a member may communicate with its n-closest neighbors in which n is a specified parameter. To operationalize this concept, consider an area of operations broken down into killboxes/keypads. Using a distance-based neighborhood, one could restrict swarm responses to only those swarm members within a certain distance. For example, only those members in adjacent killboxes can communicate. This would keep an entire theater’s worth of assets from converging on a single event.
Other neighborhood topologies may be defined socially in which each member is assigned to a particular subgroup(s) and may communicate only within its subgroup(s). This concept is also directly applicable because military assets are typically chopped to certain mission sets or organizations. Using a social topology, only assets executing the same mission set or under control of the same organization are allowed to communicate. This allows the operational commander to maintain some desired level of force allocation across various theater requirements.
The concepts of exploration and exploitation are also relevant to military application. In the optimization world, exploration is necessary because the solution spaces for problems are often not “smooth.” This means traditional calculus-based methods are of limited value. Imagine yourself amidst a vast mountain range. Your objective is to climb the highest peak, but you can only see a few feet to either side of you. Traditional calculus techniques have you find the direction of steepest ascent and move that direction until you can no longer go any higher. However, upon reaching that peak, you have no guarantee and no way of telling if you are actually on the highest peak. Instead, you have reached a locally optimal solution. To seek a globally optimal solution (the highest peak) requires exploration, which in turn requires you to move in a suboptimal direction (down). The process of climbing as high as you can is an example of exploitation. You found the best solution you could within a certain subset of the space. The act of leaving that peak in search of another is exploration. Similarly, a strict improvement algorithm means the swarm will converge on the first decent solution it finds, but may miss the actual best solution. A common method for controlling this behavior is through the velocities of individual members of the swarm. Higher velocities equal quicker convergence, but also increases risk of a false negative. Conversely, lower velocities enables greater exploration but requires more time.
In practical terms of a military swarm tasked with a fires mission, exploitation results in the swarm converging on the first threat it encounters. However, this type of swarm is highly susceptible to deception. Think Muhammad Ali and his famous “Rope a Dope” technique. Conversely, a swarm too heavily on exploration would also be disastrous. This manifests in the case that the swarm is too heavily focused on exploration and not recognizing an optimal solution (in this case, a legitimate threat) until it is too late. As an example, consider the Battle of Beersheba during World War I in which Australian cavalry supported by British artillery seized this critical town from German and Turkish troops. Using deception, most notably keeping its infantry in Gaza, the invaders effectively paralyzed their opponents’ decision making. The Germans insisted the true attack would come from Gaza and failed to recognize the cavalry charge from the opposite direction as the true attack in time to maneuver sufficient defensive forces. This situation could easily manifest in a swarm focused too heavily on exploration.
A heuristic uses stopping criteria in a number of ways. Each criterion is used in some way to force the algorithm to change its current behavior. The two most common stopping criteria are on the overall algorithm and the exploitation phase. For the overall algorithm, some combination of iterations and time is typically used to signify that the algorithm is no longer improving its best solution. For example, these criteria may say “If n iterations and/or x amount of time has passed and the overall solution has not improved more than 1% in that time, then stop.” This type of application is likely not all that applicable.
Rather, another type of stopping criteria applies to the exploitation of known parts of the solution space. The criteria would be similar to those above, but instead of stopping the entire algorithm, the members (or some subset thereof) would be forced into an exploration pattern. For example, “If n iterations and/or x amount of time has passed and the overall solution has not improved more than 1% in that time, then y% of members currently exploiting stop and return to exploration.” This is highly applicable to a military application. For example, consider a swarm of 10 autonomous vehicles operating over an area of 1 km2. Now suppose the swarm identifies a threat and dedicates 5 of its members to that threat. The stopping criteria would be how the swarm knows the threat is neutralized-either entirely or to the point that, say 3 of the 5 members are sent to continue exploration.
The more advanced versions of PSO typically utilize dynamic parameters. Each of the parameters above can be made to be dynamic and adaptive based on the environment. This is, in essence, machine learning. Distance-based neighborhoods can shrink or grow. For example, high levels of RF transmission may indicate an adversary operating across a larger spatial area, in which case the swarm may want to increase communication to greater swaths. Members can join or leave social neighborhoods. For example, consider a case where two swarms are operating in a similar area but under different commands (e.g., SOF and regular forces working toward a common objective). In this case, it may be advantageous for the swarms to join each others’ social neighborhoods for some period of time. The swarm can oscillate between times of exploration versus exploitation. For example, insurgent activity is known to have space-time dependency. In spaces and times where greater intensity is expected, the swarm should be tuned to exploitation via higher allowed velocities in order to rapidly respond to threats and decrease the risk of being overwhelmed. When lower intensity is expected, the swarm should be more explorative through lower velocities and maintain a more guarded approach. Finally, the stopping criteria can be dynamic in a number of ways. One example is in terms of demand and availability of the swarm. In times of high demand/low availability, the stopping criteria could be stricter because over-focusing on a single event could increase risk beyond acceptable levels in other mission sets. Conversely, if demand is lower or availability is high, the swarm can remain committed to a single event longer without significant operational risk.
Transforming these concepts to reality will inevitably require rethinking certain norms, parameters, and methods of implementation. Indeed, there is much work to be done to bring the swarm dream to reality. However, the starting point need not be ground zero. By taking the time to learn from existing-albeit not precisely equivalent-applications of swarming methods, the military can achieve its mandate of ensuring the nation can engage and negotiate diplomatic solutions from a position of strength.
Marcus McNabb is an Air Force officer with over 13 years of academic and operational experience as an operations research analyst. He holds a PhD in Operations Research from the Air Force Institute of Technology and has worked in a variety of jobs including test and evaluation, staff of US Air Forces in Europe, the Air Force Nuclear Weapons Center, and the 609th Air and Space Operations Center.
The views expressed are those of the author and do not necessarily reflect the official policy or position of the Department of the Air Force or the U.S. Government.