Distributed shape control of homogeneous swarms of autonomous underwater vehicles

Abstract

In this paper, we study large formations of underwater autonomous vehicles for the purposes of exploration and sampling the ocean surface. The formations or aggregates we consider are composed of up to hundreds of robots with the capability of forming various complex shapes dictated by the shape of the region to be explored, as well as special shapes suitable for migration. The shapes are determined through bathymetric maps and described with reduced-dimensional representation techniques. The approach we propose is that of breaking up the control and coordination strategy into two decoupled problems, i.e., partitioning the aggregate into two non-overlapping sets: its boundary and its interior. The boundary uses general theory of curve evolution to form shapes while the interior passively complies, using attraction-repulsion forces, to form a uniform distribution inside the boundary. This makes the problem much more tractable than previous methods. Decision making by individual robots is entirely based on local information, autonomous underwater vehicles, formation control, swarm control.

Introduction

Coordinated motion of groups of autonomous agents has been the subject of much research in the past few years. Most of the literature, either consider small formations (especially suited to aerospace applications, (Egerstedt and Hu, 2001; Zhang et al., 2003)) or swarms with no constraints on the boundary (mostly related to the study of biological organisms, (Gazi and Passino, 2004; Reif and Wang, 1999)). Only recently, researchers have started looking at large formations of robots resembling swarms but satisfying some geometrical characteristics (Belta and Kumar, 2002; Chaimowicz and Kumar, 2004; Cortes et al., 2004; Spletzer and Fierro, 2005; Chaimowicz et al., 2005). The primary application we have in mind is that of exploration of underwater environments requiring the realization of Autonomous Ocean Sampling Networks (AOSN) (Curtin et al., 1989). We are specially interested in mobile networks as opposed to static ones. In this case, autonomous submarines play the role of sensor platforms. They are equipped with special application-specific sensors as well as limited bandwidth communication capabilities. The robot aggregate is assumed to be homogeneous, consisting of identical robots. Also, interactions are limited to a small neighborhood around each robot. These local interactions should lead to the accomplishment of a global task.

In a typical underwater exploration task, a group of mobile autonomous vehicles are required to form particular shapes corresponding to underwater features and carry on some sampling process of the region. Features of interest underwater include, but are not limited to, regions with certain depth characteristics, usually represented by bathymetric maps, and plumes created as a result of emission of heat or matter from one or several sources and undergoing diffusion (Okubo, 1980). This latter example can include oil leakage (or other kinds of contamination) as well as explosions. Regions are usually connected together in a topological map of the environment. The robot aggregate needs to migrate through pathways from one node in the map to another. To do this, it may have to form particular shapes suitable for navigation and distribute again upon reaching the destination node. Figure 1 shows part of a typical scenario. In this paper, we address the issue of commanding the group to form desired shapes. We assume that signatures (shapes) of environmental features have been computed by suitable shape description methods. These signatures can be computed using groups of robots which have been adapted to the feature or they could be conveniently calculated using bathymetric maps, if available, or other means, such as using aerial vehicles. For more details, refer to Kalantar and Zimmer (2004).

Fig. 1

Underwater exploration and migration

To have a collection of robots form a certain shape we have to come up with means to describe geometric shapes. One inefficient way of doing this is to represent the position of each and every robot within the formation. This is certainly appropriate for a small number of robots such as in formation flying. Indeed, many methods have been proposed for representing small formations such as the concept of virtual structures (Ren and Beard, 2004). In Belta and Kumar (2002), a formation state is described as an element of an abstract manifold which is the Cartesian product of a Lie group G (an element of which represents the pose of the formation as a whole) and a shape manifold S which is a low-dimensional space representing the shape of the formation. They apply their theory to ellipsoid-shaped formations using the mean and variance as shape parameters. In this kind of approach, the positions of individual robots are not important as long as the whole group has a certain shape. This approach may prove to be very complex when it comes to describing more complex shapes. On the other hand, a multitude of canonical invariant representations have been used by machine vision researchers over the past few decades, such as statistical moments, Fourier descriptors, differential invariants, integral invariants and wavelets, to name the most important ones. In this paper, we propose an alternative approach where the problem is decoupled into two much simpler problems: motion of robots at the boundary of the aggregate and appropriate distribution of interior robots within the confines of the boundary. The particular boundary representation we use here is Fourier descriptors which have been widely used in pattern recognition but others can also be used. Also, we consider uniform distribution for interior robots but non-uniform ones, such as the one described in Cortes et al. (2004), are also applicable.

The physical robots we consider here are small autonomous vehicles called Serafina (Fig. 2), which have been developed in our laboratory (for information about the technical aspects of the submersibles please have a look at the web-site (http://users.rsise.anu.edu.au/~serafina/)). They have limited communication, sensing as well as computational power. For a particular sampling operation, they will be equipped with special sensors. Each robot can only communicate with vehicles in its vicinity defined by a radius. In this paper, we use a very simple control system $\dot{q}(t)=F(q(t),t)$, basically treating Serafinas as holonomic vehicles, where $q(t)=[x(t),y(t)]$ is the coordinates of the robot in the horizontal plane and F denotes the total force acting on the robot. The robots are stabilised at a certain fixed distance from the bottom of the ocean using $\dot{z}(t)=K_z(z(t) -z_d)$, so that we only consider motion in the $(x, y)$ plane.

Fig. 2

Two of the Serafina underwater vehicles

The paper is organized as follows. First, a very general global overview of our approach is presented. We then present a review of reduced-dimensional shape representations. Then, methods for effecting uniform distribution are discussed in Section 4. Separation of the group into interior and boundary robots is discussed in Section 5. After that, target shape reconstruction and the associated potential (Section 6), movement of the boundary as well as interior robots (Sections 7 and 8), are dealt with. Next, some special cases are considered. Finally, simulation results are presented.

Overview

Suppose that we are given a collection S of N robots $R_i, i = 1,\ldots, N$, represented as points in $\Re^2$ with their positions denoted as $q_i(t)=(x_i(t),y_i(t))\,(q_i(t)$ can be interpreted as the state of $R_i$). The positions are measured with respect to a fixed global coordinate system or a local one moving with the robots. The state of the system S can be described by $q(t) =(q_1(t),\ldots,q_N(t))\in \Re^{2N}$. We call S an aggregate. Each robot is uniquely identified by its label. The centre of gravity of an aggregate is defined as

$$ \bar{q}=\frac{1}{N}\sum^N_{i=1}q_i. $$

(1)

A local coordinate system can be conveniently placed at $\bar{q}$. From now on, we assume (although not entirely necessary) that all the distances are expressed in these local coordinates.

An aggregate can be partitioned into two non-overlapping sets: ${S} =I_{S} \cup B_{S}.B_{S}$ denotes the set of robots forming the boundary of the shape described by S, while $I_{S}$ is the set of robots inside the boundary. For this definition to be meaningful, the region defined by S should be connected, in the topological sense of the word.

The robots we consider here are homogeneous, meaning that they can equally well belong to $B_{S}$ or $I_{S}$, and that they can be anywhere on the boundary or inside. Any two of the robots can thus be interchanged.

Due to communication range limitations, all the processes we consider are local. Depending on which set a robot belongs to and which particular process it is involved in at a certain time instant, various neighborhoods may be defined. A neighborhood $\mathcal{N}_i$ of each robot $R_i$ defines a circular region, with radius $r(\mathcal{N}_i)$ around it and is defined as the set of robots $R_j$ such that $\|q_i(t)-q_j(t)\| \leq r(\mathcal{N}_i)$. Two robots are called neighbors (connected) if both of them belong to the other robot's neighborhood.

Boundaries can be conveniently represented by continuous closed curves $\gamma:[0,1]\rightarrow \Re^2$, parametrized by arc-length $s . \gamma(s)$ denotes the position of the point on the boundary s distance away from the starting position $\gamma(0)$ and $\gamma(1) = \gamma(0)$. In our case, the boundary is actually a polygon each vertex of which denotes the position of a boundary robot. If an order $l_B: B_S \rightarrow \{0,1,\ldots,|B_S|-1\}$ is defined on S, then $\gamma(l_B(R)/(|B_S|-1))$ defines the position of $R \in B_S$.

In our approach, the robots are initially randomly distributed in a region. They start by moving according to a rule which tries to make the region occupied by S as close as possible to a convex shape, with robots distributed uniformly inside it:

$$ \dot{q}(t) =\frac{dq(t)}{dt}=\mathcal{F}_S(q(t)) $$

(2)

As will be shown later, $\mathcal{F}_S$ is a function of the attraction-repulsion forces exerted on individual robots and is computed as the gradient of a potential $\Phi(q(t))$. After stabilization, boundary selection process can commence. Equilibrium can be determined using

$$ \left\| \Phi (q(t))-\frac{1}{T}\int^t_{t-T}\Phi(q(t))dt\right\|\leq \varepsilon_\Phi $$

(3)

In some cases, the process may also commence when the energy level falls below some limit:

$$ \Phi(q(t))\leq \varepsilon_D $$

(4)

In its most general case, boundary assignment is a statistical process. Denote by $P_B(R_i, t)$ the probability of $R_i \in B_S$ at time t. Then at a certain time T marking the end of the process, we should have $P_B(R_i, T) = 1$ for $R_i \in B_S$ and $P_B(R_i, T) = 0$ for $R_{i} \in I_{S}$. Moreover, left and right neighbors of each boundary robot should be determined by this process. Accordingly, we will have a set of coupled differential equations:

$$ \begin{array}{l}\partial P_B(R_i,t)/\partial t = \hat{P}_B(S,t)\\\partial P_l(R_i,R_j,t)/\partial t = \hat{P}_l(S,t)\\\partial P_r(R_i,R_j,t)/\partial t = \hat{P}_r(S,t)\end{array} $$

(5)

$P_{l}(R_{i}, R_{j}, t)$ represents the probability that $R_{j}$ is $R_{i}$’s left neighbor on the boundary, and $P_{r}(R_{i}, R_{j}, t)$ is similarly defined. The functions $P_{B}, P_{l}$, and $P_{r}$ work together to maximize some function of the curve:

$$ \Gamma\left(\int^1_0 \Upsilon(\gamma(s))ds\right) $$

(6)

Examples include length $(\Gamma(u) =u-L_d$, and $\Upsilon(v) = v)$, where $L_{d}$ is a minimum required length, and curvature $(\Gamma(u) =u, \Upsilon(v)=\kappa_d -\kappa(v))$.

Once a boundary has been determined, S is partitioned into two sets of robots. Interior robots move according to

$$ \frac{dq_i(t)}{dt}=\mathcal{F}_I(q(t))=\tilde{\mathcal{F}}_{IS}(q_I(t))+\tilde{F}_{BS}(q_B(t)) $$

(7)

where $\tilde{\mathcal{F}}_{IS}$ and $\tilde{\mathcal{F}}_{BS}$ are variants of $\mathcal{F}_{S}$ and represent, respectively, interaction with interior and boundary robots.

On the other hand, boundary robots will have the capability of morphing the boundary curve into a target curve $\gamma_D.\, \gamma_D$ is, in our method, constructed from a small set of shape descriptors Ξ:

$$\displaylines{ \frac{dq_i(t)}{dt} = \mathcal{F}_I(q(t))\cr = \mathcal{F}_N (\gamma(t),\gamma_D,\Theta(\gamma_D))\stackrel{\rightharpoonup}{{N}} (s)+\mathcal{F}_T(\gamma(s))\stackrel{\rightharpoonup}{T} (s) }$$

(8)

where $\stackrel{\rightharpoonup}{{N}}\!\!(s)$ and $\stackrel{\rightharpoonup}{{T}}\!\!(s)$ represent normal and tangent vectors at $\gamma(s)$, and $\Theta(\gamma_D)$ is the attracting potential corresponding to $\gamma_D$. After convergence, we'll have $\| \gamma -\gamma_D\| \leq \varepsilon_\gamma$.

Figure 3 shows the global state diagram of the system.

Fig. 3

Global view of the system

Shape representation

In this paper, we are interested in large groups of autonomous mobile vehicles which collectively form certain desired shapes. The shapes we deal with here normally correspond to environmental features such as those found in underwater landscapes, or almost stationary plumes developed through some slow diffusion process. The assembly can then act as a huge networked sensor sampling the desired feature, or simply complying with it's shape, while performing exploration tasks. In traditional formation control literature, a formation shape is usually represented by formation graphs or formation functions which encode the precise geometrical relationships between each and every robot. When the number of robots increases, the aggregate more resembles a swarm than a simple formation. On the other hand, swarm literature are interested in the inter-vehicle forces giving rise to the advection-diffusion process of swarming rather than the actual shape of the aggregate. In this paper, we combine aspects of both approaches. First, we review some of the previous attempts at finding appropriate representations.

The most reasonable way of describing the approximate shape of very large formations is to use a reduced-order representation. This is a fairly common approach used in machine vision and pattern recognition. We review the basic concept here. Let $S \subseteq \Re^M$ be a low-dimensional space of canonical invariant shape parameters with elements $\tilde{s} =\{s_0,\ldots, s_{M-1}\}$ and $G \subseteq \Re^3$ the Lie group of Euclidian transformations in the plane with elements $\tilde{g} =(\mu,\theta,l)$. A certain formation $F(t)$ can be considered as an element $\tilde{f}=(\tilde{s},\tilde{g})$ of $G \otimes S$. Let $Q =(q_o,\ldots,q_{N-1})\in \Re^N$ denote the state of the aggregate G, then$\tilde{f}=\Psi (Q)$ and $Q =\Psi^{-1}(\tilde{f}).\Psi^{-1}$ is generally not known. In such a case, we can design control laws for individual robots using a minimum norm solution of $\dot{\Psi}\dot{q} =\dot{\tilde{f}}$ in the least squares sense, where $\dot{\Psi}$ denotes the differential of Ψ. Thus, $\dot{q} =\dot{\Psi}^{-1}\tilde{f}$. At each time step, all the robots send their position information to a super-agent which calculates the error $e = \|\tilde{f}_d -\tilde{f}\|$ and sends e back to the robots. The robots then move according to $\dot{q} =\dot{\psi}^{-1}e$. In Belta and Kumar (2002), this method was originally proposed and used by defining

$$\displaylines{ \mu = \frac{1}{N}\sum^{N-1}_{i=0}q_i,\cr s_o = \frac{1}{N-1}\sum^{N-1}_{i=0}x^2_i,\qquad s_1=\frac{1}{N-1}\sum^{N-1}_{i=0}y^2_i }$$

(9)

which are the first and second moments, and defining orientation using

$$ \sum^{N-1}_{i=0}x_i y_i =0 $$

(10)

to form simple ellipsoidal shapes.

For more complex shapes, higher-order moments or better shape parameters should be used. One such method is called integral invariants. In this method, shape parameters $s_{mn}$ are defined by

$$ s_{mn} =\frac{1}{2\pi N_xN_y}\int_X\int_Y \Bigg(\sum_{q\in G}e^{-\sigma\|q-(x,y)\|^2}\Bigg)^m $$

(11)

$$ \Bigg[\int^{2\pi}_0 \Bigg(\sum_{q \in G}e^{-\sigma\|q-((x,y)+R(\phi)re_x\|^2}\Bigg)^nd\phi \Bigg]dxdy $$

(12)

where

$$ \begin{array}{@{}l@{}} X =\Big[\displaystyle\min_{q_i\in G}(x_i) -d, \max_{q_i\in G} (x_i) +d\Big],\\[6pt] Y =\Big[\displaystyle\min_{q_i\in G}(y_i) -d, \max_{q_i\in G} (y_i) +d\Big],\\[6pt] N_x = \displaystyle\max_{q_i\in G}(x_i) - \min_{q_i\in G} (x_i) -2d,\\[6pt] N_y = \displaystyle\max_{q_i\in G}(y_i) - \min_{q_i\in G} (y_i) -2d. \end{array} $$

(13)

The parameters are calculated as $s_{00}, s_{01}, s_{11}$, etc. where d denotes a desired margin around the area covered by robots. This representation, although very powerful, is very costly and $\Psi^{-1}$ or $\dot{\Psi}^{-1}$ can not be easily computed, if at all.

The complexities associated with using the above representation techniques for more complex shapes prompted us to consider a slightly different approach where the aggregate is partitioned into two non-overlapping sets: the interior and the boundary. In most applications, the interior is just required to maintain a uniform distribution inside the boundary. What was said about reduced dimensional representations need only be applied to the boundary set. Among the various proposed boundary representations, complex Fourier descriptors are the most popular. A handful of Fourier descriptors $\mathcal{F} =\{\mathcal{F}_{-M},\ldots,\mathcal{F}_M\}\in \Re^{2M}$, with M usually very small, can represent fairly complex shapes and, furthermore, given $\mathcal{F}$, the original curve $\gamma_{\mathcal{F}}(s) =\Psi^{-1}\{q_o,\ldots, q_{N-1}\}$, with desired granularity specified by N, can easily be recovered. The version we use here is invariant under homogeneous transformations, details of which will be presented in Section 6. Figure 4 is a visual demonstration of shapes and transformations.

Fig. 4

Formation shapes and transformations

Uniform distribution

We use the recipe for swarming for two purposes. One is to make the interior robots form a uniform distribution inside the boundary and the other is to make the whole assembly form a more appropriate shape prior to the commencement of the boundary assignment process. The rationale behind this assumption is that, as will be seen shortly, the type of swarming behaviour we consider here is actually a discrete implementation of a diffusion process which relates the time derivative of the concentration to the second spatial derivative of concentration (local curvature) that will effectively act like a low pass filter on the concentration profile.

Suppose that the individual robots move according to the control law

$$ \dot{q}_i(t) =\frac{dq_i(t)}{dt}=\lambda \mathcal{F}_i(q(t)), $$

(14)

where $\mathcal{F}_{i}(q(t))$ is a force driving each robot and λ is a damping coefficient. Here, we have ignored inertial effects. The system S is thus governed by the coupled differential equations

$$ \dot{q}(t) =\lambda \mathcal{F}(q(t)) $$

(15)

Definition 1.

Let $D_{S} > 0$ be a given number (comfortable distance between neighboring robots). Define a neighborhood $\mathcal{N}_{i}$ around each robot with $r(\mathcal{N}_{i}) = D_{S}$. Let the robots be initially positioned at locations $q_1(t_0),\ldots, q_N(t_0)$ at time $t_{0}$. Let the robots evolve according to (2). Suppose that after a finite time, say $T_{c}$, all the robots reach their equilibrium (stop moving) and for every pair of robots $R_{i}$ and $R_{j}$, such that $R_i \in \mathcal{N}_j$ and $R_j \in \mathcal{N}_i$, we have $\|q_i(t_C)-q_j(t_C)\| =D_S$, where $t_{C} = t_{0} + T_{C}$. Then, we say that the robots have formed a swarm. In absence of any external perturbations, the swarm will stay in equilibrium for all times $t>t_{C}$. We call $\mathcal{F}$ a swarm generator. The set of states $q(t_{C})$ satisfying the above definition can be considered as the invariant set $\Omega_{\mathcal{F}}$ for the system (3). A swarm generator $\mathcal{F}$ is called invariant if it is invariant under affine transformations. In other words, $q(t)$ is an equilibrium state of $\mathcal{F}$, then so are $q(t) + \tilde{q}$ and $R(\theta)q(t)$, where $\tilde{q}$ is a translation and $R_{z}(\theta)$ represents the rotation matrix around the z axis applying a θ degree rotation to all $q_{i}$.

It is easy to see that the only local arrangement, satisfying (4), is a hexagon centred around each robot, as Fig. 5 depicts. In other words, if there exits a swarm generator $\mathcal{F}$, then after the swarm has been formed, the structure would locally look like the one in Fig. 5. Thus, every neighborhood consists of just seven robots, with one robot at the centre and the other six distributed around the perimeter of a circle with radius $D_{S}$.

Fig. 5

Uniform distribution by swarming

For the class of swarm generators we are interested in, $\Omega_{\mathcal{F}}$ is infinite, i.e., there are an infinite number of equilibrium states. This is always true for invariant generators.

In real environments, there are always some sort of external disturbance that tries to destabilize the swarm. In such a case, we require that a bound such as $D_S -\varepsilon \leq \|q_i(t_C)-q_j(t_C)\| \leq D_S +\varepsilon$ be actually satisfied.

One way of designing a swarm generator $\mathcal{F}$ is to first design a potential function $\Psi(q, t)$ whose minimums correspond to the invariant set $\Omega_{\mathcal{F}}$. Then, we can define

$$ \mathcal{F} (q(t)) = -\nabla_{q} \Omega(q,t) $$

(16)

The control laws for individual robots would thus be defined as

$$ \mathcal{F}_i(q(t)) = -\nabla_{q_i} \Omega (q,t) $$

(17)

Although the forces $\mathcal{F}(q(t))$ can be designed without having to define a potential first, nevertheless, to every such force there always corresponds a potential:

$$ \Omega(q,t) = \int_{t_0}^t \mathcal{F} (q(t)) dt $$

(18)

It is worth noting that $\Psi(q, t)$ can be used as a Lyapunov function for the aggregate.

There are quite a number of ways that a swarm generator can be designed. Here, we consider a special type of swarm generator constructed from a potential. Let

$$ \phi_{LJ} (\tau) = \frac{-\mathcal {E}_D}{m - n}\left(m\left(\frac{\mathcal{D}_S}{\tau}\right)^n - n\left(\frac{\mathcal{D}_S}{\tau}\right)^m\right). $$

(19)

(depicted in Fig. 6(a). Then, the potential energy between two robots $R_i$ and $R_j$ is defined by $\phi_{LJ}^{ij} \equiv \phi_{LJ} (\| q_i(t) - q_j(t)\|)$ and is called the Lennard-Jones bi-reciprocal potential. $\mathcal{E}_D$ is called the dissociation energy and $\mathcal{D}_S$ is called the equilibrium separation distance. When the two robots $R_i$ and $R_j$ are in equilibrium, $\phi_{LJ} (D_{ij}) = -\mathcal{E}_D$, its minimum value, and the distance between them would be equal to $\mathcal{D}_s$. Lennard-Jones potentials were initially used to model interaction forces between molecules. It has since been used for geometric modelling (Tonnesen, 1998) and other similar applications. Here, we use it to create uniform distributions of robots in a spatial extent.

Fig. 6

Swarming potentials and associated forces

We have

$$ \nabla_{q_i} \phi_{LJ}^{ij} = \frac{d}{d\tau} \phi_{LJ} (\|q_i(t)- q_j(t)\|) \frac{q_i(t) - q_j(t)}{\|q_i(t) - q_j(t)\|} $$

(20)

where

$$ \frac{d}{d\tau}\phi_{LJ}(\tau) = \frac{\mathcal{E}_{D}mn}{m - n}\left(\frac{\mathcal{D}_S^n}{\tau^{n + 1}} -\frac{\mathcal{D}_S^m}{\tau^{m + 1}}\right) $$

(21)

Now, define

$$ f_{\phi_{LJ}}^{ij} = f_{\phi_{LJ}} (q_i(t) - q_j(t)) =-\nabla_{q_i} \phi_{LJ}^{ij} $$

(22)

as the force between two robots $R_i$ and $R_j$ and define

$$ f_{\phi_{LJ}}^i (q(t)) = \sum_{j = 1}^N f_{\phi_{LJ}}(q_i(t) - q_j(t)) $$

(23)

as the total force experienced by $R_i$. If we set

$$ \mathcal{F}_i(q(t)) = f_{\phi_{LJ}}^i (q(t)) $$

(24)

then the system defined by (2) will strive to minimize the total potential of the aggregate (also, the Lyapunov function) which is defined as

$$ \phi_{LJ}^S (q(t)) \equiv \frac{1}{2} \sum_{i = 1}^N \sum_{j = 1,j \neq i}^N \phi_{LJ} (\|q_i(t) - q_j (t)\|) $$

(25)

The Lennard-Jones potential $\phi_{LJ}$ goes to zero at infinity and at a point called the collision distance $\mathcal{C}_D$. If $n = 2m$, then $\mathcal{C}_D = \mathcal{D}_S(2^{-1/m})$.

Refer to Tonnesen (1998) for a detailed description of the effect of varying $\mathcal{E}_D, n$ and m on compressibility and brittleness of the swarm.

As is clear from previous section, $\phi_{LJ}(\|q_i(t) - q_j(t)\|)$ and $f_{LJ}(q_i - q_j)$ go to infinity as $\|q_i - q_j\|\to 0$. This causes problems when implementing on a real computer with limited computing capabilities. Moreover, when the robots get very close together, the Lennard-Jones potential applies very large forces on robots. In simulations, this effect is seen as an explosion of the swarm. Although the robots have physical constraints limiting their actual velocities, nevertheless, it is highly desirable if the actual computed forces somehow captured this limitation. Bounding the potential at a certain maximum $\phi_M$ is tantamount to asserting that below a certain distance, the force (pressure) exerted on each robot does not change. We can realize this using a transformation on τ, i.e., the distance between two robots. Suppose that $\tau_M = \phi^{-1}(\phi_M)$, such that $\tau_M < \mathcal{C}_D$. Now consider the mapping

$$\gamma(\tau) = \tau_M\sqrt{\beta \tau^2 + 1} $$

(26)

The graph of this mapping is shown in Fig. 6(e) with $\beta = (1/\tau_M)^2$ (which corresponds to a slope of 1, because the slope equals $\alpha \sqrt{\beta})$. As can be seen in the figure, the mapping is almost linear and one-to-one when τ is greater than some value, and decays to $\tau_M$ as $\tau\to 0$.

The bounded potential is now defined by

$$\phi_{LJ_B} (\tau) = \phi_{LJ}\, {\circ}\, \gamma (\tau) $$

(27)

with corresponding force calculated as

$$f_{LJ_B} (\zeta) = -\frac{d}{d\gamma} \phi_{LJ} (\gamma(\|\zeta\|)) \frac{d}{d\tau} \gamma(\|\zeta\|)\frac{\zeta}{\|\zeta \|}$$

(28)

Here, ζ is the vector representing the difference of two positions on the plane, e.g., $q_i(t) - q_j(t)$, and let $\tau = \|\zeta\|$. Note that $\partial \tau/\partial \zeta = \zeta/\|\zeta\|$. The critical points of $\phi_{LJ_B}$ occur at points τ where $\phi'_{LJ_B} (\tau) = \phi'_{LJ_B} (\gamma(\tau))\gamma'(\tau) = 0$. The one corresponding to $\gamma'(\tau) = 0$ is zero (the point at which the potential attains its maximum) and the one corresponding to $\phi'_{LJ_B}(\gamma(\tau)) = 0$ is equal to

$$ \mathcal{D}_{S_B} =\sqrt{\bigg(\left(\frac{\mathcal{D}_S}{\tau_M}\right)^2 -1\bigg)\bigg/ {\beta}} $$

(29)

which is also the point at which the force is zero. This means that with bounded potentials, the comfortable distance would be $\mathcal{D}_{S_B}$. If we plug this value into the expression for $\phi_{LJ_B}$, we get $-\mathcal{E}_D$, so that the minimum value of the original potential is not changed under the action of $\gamma(\mathcal{E}_{D_B} = \mathcal{E}_D)$ as long as $\tau_M < \mathcal{C}_D$. For a desired comfortable distance $\tilde{{D}}_S$, one should put $\mathcal{D}_S = \tau_M \sqrt{\beta\tilde{\mathcal{D}^2_S} + 1}$.

To prevent the discontinuity at neighborhood boundary, weighting has been proposed in Tonnesen (1998) to make the potential smoothly die off at the boundaries. Again, refer to Tonnesen (1998) for details. Now, the potential is defined as

$$\phi_{LJ_W} (\tau) = w (\tau) \phi_{LJ} (\tau)$$

(30)

(Fig. 6(c)). The way $w(\tau)$ (Fig. 6(c)) is defined ensures that for every robot $R_i$,

$$\sum_{j = 1, j\neq i}^N w^{ij} \phi_{LJ}^{ij} =\sum_{j \in \mathcal{N}_i} w^{ij} \phi_{LJ}^{ij}$$

(31)

where $w^{ij} = w(\|q_i(t) - q_j (t)\|)$. The interaction force applied to a robot $R_i$ from another robot $R_j$ would thus be

$$\displaylines{f_{LJ_W}(q_i(t) - q_j(t)) \cr = - \nabla_{q_i} (w(\tau)\phi_{LJ}(\tau_{ij})\cr = \left(w(\tau_{ij})\frac{d}{d\tau}\phi_{LJ}(\tau_{ij}) + \phi_{LJ}(\tau_{ij}) \frac{d}{d\tau} w(\tau_{ij})\right) \frac{q_i(t) - q_j(t)}{\tau_{ij}}} $$

(32)

where $\tau_{ij} = \|q_i(t) - q_j(t)\|$ and is depicted in Fig. 6(d).

In this case, we have

$$\phi_{LJ_{BW}} (\tau) = w(\tau) \phi_{LJ_{B}} (\tau),$$

(33)

$$f_{LJ_{BW}} (q_i(t) - q_j(t)) = -\nabla_{q_i} (w(\tau)\phi_{LJ_{B}} (\tau_{ij})).$$

(34)

The latter is shown in Fig. 6(i), while the former can be seen in Fig. 6(j). Figure 6 shows the various potentials and the associated forces. Finally, the bounded forces, although within the limitations of the processor, are still too big to be realized by real robots. To dampen out the spikes that occur when robots get close together, we use the shunting model. In this model the actual force applied to a robot, $\tilde{f}_{LJ_{BW}}^i (t)$, is the solution to the differential equation

$$\displaylines{ \frac{\partial \tilde{f}^i_{LJ_{BW}} (t)}{\partial t}\cr \qquad =-D\tilde{f}_{LJ_{BW}}^i (t) + \big(B_{U} - \tilde{f}_{LJ_{BW}}^i (t)\big)\max \big(0, \tilde{f}_{LJ_{BW}}^i (t)\big)\cr \quad\quad -\, \big(B_L + \tilde{f}_{LJ_{BW}}^i(t)\big) \max \big(0, -\tilde{f}_{LJ_{BW}}^i (t)\big) }$$

(35)

where D is the decay rate and $B_U$ and $B_L$ are the upper and lower bounds. We set $D = \mathcal{E}_{D}/10$. In the discrete implementation, $\Delta t = 1/D$ should be used. Shunting model was introduced by Grossberg and was originally used in neural networks but can generally be used to limit an arbitrary signal to lower and upper bounds. It also exhibits some memory effects in that big spikes are not just cut out but retain their action over an extended period of time. This will produce smooth transitions.

Boundary assignment

Assigning boundary robots is indeed the most crucial phase in the proposed system. The whole aggregate should self-organize itself into two non-overlapping sets. It is a difficult problem even in the presence of global information. In our case, all the decisions have to be made with respect to local neighborhoods, which makes the problem even harder. In its most general form, the solution can be formulated as the solution of a set of coupled selection equations with dynamic variables $\xi_i \in [0,1]$ ($\xi_i = 1$ means $R_i \in B_S), \zeta_{ij}^i \in [0,1]\, (\zeta_{ij}^l = 1 \,{\rm means}\, {R_i} \in {B_S},{R_j} \in {B_S},$ and $R_j$ is $R_i$'s left neighbor on the boundary), $\zeta_{ij}^r \in [0, 1]$ (defined similarly to $\zeta_{ij}^l$), subject to constraints imposed on the desired quality of the boundary (length, curvature, ...). The resulting $B_S$ should of course be a boundary for $S: R_i \in B_S$ should form a closed polygon without intersections and all $R \in I_S (=S\backslash B_S)$ should be inside this polygon. The system can be written

$$\varrho = \varsigma \left(\xi, \zeta^l, \zeta^r, \left\{\Gamma_\alpha\left(\int_0^l\Upsilon_{\alpha}(\gamma(s))ds\right)\right\}\right)$$

(36)

where $\varrho = [\dot{\xi}, \dot{\zeta}^l, \dot{\zeta}^r]^T$. The assignment should emerge in the limit as an asymptotically stable point of the above dynamics (refer to Starke (1987) for a similar problem).

In this section, rather than attempting to solve the general problem, we present a procedure which can be considered as a rough discrete approximation of the continuous dynamics. It is always successful if certain conditions are met.

As before, $\mathcal{N}_r(R_i)$ denotes the neighborhood of $R_i$ with radius r. Define

$$ \begin{array}{l}\rho : \mathcal{N}_r (R_i) \to [0, 2\pi],\\R_{\alpha} \to s_{2\pi} \big({\rm atan} \big((y_{R_{\alpha}} - y_{R_1}\big)/\big(x_{R_{\alpha}} - x_{R_1}\big)\big)\big),\\ s_{2\pi} (\theta) = \theta - 2\pi\lfloor \theta/(2\pi)\rfloor\end{array} $$

(37)

Define a partial order $\preceq$ on $\mathcal{N}_r (R_i)$ such that $R_{\alpha} \preceq R_{\beta} \Leftrightarrow \rho (R_{\alpha}) \le \rho(R_\beta)$. Now, re-label the robots in $\mathcal{N}_r (R_i)$ as $\{R_0, \ldots, R_{|\mathcal{N}_r (R_i)| - 1}\}$ according to the order. Also define the mappings

$$ \iota_+:\mathcal{N}_r (R_i) \to \mathcal{N}_r (R_i), R_{\alpha} \to R_{(\alpha + 1) {\rm mod}|\mathcal{N}_r(R_i)|}$$

(38)

$$ \iota_- : \mathcal{N}_r (R_i) \to \mathcal{N}_r (R_i), R_{\alpha} \to R_{(\alpha - 1) {\rm mod}|\mathcal{N}_r(R_i)|}$$

(39)

Finally, consider the maps $l,r: B_S \to B_S$, which define the left and right neighbors of $R_i \in B_S$. The boundary assignment scheme should determine $B_S, l(B_S)$ and $r(B_S)$.

We now describe 5 heuristic rules which will identify $B_S$. They should be active during the process. First, fix some $\theta_{G\cdot}\, \theta_{G}$ can be used to control the length and curvature of the resulting curve. Furthermore, let $B_S = \varnothing$ initially.

Rule 1.

Suppose there exists a $R_{\alpha} \in \mathcal{N}_r (R_i)$ such that for every $R_{\beta} \in \mathcal{N}_r (R_i), R_{\beta} \neq R_{\alpha}$, we have $\mathcal{G} (R_{\alpha}) \ge \mathcal{G}(R_{\beta})$ and $\mathcal{G}(R_{\alpha}) \ge \theta_G$, where

$$\mathcal{G} (R_{\alpha}) = {\rm acos} \frac{(R_{\alpha} - R_i)(\iota_+(R_{\alpha}) - R_i)}{\| R_{\alpha} - R_i\| \|(\iota_+(R_{\alpha}) -R_i)\|}.$$

(40)

Then, let $B_S \leftarrow B_S \cup \{R_i\}$ and define $\iota(R_i) = l_+(R_{\alpha}), r(R_i) = R_{\alpha}$.

Rule 2.

Suppose $R_{\alpha} \in \mathcal{N}_r (R_i)$ such that $R_{\alpha} \succeq l(R_i), r(R_{\alpha}) = R_i$, and $\|q_{\alpha} (t) - q_i(t)\| \le \| q_{l(R_i)} (t) - q_i (t)\|$. Then define $l(R_i) = R_{\alpha}$.

Rule 3.

Suppose $R_{\beta} \in \mathcal{N}_r(R_i)$ such that $R_{\alpha} \preceq r(R_i), l(R_{\alpha}) = R_i$, and $\|q_{\beta} (t) - q_i (t) \| \le \|q_{r(R_i)} (t) - q_i (t)\|$. Then define $r(R_i) = R_{\beta}$.

Rule 4.

Suppose $R_j \in \mathcal{N}_r (R_i)$ such that

$$\chi(q_{r(R_i)} (t), q_i(t), q_{l(R_j)} (t), q_j (t)) > 0,$$

(41)

where

$$ \begin{array}{l} \chi(q_q, \tilde{q}_1, q_2, \tilde{q}_2) = (l_1 - \|{\mathcal U}_1\|) (l_2 - \|{\mathcal U}_2 \|),\\[5pt] l_1 = \displaystyle\frac{1}{2} \|q_1 - \tilde{q}_1\|, {\mathcal U}_1 = Q - m_1, m_1 = \frac{1}{2} (q_1 + \tilde{q}_1)\\[7pt] l_2 = \displaystyle\frac{1}{2} \|q_2 - \tilde{q}_2\|, {\mathcal U}_2 = Q - m_2, m_2 = \frac{1}{2} (q_2 + \tilde{q}_2)\\ x_{Q} = (1/D)\big(\big(x_{q_2} - x_{\tilde{q}_2}\big)\big(x_{q_1}, y_{q_1} - y_{q_1} x_{q_1}\big)- \big(x_{q_1 - x_{\tilde{q}_1}}\big)\nonumber\\ \qquad\quad \big(x_{q_2} y_{q_2} - y_{q_2} x_{q_2}\big)\big)\\ y_{Q} = (1/D)\big(\big(y_{q_2} - y_{\tilde{q}_2}\big) \big(x_{q_1} y_{q_1} - y_{q_1} x_{q_1}\big)-\big(y_{q_1} - y_{\tilde{q}_1}\big)\nonumber\\ \qquad\quad \big(x_{q_1} y_{q_2} - y_{q_2} x_{q_2}\big) \\ {\cal D} = \big(x_{q_1} - x_{\tilde{q}_1}\big)\big(y_{q_2} - y_{{\tilde{q}_{2}}}\big)-\big(y_{q_1} - y_{\tilde{q}_1})(x_{q_2} -x_{\tilde{q}_2}\big)\end{array} $$

(42)

Then, let $r(R_i) = R_j$.

Rule 5.

Suppose $R_i \in \mathcal{N}_r(R_j)$ such that

$$ \chi (q_{{l(R_j)}}) (t), q_j(t), q_{r(R_i)} (t), q_i(t)) > 0. $$

(43)

Then, set $l(R_j) = R_i$.

Figure 7 shows the rules. To make the formulas in the following sections more readable, instead of using $l(R_i)$ and $r(R_i)$ for referring to a robot's left and right neighbors, we imagine that the boundary robots are re-labelled in such a way that their labels parametrize the boundary. The $R_i \in B_S$ with the least i (in fact, any robot can be picked for this purpose) can be chosen as the starting point of the curve $(s = 0)$. The robot immediately to its left is labelled $s = 1$ and so on. The robot to the right of the starting robot would thus be labelled $s = |B_S| - 1$.

Fig. 7

Boundary-assignment rules

Target shape and potential

Curve evolution, as discussed in Section 8, requires that a potential around the desired shape be defined. In our approach, a shape is simply represented by its boundary. Among the many approximate methods devised to describe shapes, Fourier descriptors can very compactly encode shapes and provide us with a simple reconstruction recipe. Any closed curve, parametrized by s (the arc length) and with perimeter T can be described by its Fourier expansion

$$q(s)=\sum^{\frac{N}{2}}_{n=-\frac{N}{2}} c_ne^{jn\omega s},\omega=\frac{n \pi}{T}$$

(44)

where the Fourier coefficients are given by

$$c_n=\frac{1}{T} \int^T_0 q(s)e^{-jns}ds.$$

(45)

Here, we assume that the perimeter is normalized by $T = 2\pi$, i.e. $\omega = 1$. For a shape described by a set of vertices $q_{i}, i = 0, \ldots, N - 1$, the Fourier descriptors $c_{n}, n = -N/2, \ldots, N/2$ are the coefficients of the Fourier transform of $q_{i}$:

$$ q_i=\sum^{\frac{N}{2}}_{k=-\frac{N}{2}} c_ke^{2\pi j\frac{ki}{N}}, c_k =\frac{1}{N}\sum^N_{i=0}q_ie^{-2\pi j\frac{ik}{N}} $$

(46)

Refer to Kalantar and Zimmer (2004) for the calculation of the set of Fourier descriptors $\{\mathcal{F}_n=(\mathcal{F}_{n_{x}}, \mathcal{F}_{n_{y}})\}$, invariant with respect to translation, rotation, scaling and choice of starting point, given the set $\{q_0,\ldots, q_{N-1}\}$ of vertices. The periodic boundary condition is defined by $q_{N-1+i}=q_{i-1}$ and $q_{-i} = q_{N-i}$, where $i = 1, \ldots, N$.

Given a set of invariant features $\mathcal{F}_{-M},\ldots,\mathcal{F}_M$ (comprising the canonical representation of $\gamma_{D}$) and the set $\{\mu^w_d, \theta_d, s_d\}$ of geometrical properties of the shape, where $\mu^w_d, \theta_d, s_d$ represent desired areal centre of gravity, orientation (with respect to the original shape), and scaling (expansion/shrinking), the formula

$$v_i=s_dR(\theta_d)v_i^{\mathcal{F}_d}+\mu^w_d$$

(47)

gives the positions of the vertices $\{v_o,\ldots, v_{N-1}\}$ of the polygon approximating the target shape, where $R (\vartheta)$ denotes the rotation matrix around the z axis by ϑ degrees, and

$$ v_i^{\mathcal{F}_d}=\sum^{M}_{n=-M, n \neq 0}\mathcal{F}_n{e^{\frac{2jn \pi i}{N}}} $$

(48)

A potential around $\gamma_{D}$ can be constructed using a distance function $d(\gamma_{D}, q(t))$ giving the closest point on $\gamma_{D}$ to a point q inside or outside the boundary. In Wang et al. (2002) a simple method is proposed. $\gamma_{D}(s)$ is first approximated with a cubic spline function $\tilde{\gamma}_{D}(s)$ with equally spaced breakpoints $\{s_o,\ldots, s_{N-1}\}$, with $s_{0} = 0$ and $s_{{N} - 1} = 1$. The distance between $q(t)$ and position $\tilde{\gamma}_{D}(s)$ is $D(s) = \|\tilde{\gamma}_D(s)-q(t)\|$ The value $s^{\ast}$ minimizing $D(s)$ is the closest point to $q(t), \stackrel{\raise1.52pt\hbox{\vrule height.4pt width36pt}{\kern-2pt}\rightharpoonup}{D(s^*)q(t)}$ is perpendicular to the curve and its distance is the shortest distance between $q(t)$ and the curve. For each segment $[s_{i}, s_{i+1}]$, let $P(s)$ be the quadratic polynomial interpolating $\tilde{\gamma}_{D}(s)$ at $s_{i}, (s_{i} + s_{i + 1})/2$, and $s_{i + 1}$. At each iteration, the value among $\{s_i,(s_i+s_{i+1})/2, s_{i+1}, s^\ast\}$ which gives the largest P is eliminated and the process continued until either $P(s^{\ast}) \leq \varepsilon_P$ or $s^{\ast}$ goes out of the segment. In case of convergence, Newton's formula

$$s^\ast=s^\ast-D'(s^\ast)/D''(s^\ast)$$

(49)

is used to get a better solution. Otherwise, another segment is tried.

Here, we use a much simpler strategy based on the polygonal approximation of $\gamma_{D}$. For each segment $S_{i} = \{v_i, v_{i+1}\}$ and point $q(t)$, let

$$\tilde{Q}(q(t), S_i)=v_i+\tilde{u}(v_{i+1}-v_{i})$$

(50)

$$\tilde{u}=\frac{\langle(q(t)-v_i),(v_{i+1}-v_i)\rangle}{\|v_{i+1}-v_i\|^2} $$

(51)

$$\displaylines{ Q(q(t), S_i) \cr = \left\{\begin{array}{l@{\quad}l} \tilde{Q}(q(t),S_i);&\|M_{S_i}-\tilde{Q}q, S_i\|\leq \displaystyle\frac{v_{i+1}-v_i}{2}\\[3pt] \imath(\tilde{Q}(q(t), S_i), v_{i+1}, v_i);&{\rm otherwise}\end{array}\right. }$$

(52)

$$\displaylines{ \imath(\tilde{Q}(q(t), S_i), v_{i+1}, v_i) \cr =\left\{\begin{array}{l@{\quad}l}v_{i-1};&\|\tilde{Q} q,S_i-v_i\|>\|\tilde{Q} q, S_i-v_{i+1}\|\\[3pt] v_i;&{\rm otherwise}\end{array}\right. }$$

(53)

where $M_{S_i}=(v_{i+1}+v_i)/2$. Moreover, let

$$ \phi_{v_{i+1}-v_i}={\rm atan}\big(y_{v_{i+1}-v_i}/x_{v_{i+1}-v_i}\big) $$

(54)

$$ (q-v_i)^\ast=R_z\big(-\phi_{v_{i+1}-v_i}\big)(q-v_i) $$

(55)

$$ \phi_{(q-v_i)^\ast}={\rm atan}\big(y_{(q-v_i)^\ast}/x_{(q-v_i)^\ast}\big) $$

(56)

Now, the distance function is defined as

$$ d(\gamma_D, q(t))=\min_{S_i}\|q(t)-Q(q(t),S_i)\|,$$

(57)

where the minimum is taken over all $S_{i}$ subject to the constraints

$$ \phi_{(q-v_i)^\ast} \neq \pi\quad {\rm and}\quad \phi_{(q-v_i)^\ast}\neq 0. $$

(58)

The in-out function is 1 if $q(t)$ is outside the shape and is $-1$ if it is inside and is defined by:

$$ f_{IO}(q(t), \gamma_D)=\left\{ \begin{array}{l@{\quad}l} 1;&0 \leq \phi_{(q-v_i)^\ast} < \pi\\ -1;&\pi \leq \phi_{(q-v_i)^\ast}<2\pi\end{array}\right. $$

(59)

$Q(q(t), S_{i})$ is the closest point on $\gamma_{D}$ to $q(t)$ and we denote it by $Q_{\gamma_{D}}(q(t))$.

The distance function provides a scalar field over $\Re^{2}$. To create a vector field, let's define

$$ g(q(t))=\xi(1-G_\sigma(d(\gamma_D, q(t)))) $$

(60)

where $G_\sigma(\cdot) \sim \mathcal{N} (0, \sigma)$. The gradient is computed as

$$\displaylines{ \nabla_{q(t)}g(q(t)) =-\xi \dot{G}_\sigma(d(\gamma_D,q(t)))\frac{N_{\gamma_{D}}(q(t))}{\|N_{\gamma_{D}}(q(t))\|} \cr = -\ \xi\frac{1}{\sigma^2}G_\sigma(d(\gamma_D,q(t)))N_{\gamma_D}(q(t)) }$$

(61)

where

$$\displaylines{ N_{\gamma_{D}}(q(t)) = Q_{\gamma_{D}}(q(t))-q(t), \cr \|N_{\gamma_{D}}(q(t))\| = d(\gamma_D, q(t)). }$$

(62)

$\nabla g(\cdot)$ defines a force field as required by curve evolution schemes.

Boundary morphing

The shape of the aggregate is controlled by the motion of the boundary robots; the interior robots passively comply. This is equivalent to continuous deformation of the initial closed simple curve $\gamma_{0} = \gamma(0)$ into another desired curve $\gamma_\infty$, ensuring collision-free paths for the robots and no self-intersections. There exists several possible solutions. In Kalantar and Zimmer (2004), an ad hoc strategy is proposed in which the initial curve, represented by a set of Fourier descriptors, successively evolves into intermediate curves constructed with decreasing subsets of the descriptor set, to form an ellipsoidal shape in the limit, and then evolving into curves given by increasing subsets of the descriptor set of the target curve. This method (shape interpolation) involves unnecessary intermediate curves, several re-parametrizations, and substantial synchronization.

A more formal method relies on general curve evolution theory (Kichenassamy et al., 1995; Chenyang et al., 2000; Belyaev et al., 1999). Let $\mathcal{U}: \gamma \to \mathcal{U}(\gamma) \in \Re$ denote a cost functional along γ. A curve evolution equation gives a one-parameter family of curves $\{\gamma(t)\}, t \in \Re^+$, such that $\gamma_t |_{t=0} = \gamma_0$ and $\gamma_\infty=\lim_{t \to \infty} \gamma_t$ is a local minimum of $\mathcal{U}$. The evolution equation takes the form of a partial differential equation $\partial \gamma(t)/\partial t=\Omega(\gamma(t), \nabla \mathcal{U}(\gamma(t)))$ and follows the gradient descent of $\mathcal{U}$. These curves are usually called active contours, especially in machine vision literature.

There are two different approaches to representation and implementation of active contours. Parametric active contours are explicitly represented as curves $\gamma(s, t)=[x(s, t), y(s, t)]$ parametrized by the arclength $s \in [0, 1]$. The curve evolves according to the Lagrangian dynamic reaction-diffusion equation $\partial \gamma(s, t)/\partial t=\Omega(\gamma(s, t), \nabla \mathcal{U} (\gamma(s, t)))$. The force Ω can be decomposed into its normal and tangential components. Thus, the equation would be

$$ \frac{\partial \gamma(s, t)}{\partial t}=\Omega_N(s,t)\stackrel{\rightharpoonup}{N}_\gamma(s, t)+\Omega_T(s,t)\stackrel{\rightharpoonup}{T}_\gamma(s,t) $$

(63)

where $\stackrel{\rightharpoonup}{N}_\gamma(s,t)$ and $\stackrel{\rightharpoonup}{T}_\gamma(s,t)$ denote, respectively, the inward normal and the tangent to the curve at s. The tangential component only changes the parametrization, while the normal component modifies the shape of the curve and is usually called the speed function. A classic example is the deformable active contour (snake):

$$\frac{\partial \gamma(s, t)}{\partial t}= (I(s, t)-\nabla P(\gamma(s, t)) \cdot \stackrel{\rightharpoonup} {N}_\gamma(s,t)) \cdot \stackrel{\rightharpoonup}{N}_\gamma(s,t) $$

(64)

$$ I(s, t)=\frac{\partial}{\partial s}\left(\alpha(s)\frac{\partial\gamma(s,t)}{\partial s}\right) - \frac{\partial^2}{\partial s^2}\left(\beta(s)\frac{\partial^2\gamma(s, t)}{\partial s^2}\right) $$

(65)

where $\alpha(s)$ and $\beta(s)$ control, respectively, the elasticity and rigidity of the contour. $\nabla P$ is a force field directing γ to the final desired curve $\gamma_{D}$. Also,

$$\displaylines{ \mathcal{U}(\gamma_t) = \frac{1}{2}\int^1_0\left(\alpha(s)\left\|\frac{\partial \gamma_t(s)}{\partial s}\right\|^2+\beta(s)\left\|\frac{\partial^2 \gamma_t(s)}{\partial s^2}\right\|^2\right) ds \cr -\ \int^1_0 P(\gamma_t(s))ds }$$

(66)

Geometric active contours, on the other hand, are implicitly defined as the zero level set of a scalar function $\psi(x, t), x \in \Re^{2}$. The curves evolve according to the Eulerian (heat) equation

$$ \frac{\partial_\psi(x, t)}{\partial t}=g(x)(\kappa+v_0)\|\nabla_\psi\|+\nabla g(x) \cdot \nabla_\psi, $$

(67)

where $g(x)$ is the same function as in Eq. (60) in Section 6, κ is the curvature and $v_{0}$ is a constant. For our application, the Lagrangian formulation is more suitable because it lends itself to distributed implementation. The evolution equation we use here is the parametrized equivalent of the general Eq. (67),

$$\displaylines{ \frac{\partial\gamma(s, t)}{\partial t} = (\alpha+\beta \kappa(s,t)) \cdot g((\gamma(s, t)))\stackrel{\rightharpoonup}{N}_\gamma(s, t) \cr -\ \langle\nabla g(s, t),\stackrel{\rightharpoonup}{N}_\gamma(s, t) \rangle\stackrel{\rightharpoonup}{N}_\gamma(s, t) \cr +\ \omega(\gamma(s,t))\stackrel{\rightharpoonup}{T}_\gamma(s, t)} $$

(68)

where

$$ \alpha= f_{IO}(\gamma(s, t), \gamma_D), $$

(69)

$$ g(\gamma(s, t))=G_\sigma(d(\gamma_D(t), \gamma(s, t))), $$

(70)

$$ \stackrel{\rightharpoonup}{N}_\gamma(s, t)=\frac{{y}_s(s,t)-x_s(s, t)}{\sqrt{x_s(s, t)^2+{y}_s(s, t)^2}}, $$

(71)

$$ \stackrel{\rightharpoonup}{T}_\gamma(s, t)=\frac{\partial \gamma(s, t)/\partial s}{\|\partial\gamma(s, t)/\partial s\|}=\stackrel{\rightharpoonup}{N}_\gamma(s, t)^\bot, $$

(72)

$$\kappa(s, t)=\frac{{y}_{ss}(s, t) \cdot x_s(s,t)-x_{ss}(s, t)\cdot {y}_s(s, t)}{\sqrt{x_s(s,t)^2+{y}_s(s, t)^2}}$$

(73)

g is zero at the desired boundary and stops the propagating front, the term involving κ smooths the curve such that those areas of the boundary with higher curvatures move faster. $\omega(\gamma(s, t))$ does not have any effect other than re-parametrizing but is crucial for numerical implementation, as will be discussed next. Figure 8 shows the evolution of the boundary under the influence of the force field.

Fig. 8

Motion of curves under shape potentials

Boundary robots use a discretized version of Equ. (68) to move. We use the following rule:

$$ \begin{array}{@{}l@{}} \displaystyle q_i [n] \nonumber \\ \displaystyle = q_i [n-1] + \Delta t (f_{1O} (\gamma_i [n]) + \beta\kappa_i[n]) \cdot g (\gamma_i [n]) \cdot{\mathop{N}^\rightharpoonup}_{\gamma_i}[n] \nonumber \\ \displaystyle{\quad} -\ (\nabla_{q_i[n]} g(q_i [n]) \cdot {\mathop{N}^\rightharpoonup}_{\gamma_i} [n]) \cdot{\mathop{N}^\rightharpoonup}_{\gamma_i}[n] + \omega_i [n] \cdot{\mathop{T}^\rightharpoonup}_{\gamma_i}[n]) \end{array} $$

(74)

We use the following central difference approximations:

$$ \begin{array}{c} \displaystyle dx_i [n]/ ds \approx \Delta x / 2 \Delta s, d^2 x_i [n]/ ds^2\approx \Delta x^2 / \Delta s^2, \\[3pt] \displaystyle dy_i [n]/ ds \approx\Delta y / 2 \Delta s, d^2 y_i [n]/ ds^2 \approx \Delta y^2 /\Delta s^2, \end{array} $$

(75)

where

$$ \begin{array}{l} \displaystyle \Delta x = x_{i+1}[n] - x_{i-1} [n], \\[3pt] \displaystyle \Delta y = y_{i+1}[n] - y_{i-1} [n],\\[3pt] \displaystyle \Delta_{xx} = x_{i-1}[n] - 2x_{i} [n] + x_{i+1} [n], \\[3pt] \displaystyle \Delta_{yy} = y_{i-1}[n] - 2y_{i} [n] + y_{i+1} [n],\\[3pt] \displaystyle {\rm and}\ \Delta s = \int^1_0 \frac{\gamma (s)ds}{\|B_S\|} \end{array} $$

(76)

Thus

$$ {\mathop{N}^\rightharpoonup}_{\gamma} [n] = \frac{\Delta y -\Delta x}{\sqrt{\Delta x^2 + \Delta y^2}}, $$

(77)

$$\kappa_i [n]= 4 \frac{\Delta_{yy} \cdot \Delta x - \Delta_{xx}\cdot \Delta y}{(\Delta x^2 \cdot \Delta y^2)^{3/2}}$$

(78)

In the above formulas $\Delta s$ does not appear so that as robots get closer to each other, the calculations will get more unstable due to accumulation of errors. That's the reason why a non-zero tangential force is used. This force should uniformly distribute the robots along the boundary. Rather than calculating the perimeter of the boundary and dividing it by the number of robots to determine the spacing between robots, we use a simple local force acting on each robot that achieves the same thing upon convergence:

$$ \omega_i(t)=\zeta\left(e^{\frac{4(q_i(t)-q_{i-1}(t))^2}{\varsigma(t)^2}}-e^{\frac{4(q_{i+1}(t)-q_i(t))^2}{\varsigma(t)^2}}\right) $$

(79)

where $\varsigma(t)=\|q_{i+1}-q_i\|+\|q_i-q_{i-1}\|$.

It should be noted that instead of gradients constructed out of descriptor sets for desired geometric shapes, we can use concentration gradients of a diffusion process and stop at an isocline. This way, the geometric shape is not predefined and is the shape of the isocline (Bertozzi et al., 2005).

Interior motion

The interior robots should at all times distribute themselves uniformly inside the boundary while staying far enough away from the boundary to prevent possible leakage out of it. Each interior robot has to handle two different interactions: one with other interior robots and the other with boundary robots. Interaction with fellow interior robots is the same as motion under the influence of Lennard–Jones forces described in Section 4. If there are no boundary robots in the neighborhood of an interior robot, the net force on it is simply calculated using Eq. (23). If the boundary robots are treated the same way as interior robots, interior robots can in many situation easily escape the boundary by squeezing through boundary robots. This can happen when two boundary robots are further than some certain distance apart and the aggregated force from the interior on a particular interior robot in the vicinity of the boundary exceeds the one imposed on it by the boundary robots. This means that the forces from the boundary robots and from the interior robots should be balanced. One might be tempted to prevent the interior robots from moving in the direction of the boundary by using the formula

$$ \left\langle \mathcal{F}_I,\left(\frac{\mathcal{F}_B}{\|\mathcal{F}_B\|}\right)^\bot\right\rangle+\mathcal{F}_B $$

(80)

when the angle between $\mathcal{F}_{B}$ and $\mathcal{F}_{I}$ is greater than $\pi/2$. This will cause the interior robots in the neighborhood of the boundary to keep moving along the boundary. Another solution is to balance the forces using a weighted summation $w_B \mathcal{F}_B+w_I\mathcal{F}_I$ but then the optimal weights have to be determined.

The strategy we will use here is to treat the boundary as being composed of segments rather than individual robots and calculate the force from the boundary as a function of the distance to these segments. For each interior robot $R_i$, consider the set

$$ \begin{array}{l} \displaystyle \Omega_i = \{\{q_{\alpha},q_{\beta}\}| R_{\alpha},R_{\beta} \in B_S, \\ [3pt] \displaystyle (R_{\alpha} = l(R_{\beta}),R_{\beta} = r(R_{\alpha})), \\[3pt] \displaystyle (R_{\alpha} \in N_i \cap B_S) \vee (R_{\beta} \in N_i \cap B_S)\} \end{array} $$

(81)

Now, define the motion of $R_i$ as

$$\displaylines{ \dot{q}_i(t) = \mathcal{F}^i_I(q(t)) \cr = \sum_{R_{\eta} \in I_S} f_{LJ_{BW}}(q_i(t) - q_{\eta}(t))\cr +\ \sum_{\{q_{\alpha},q_{b}\} \in \Omega_i}\frac{\partial \phi_{LJ_{BW}}}{\partial t}(d(q_i(t),\{q_{\alpha},q_{\beta}\})\cr \times\ \frac{Q(q_i(t),\{q_{\alpha},q_{\beta}\}) -q_i(t)}{\|Q(q_i(t),\{q_{\alpha},q_{\beta} \}) - q_i(t)\|}} $$

(82)

where

$$ \tilde{Q}(q_i(t),\{q_{\alpha},q_{\beta}\}) = q_{\alpha} +\tilde{u}(q_{\beta} - q_ {\alpha}), $$

(83)

$$\tilde{u} = \frac{\langle (q_i (t) - a_{\alpha}), (q_{\beta} -q_{\alpha})\rangle} {\|q_{\beta} - q_{\alpha}\|^2},$$

(84)

$$\displaylines{ Q(q(t),\{q_{\alpha},q_{\beta}\}) \cr =\ \left\{ \begin{array}{l@{\quad}l} \tilde{Q}(q(t), \{q_{\alpha},q_{\beta}\}); & \varrho \leq 0\\ \iota(\tilde{Q}(q(t),\{q_{\alpha},q_{\beta}\}),q_{\beta,q_{\alpha}}); & {\rm otherwise}\end{array}\right. }$$

(85)

$$ \varrho = \|M_{\{q_{\alpha},q_{\beta}\}} -\tilde{Q}(q,\{q_{\alpha},q_{\beta}\})\| - \|q_{\beta} -q_{\alpha}\|/2 $$

(86)

$$\displaylines{ \iota(\tilde{Q}(q(t),\{q_{\alpha},q_{\beta}\}),q_{{\beta},q_{\alpha}}) \cr =\ \left\{\begin{array}{l@{\quad}l} q_{\beta}; & \|(\tilde{Q}(q, \{q_{\alpha},q_{\beta}\})\!-\! q_{\alpha}\|\! >\! \|\tilde{Q} (q, \{q_{\alpha},q_{\beta}\}) - q_{\beta}\|\\[3pt] q_{\alpha}; & {\rm otherwise}\end{array}\right. }$$

(87)

where $M_{\{q_{\alpha},q_{\beta}\}} = (q_{\beta} + q_{\alpha})/2$. This scheme is like applying usual particle-based forces for a very dense boundary (Fig. 9).

Fig. 9

Motion of boundary and interior robots

The maximum area covered by an aggregate of robots is a function of the comfortable distance $D_S$. Suppose $D_S$ is fixed, and denote the area by $\mathcal{A}_{D_S}$. If the area of the target curve $\gamma_D$,

$$ \mathcal{A}_{\gamma_D} = \frac{1}{2}\oint f(\gamma_D(s))\gamma'{_D}(s)ds, $$

(88)

$f(x, y) = (y - x)$ is smaller than $\mathcal{A}_{D_S}$, then the interior robots will be compacted together but will still cover this area uniformly. On the other hand, if it is larger, then part of the area surrounded by $\gamma_D$ will be empty. This means that $D_S$ should increase to compensate. $D_{S_i}(t)$ can be changed adaptively as a function of the difference $\mathcal{A}_{\gamma_D} - \mathcal{A}_{D_S}$. Note the dependence on time as well as the individual. This method can also be implemented locally. Define the measure of pressure (or lack of it) on an interior robot $R_i$ as

$$\displaylines{\Psi_i(t) = \sum_{\alpha \in \hat N_{R_i{(t)}}} \frac{\|q_{\alpha}(t)- q_i(t)\| - (D_{S_i} (t)- \varepsilon)}{D_{S_U} - D_{S_L}} \cr +\ \frac{(\theta_{\alpha + 1} - \theta_{\alpha}) - \pi/3}{2\pi} }$$

(89)

where $\hat{N}_{R_i}$ is the same as $N_{R_i}$ except that the elements are ordered according to

$$\theta_{\alpha} = {\rm a}\tan\big(y_{q_{\alpha}{{(t)}} -q_{i{^{(t)}}}}/x_{q_{\alpha}{{(t)}} - q_{i{^{(t)}}}}\big) $$

(90)

in the interval $[0, 2\pi], D_{S_U}$ and $D_{S_L}$ denote bounds on $D_S(t) \cdot \Psi_i (t)$ is actually measure of how far the local status is from a perfect hexagon. The minimum of $\Psi_i(t)$ (maximum pressure) is

$$L_{\Psi_i} = -(\|S\| - 1)\left(\frac{D_{S_i}(t) -\varepsilon}{D_{S_U} - D_{S_L}} + \frac{1} {6}\right)$$

(91)

(corresponding to a situation where all of the aggregate is located at $q_i(t)$) and the maximum (least pressure) occurs when there is only one robot at the farthest end of the neighborhood and is calculated as

$$ U_{\Psi_i} = \frac{r(N_i) - D_{S_i}(t) + \varepsilon}{D_{S_U} -D_{s_L}} + \frac{5}{6}.$$

(92)

When $\hat{N}_{R_i} = \O$, we put $\Psi_i (t) = {\mathcal U}_{\Psi_i}$ Define

$$ \Lambda(v) = \left\{\begin{array}{l@{\quad}l} v \cdot (D_{S_U} - D_{S_i})/U_{\Psi_i}; & v > 0\\0; & v = 0\\v \cdot (D_{S_L} - D_{S_i})/L_{\Psi_i}; & v < 0\end{array}\right. $$

(93)

The algorithm is as follows: when an equilibrium is reached, $D_{S_i}(t)$ is updated using

$$D_{S_i}(t) = D_{S_i}(t) + \Lambda(\Psi_i(t)). $$

(94)

This will perturb the system from equilibrium. To achieve uniform coverage, all the $D_{ S_i}(t)$ should be the same. This can be achieved via synchronization among interior robots. A strategy for this is evolving $D_{S_i}(t)$ according to the formula

$$D_{S_i}(t) = \frac{D_{S_i}(t) + \sum_{R_j \in N_i (t) \cap I_S}R_j}{1 + \|N_i (t) \cap I_S\|} $$

(95)

This scheme has been proved to be convergent (Jadbabaie et al., 2003). After convergence, $D_{S_i}$ will converge to the average

$$ \frac{1}{\|I_S\|}\sum_{R_i \in I_S} D_{S_i}.$$

(96)

Here, we instead use the simplest solution. We put $D_S$ to a large value such we will always have $\mathcal{A}_{\gamma_D} \ll \mathcal{A}_{D_S}$. This simple solution has the drawback that the motion of the interior robots has to be sufficiently shunted to prevent large abrupt forces.

Special cases

In this section, we discuss two classes of shapes. One is the ellipsoid, which can be related to previous work in Belta and Kumar (2002), and the other is one which facilitates splitting and joining two assemblies of robots.

Fig. 10

Split and join operations

Unlike small formations, join and split operations for a large aggregate with approximate shapes is not trivial. Here, we just mention a possible avenue. The main idea is that the boundary shape descriptors can be calculated in such a way that the resulting shape is more appropriate for these operations. As an example, consider the shape in Fig. 10, composed of two overlapping closed curves (circles in this case). This shape is clearly more suitable for splitting. Let $\gamma_r(s)$ denote a circle with radius r located at (0, 0). Let $0 < L < 2r$ be given. From the figure, it is obvious that $\theta = {\rm asin}(L/(2r))$ and that $d = r \cos(\theta)$. Now, define the shape by

$$ \gamma_S(s) = \left\{ \begin{array}{l@{\quad}l} \displaystyle\gamma_r(s) + d; &\displaystyle 0 \leq s < \frac{1}{4}\\ \displaystyle\gamma_r\left(s + \frac{\pi - \theta}{4\theta}\right) - d; &\displaystyle \frac{1}{4} \leq s < \frac{3}{4}\\ \displaystyle\gamma_r(s) + d; &\displaystyle \frac{3}{4} \leq s < 1\end{array}\right. $$

(97)

Denote the scaled, translated and rotated curve by $\tilde{\gamma}_S(s) = s_S R_z (\phi_ S)\gamma_S(s) + t_S$. Suppose we discretize $\gamma_S$ with N points and compute the Fourier descriptors. Let $\mathcal{F} = \{\mathcal{F}_{-M}, \ldots, \mathcal{F}_M\}$ be the calculated descriptors. Using $\mathcal{F}$, the boundary robots will form an approximate shape (shown in the figure with thick lines). Define the b-Neighborhood of $R_i \in B_s$ by

$$ N^B_b(R_i) = \{R_j \in B_S| j \leq (i + b)_{{\rm mod}{\it N}}, j \geq (i -b)_{{\rm mod}{\it N}}\} $$

(98)

Suppose, for a certain $R_i \in B_S$, there exists a $R_j \in (B_S \cap N_r (R_i))\backslash N_b^B (R_i)$, such that $\|q_i(t) - q_j(t)\|$ is the minimum, and similarly for $R_j$. If there is just one such pair $\{R_i, \hat{R}_i = R_j\}$, then, for splitting, we set

$$ \begin{array}{@{}l@{}} l(R_i) = \hat{R}_i, r(\hat{R}_i) = R_i, \quad\mbox{and we put} \\[3pt] r(R_{i + 1}) = R_{j - 1},\quad {\rm and}\quad l(R_{j - 1}) =R_{i + 1}. \end{array} $$

(99)

Alternatively, one might define

$$ \begin{array}{@{}l@{}} r(R_i) = \hat{R}_i, l(\hat{R}_i) = R_i, \\ [3pt] l(R_{i - 1}) =R_{j + 1},\quad {\rm and}\quad r(R_{j + 1}) = R_{i - 1}. \end{array} $$

(100)

After this, a reordering should be done on the newly created curves. L should be chosen small enough so that no interior robots get trapped inside the narrow region where the two ends of the curve are close together.

For joining two aggregates $S_1$ and $S_2$, they first have to form circular shapes with roughly the same scale and get close enough together. The procedure is very similar to splitting but encompasses two aggregates. Suppose, for a certain $R_i \in B_{S_1}$, there exists a $R_j \in B_{S_2} \cap N_r(R_i)$, such that $\|q_i(t) - q_j(t)\|$ is the minimum in $R_b^B(R_i)$, and similarly for $R_j$. Then, we can set

$$ \begin{array}{@{}l@{}} l(R_i) = R_j, r(R_j) = R_i, \\ [3pt] r (R_{i + 1}) = R_{j - 1},\quad {\rm and}\quad l(R_{j - 1}) = R_{i + 1}, \end{array} $$

(101)

or, alternatively,

$$ \begin{array}{@{}l@{}} r(R_i) = R_j, l(R_j) = R_i, \\[3pt] l(R_{i - 1}) = R_{j + 1}, \quad {\rm and}\quad r(R_{j + 1}) = R_{i - 1}, \end{array} $$

(102)

The two alternative cases in both operations can be selected according to some bound on maximum curvature. In both operations, if there are more than one pair satisfying the minimum condition, a more involved strategy should be devised. In Belta and Kumar (2002), control rules are developed to form ellipsoidal shapes with large number of robots. In our approach, such ellipsoids can be formed using just the two descriptors $\{\mathcal{F}_{-1},\ldots, \mathcal{F}_1\}$. They identify the main axes of the ellipsoid (the best fit to a shape). $\mathcal{F}_{-1}$ and $\mathcal{F}_1$ would be the result of applying Fourier transformation to the unit circle. An ellipsoidal curve with axes $0 < A_x \leq 1$ and $0 < A_y \leq 1$, can then be constructed using the formula

$$ sR(\phi) \big(\mathcal{F}_{-1}e^{-2j\pi\frac{s}{N}} +\mathcal{F}_1 e^{-2j\pi\frac{s} {N}}\big) + t, $$

(103)

where the equation

$$\displaylines{ \frac{(\mathcal{F}_{1_x} \cos (2\pi i/N) + \mathcal{F}_{-1_x} \cos(-2\pi i/N))^2}{A^2_x} \cr + \frac{(\mathcal{F}_{1_y} \sin (2\pi i/N)+ \mathcal{F}_{-1_y} \sin (-2\pi i/N))^2}{A^2 _y} = 1 }$$

(104)

should be satisfied. We can arbitrarily choose three of the parameters and calculate the fourth.

Simulation results

In this section, we present two simulations. The first one shows the boundary-assignment procedure in action. The second one demonstrates the morphing process through snapshots of the aggregate.

In Fig. 11(1), an initial assembly of robots is shown. The initial distribution must be such that the formation graph is connected (in the sense defined in Section 2). This is, of course, just a necessary but not a sufficient condition for the whole aggregate to form a single cohesive group. Figure 11(2) through to 11(4) show the evolution in time of the swarm. In this simulation, the boundary-determination process is active from the start. Here, we have chosen $\theta_G = 70$. Note that, as the energy of the whole system, $\phi^S_{LJ}(q(t))$, is decreased, the quality of the boundary improves. In snapshots 1, 2, and 3, only rule 1 is active. In snapshot 4, the other rules have been turned on as well.

Fig. 11

Boundary self-organization

Fig. 12

Morphing

Fig. 13

Control system function block diagram

Figure 12 shows the sequence of snapshots of an aggregate composed of N robots going through the morphing process. Here, the target curve coincides with the centre of mass of the initial aggregate. Translation and rotation can be carried out using the simple law

$$ \dot{q}_i(t) = \upsilon_0\frac{\mu_d - \mu(t)}{\|\mu_d - \mu(t)\|}+ \big(e^{i(h\omega_0 t)q _i(t)} - q_i (t)\big) $$

(105)

where $\upsilon_0$ and $\omega_0$ denote nominal linear and angular velocities, and h determines the sense of rotation. Alternatively, $\mu_d$ and $\theta_d$ can be entered into formula (47) defining $\gamma_D$.

Figure 13 shows the function block diagram of the control system when in morphing mode. The various equations derived in the paper are shown in the corresponding blocks.

Conclusions and further research

We showed that large aggregates of autonomous vehicles with limited communication capabilities can be commanded to form complex geometric shapes using low-dimensional shape descriptors. We also showed that the problem can be further simplified if the aggregate is treated as being composed of two components, its boundary and its interior, with the boundary performing shape formation and the interior part maintaining a uniform distribution. We solved the problem of boundary assignment through a simple self-organization strategy. We also derived precise distributed control rules, relying on neighborhood information, implementing these behaviours. The validity of the process was demonstrated by simulation results. There is definitely a lot of work to be done before this scheme can be implemented on real robots, and is currently a topic of further research. Also, we just addressed the 2-D case. The method should be extended to motion on surfaces. Also, we have only considered synchronous update; a communication strategy with delays is more close to reality. It is worthwhile to note that the formulation we used here can be extended to a continuous one. Thus, the formation can be described by $\mathcal{R}(t) = (\gamma(t), \rho(t))$, where $\gamma: [0, 1] \otimes \mathfrak{R}_{+} \rightarrow \mathfrak{R}^2$ is a family of curves, and $\rho : I(\gamma(t)([0, 1])) \rightarrow \mathfrak{R}$ is the concentration function, with I giving the interior of a closed curve in $\mathfrak{R}^2$. The motion of γ is given in Eq. (75), and the motion of the interior, i.e. ρ, is governed by the diffusion equation

$$ \frac{\partial \rho (x,y,t)}{\partial t} = D\left(\frac{\partial^2\rho}{\partial x^2} + \frac{\partial^2 \rho}{\partial y^2}\right) $$

(106)

where $D = 1 - e^{-\alpha(\rho(t)-\rho_d)}$ is the diffusion rate corresponding to the force acting on a particle, subject to the boundary condition

$$ \frac{\partial \rho (x,y,t)}{\partial \stackrel{\rightharpoonup}{N}\gamma(s,t)} = 0 $$

(107)