text:
# Introduction

## Introduction

Gravitational waves, that is a propagating warpage of space time generated from compact concentrations of energy, like neutron stars and black holes, have not yet been detected directly, although their indirect influence has been seen and measured with great accuracy. Presently there are, worldwide, many efforts to detect gravitational radiation, not only because a direct confirmation of their existence is interesting per se but also because new insights on the nature of gravity and of the Universe itself could be gained. For these reasons exact solutions of the Einstein field equations deserve special attention when they are of propagative nature. The need of taking into full account the nonlinearity of Einstein’s equations when studying the generation of gravitational waves from strong sources is generally recognized . Moreover, despite the great distance of the sources from Earth (where almost all the experimental devices, laser interferometers and resonant antennas, are located) there are situations where the non linear effects cannot be neglected. This is the case when the source is a binary coalescence: indeed it has been shown  that a secondary wave, called the Christodoulou memory is generated via the non linearity of Einstein’s field equations. The memory seems to be too weak to be detected from the present generation of interferometers  (even if its frequency is in the optimal band for the LIGO/VIRGO interferometers) but of the same order as the linear effects related to the same source, thus stressing the relevance of the nonlinearity of the Einstein’s equations also (soon) from an experimental point of view.

On the theoretical side, starting from the seventy’s new powerful mathematical methods have been developed to deal with nonlinear evolution equations. For instance, a suitable generalization of the  Inverse Scattering Transform allows to integrate  Einstein field equations for a metric of the form

$$g=f(z,t)\left(dt^2dz^2\right)+h_{11}(z,t)dx^2+h_{22}(z,t)dy^2+2h_{12}(z,t)dxdy.$$

Indeed, the corresponding vacuum Einstein field equations reduce essentially111The function $`f`$ can be obtained by quadratures in terms of the matrix $`𝐇`$. to

$$\left(\alpha 𝐇^1𝐇_\xi \right)_\eta +\left(\alpha 𝐇^1𝐇_\eta \right)_\xi =0,$$

where $`𝐇`$ $`h_{ab},`$ $`\xi =\left(t+z\right)/\sqrt{2},\eta =\left(tz\right)/\sqrt{2},\alpha =\sqrt{\left|det𝐇\right|}`$. This is a system of non-linear differential equations whose form is typical for two-dimensional integrable systems. Its solution through the  Inverse Scattering Transform, yields  gravitational solitary waves solutions.

A geometric inspection of the metric above shows that it is invariant under translations along the $`x,y`$-axes, i.e. it admits two Killing fields, $`_x`$ and $`_y`$, closing on an Abelian222The study of metrics invariant for a Abelian $`2`$-dimensional Killing Lie algebra goes back to Einstein and Rosen , Kompaneyets ; recent analysis can be found in  two-dimensional Lie algebra $`𝒜_2`$. Moreover, the distribution $`𝒟`$, generated by $`_x`$ and $`_y`$, is $`2`$-dimensional and the distribution $`𝒟^{}`$ orthogonal to $`𝒟`$ is integrable and transversal to $`𝒟`$.

Thus, it has been natural to consider  the general problem of characterizing all gravitational fields $`g`$ admitting a Lie algebra $`𝒢`$ of Killing fields such that:

I. the distribution $`𝒟`$, generated by the vector fields of $`𝒢`$, is two-dimensional.

II. the distribution $`𝒟^{}`$ orthogonal to $`𝒟`$ is integrable and transversal to $`𝒟`$.

The aim of this article is to study, among those solutions, the ones which show a propagative nature. A preliminary account of our results is given in .

The article is organized as follows. In section 1 gravitational fields invariant for a two dimensional Lie algebra are characterized by reducing the Einstein equations to the so called $`\mu `$-deformed Laplace equation. Harmonic coordinates are also introduced. Section 2 is devoted to the analysis of the wave-like character of the solutions through the Zel’manov and the Pirani criteria. In section 3 realistic sources are described. In section 4 Landau-Lifshitz’s and Bel’s energy-momentum pseudo-tensors are introduced and a comparison with the linearised theory is performed. Eventually, section 5 is devoted to the analysis of the polarization of the waves.

In the following, $`𝒦il\left(g\right)`$ will denote the Lie algebra of all Killing fields of a metric $`g`$ while Killing algebra will denote a sub-algebra of $`𝒦il\left(g\right)`$.

Moreover, an integral (two-dimensional) submanifold of $`𝒟`$ will be called a Killing leaf, and an integral (two-dimensional) submanifold of $`𝒟^{}`$ orthogonal leaf.

## 1 Invariant vacuum gravitational fields

Let $`g`$ be a metric on the space-time $`M`$ and $`𝒢_2`$one of its Killing algebras whose generators $`X,Y`$ satisfy the commutation relation

$$[X,Y]=\sigma Y,\sigma =0,1.$$
(1)
The Frobenius distribution $`𝒟`$ is two-dimensional and a coordinate system $`(x^\mu )`$, $`\mu =1,2,3,4`$ exists such that

$$X=\frac{}{x^3},Y=\mathrm{exp}\left(\sigma x^3\right)\frac{}{x^4}.$$

Such a coordinate system is called  semiadapted (to the Killing fields).

Condition II of the previous section allows to construct special semi-adapted charts such that the fields $`e_1=/x^1`$, $`e_2=/x^2`$, belong to $`𝒟^{}`$. In such a chart, called from now on adapted, the most general $`𝒢_2`$-invariant metric has the form

$`g`$ $`=`$ $`g_{ij}dx^idx^j+\left(\sigma ^2\lambda \left(x^4\right)^22\sigma \mu x^4+\nu \right)dx^3dx^3+`$
$`2\left(\mu \sigma \lambda x^4\right)dx^3dx^4+\lambda dx^4dx^4,i,j=1,2`$
where $`g_{ij}`$, $`\lambda `$, $`\mu `$, $`\nu `$ are arbitrary functions of $`(x^1,x^2)`$.

If the Killing field $`Y`$ is not of  light type, i.e. $`g(Y,Y)0`$ , condition II follows automatically from I. The local structure of this class of Einstein metrics has been explicitly described; it turns out  that a third Killing field $`Z`$ exists such that $`(X,Y,Z)`$ span the Killing algebra $`so(2,1)`$ and all invariant metrics are static and locally diffeomorphic to the pseudo-Schwarzschild metric. This metric was also found in the context of warped solutions .

In the following the Killing field $`Y`$ will be assumed to be of  light type. In this case the general solution of vacuum Einstein equations, in the adapted coordinates $`(x^1,x^2,x^3,x^4)`$, is given by

$$g=2f(dx^1dx^1+dx^2dx^2)+\mu [(w(x^1,x^2)2\sigma x^4)dx^3dx^3+2dx^3dx^4],$$
(2)
where $`\mu =D\mathrm{\Phi }+B`$; $`D,B`$, $`\mathrm{\Phi }`$ is a non constant harmonic function of $`x^1`$ and $`x^2`$, $`f=\left(\mathrm{\Phi }\right)^2\sqrt{\left|\mu \right|}/\mu `$, and $`w(x^1,x^2)`$ is a solution of the $`\mu `$-deformed Laplace equation:

$$\mathrm{\Delta }w+\left(_{x^1}\mathrm{ln}\left|\mu \right|\right)_{x^1}w+\left(_{x^2}\mathrm{ln}\left|\mu \right|\right)_{x^2}w=0.$$
(3)
The solutions of the $`\mu `$-deformed Laplace equation will also be called  $`\mu `$-harmonic functions.

In the particular case $`\sigma =1`$, $`f=1/2`$ and $`\mu =1`$, the above metrics are locally diffeomorphic to a subclass of the vacuum Peres solutions  corresponding to a special choice of the harmonic function parameterising that metrics.

This is easily seen by introducing, for $`\stackrel{~}{u}0`$, new coordinates $`(x,y,\stackrel{~}{u},\stackrel{~}{v})`$ defined by $`x^1=x,x^2=y,x^3=\mathrm{ln}\left|\stackrel{~}{u}\right|,x^4=\stackrel{~}{u}\stackrel{~}{v}.`$

Of course, metrics (2) can also be obtained by imposing an additional isometry to metrics admitting a Killing vector field of light type and, indeed, they are an extension of the ones reported in .

When $`w`$ is constant the above family of Einstein metrics admits the  time-like Killing vector field

$$T=\mathrm{exp}\left(x^3\right)\frac{}{x^3}+\frac{1}{2}\left[\left(w2\sigma x^4\right)\mathrm{exp}\left(x^3\right)+\mathrm{exp}\left(x^3\right)\right]\frac{}{x^4}$$

which is hypesurfaces orthogonal. This means that these Einstein metrics are just static gravitational fields.

As it will be argued in the next sections, when $`w`$ is not constant the above family of Einstein metrics may represent propagative gravitational fields.

Since the distribution $`𝒟^{}`$ is assumed to be transversal to $`𝒟`$, the restriction of $`g`$ to any Killing leaf, say $`𝒮`$, is non-degenerate. So, $`(𝒮,g|_S)`$ is a homogeneous two-dimensional Riemannian manifold. In particular, the Gauss curvature $`K\left(𝒮\right)`$ of the Killing leaves is constant. An explicit computation shows that $`K\left(𝒮\right)`$ vanishes.

Thus, the space-time $``$ has a fiber bundle structure

$$\pi :𝒲,$$

whose basis $`𝒲`$ is diffeomorphic to the orthogonal leaves and whose fibers are the Killing leaves and as such are flat two-dimensional Riemann manifolds.

Despite the non-linear nature of general relativity, gravitational fields (2) obey to two superposition laws. Indeed, with two harmonic functions $`\mathrm{\Phi }_1`$ and $`\mathrm{\Phi }_2`$ we can associate three gravitational fields (in facts a whole two-parameters family), that is, $`g_{\mathrm{\Phi }_1}`$, $`g_{\mathrm{\Phi }_2}`$ and $`g_{a\mathrm{\Phi }_1+b\mathrm{\Phi }_2}`$; the last one, which is associated with the linear combination of $`\mathrm{\Phi }_1`$ and $`\mathrm{\Phi }_2`$, may be regarded as the superposition of the two associated solutions $`g_{\mathrm{\Phi }_1}`$ and $`g_{\mathrm{\Phi }_2}`$.

The second superposition law follows from the linearity of the $`\mu `$-deformed Laplace equation, so that with two $`\mu `$-harmonic functions $`w_1`$ and $`w_2`$ we can associate three gravitational fields $`g_{w_1}`$, $`g_{w_2}`$ and their sum $`g_{w_1+w_2}\left(g_{2w_1}+g_{2w_2}\right)/2`$

### 1.1 The harmonic coordinates.

The coordinates $`(x^3,x^4)`$ on the Killing leaves $`𝒮`$ have a clear geometric meaning but are of difficult physical interpretation. Fortunately, being the Killing leaves flat manifolds, it is possible to introduce coordinates $`(\stackrel{~}{z},\stackrel{~}{t})`$ diagonalizing the metric

$$g|_𝒮=\stackrel{~}{\mu }[(\stackrel{~}{w}2\sigma x^4)dx^3dx^3+2dx^3dx^4],$$

where $`\stackrel{~}{\mu }`$ and $`\stackrel{~}{w}`$, being the restriction of the functions $`\mu `$ and $`w`$ to the Killing leaves, are constant.

The coordinate system $`(x,y,z,t)`$, where for $`z>t`$

$$\{\begin{array}{c}x=w_1(x^1,x^2)\hfill \\ y=w_2(x^1,x^2)\hfill \\ z=\frac{1}{2}\left[\left(2x^4w(x^1,x^2)\right)\mathrm{exp}\left(x^3\right)+\mathrm{exp}\left(x^3\right)\right]\hfill \\ t=\frac{1}{2}\left[\left(2x^4w(x^1,x^2)\right)\mathrm{exp}\left(x^3\right)\mathrm{exp}\left(x^3\right)\right],\hfill \end{array}$$

is harmonic, $`w_1(x^1,x^2)`$ and $`w_2(x^1,x^2)`$ denoting any two independent $`\mu `$-harmonic functions. The generic Killing leaf $`𝒮`$ is mapped onto the half-plane $`z>t`$, the line $`z=t`$ representing the points with $`x^3=+\mathrm{}`$.

In these coordinates, metrics (2) take the form

$`g`$ $`=`$ $`2{\displaystyle \frac{\sqrt{\mu }\left(\mathrm{\Phi }\right)^2J^2}{\mu }}[(y)^2dx^2+(x)^2dy^22xydxdy]`$
$`+\mu [dz^2dt^2+d\left(w\right)d\left(\mathrm{ln}\right|zt|])],`$
where $`J=_{x^1}w_1_{x^2}w_2_{x^2}w_1_{x^1}w_2`$ is the Jacobian determinant of the map $`(x^1,x^2)(x,y)`$.

In the case $`\mu =`$ const, the $`\mu `$-deformed Laplace equation reduces to the Laplace equation and $`w_1`$, $`w_2`$ reduce to be just harmonic functions. Thus, it is possible to choose $`x=x^1,y=x^2`$ so that in the harmonic coordinates $`(x,y,z,t)`$, and for $`\mu =1`$, the above Einstein metrics take the particularly simple form

$$g=2f(dx^2+dy^2)+dz^2dt^2+d\left(w\right)d\left(\mathrm{ln}\right|zt|]).$$
(5)
This coordinates system explicitly shows that, when $`w`$ is constant, the Einstein metrics given by Eq. (5) are static and, under the further assumption $`\mathrm{\Phi }=x\sqrt{2}`$, they reduce to the Minkowski one. Moreover, when $`w`$ is not constant, gravitational fields (5) look like a disturbance moving, along the$`z`$ direction on the Killing leaves, at light velocity. However, the last observation is neither rigorous nor covariant. Since the propagation direction is the most important ingredient in the study of the polarization, in the following sections a detailed analysis will be devoted to this question.

In the following we will assume that $`w`$ is not constant.

## 2 Zelmanov’s and Pirani’s criteria

To check the wave character of gravitational fields (2), a Zakharov generalization of the Zel’manov criterion  will be applied which states that a vacuum solution of the Einstein equations is a gravitational wave if the components $`R_{\mu \nu \lambda \sigma }`$ of the corresponding Riemann tensor field $`R`$, satisfy a hyperbolic equation of the form

$$g^{\alpha \beta }_\alpha _\beta R_{\mu \nu \lambda \sigma }=N_{\mu \nu \lambda \sigma }$$
(6)
where $`_\beta `$ denotes the Levi-Civita covariant derivative of the metric and $`N_{\mu \nu \lambda \sigma }`$ denote the components of a tensor field $`N`$ depending at most on first derivatives of the Riemann tensor itself.

For symmetric manifolds Eq. (6) with $`N=0`$ is an identity because the Riemann tensor is covariantly constant, but it may become an identity also in the case of Einstein manifolds ($`R_{\alpha \beta }=\kappa g_{\alpha \beta }`$), for special choices of the tensor field $`N`$. Hence, to exclude a priori these situations, the original Zel’manov criterion is formulated in the more restrictive assumptions:

* $`R_{\alpha \beta \gamma \delta }`$ not covariantly constant333That is the manifold is not symmetric. ;
* $`g^{\alpha \beta }_\alpha _\beta R_{\mu \nu \lambda \sigma }=0`$ .

The metrics in Eq. (2) certainly do not define symmetric or Einstein manifolds, as can be checked from the components of the Ricci tensor given below. Hence, the first hypothesis is certainly satisfied while the second one, i.e. $`N=0`$, which ensures the applicability of the criterion to Einstein manifolds too, is not needed.

Concerning the physical meaning of this criterion, it can be shown  that the characteristic hypersurface of the system of equations (6) is identical with the characteristic hypersurface of the Einstein and Maxwell equations in curved space-time. Consequently, Eqs. (6) describe the propagation of the discontinuities of the second derivatives of the Riemann tensor. This links the Zel’manov criterion to the intuitive concept of local wave of curvature. The criterion is independent on the explicit form of $`N_{\mu \nu \lambda \sigma }`$; in fact, the characteristic hypersurface of a system of equations is determined only by the highest derivative term. Then we will not fix an explicit form of $`N_{\mu \nu \lambda \sigma }`$ but just require that $`N_{\mu \nu \lambda \sigma }`$ be a tensor containing at most first derivatives of the Riemann tensor. This clearly corresponds to a covariant criterion . Then a sufficient condition is

$$g^{\alpha \beta }_\alpha _\beta R_{\mu \nu \lambda \sigma }=0,$$
(7)
where $`_\beta `$ are the usual partial derivatives. In fact, if this is the case then $`N_{\mu \nu \lambda \sigma }`$ is a tensor containing at most first derivatives of the Riemann tensor.

To start with, let us verify that gravitational fields (5) do satisfy Eqs. (7).

In the harmonic coordinates system the only nonvanishing components of the Riemann and Ricci tensor fields corresponding to metrics (5) are proportional to one of the following

$`R_{txzx}`$ $`=`$ $`{\displaystyle \frac{(2fw,_{xx}+f,_yw,_yf,_xw,_x)}{4f\left(zt\right)^2}}`$
$`R_{txzy}`$ $`=`$ $`{\displaystyle \frac{(2fw,_{xy}f,_yw,_xf,_xw,_y)}{4f\left(zt\right)^2}}`$
$`R_{tyzy}`$ $`=`$ $`{\displaystyle \frac{(2fw,_{yy}f,_yw,_y+f,_xw,_x)}{4f\left(zt\right)^2}}`$
$`R_{xyxy}`$ $`=`$ $`{\displaystyle \frac{f,_y^2+f,_x^2f(f,_{xx}+f,_{yy})}{f}},`$ (8)
and

$$R_{tt}=\frac{\mathrm{\Delta }w}{2f\left(zt\right)^2},R_{xx}=\frac{\left(f\right)^2f\mathrm{\Delta }f}{2f^2},$$

respectively.

Moreover, the harmonicity condition for $`\mathrm{\Phi }`$ implies the last component vanishes. In fact, when $`\mu =`$const, $`\mathrm{\Delta }\mathrm{\Phi }=0`$ implies for $`f`$ that

$$f\mathrm{\Delta }f(f)^2=0.$$
(9)
* When $`f`$ is a constant function, Eqs. (8) reduce to

$$R_{txzx}=\frac{w,_{xx}}{2(zt)^2},R_{txzy}=\frac{w,_{xy}}{2(zt)^2},R_{tyzy}=\frac{w,_{yy}}{2(zt)^2}$$
(10)
which, $`w(x,y)`$ being a harmonic function, are all harmonic functions of $`x,y`$. As a consequence, it is straightforward to check that the generalized Zel’manov criterion, in the form (7) , is satisfied .
* When $`f`$ is not a constant function, the generalized Zel’manov criterion is still satisfied in the form (7) thanks to a non trivial combination of the harmonicity condition for $`w`$ and Eq. (9).
* In the general case when $`f`$ and $`\mu `$ are not constant functions the Zel’manov criterion is satisfied in the form expressed by Eq.(6). This may be more conveniently checked in the adapted coordinates $`x^\mu `$.

The Zel’manov criterion, even if it is covariant and allows a clear physical interpretation in terms of local waves of curvature, does not determine the propagation direction of the waves, that is the most important ingredient in the study of their polarization. In the next sections we will overcome this drawback of the Zel’manov criterion by using a suitable energy-momentum pseudo-tensor.

Besides the Zel’manov-Zakharov criterion, the Pirani algebraic criterion, which is based on the Petrov classification, is satisfied. First of all, let us recall that a vacuum solution of the Einstein equations is a gravitational wave according to Pirani if its Riemann tensor is of type II, N or III in the Petrov classification . Then, in light-cone coordinates ($`u=\left(zt\right)/\sqrt{2},v=\left(z+t\right)/\sqrt{2}`$), where the metrics given by Eq.(5) read

$$g=2f(dx^2+dy^2)+2dudv+dwd\mathrm{ln}\left|u\right|,$$
(11)
the vector fields $`_u`$ and $`_v`$ are both isotropic. Moreover, it is trivial to show that the only non vanishing components of the Riemann tensor are

$$R_{uiuj}=\pm \frac{1}{2u^2}_{ij}^2w$$

and this clearly corresponds to a type-N Riemann tensor in the Petrov classification. Furthermore, it follows from the natural interpretation of the Pirani criterion  that the gravitational wave propagates along the null vector field $`_u`$, or, in other words, the gravitational wave (5) propagates along the $`z`$axis with velocity $`c=1`$. Thus, the Pirani criterion, even if with a less clear physical interpretation, allows an easy and covariant determination of the propagation direction. It will be an important self-consistency check for our calculations to discover the same results by means of the energy-momentum pseudo-tensors.

## 3 The sources

In the theory of gravitational waves a crucial problem is to characterise realistic sources able to generate waves enough strong to be detected by the experimental devices.

The simplest source for metrics (2) (with $`\sigma =1`$) is dust with density $`\rho `$ and velocity $`U^\mu `$ and, then, characterized by an energy-momentum tensor $`T_{\mu \nu }=\rho U_\mu U_\nu `$. When $`U^\mu `$ is a light-like vector field, this kind of energy-momentum tensor can describe the energy and momentum of null electromagnetic waves, i.e., electromagnetic fields whose scalars, $`F^{\mu \nu }F_{\mu \nu }`$ and $`ϵ^{\alpha \beta \mu \nu }F_{\alpha \beta }F_{\mu \nu }`$, both vanish. In this way it would be possible to describe the gravitational effects (in particular the emission of gravitational waves) of a very interesting astrophysical phenomenon, the $`\gamma `$ray bursts (GRBs): emission of ultra-high energetic $`\gamma `$-rays ($`10^{20}`$ $`eV`$), whose origin is still to be fully understood.

Moreover, with this source one can also preserve the symmetries  of the vacuum solution. It can be shown  that, in the adapted coordinates $`(x^1,x^2,x^3,x^4)`$, the corresponding solutions of Einstein equations represent the following gravitational fields

$$g=2f(dx^1dx^1+dx^2dx^2)+\mu [(\stackrel{~}{w}(x^1,x^2)2x^4)dx^3dx^3+2dx^3dx^4],$$

where $`\mu =D\mathrm{\Phi }+B`$; $`D,B`$, $`\mathrm{\Phi }`$ is a non constant harmonic function of $`x^1`$ and $`x^2`$, $`f=\left(\mathrm{\Phi }\right)^2\sqrt{\left|\mu \right|}/\mu `$, while $`\stackrel{~}{w}(x^1,x^2)`$ is a solution of the $`\mu `$-deformed Poisson equation

$$\mu \mathrm{\Delta }\stackrel{~}{w}+\mu \stackrel{~}{w}=2f\mu ^2\rho ,$$

in which, to save writing, beyond $`c=1`$, it has been taken $`8\pi G=1`$, $`G`$ being the Newton gravitational constant.

It is worth to remark that spin-1 gravitational waves in vacuum necessarily are not square integrable. Thus, if they are requested to be asymptotically flat, then $`\delta `$-like singularities appear in the plane $`(x,y)`$ in a neighborhood of the origin; in presence of matter sources the singularities are smoothed out.

## 4 The energy-momentum pseudo-tensors

The definition of momentum and energy associated with a gravitational field is an intrinsically controversial problem because these quantities are connected to the space-time translation invariance, whereas the group of invariance of general relativity is much bigger. With this cautionary remark in mind, various definitions are available which attain to different physical situations. When dealing with the solutions of the linearised Einstein equations in the vacuum (plane gravitational waves) a commonly accepted definition is based on the canonical energy-momentum pseudo-tensor ( ):

$$\tau _\mu ^\nu =\frac{L}{\left(_\nu g_{\alpha \beta }\right)}_\mu g_{\alpha \beta }g_\mu ^\nu L,$$
(12)
where

$$L/\sqrt{\left|g\right|}=g^{\mu \nu }\left[\mathrm{\Gamma }_{\mu \nu }^\lambda \mathrm{\Gamma }_{\lambda \sigma }^\sigma \mathrm{\Gamma }_{\mu \rho }^\sigma \mathrm{\Gamma }_{\nu \sigma }^\rho \right]$$
(13)
is the Ricci scalar deprived of terms containing the second derivative of the metric.

Then, for the wave solutions of the linearised Einstein equations the energy density $`\tau _0^0`$ is expressed  as the sum of squares of derivatives of some metric components which do represent the physical degrees of freedom of the metric.

Under a transformation preserving the propagation direction and the harmonic character of the coordinates system, in particular a rotation in the $`(x,y)`$ plane, the physical components of the metric transform like a spin-$`2`$ field. It is well known that in general $`\tau _\mu ^\nu `$ in Eq. (12) is not a tensor field but it does transform as a tensor field under those transformations which preserve the character of the field of consisting only of waves moving in the $`z`$ direction, so that the $`g_{\mu \nu }`$ remain functions of the single variable $`zt`$.

Thus, within the linearised theory, the canonical energy-momentum pseudo-tensor is a good tool to study the physical properties of the gravitational waves.

### 4.1 Comparison with the linearised theory

The exact gravitational wave

$$g=dx^2+dy^2+dz^2dt^2+d\left(w\right)d\left(\mathrm{ln}\left|zt\right|\right),$$
(14)
given by Eq. (5) for $`\mu =1,f=1/2`$ , has the physically interesting form of a perturbed Minkowski metric  with $`h=dwd\mathrm{ln}\left|zt\right|`$ .

Moreover, besides being an exact solution of the Einstein equations, it is a solution of the linearised Einstein equations on a flat background too:

$$\{\begin{array}{c}\eta ^{\mu \nu }_\mu _\nu h=0\hfill \\ \eta ^{\mu \nu }(2h_{\mu \rho ,\nu }h_{\mu \nu ,\rho })=0\hfill \end{array}$$

Then, to study its energy and polarization, the standard tools of the linearised theory and in particular the canonical energy-momentum pseudo-tensor, could be used. Nevertheless, with $`h=d\left(w\right)d\left(\mathrm{ln}\left|zt\right|\right)`$ the $`\tau _0^0`$ component of the canonical energy-momentum tensor vanishes. This is due to the fact that the components of the tensor $`h`$ cannot be expressed in the transverse-traceless gauge since $`h`$ has only one index in the plane transversal to the propagation direction.

Even if not explicitly declared, the standard textbooks analysis of the polarization is performed for the square integrable solutions of the wave-equation. Indeed, they can be always Fourier developed in terms of plane-wave functions with a light-like vector wave $`k_\mu `$.

The harmonicity condition for the plane wave solutions $`h_{\mu \nu }=e_{\mu \nu }e^{i\rho }+e_{\mu \nu }^{}e^{i\rho }`$ with $`\rho =k_\mu x^\mu `$ and $`k_\mu k^\mu =0`$, reduces to

$$\frac{1}{2}k_\lambda \eta ^{\mu \nu }e_{\mu \nu }=\eta ^{\mu \nu }k_\nu e_{\mu \lambda }.$$
(15)
It is trivial to see that the symmetry group of this equation, which encodes the harmonic nature of the coordinate system, reduces to linear transformations and more precisely to Poincaré transformations  (these are nothing but the usual ”gauge transformations” of the linearised gravity). It can be easily shown that, for square integrable perturbations, one can always choose the transverse-traceless gauge. In other words, it is always possible to eliminate, with a suitable gauge transformation, the components of the perturbations with one index in the propagation direction , i.e. square integrable perturbations of spin-1 do not exist. For these reasons, the canonical energy-momentum pseudo-tensor, which is gauge invariant in the sense of the linearised gravity, ”cannot see” the energy and momentum of gravitational fields given by Eq.(14) which have one index in the propagation direction444Of course, it is possible to find  a coordinate system in which the perturbation $`h`$ has non vanishing components only in the transverse plane. However such a coordinate system is not harmonic. (but they are not square integrable so they cannot be gauged away). The fact that square integrable perturbations with one index in the propagation direction are always pure gauge is equivalent to the fact that, for such perturbations, the canonical energy-momentum pseudo-tensor identically vanishes.

### 4.2 Landau–Lifshitz’s and Bel’s energy-momentum pseudo-tensors

Besides the canonical energy-momentum pseudo-tensor, a deep physical significance can be given to the Landau-Lifshitz energy-momentum pseudo-tensor $`\tau ^{\rho \kappa }`$  defined by

$`\tau ^{\rho \kappa }`$ $`=`$ $`{\displaystyle \frac{1}{16\pi k}}\{(2\mathrm{\Gamma }_{\lambda \mu }^\nu \mathrm{\Gamma }_{\nu \sigma }^\sigma \mathrm{\Gamma }_{\lambda \sigma }^\nu \mathrm{\Gamma }_{\mu \nu }^\sigma \mathrm{\Gamma }_{\lambda \nu }^\nu \mathrm{\Gamma }_{\mu \sigma }^\sigma )(g^{\rho \lambda }g^{\kappa \mu }g^{\rho \kappa }g^{\lambda \mu })`$ (16)
$`+`$ $`g^{\rho \lambda }g^{\mu \nu }(\mathrm{\Gamma }_{\lambda \sigma }^\kappa \mathrm{\Gamma }_{\mu \nu }^\sigma +\mathrm{\Gamma }_{\mu \nu }^\kappa \mathrm{\Gamma }_{\lambda \sigma }^\sigma \mathrm{\Gamma }_{\nu \sigma }^\kappa \mathrm{\Gamma }_{\lambda \mu }^\sigma \mathrm{\Gamma }_{\lambda \mu }^\kappa \mathrm{\Gamma }_{\nu \sigma }^\sigma )`$
$`+`$ $`g^{\kappa \lambda }g^{\mu \nu }(\mathrm{\Gamma }_{\lambda \sigma }^\rho \mathrm{\Gamma }_{\mu \nu }^\sigma +\mathrm{\Gamma }_{\mu \nu }^\rho \mathrm{\Gamma }_{\lambda \sigma }^\sigma \mathrm{\Gamma }_{\nu \sigma }^\rho \mathrm{\Gamma }_{\lambda \mu }^\sigma \mathrm{\Gamma }_{\lambda \mu }^\rho \mathrm{\Gamma }_{\nu \sigma }^\sigma )`$
$`+`$ $`g^{\mu \lambda }g^{\sigma \nu }(\mathrm{\Gamma }_{\lambda \nu }^\rho \mathrm{\Gamma }_{\mu \sigma }^\kappa \mathrm{\Gamma }_{\lambda \mu }^\rho \mathrm{\Gamma }_{\nu \sigma }^\kappa )\}.`$
There are strong evidences that, in some cases, it gives the correct definition of energy . In fact, the energy flux radiated at infinity for an asymptotically flat space-time, evaluated with the Landau-Lifshitz energy-momentum pseudo-tensor, has been seen to agree with the Bondi flux  that is with the energy flux evaluated in the exact theory.

It is easy to check that the components $`p^\mu \tau _0^\mu `$ of the $`4`$-momentum density are

$$\{\begin{array}{c}p^0=\frac{4}{\left(tz\right)^2}[C_1(w_{,xx})^2+C_2(w_{,xy})^2]+\frac{4}{\left(tz\right)^4}C_3[\left|w\right|^2w],\hfill \\ p^1=p^2=0,p^3=p^0,\hfill \end{array}$$

where $`C_i`$ are some positive numerical constants, $`=(_x,_y)`$ and the harmonicity condition for $`w`$ has been used.

The use of the Bel’s superenergy tensor

$$T^{\alpha \beta \lambda \mu }=\frac{1}{2}\left(R^{\alpha \rho \lambda \sigma }R_{\rho \sigma }^{\beta \mu }+{}_{}{}^{}R_{}^{\alpha \rho \lambda \sigma }{}_{}{}^{}R_{\rho \sigma }^{\beta \mu }\right),$$

where the symbol $``$ denotes the volume dual, leads to the same result. Indeed, in adapted coordinates the metric has the form

$$g=dx^1dx^1+dx^2dx^2+(w(x^1,x^2)2x^4)dx^3dx^3+2dx^3dx^4$$

and the only non vanishing independent components of the covariant Riemann tensor $`R_{\alpha \beta \gamma \delta }=g_{\alpha \rho }R_{\beta \gamma \delta }^\rho `$ are

$$R_{1313}=w,_{11};R_{\mathrm{\hspace{0.17em}1\hspace{0.17em}323}}=w,_{12};R_{2323}=w,_{22}.$$

It follows that the density energy represented by the Bel’s scalar

$$W=T_{\alpha \beta \lambda \mu }U^\alpha U^\beta U^\lambda U^\mu ,$$

the $`U^\alpha `$’s denoting the components of a time-like unit vector field, depends on the squares of $`w,_{ij}`$. Thus, both the Landau-Lifshitz pseudo tensor and the Bel superenergy tensor single out the same physical degrees of freedom. In particular, we can take the components $`h_{tx}`$ and $`h_{ty}`$ as fundamental degrees of freedom for the gravitational wave (14).

Concerning the definition of the polarization, the above form for $`\tau _0^\mu `$ is particularly appealing because, apart from a physically irrelevant total derivative that does not contribute to the total energy flux, the component $`\tau _0^0`$ representing the energy density is expressed as the sum of square amplitudes. The momentum $`p^i=\tau _0^i`$ is non vanishing only in the $`z`$direction and it is proportional to the energy with proportionality constant $`c=1`$; that is these waves move with light velocity along the $`z`$axis. Moreover, this result is perfectly consistent with the one obtained with the Pirani criterion.

## 5 Spin

The definition of spin or polarization for a theory, such as general relativity, which is non-linear and possesses a much bigger invariance than just the Poincaré one, deserves a careful analysis .

It is well known that the concept of particle together with its degrees of freedom like the spin may be only introduced for linear theories (for example for the Yang-Mills theories, which are non linear, it is necessary to perform a perturbative expansion around the linearised theory). In these theories, when Poincaré invariant, the particles are classified in terms of the eigenvalues of two Casimir operators of the Poincaré group, $`P^2`$ and $`W^2`$ where $`P_\mu `$ are the translation generators and $`W_\mu =\frac{1}{2}ϵ_{\mu \nu \rho \sigma }P^\nu M^{\rho \sigma }`$ is the Pauli-Ljubanski polarization vector with $`M^{\mu \nu }`$ Lorentz generators.

As it has been shown, the gravitational fields of Eq. (14) represent gravitational waves moving at the velocity of light, that is, in the would be quantised theory, particles with zero rest mass. Thus, if a classification in terms of Poincaré group invariants could be performed, these waves would belong to the class of unitary (infinite-dimensional) representations of the Poincaré group characterized by $`P^2=0`$, $`W^2=0`$. But, in order for such a classification to be meaningful, $`P^2`$ and $`W^2`$ have to be invariants of the theory. This is not the case for general relativity, unless we restrict to a subset of transformations selected for example by some physical criterion or by experimental constraints. For the solutions of the linearised vacuum Einstein equations the choice of the harmonic gauge does the job . There, the residual gauge freedom corresponds to the sole Lorentz transformations.

For these reasons, only gravitational fields represented by Eq. (14) will be considered, which, besides being exact solutions, solve the linearised vacuum Einstein equations as well. There exist several equivalent procedures to evaluate their polarization. For instance, one can look at the $`\tau _0^0`$ component of the Landau-Lifshitz pseudo-tensor and see how the metric components that appear in $`\tau _0^0`$ transform under an infinitesimal rotation $``$ in the plane $`(x,y)`$ transverse555With respect to the Minkowskian background metric, this plane is orthogonal to the propagation direction. With respect to the full metric this plane is transversal to the propagation direction and orthogonal only in the limit $`\left|zt\right|\mathrm{}`$. to the propagation direction666It has been said before, that this transformation preserves the harmonicity condition..

The physical components of the metric are $`h_{tx}`$ and $`h_{ty}`$ and under the infinitesimal rotation $``$ in the plane $`(x,y)`$ transform as a vector. Applied to any vector $`(v_1,v_2)`$ the infinitesimal rotation $``$, has the effect

$$v_1=v_2,v_2=v_1,$$

from which

$$^2v_i=v_ii=1,2,$$

so that $`i`$ has the eigenvalues $`\pm 1`$.

Thus, the components of $`h_{\mu \nu }`$ that contribute to the energy correspond to spin-$`1`$ fields777There is nothing to forbid the existence of two spin-1 fields, but one consequence is that particles with the same orientation repel and particles with opposite orientation attract., provided that only Lorentz transformations are allowed.

Spin-$`0`$ and spin-$`1`$ gravitons have been considered, in a different context, in .

## 6 Conclusions

It has been shown that gravitational fields (11) represent spin-1 gravitational waves and that the reason why it is commonly believed that spin-1 gravitational waves do not exist is that, in dealing with the linearised Einstein theory, all authors implicitly assume a square integrable perturbation. In other words, square integrable spin-1 gravitational waves are always pure gauge. However, it has been proven that there exist interesting non square integrable wave-like solutions of linearised Einstein equations that have spin-1. These solutions are very interesting at least for two reasons. Firstly, they are asymptotically flat (with at least a $`\delta `$-like singularity) in the plane orthogonal to the propagation direction. Secondly, they are solutions of the exact equations too, so that the spin-1 cannot be considered as an ”artifact” of the linearised theory. Realistic sources able to smooth out the mentioned singularities have also been found.


format: text

text:
# *

## 1 Introduction

The objective of swarm robotics is to program a huge number of simple, tiny robots to perform complex tasks collectively. A typical application scenario for a robot swarm may involve two phases: first, the robot swarm fills an environment as quickly as possible while keeping the swarm “connected” (a term made more precise later). Once the robots are distributed in the environment, the robots perform world-embedded computational tasks, such as computing distances and short paths between points in the environment, finding chokepoints, mapping the environment, and searching for intruders.

This paper develops efficient algorithms for filling an environment with a swarm of robots, thus focusing on the first phase described above. Because target applications require thousands to millions of robots and current demonstration scenarios have at most hundreds of robots, it is crucial to develop algorithms that have explicitly stated performance guarantees, thus ensuring scalability.

There has already been work on dispersion algorithms, but most dispersion algorithms rely on greedy strategies such as go-for-free space, where robots move to fill unoccupied space, or artificial physics strategies, where neighboring robots exert “forces” on each other: repulsion forces if the robots are closer than the target separation, and attraction forces if the neighboring robots are too far away. Although such robot behaviors often lead to reasonable dispersion, there are cases in which the swarm enters infinite loops, never filling the domain. Even in artificial physics strategies, which seem to disperse robots most efficiently, there are no guarantees on filling time. Furthermore, the swarm behavior under artificial-physics rules results in dispersions that are more reminiscent of molecular dynamics simulations (with large amounts of “bouncing” and “jitter”) than of the ideal coordinated behavior of cooperating teams of robots.

The dispersion algorithms in this paper represent a departure from previously studied dispersion strategies. First of all, we test our algorithms in arbitrary polygonal environments, rather than restricting ourselves to rectangles or the infinite plane. It is important to study the dispersion algorithms in complicated polygonal domains because the target domains may be bottleneck-filled indoor environments or systems of pipes or ductwork.

Our algorithms are based on follow-the-leader local rules, where the robots form chains of leaders and followers emanating from a central source of robots. (the “doors”). The emergent behavior of our main algorithm is a left-hand-on-the-wall strategy, where the entire robot swarm hugs the left wall of the domain as the filling proceeds. We provide matching lower and upper bounds on the amount of time to fill as a function of the total size of the source. The difficulty in dispersing efficiently is in sustaining a large flow of robots coming in through the doors; the “chains” of robots coming in through the doors have a tendency to “cut each other off”; see Figure 1(left). Thus, we devise a set of local rules for splitting and splicing the robot chains. Our experience with our robot simulator shows that unless the local rules are precisely implemented, the flow of robots out of the source diminishes and perhaps even grinds to a halt prematurely.

### 1.1 Our Results

We develop and analyze algorithms for dispersing robot swarms in an unknown environment $`R`$. The primary objective is to minimize the makespan, that is, the time to fill the entire region. An environment is composed of squares or pixels that form a connected subset of the integer grid; such an environment is also called a maze. There is at most one robot per pixel and robots move horizontally or vertically at unit speed. There is a source of robots entering the environment through $`k1`$ doors. Robots are primitive finite automata, only having local communication, local sensors, and a constant-sized memory. The challenge is in proving that purely local strategies distributed over a swarm of agents can result in a predictable and provable behavior for the collective.

This paper presents the following results:

* We give filling algorithms for the single-door case (i.e., $`k=1`$), analyzing the algorithms both theoretically and experimentally in terms of natural performance metrics, such as makespan and total traveled distance by all robots. Our algorithms are based on leader-follower strategies that are adapted from depth-first and breadth-first search to apply to robot swarms. We prove that our algorithms have optimal makespan $`2A1`$, where $`A`$ is the area (number of pixels) of $`R`$.
* We give a filling algorithm for the multi-door case ($`k1`$), also based on a leader-follower strategy. The emergent behavior of the swarm is a filling strategy, called laminar flow, that generalizes the “left-hand-on-wall” strategy to multiple streams of robots coming in through multiple doors. An important contribution of the algorithm is the formulation of splitting and splicing strategies that maintain a large flow of robots out of the doors. We prove that the laminar flow algorithm is $`O(\mathrm{log}(k+1))`$-competitive, that is, the ratio of the makespan of our algorithm to the optimal makespan is $`O(\mathrm{log}(k+1))`$.
* We give a matching lower bound of $`\mathrm{\Omega }(\mathrm{log}(k+1))`$ on the competitiveness of the natural class of “simple-minded” strategies that use only strictly local information.
* We report on experiments with a Java simulator that we built for swarms in grid environments. All of the algorithms in this paper are implemented in this simulator.

While our results here are given purely in terms of robots moving synchronously on discrete grids, the results apply also to dispersing swarms of robots within an arbitrary connected planar domain, in the ideal setting in which the robots have perfect motion control and synchrony. More importantly, our results may form the foundation for theoretical work on more realistic models of swarm robotics in the continuum, with asynchronous motion, sensor errors, slippage, and hardware failures.

### 1.2 Prior and Related Work

There has been considerable study recently of distributed control and coordination of a set of autonomous robots. Gage  has proposed the development of command and control tools for arbitrarily large swarms of microrobots and has proposed coverage paradigms in the context of robot dispersal in an environment. Payton et al  propose the notion of “pheromone robotics” for world-embedded computation. Wagner et al.  developed multi-robot algorithms, directly inspired by ant behaviors, for searching and covering. Principe et al  and Suzuki et al  have studied algorithmic aspects of pattern formation in distributed autonomous robotics under various models of robots with minimal capabilities. The related flocking problem, which requires that a set of robots follow a leader while maintaining a formation, has been studied in several recent papers; see, e.g., . Balch  has developed “Teambots”, a Java-based general-purpose multi-robot simulator.

There is a vast literature on algorithms for one or several robots to explore unknown environments. The environments can be modeled as graphs (directed or undirected), mazes, or geometric domains, and the robots can have a range of computing powers; see, e.g., . Mitchell  includes a survey of many results on exploring and navigating in geometric environments.

Dispersion algorithms have been recently studied both in the context of multi-robot coverage and sensor network deployment; see . Methods include potential fields , “artifical physics” , attraction-repulsion , and algorithms based on molecular dynamics . While these studies have examined empirically the merits of heuristics, they have not addressed formally the algorithmic efficiency of the dispersion problem.

## 2 Preliminaries

For an arbitrary connected region $``$ in the plane, we let $`R`$ denote the set of pixels that lie entirely within $``$. A pixel is an axis-aligned unit square, $`\{(x,y):ixi+1,jyj+1\}`$, whose lower left corner is given by the integer grid point $`(i,j)`$. Two pixels are neighbors if they share a common edge; thus, pixel $`(i,j)`$ has four neighbors, $`(i1,j)`$, $`(i+1,j)`$, $`(i,j1)`$, and $`(i,j+1)`$. We refer to $`R`$ as the environment, and we assume that it is connected. A subset, $`DR`$, of the pixels are doors, which serve as sources of incoming robots. See Figure 1(right).

A robot $`r`$ is said to occupy a pixel $`p=(i,j)`$ when it is located in that pixel. We assume that at most one robot can occupy any one pixel at any given time $`t`$. We let $`p(r,t)`$ denote the pixel occupied by robot $`r`$ at time $`t`$. We let $`prev(r,t)=p(r,t1)`$ denote the pixel previously occupied by robot $`r`$.

Time is discretized into steps $`t=0,1,2,3,\mathrm{}`$. The positions of the robots at time $`t`$ are given by the set $`S(t)`$, where $`DS(t)R`$. At time $`0`$, there is one robot in each door: $`S(0)=D`$.

Each pixel is in one of three states at time $`t`$: (1) the pixel is an obstacle if it does not lie in $`R`$; (2) the pixel is occupied if it is in $`R`$ and a robot occupies it; or (3) the pixel is unoccupied if it is in $`R`$ and no robot occupies it at time $`t`$. An unoccupied pixel at time $`t`$ is classified as either previously occupied, if it was occupied by some robot at some time prior to $`t`$, or frontier, if it has never been occupied.

Robots have sensors that detect information about the local environment. In particular, if a robot occupies pixel $`(i,j)`$ at time $`t`$, then we assume that it can detect the state of each pixel within a distance $`r_S`$ of $`(i,j)`$, where $`r_S`$ is the (fixed) sensor radius. Robots have no global sensor (e.g., a GPS) and no knowledge of the coordinates of the pixels they occupy.

We assume that each robot has a small finite memory that allows it to remember the sensor readings of the last $`T1`$ time steps; i.e., a robot knows the sensor readings it has taken at time $`tT`$, $`tT+1,\mathrm{},t1,t`$. In particular, each robot knows which nearby pixels have been occupied recently by other robots. The algorithms in this paper have an $`O(1)`$-bit memory; thus, the robots have the computational power of finite automata.

We assume that robots have a limited ability to communicate with nearby robots. In particular, at any given time step a robot is able to exchange a constant-size message with any robot that lies within a prescribed communication radius, $`r_C`$, of the robot. The communication graph, $`𝒢(t)`$, of the swarm $`S(t)`$ at time $`t`$ is defined to be the undirected graph whose nodes are the robots $`S(t)`$ and whose edges link pairs of robots that communicate. The swarm is said to be connected at time $`t`$ if each connected component of $`𝒢(t)`$ contains at least one door pixel.

Robots move discretely on the grid of pixels. If at time $`t`$ a robot occupies pixel $`(i,j)`$ of $`R`$, and a neighboring pixel (say, $`(i+1,j)`$) of $`R`$ is unoccupied at time $`t`$, then the robot may take a step to the right, so that at time $`t+1`$ it occupies pixel $`(i+1,j)`$. Naturally, no two robots can move into the same pixel, since no pixel can be occupied by more than one robot. Thus, if two robots are occupying pixels that neighbor an empty pixel $`p`$ of $`R`$, then the robots must negotiate which one of them will have the right of way to enter $`p`$. A simple way to handle this negotiation is to establish a priority among the four directions, e.g., north, south, east, west. The robot occupying the pixel with the highest priority with respect to $`p`$ has first rights for moving to $`p`$.

The above rules on occupying and vacating pixels force a constant delay in the motion. Suppose that robot $`r`$ occupies pixel $`(i,j)`$ at time $`t`$ and vacates $`(i,j)`$ at time $`t+1`$. No other robot $`r^{}`$ can occupy pixel $`(i,j)`$ during time $`t+1`$; the earliest possible time that the pixel can be occupied is $`t+2`$. In principal, we could vary these local rules. For example, we could allow robot $`r^{}`$ to enter pixel $`(i,j)`$ at timestep $`t+1`$, if it enters in one direction while the current robot $`r`$ leaves in the opposite direction. However, these rules would require a much higher degree of coordination among the robots, and the movement decisions of robots would have to be less local. Specifically, whether a given robot can enter one pixel may depend on whether a different robot far away leaves another pixel. Alternatively, we could build a longer delay into the movement rules, but the resulting filling algorithms would be essentially the same. Note that the delay has an immediate impact on the necessary sensor range: If we require a delay of two time steps, robots need at least a sensor range of two, in order to be able to keep track of predecessors and successors.

A similar issue arises in the way new robots enter through the door. For simplicity, we assume that a door pixel is always occupied by a robot; as soon as the robot occupying a door pixel moves to an adjacent pixel, a new robot materializes at the door. One can consider there to be an infinite supply of robots on the “other side” of a door pixel, so that a new robot steps into the door whenever the robot that was there previously moves to another pixel of $`R`$. When a robot first appears at the door, we assume that the robot points north.

We say that the robots have filled the region $`R`$ at time $`t`$ if $`S(t)=R`$; in this case, the robots are well dispersed. A strategy is a set of rules by which robots move, basing their movement decisions solely on the constant amount of information they sense and remember. The makespan of a strategy is the minimum time, $`t^{}`$, until the robots have filled the region $`R`$.

## 3 Dispersion Strategies for a Single Door

We begin with the case of a single door pixel $`s`$, which we call the source. We describe strategies based on the notion of “leaders” and “followers”.

A robot $`r`$ at time $`t`$ at position $`p(r,t)`$ is classified as moving (meaning that it is “active”) or stopped (meaning that it no longer moves). If $`r`$ is moving, it is classified as either a leader or a follower.

In our leader-follower strategies, each robot $`r`$ at time $`t`$ has a successor robot, $`succ(r,t)`$, that is following $`r`$ and a predecessor robot, $`pred(r,t)`$, that is leading $`r`$. If robot $`r`$ is at the door at time $`t`$ ($`p(r,t)=s`$), then we define $`succ(r,t)`$ to be NIL; if $`r`$ is a leader, then we define $`pred(r,t)`$ to be NIL.

At time $`t=0`$ there is a robot at the door $`s`$, which is designated as moving and as a leader.

### 3.1 Depth-First Leader-Follower

The depth-first leader-follower strategy (DFLF) is inspired by depth-first search in a graph. Specifically, at any given time $`t\{0,1,2,3,\mathrm{}\}`$, there is exactly one leader, $`r`$, which is on pixel $`p(r,t)`$ and $`r`$ is looking for a frontier pixel (one that has never been occupied by a robot). (Thus, necessarily the pixel from which the robot came, $`prev(r,t)`$, is not frontier at time $`t`$.) If there are two or more frontier pixels neighboring $`p(r,t)`$, the leader selects any one of them as its next destination.

If the leader has no frontier pixel next to it, it stops (its state changes to “stopped”), and it tells its successor, $`succ(r)`$, to assume the leadership ($`succ(r)`$’s state changes to “leader”) at the conclusion of this time step. (The predecessor completes its move before taking over the leadership.) If the leader has no predecessor (i.e., it is a robot at the door), then the algorithm halts. (In this section, successors and (non-Nil) predecessors are invariant over time, and thus $`t`$ is removed from the argument.)

Any robot $`r`$ that is a follower (i.e., not the leader) simply follows its predecessor: at time $`t`$ it steps next to $`prev(pred(r),t)`$, the pixel previously occupied by the predecessor of $`r`$. Note that once a robot stops, it never moves again. Furthermore, at any point in time there is exactly one leader.

When dealing with finite automata, we have to use particular care when implementing the leader-follower strategy. As each robot has only a finite number of states, it cannot keep track of the identities of other robots, nor carry its own “ID label”. Instead, we use spatial information to pursue the immediate predecessor. Each robot $`r`$ has a “heading”, indicating the direction in which it is moving. The predecessor $`pred(r)`$ is the nearest robot in that direction. Similarly, each robot keeps track of its “tailing”, the direction from which it came. Thus, the successor is the nearest visible robot in that direction. Whenever a robot is about to change its heading, it signals this turn to its immediate successor. Heading and tailing are updated according to delay and sensor-range. This is reflected in the following lemma and corollary, which are proved by introduction on time.

###### Lemma 3.1.

If $`r`$ is not the leader at time $`t`$, then $`prev(pred(r),t)`$ is an unoccupied pixel neighboring $`p(r,t)`$. Furthermore, the maximum ($`L_1`$) distance between $`r`$ and $`pred(r)`$ is 2.

###### Corollary 3.2.

If a pixel is not occupied in two consecutive time steps $`t`$ and $`t+1`$, then it was never occupied before time $`t`$. (i.e., there are no “large gaps” of time in the occupation of a pixel.)

A further consequence of the above lemma and corollary is that the DFLF strategy can be implemented with a sensor radius of $`r_S=2`$ and a memory of $`T=1`$ (i.e., each robot recalls its previous sensor reading). Now it is not hard to derive the following result:

###### Theorem 3.3.

The DFLF algorithm halts when all pixels are occupied by robots. The makespan of the DFLF algorithm is $`2A1`$, where $`A`$ is the number of pixels of the environment $`R`$.

###### Proof 3.4.

At each time step there is exactly one leader and that leader will do one of two things: (1) move to a frontier pixel, or (2) change its status to stopped and transfer leadership to its predecessor. (If the leader has no predecessor, that is, it is at the door, the algorithm halts.) Since each non-door pixel can be changed from frontier to non-frontier at most once, and each pixel can have a robot “park” itself on top of it at most once, the number of steps before the algorithm halts is at most $`2A1`$. The algorithm does not stop earlier since there is always a leader and the leader must do one of the two actions ((1) or (2)) above.∎

Note that the factor 2 is a result of using a delay of 2. It is easy to see that this is best possible.

The total distance traveled by all robots in a filling using DFLF is at most $`A^2`$, since each robot steps at most $`A`$. We note that there are examples in which any dispersion strategy will require $`\mathrm{\Omega }(A^2)`$ total travel. One trivial example is a $`1\times A`$ rectangle, with the door pixel at one end. A trivial lower bound on the total travel for any given instance is the sum of the distances from each pixel of $`R`$ to the door.

DFLF may use substantially more total travel than an optimal (minimum makespan) strategy that minimizes total travel; consider, for example, a square with side lengths $`A^{1/2}`$, for which DFLF requires total travel of $`A^2`$ while an optimal strategy achieves total travel $`O(A^{3/2})`$.

### 3.2 Breadth-First Leader-Follower

We now describe an alternative dispersion algorithm, the breadth-first leader-follower (BFLF) strategy. BFLF often has advantages over the DFLF strategy in terms of other metrics of performance (total travel of the robots, maximum travel of any one robot, total relative distance, etc), while still being optimal in terms of makespan ($`2A1`$).

The BFLF strategy is substantially more complex than the DFLF, as it is not trivial to implement breadth-first search with local decision rules on (finite-automata) robots; indeed, our strategy does not perform breadth-first search, but it “approximates” breadth-first search sufficiently well to have some similar properties.

As before, a robot can be in a “moving” state or a “stopped” state; however, we now introduce a third state, the waiting state, which is an interim state when a robot pauses temporarily and waits to be able to move. Once a robot is in a stopped state, it never moves again. In the BFLF strategy we can have multiple leaders, while in DFLF we have only one. As described for DFLF, we use a limited amount of spatial information to keep track of successors and predecessors. Other local rules are more complex and are described in the following.

Initially, there is one leader robot — the robot at the door, $`s`$. When a robot $`r`$ materializes at the door, it chooses to follow the previous robot that left the door. A leader always attempts to go to a neighboring frontier pixel, but makes sure it does not stray too far from its follower. If there are no neighboring frontier pixels, the leader waits for the immediate follower to catch up. As soon as the immediate follower catches up, the leader becomes stopped and passes on the leadership role to the immediate follower. If the leader $`r`$ at pixel $`u`$ has a choice among neighboring frontier pixels, it picks any one of them to be its heading. If other frontier pixels adjacent to $`u`$ remain unclaimed by other robots following different branches of dispersion, then the follower $`r^{}`$ of $`r`$ will choose one of these pixels as its heading when it arrives at $`u`$; if there remains a frontier pixel adjacent to $`u`$, then $`r^{}`$’s follower $`r^{\prime \prime }`$ chooses this pixel as its heading when it arrives at $`u`$. Here, $`r^{}`$ and $`r^{\prime \prime }`$ are relabeled “leaders” and pixel $`u`$ is marked as a branching point.

A robot $`r`$ is only allowed to move at time $`t`$, if it satisfies the Movement Criterion (MC): A robot currently occupies $`prev(r,t)`$ (its “parent” position) or a robot is currently heading for $`prev(r,t)`$. If the MC is satisfied, the robot $`r`$ moves to its heading; otherwise, it remains at its current position, $`p(r,t)`$ but is still heading for its target pixel. As we will see below, a robot $`r`$ is never blocked by its immediate predecessor except for the time step at which $`r`$ first appears at the door or a time when its immediate predecessor is a leader with nowhere to go, meaning that the leadership will be passed to $`r`$.

The BFLF strategy tries to create as many paths as possible at all times. The visited pixels form a tree that guides the directions that robots move; thus, pixels have parents and grandparents. At branches in the tree (pixels with $`2`$ children), robots alternate the direction that they travel. Specifically, when a robot $`r`$ leaves a pixel at time $`t`$, it tells its immediate follower $`r^{}=succ(r,t)`$ what $`r^{}`$’s immediate destination should be. Branching enables robots arriving at the same pixel at different times to go in different directions, thereby balancing the flow.

###### Lemma 3.5.

If not all pixels are occupied, then some robot can move.

The following structural lemma shows that the BFLF algorithm is nonblocking, i.e., a robot $`r`$ is never “delayed” by its predecessors, only by its followers; i.e., only the MC holds a robot back, not temporary blockages downstream. Correctness follows by induction on the height of the tree.

###### Lemma 3.6.

If a robot is at pixel $`v`$ and a robot is at pixel $`u`$, the non-root parent of $`v`$, then the robot at $`v`$ is stopped.

###### Corollary 3.7.

A robot moves from the root every other time step, until all pixels are occupied. I.e., if a robot did not pop up at the root at time $`t`$, then one must pop up at time $`t+1`$, unless all pixels (including the root) are occupied.

###### Lemma 3.8.

The robots maintain a communication distance of $`3`$, meaning that the algorithm works for $`r_S3`$. The maximum $`L_1`$-distance from a robot to a follower is $`3`$. Furthermore, at least one of the following pixels is occupied when a robot is at pixel $`u`$: (1) the parent of $`u`$, (2) the grandparent of $`u`$, or (3) the uncle of $`u`$.

Putting all the claims together and using similar reasoning as for Theorem 3.3, we get the same kind of bound on the makespan:

###### Theorem 3.9.

The BFLF algorithm halts when all pixels are occupied by robots. The makespan of the BFLF algorithm is $`2A1`$, where $`A`$ is the number of pixels of the environment $`R`$.

### 3.3 Experimental Comparison

While the DFLF and BFLF strategies both have optimal makespan, they differ with respect to other performance metrics. We have implemented in Java a simulator for testing our dispersion strategies, while measuring various performance measures, including: (1) the depth of the tree of all paths from the source (i.e., the length of the longest path of a robot); (2) the average distance traveled by a robot during the dispersion; and (3) the average of the ratios, $`\rho _i=l_i/d_i`$, of the ($`L_1`$) distance $`l_i`$ from the door to robot $`i`$’s final location to the total distance $`d_i`$ traveled by robot $`i`$ during the dispersion.

We have compared the DFLF and BFLF strategies for the case of a single door, in a variety of different environments. Our results show that the average depth of the tree grows substantially more rapidly, as a function of the number of pixels, for DFLF than it does for BFLF; e.g., for an $`n`$-by-$`n`$ square grid, BFLF tree depth grows linearly in $`n`$ while DFLF depth grows close to quadratically in $`n`$. Similarly, the average distance traveled by a robot using DFLF grows more rapidly than using BFLF. The average of the ratios $`\rho _i=l_i/d_i`$ decreases with increasing problem size for DFLF, while it increases for BFLF. Details of the experimental results are deferred to the full paper.

## 4 Dispersion with Multiple Doors

We now consider the case in which there are $`k1`$ door pixels. In order to achieve rapid filling, the objective is to maintain a flow of robots out of as many doors as possible. The difficulty is that one robot chain out of one door pixel may unnecessarily block the flow of robots out of other door pixels. (See the introduction and Figure 1(left) for examples.)

### 4.1 Laminar Flow Leader-Follower (LFLF) Algorithm

This section describes the Laminar Flow Leader-Follower (LFLF) algorithm. The LFLF algorithm maintains rapid flows by careful use of cutting and splicing. The emergent behavior of the swarm is a left-hand-on-wall strategy. The behavior of the algorithm is complex because bottlenecks in the environment may force the flow to divide into smaller flows that fill different regions and may merge and split.

In the LFLF algorithm there are $`k`$ multiple door pixels, $`s_1,s_2,\mathrm{},s_k`$. Note that LFLF matches DFLF algorithm if $`k=1`$. As in the $`k=1`$ case, our dispersion strategies are based on leaders and followers. A robot $`r`$ at time $`t`$ at position $`p(r,t)`$ is classified as active or inactive (stopped). If $`r`$ is active, it is either a leader or a follower. However, unlike for $`k=1`$, robots revert between leaders and followers. (In contrast, for $`k=1`$ a robot changes roles from follower to leader but only relinquishes the leader role by stopping and becoming inactive.) Furthermore, in DFLF once a robot stops, it becomes inactive. In contrast, in LFLF a robot may temporarily stop while still remaining active.

In LFLF (as in DFLF), robots have successors and predecessors, but in LFLF a robot’s immediate successor or predecessor may change over time. Thus, each robot $`r`$ at time $`t`$ has a predecessor robot denoted $`\text{robot-pred}(r,t)`$ and a successor robot denoted $`\text{robot-succ}(r,t)`$. If robot $`r`$ is at a door pixel at time $`t`$ ($`p(r,t)=s_i`$, for $`i[1,k]`$), then $`\text{robot-succ}(r)=\text{NIL}`$; if $`r`$ is a leader at time $`t`$, then $`\text{robot-pred}(r)=\text{NIL}`$.

Here we further refine the roles of the pixels. A pixel can be: (1) an obstacle, (2) a frontier pixel (a pixel that has never been occupied), (3) an inactive pixel, that is, an (occupied) pixel that hosts an inactive robot, (4) an active pixel, (which may be occupied or not). If a pixel is unoccupied but previously occupied, then it is always active; if a pixel is occupied, then it is active if and only if the robot it hosts is active.

Note that door pixels may be active or inactive, as described later. Active pixels play the role of transporting robots throughout the domain whereas inactive pixels are essentially obstacles. Analogous to the definition of predecessor and successor robots, each active pixel has predecessor and successor pixels. In particular, pixel $`u`$ at time step $`t`$ has successor pixel $`\text{pixel-succ}(u,t)`$ and predecessor pixel $`\text{pixel-pred}(u,t)`$. For door pixels $`s_i`$ at any time $`t0`$ $`\text{pixel-succ}(u,t)=\text{NIL}`$.

A leader pixel $`u`$ at time $`t`$ has $`\text{pixel-pred}(u,t)=\text{NIL}`$. As we will see, if a leader pixel contains a robot, then the robot is a leader, however the leader robot may not be on a leader pixel and the leader pixel may not contain robots. We call a chain of predecessor pixels starting from the door pixel $`s_i`$ and ending at a leader pixel, a flow line.

We now define formally the left side and right side of the flow. To do so, we first present some intermediate definitions. Consider a pixel $`v`$ at time $`t`$, and let $`u=\text{pixel-succ}(v,t)`$ and $`w=\text{pixel-pred}(v,t)`$. Let the incoming direction for $`v`$ at time $`t`$ be the vector $`\stackrel{}{vu}`$ and let the outgoing direction for $`v`$ at time $`t`$ be the vector $`\stackrel{}{vw}`$.

Consider the (vertical or horizontal) neighboring pixels, when we start from the incoming direction $`\stackrel{}{vu}`$ and rotate clockwise until reaching the outgoing direction $`\stackrel{}{vw}`$. Those neighboring pixels at intermediate (vertical or horizontal) orientations are defined to be on the left-hand side of $`v`$ time $`t`$. Thus, the left-hand side may contain $`0`$, $`1`$, or $`2`$ pixels. Any neighboring pixel that is not on the left-hand side, is on the right-hand side; this includes the pixels at the incoming and outgoing directions.

Note that leader pixels do not have outgoing edges, invalidating this definition. For a leader pixel, we define all neighboring pixels (except the successor pixel) to be on the left-hand side.

The left side of a flow line is the union of the left sides of the non-leader pixels in the flow line.

The essential idea the LFLF algorithm is to treat the left side of the flow line completely differently from the right side of the flow line. Specifically, we splice into the left-hand side but we cannot splice into the right.

### 4.2 Splicing and the LFLF Algorithm

Suppose that at time $`t`$ a leader robot $`r_a`$ reaches a pixel $`u=p(r_a,t)`$. If $`u`$ has an (unoccupied) predecessor pixel $`\text{pixel-pred}(u,t)`$, then robot $`r_a`$ moves to this pixel. (Since $`r_a`$ is a leader robot, it will never have an occupied predecessor pixel.)

Otherwise, pixel $`u=p(r_a,t)`$ is a leader pixel. If $`u=p(r_a,t)`$ has no neighboring frontier pixels, then robot $`r_a`$ tries to pass on the leadership. Robot $`r_a`$ first looks for a neighboring active pixel $`v`$. If no such $`v`$ exists, then $`r_a`$ becomes inactive and passes the leadership to its successor robot $`\text{robot-succ}(r_a,t)`$. When $`r_a`$ becomes inactive, pixel $`u`$ also becomes inactive and its successor pixel becomes the new leader pixel.

If robot $`r_a`$ looks for a neighboring active pixel $`v`$, and such a $`v`$ exists, then $`r_a`$ checks whether $`u=p(r_a,t)`$ is a left-hand neighbor of $`v`$. If this is not the case for any possible $`v`$, then again $`r_a`$ becomes inactive and passes the leadership to its successor robot $`\text{robot-succ}(r_a,t)`$. As before, when $`r_a`$ becomes inactive, pixel $`u`$ also becomes inactive and its successor pixel becomes the new leader pixel.

If there exists such a $`v`$, robot $`r_a`$ chooses the first such $`v`$ sweeping clockwise, starting from the incoming direction. We redefine the predecessor pixel $`\text{pixel-pred}(u,t+1):=v`$ and thus successor pixel $`\text{pixel-succ}(v,t+1):=u`$. Thus, the previous successor pixel of $`v`$ becomes a new leader pixel. (Note that this new leader pixel may or may not have a robot on it.) Now $`r_a`$ identifies its new leader; it follows predecessor pixels starting at $`v`$ until it finds a robot $`r_b`$ and sets $`\text{robot-pred}(r_a,t+1)=r_b`$ and $`\text{robot-succ}(r_b,t+1)=r_a`$. Robot $`r_a`$ then passes the leadership to $`r_c=\text{robot-succ}(r_b,t)`$.

### 4.3 Correctness of LFLF

We now show that LFLF always fills an environment. During LFLF, we claim that the following invariant is maintained: The left side of a flow line consists of visited pixels and obstacles. This follows from the fact that, whenever a robot enters a pixel, it turns as far left as it can (left-hand-on-the-wall). The invariant implies the following lemma, which we use to show that the visited regions propagate out from obstacle pixels:

###### Lemma 4.1.

The union of boundary points separates the visited region from obstacles and the right side of flows. In other words, the unvisited region only touches a flow from its right.

Another useful property of flow lines is the following:

###### Lemma 4.2.

Flows do not self-intersect.

###### Lemma 4.3.

Leadership passing does not change the total number of leader robots. Thus, the number of leader robots at any time step $`t`$ is equal to the number of active doors.

###### Theorem 4.4.

The robots always fill environment $`R`$.

###### Proof 4.5.

When a robot becomes inactive, it is a leader and its surrounding pixels must all not be frontier, for otherwise $`r`$ would advance to such a pixel and still be active. Therefore, if an active pixel $`u`$ is next to a frontier pixel $`v`$, any robot advancing into $`u`$ will not become inactive and some flow lines can advance into the empty region so it will be filled.∎

In the next sections we analyze the makespan for this filling strategy.

### 4.4 Competitive Analysis for Online Strategies

For any strategy $`𝒮`$, let $`n_𝒮(t)`$ be the number of robots that enter through the doors during timestep $`t`$; we define $`n_𝒮(0)=k`$.

Note that the inherent delay of $`2`$ in robot movement means that $`n_𝒮(t)`$ is a highly erratic function, so that in one timestep $`k`$ robots might enter the doors, implying that in the next timestep no robots enter the doors. In LFLF additional delays are caused by splicings, and therefore we cannot even say that a robot enters an active door pixel every other timestep. To understand why, consider Figure 2. When one flow line splices into a different flow line, a robot may get delayed by one additional time step in order to obtain the required separation between robots. If many splicing are happening next to each other, this can cause an accumulated delay of up to $`k`$ time units, which causes a “wave” of packed robots that propagates back towards the door pixels. Thus, a door pixel might temporarily hold off ejecting robots for many units without the door pixel becoming inactive. Whenever an active door pixel does not eject a robot we say there is a door-pixel delay.

Fortunately, the following lemma bounds the number of splicings (and also the total number of door-pixel delays).

###### Lemma 4.6.

A pixel can only be used to initiate $`O(1)`$ splicings.

###### Theorem 4.7.

The LFLF strategy is $`O(\mathrm{log}(k+1))`$-competitive.

###### Proof 4.8.

Consider the times $`\{t_i\}_{i=0}^{\mathrm{log}(k+1)}`$, where $`t_i`$ is the latest timestep during which at least $`k/2^i`$ door pixels are active. We call times $`t_0,t_1,t_2,\mathrm{},t_{\mathrm{log}(k+1)}`$ significant events. Consider the time interval from $`t_i`$ to $`t_{i+1}`$, when at least $`k/2^{i+1}`$ door pixels are active. Thus, the total number of robots leaving the door plus door-pixel delays during this interval is at least $`(k/2^{i+1})(t_{i+1}t_i)`$.

Now consider an optimal strategy $`𝒮^{}`$, and consider the cut $`\chi `$ associated with the significant event $`t_i`$ of LFLF. Cut $`\chi `$ is the boundary between the occupied and frontier pixels and has size at most $`k/2^i`$. A lower bound on the makespan of any strategy is the area “behind” $`\chi `$ (i.e., the side of $`\chi `$ not containing the doors) divided by the length of $`\chi `$ plus the amount of time required to send the flow from the door to reach $`\chi `$. Thus, the makespan, opt, of $`𝒮^{}`$ satisfies

$$\text{opt}\frac{k/2^{i+1}(t_{i+1}t_i)}{k/2^i}=(t_{i+1}t_i)/2.$$

Summing over all significant events we obtain that the total filling time of LFLF is $`O(\text{opt}\mathrm{log}(k+1))`$.∎

If we disregard the issue of delays caused by pixels having to be fully vacated before being re-entered, we get a whole class called sensible strategies, defined by the following two conditions:

$`n_𝒮(t)`$ is non-increasing in $`t`$; and

If $`n_𝒮(t)>n_𝒮(t+1)`$, then at time $`t`$ the number of occupied pixels bordering on a frontier pixel is $`n_𝒮(t+1)`$.

The above proof also implies the following; quite clearly, this result still holds if we extend the notion of sensible strategies to allow for some delays, as long as these only add a constant factor to the filling times.

###### Theorem 4.9.

Any sensible strategy is $`O(\mathrm{log}(\frac{k}{b}+1))`$-competitive.

### 4.5 Competitive Analysis of Simple-Minded Strategies

Under certain natural assumptions that limit the power of strategies, it is possible to give matching lower bounds on the competitiveness. To give some intuition, consider first the class of examples shown in Figure 3(left), which shows that the laminar flow algorithm may take as much as $`\mathrm{\Omega }(\mathrm{log}(k+1))`$ times opt.

###### Theorem 4.10.

The LFLF algorithm is $`\mathrm{\Omega }(\mathrm{log}(k+1))`$-competitive.

This lower bound can be generalized to a much larger class of strategies. We say that strategy $`𝒮`$ is simple-minded if the following condition holds: There is a constant $`C`$, such that we can only tell the number $`A^{}`$ of pixels in a region $`R^{}R`$ when a set $`R^{\prime \prime }R`$ has been visited that has all pixels in $`R^{}`$ within $`L_1`$ distance $`C`$.

Considering simple-minded strategies is quite natural in the context of robot swarms: If we assume we only “know” a region $`R^{}`$ after each pixel has been seen by one of the robots, then the constant $`C`$ corresponds precisely to the sensor range. The example of Figure 3(left) can be generalized as shown schematically in Figure 3(right), which forms the basis for the proof of the following theorem:

###### Theorem 4.11.

Any simple-minded strategy is $`\mathrm{\Omega }(\mathrm{log}(k+1))`$-competitive.

A particular subclass of simple-minded strategies is one that arises quite naturally in exploration problems: We say that a strategy is conservative if any pixel that has been “discovered”, i.e., come within sensor range of a robot, must stay within sensor range of some robot. For a constant-size sensor range, it is easy to prove the following statement, which has been claimed for a long time in a different context:

###### Proposition 4.12.

All conservative strategies are simple-minded.

As the LFLF strategy is conservative by design, we conclude that the lower bound of Theorem 4.11 applies to LFLF.

#### Acknowledgements

We thank N. Jovanovic and M. Sztainberg for contributions to this research. This reseearch was partially supported by HRL Labs (a DARPA subcontract), Honda Fundamental Research Labs, NASA Ames Research (NAG2-1325), NSF (CCR-0098172, EIA-0112849, CCR-0208670), U.S.-Israel Binational Science Foundation, and Sandia National Labs.