Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2011 | Book

Introduction Read chapter Read first chapter

Swarm Stability and Optimization

Authors: Veysel Gazi, Kevin M. Passino

Publisher: Springer Berlin Heidelberg

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

Swarming species such as flocks of birds or schools of fish exhibit

fascinating collective behaviors during migration and predator

avoidance. Similarly, engineered multi-agent dynamic systems such as groups of autonomous ground, underwater, or air vehicles (“vehicle swarms”) exhibit sophisticated collective behaviors while maneuvering.

In this book we show how to model and control a wide range of such

multi-agent dynamic systems and analyze their collective behavior

using both stability theoretic and simulation-based approaches. In

particular, we investigate problems such as group aggregation, social

foraging, formation control, swarm tracking, distributed agreement,

and engineering optimization inspired by swarm behavior.

Table of Contents

Frontmatter

Basic Principles

Frontmatter
Introduction
Abstract
In engineering, the terminology of “swarms” has come to mean a set of agents possessing independent individual dynamics but exhibiting intimately coupled behaviors and collectively performing some task. Another terminology to describe such systems is the term “multi-agent dynamic systems.” Examples of engineering swarms include autonomous ground, air, underwater or surface vehicles, satellites or deep space vehicles performing a cooperative task such as surveillance or monitoring of an area, extracting the map of an area, searching for an object, cultivating crop fields, cleaning mines, collectively carrying an object, etc. In biology, the terminology of swarms is reserved for certain species when they are in certain behavioral modes (e.g., honey bees after hive fission occurs and the swarm of bees is searching for, or flying to, a new home).
Veysel Gazi, Kevin M. Passino
Swarm Coordination and Control Problems
Abstract
There are a number of different swarm coordination and control tasks that will be investigated in this book. In this chapter,we briefly introduce these problems. In particular, we present aggregation, social foraging, formation control, swarm tracking, and distributed agreement. We also present the problem of function minimization since we will approach it using biologically inspired direct search methods in the last part of this book. At the end of the chapter we also point out other tasks investigated in the multi-agent systems literature which are of immediate relevance to the tasks or behaviors considered in this book.
Veysel Gazi, Kevin M. Passino

Continuous Time Swarms

Frontmatter
Swarms of Single Integrator Agents
Abstract
The simplest mathematical representation of agents (e.g., robots, satellites, unmanned ground or air vehicles) used for studying swarm behavior is the single integrator model. In this model the motion of an agent i, i = 1, ..., N, is given by
$$ \dot{x}_{i} = u_{i}, $$
where \(x_{i} \in {\mathbb R}^{n}\) is the state of agent i and \(u_{i} \in {\mathbb R}^{n}\) is its control input. We refer to this model as a higher-level or kinematic agent model since it ignores the lower-level vehicle dynamics of the individual agents.
Veysel Gazi, Kevin M. Passino
Swarms of Double Integrator Agents
Abstract
In this chapter we consider a double-integrator model of an agent. As in the last chapter, we characterize swarm cohesiveness as a stability property and use a Lyapunov approach to develop conditions under which local agent actions lead to cohesive foraging. The conditions here allow for the presence of “noise” characterized by uncertainty on sensing other agent’s position and velocity, and in sensing nutrients (a resource profile) that each agent is foraging for. The results quantify claims in biology that social foraging is in a certain sense superior to individual foraging when noise is present, and provide clear connections between local agent-agent interactions and emergent group behavior. Moreover, the simulations at the end of the chapter show that very complicated but orderly group behaviors, reminiscent of those seen in biology, emerge in the presence of noise.
Veysel Gazi, Kevin M. Passino
Swarms of Fully Actuated Agents with Model Uncertainty
Abstract
In this chapter, we consider a swarm of N agents whose dynamics evolve based on a more realistic agent dynamics model compared to the single integrator and the double integrator point mass models considered in the preceding chapters. In particular, we assume that the dynamics of the agents obey the fully actuated model
$$ M_{i}(x_{i})\ddot{x}_{i} + f_{i}(x_{i}, \dot{x}_{i}) = u_{i}, 1 \le i \le N$$
where x i represents the position or configuration of agent i, \(M_{i}(x_{i}) \in {\mathbb R}^{n \times n}\) is its mass or inertia matrix, \(f_{i}(x_{i}, \dot{x}_{i}) \in {\mathbb R}^{n}\) represents the centripetal, Coriolis, gravitational effects, and additive disturbances.
Veysel Gazi, Kevin M. Passino
Swarms of Non-holonomic Unicycle Agents with Model Uncertainty
Abstract
In this chapter, we consider a swarm composed of N agents whose dynamics have velocity constraints and evolve based on the equations
$$ \begin{array}{rcl} \dot{p}_{xi} & = & v_i\cos(\theta_i), \\ \dot{p}_{yi} & = & v_i\sin(\theta_i), \\ \dot{\theta}_i & = & w_i, \\ \dot{v}_i & = & \frac{1}{m_i}\left[u_{i1}+f_{v_i}\right], \\ \dot{w}_i & = & \frac{1}{I_i}\left[u_{i2}+f_{w_i}\right], \end{array} \label{eqn:unicycle_dynamics} $$
where \(x_i(t)=[p_{xi}(t), p_{yi}(t)]^{\top}\) denotes the position of agent i at time instant t in cartesian coordinates, θ i is the steering angle, v i is the linear speed, and w i is the angular speed of agent i. The quantities m i and I i are positive constants and represent the mass and the moment of inertia of agent i, respectively. The control inputs for agent i are the force input ui1 = F i and the torque input ui2 = τ i .
Veysel Gazi, Kevin M. Passino
Formation Control Using Nonlinear Servomechanism
Abstract
In this chapter we consider the formation control problem in the context of output regulation of nonlinear systems or basically nonlinear servomechanism, which is a completely different approach from the potential functions method discussed in the preceding chapters. First we formulate the problem for general nonlinear agent dynamics and present two different type of controllers which are namely the full information and error feedback controllers. Following that we discuss how various formation maneuvers can be achieved using the procedure presented. Finally, numerical simulation examples are presented in order to illustrate the technique.
Veysel Gazi, Kevin M. Passino

Discrete Time Swarms

Frontmatter
One-Dimensional Discrete-Time Swarm
Abstract
The simplest case which can be considered in a discrete-time setting is the case in which a swarm moves in one-dimensional space. In this chapter we will consider this case. First, we describe the model of a single agent. Then, we present the one-dimensional swarm model (i.e., when many agents are arranged next to each other on a line). The model we consider also allows for asynchronous operation and time delays in neighbor position sensing. Therefore, the analysis of the swarm dynamics is relatively difficult. For this reason, we first analyze the dynamics of the swarm under the assumption of synchronous operation and perfect sensing (without time delays). Then, we build on the results obtained for this case and investigate the dynamics of the asynchronous swarm with sensing delays.
Veysel Gazi, Kevin M. Passino
Asynchronous Distributed Agreement in Discrete Time Swarms
Abstract
In this chapter we consider a substantially different problem from the problems considered so far in this book. It is the problem of distributed agreement in a swarm of agents using only local interactions. This problem has been considered in the literature under various names including synchronization and consensus. However, we believe that the term distributed agreement is the most appropriate terminology for the problem under consideration.
Veysel Gazi, Kevin M. Passino
Formation Control with Potential Functions and Newton’s Iteration
Abstract
In this chapter, we consider again the formation control problem. However, we take a different approach for solving the problem. In particular, we consider a discrete-time model for agent motion dynamics. Such a model does not necessarily represent dynamics of physical agents. However, one can view the model as a high-level representation which generates way-points for the physical agents.
Veysel Gazi, Kevin M. Passino

Swarm Based Optimization Methods

Frontmatter
Bacteria Foraging Optimization
Abstract
Natural selection tends to eliminate animals with poor “foraging strategies” (methods for locating, handling, and ingesting food) and favor the propagation of genes of those animals that have successful foraging strategies since they are more likely to enjoy reproductive success (they obtain enough food to enable them to reproduce). After many generations, poor foraging strategies are either eliminated or shaped into good ones. Such evolutionary principles have led scientists to hypothesize that it is appropriate to model the activity of foraging as an optimization process. In this chapter, we first explain the biology and physics underlying the chemotactic (foraging) behavior of E. coli bacteria. Next, we introduce an algorithmic optimization model of E. coli foraging behavior. Finally, we show that this algorithm can perform optimization for a multiple-extremum function minimization problem.
Veysel Gazi, Kevin M. Passino
Particle Swarm Optimization
Abstract
In this chapter we consider the Particle Swarm Optimization (PSO) algorithm, which is another biologically inspired optimization algorithm. Consider again the problem in which we want to find the minimum of a function J(x), \(x \in {\mathbb R}^{n}\). Assume that measurements or an analytical expression of the gradient \(\nabla J(x)\) are not available. Moreover, even if they are available, assume the function is very non-uniform or noisy so that this information is not useful. The PSO algorithm is another population based optimization algorithm which can be used to solve such problems. It is a direct search (non-gradient) algorithm where a population of particles “search” in parallel for the minimum of a given function in a multi-dimensional (n-dimensional) space (or region/domain) without using gradient information. Below we describe the basic PSO iteration. Then we discuss a modified decentralized and asynchronous version better suited for parallel and distributed implementations. Moreover, we discuss various neighborhood strategies including static and dynamic (i.e., time-varying) neighborhoods.
Veysel Gazi, Kevin M. Passino
Backmatter
Metadata
Title
Swarm Stability and Optimization
Authors
Veysel Gazi
Kevin M. Passino
Copyright Year
2011
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-18041-5
Print ISBN
978-3-642-18040-8
DOI
https://doi.org/10.1007/978-3-642-18041-5

Premium Partner

    Image Credits