Multi-Robot Motion Planning Using Swarm Intelligence

Abstract

Swarm intelligence theory is proposed for motion planning of multi-robot systems. Multiple particles start from different points in the solutions space and interact to each other while moving towards the goal position. Swarm intelligence theory is a derivative-free approach to the problem of multi-robotcooperation which works by searching iteratively in regions defined by each robot's best previous move and the best previous move of its neighbors. The method's performance is evaluated through simulation tests.

Keywords

swarm intelligence multi-robot system motion planning stochastic search algorithms Lyapunov stability

1. Introduction

In the recent years there has been growing interest in multi-robot systems. As the cost of robots goes down and as robots become more compact the number of military and industrial applications of multi-robot systems increases. Possible industrial applications of multi-robot systems include hazardous inspection, underwater or space exploration, assembling and transportation. Some examples of military applications are guarding, escorting, patrolling and strategic behaviors, such as stalking and attacking.

Of primary importance in the design of multi-robot systems is motion planning through obstacles (Guo, Y. & Parker, L.E., 2002). To solve this problem algorithms based on stochastic gradient methods (Duflo, M., 1996) have been proposed. These are an extension of the potential fields methods which have have been previously used for robot path-planning (Khatib, O., 1986), (Rimon, E. & Koditscheck, D.E., 1991), (Reif, J.H. & Wang, H. 1999). The potential of each robot consists of two terms: (i) the cost Vⁱ due to the distance of the i -th robot from the goal state, (ii) the cost due to the interaction with the other M − 1 robots. Moreover, a repulsive field, generated by the proximity to obstacles, is taken into account. The differentiation of the aggregate potential provides the kinematic model for each robot. It has been proved that the velocity update equation is equivalent to a distributed gradient algorithm. The convergence to the goal state is studied with the use of Lyapunov stability theory. It is shown that in the case of a quadratic cost function Vⁱ the mean position of the multi-robot system converges to the goal state x^* while each robot stays in a bounded area close to x^* (Rigatos, G.G., 2005), (Rigatos, G.G., Tzes, A.P., & Tzafestas, S.G., 2005).

An alternative for multi-robot motion planning, which will be studied in this paper, is based on swarm intelligence. This method works by searching iteratively in regions defined by each robot's best previous move and the best previous move of its neighbors. Swarm intelligence is evident in biological systems and has been also studied in statistical physics, where collective behavior of self-propelled particles has been observed (Levine, H. & Rappel, W.J., 2002). The method is particularly useful for the avoidance of local minima. A swarm, which is a collection of robots, can converge to a wide range of distributions, while no individual robot is aware of the distribution it is working to realize. The dynamic behavior of the robots under particle swarm algorithm is analyzed with the use of ordinary differential equations. It is shown that appropriate tuning of the differential equation's coefficients can prevent explosion, i.e. the robots velocity is kept within certain bounds.

The structure of the paper is as follows: In Section 2 particle swarm theory is proposed for multi-robot motion planning. In Section 3 the convergence of the particle swarm algorithm used for robots steering, is analyzed with the use of ordinary differential equations. In Section 4 the performance of the particle swarm theory in the problem of multi-robot motion planning is tested through simulation tests. Finally, in Section 5 concluding remarks are stated.

2. Particle swarm theory for multi-robot motion planning

A method of distributed search for the goal position is the particle swarm algorithm which belongs to derivative-free optimization techniques and which is more likely to escape from local minima (Clerk, M. & Kennedy, J., 2002).

In the single robot case it has been shown that convergence to the goal position can be controlled using simple state machines (Rigatos, G.G., Tzafestas, S.G. & Evangelidis, G.J., 2001), (Rigatos, 2003). Coordinated motion of a swarm of mobile robots towards the goal position is however a more complicated problem.

Particle models consist of M particles with mass m_i, position xⁱ and velocity vⁱ. Each particle has a self-propelling force Fⁱ. To prevent the particles from reaching large speeds, a friction force with coefficient K_v is introduced. In addition, each particle is subject to an attractive force which is affected by the proximity σ to other particles. This force is responsible for swarming. To prevent particle collisions a shorter-range repulsive force is introduced. The potential of the particles is given by

V_{a} - V_{r} = \sum_{j = 1, j \neq i}^{M} a e^{- \frac{| x^{i} - x^{j} |^{2}}{2 σ^{2}}} - \sum_{j = 1, j \neq i}^{M} b e^{- \frac{| x^{i} - x^{j} |^{2}}{2 σ^{2}}}

(1)

where a and b determine the strength of the attractive and the repulsive force respectively. Thus, the motion equations for each particle are (Levine, H. & Rappel, J., 2000):

\begin{array}{l} m_{i} \frac{\partial}{\partial t} v^{i} = F^{i} - K_{v} v^{i} - \nabla (V_{a} - V_{r}) \\ \frac{\partial}{\partial t} x^{i} = v^{i} \end{array}

(2)

The particle swarm algorithm evolves in the search space by modifying the trajectories of the independent vectors xⁱ(t) which are called particles. Considering each robot as a particle, the new position of each robot xⁱ(t + 1) is selected taking into account the moves of the robot from its current position xⁱ(t) and the best moves of the rest M−1 robots from their positions at time instant t, i.e. Assume a set of M robots which is initialized at random positions xⁱ(0) and which have initial velocities vⁱ(0). The cost function of the i-th robot is denoted again by Vⁱ(xⁱ). The following parameters are defined in the Von Neumann region (Golez, E. & Matrinez, S., 1990) depicted in Fig. 1: (i) xⁱ(t) is the position vector of the i-th robot at time instant t, (ii) pⁱ(t) is the best position (according to Vⁱ) to which the i-th robot can move, starting from its current position xⁱ(t), (iii) p^g(t) is the best position (according to Vⁱ) to which the neighbors of the i-th robot can move, starting from their current positions x^j(t) j = 1, …, M ∨ j ≠ i.

Fig. 1.

Von Neumann region round each robot in the particle swarm algorithm

3. Stability of the particle swarm algorithm

The primary concerns of the particle swarm theory are: (i) Each particle i should move in the direction of cost function decrease (negative gradient), taking into account the directions already examined by the neighboring particles, (ii) The velocity of each particle should approach 0 as time goes to infinity.

To this end, the dynamic behavior of the particle swarm can be studied the use of ordinary differential equations, following the analysis given in [9]. The position and the velocity of the i-th particle is renewed according to:

v^{i} (t + 1) = v^{i} (t) + ϕ_{1} (p^{k} - x^{i}) + ϕ_{2} (p^{g} - x^{i})

(2)

x^{i} (t + 1) = x^{i} (t) + v^{i} (t + 1)

(3)

The following parameters are defined: φ = φ₁ + φ₂ and $p^{i} = \frac{ϕ_{1} p^{i} + ϕ_{2} p^{g}}{ϕ_{1} + ϕ_{2}}$ . It holds that

\begin{array}{l} v^{i} (t + 1) = v^{i} (t) + ϕ_{1} (p^{k} - x^{i}) + ϕ_{2} (p^{g} - x^{i}) \Rightarrow \\ v^{i} (t + 1) = v^{i} (t) + \frac{ϕ_{1} p^{i} + ϕ_{2} p^{g}}{ϕ_{1} + ϕ_{2}} (ϕ_{1} + ϕ_{2}) - x^{i} (ϕ_{1} + ϕ_{2}) \Rightarrow \\ v^{i} (t + 1) = v^{i} (t) + ϕ \bar{p} - ϕ x^{i} \Rightarrow v^{i} (t + 1) = v^{i} (t) + ϕ (\bar{p} - x^{i}) \end{array}

Thus, the following simplified equations are derived

v^{i} (t + 2) = v^{i} (t + 1) + ϕ (\bar{p} - x^{i} (t + 1))

(4)

x^{i} (t + 1) = x^{i} (t) + v^{i} (t + 1)

(5)

To refine the search in the solutions space, tuning through a constriction coefficient χ = κ/ρ₂, κ ∈ (0, 1) is introduced in Eq. (3) and Eq. (4). In that case the particle swarm algorithm takes the following form:

v^{i} (t + 1) = χ v^{i} (t) + ϕ (\bar{p} - x^{i} (t))

(6)

x^{i} (t + 1) = χ x^{i} (t) + v^{i} (t + 1)

(7)

It holds that

v^{i} (t + 2) = v^{i} (t + 1) (1 - ϕ) + ϕ (\bar{p} - x^{i} (t))

(8)

Subracting Eq. (5) from Eq. (8) yields

v^{i} (t + 2) + (ϕ - 2) v^{i} (t + 1) + v^{i} (t) = 0

(9)

Using the z-transform a frequency space expression of the above difference equation is z² + (φ−2)z + 1 = 0. Thus, the dynamic behavior of the particle depends on the roots of the polynomial z² + (φ−2)z + 1 which are $ρ_{1} = 1 - \frac{ϕ}{2} + \frac{\sqrt{ϕ^{2} - 4 ϕ}}{2}$ and $ρ_{2} = 1 - \frac{ϕ}{2} - \frac{\sqrt{ϕ^{2} - 4 ϕ}}{2}$ . The general solution of the differential equation is

v^{i} (t) = c_{1}^{i} e^{ρ_{1} t} + c_{2}^{i} e^{ρ_{2} t}

(10)

The parameters $c_{1}^{i}$ and $c_{2}^{i}$ are random. In Eq. (10) the stability condition ${lim}_{t \to \infty} v^{i} (t) = 0$ is assured if φ ≥ 4 (Clerk, M. & Kennedy, J. 2002). The pseudocode of the particle swarm algorithm is summarized as follows:

Initialize the robots population randomly: xⁱ(0), vⁱ(0), i = 1,2,…, M

Do (until convergence to x^* { For (i = 1; i < M; i + +) For all possible moves pⁱ, i = 1, 2,…, N from xⁱ p^k = arg min_pi {Vⁱ (pⁱ)} For all particles x^j, j = 1,2,…,G in area g p^g = arg min_pj {Vⁱ(p^g)} If (Vⁱ (p^k) < Vⁱ (xⁱ)) vⁱ (t + 1) = vⁱ + ϕ (p^k - xⁱ) + ϕ₂ (p^g - xⁱ) vⁱ (t + 1) = sgn{vⁱ (t + 1) min[vⁱ (t + 1), v_max]} xⁱ (t + 1) = xⁱ (^t) + vⁱ (t + 1) }

Parameters φ₁ and φ₂ are selected from a uniform distribution, taking into account the above mentioned convergence conditions. The robots velocity is bounded in the interval ±v_max. Random weighting with the use of the parameters φ₁ and φ₂ helps to avoid local minima but can lead to explosion.

4. Simulation tests

In the conducted simulation tests the multi-robot system consisted of 10 robots which were randomly initialized in the 2-D field. Two cases were distinguished: (i) motion in an obstacle-free environment (Fig. 2 – Fig. 3) and (ii) motion in an environment with obstacles (Fig. 4 – Fig. 5).

Fig. 2.

Particle swarm with robots interaction in an obstacles-free environment, considering a quadratic cost function.

Fig. 3.

Particle swarm with robots interaction in an obstacles-free environment: Trajectory of the mean of the multi-robot system

Fig. 4.

Particle swarm with robots interaction in an environment with obstacles environment, considering a quadratic cost function

Fig. 5.

Particle swarm with robots interaction in an environment with obstacles: Trajectory of the mean of the multi-robot system

The objective was to lead the robot swarm to the origin [x₁, x₂] = [0,0]. To avoid obstacles, apart from the motion equations given in Section 2 repulsive forces between the obstacles and the robots had to be taken into account. The reactive robot behavior for obstacle avoidance prevailed locally the motion laws which were derived using potential fields theory. This means that the collision avoidance was set to higher priority than maintenance of the cohesion of the robots swarm.

When the multi-robot system evolved in an environment with obstacles, the interaction between the individual robots (attractive and repulsive forces) had to be loose, so as to give priority to obstacles avoidance. In the particle swarm algorithm the area of possible moves round each robot was a Von Neumann one (Fig. 1). It was observed that the ratio Λ = φ₁/φ₂ affected the performance of the algorithm. It was observed that large Λ resulted in excessive wandering of the robots, while small Λ led to the early formation of a robot cluster.

For the motion in an obstacle-free environment using the particle swarm approach, the evolution of the aggregate Lyapunov function of the multi-robot system, as well as of the Lyapunov functions of the individual robots, is depicted in Fig. 6 and Fig. 7.

Fig. 6.

Particle swarm approach: Lyapunov function of the individual robots in an obstacles-free environment

Fig. 7.

Particle swarm approach: Lyapunov function of the mean of the multi-robot system in an obstacles-free environment

For the motion in an environment with obstacles using particle swarm approach, the evolution of the aggregate Lyapunov function of the multi-robot system, as well as of the Lyapunov functions of the individual robots, is depicted in Fig. 8 and Fig. 9.

Fig. 8.

Particle swarm approach: Lyapunov function of the individual robots in an environment with obstacles

Fig. 9.

Particle swarm approach: Lyapunov function of the mean of the multi-robot system in an environment with obstacles

5. Conclusions

In this paper the problem of distributed multi-robot motion planning was studied. A M -robot swarm was considered and the objective was to lead the swarm to a goal position. The paper considered a derivative-free technique capable of solving the problem of multi-robot motion planning. The multi-robot system was viewed as a swarm of M particles and the update of the position and velocity of each robot was carried out with the use of particle swarm theory. In that case there was no explicit calculation of the potential function's gradient. The dynamic behavior of the particle swarm was studied with the use of ordinary differential equations. Appropriate tuning of the differential equation's coefficients can assure that the particles velocity will converge asymptotically to zero.

Particle swarm theory for multi-robot motion planning were evaluated through simulation tests. It was observed that when the multi-robot system was evolving in an environment with obstacles, the interaction between the individual robots (attractive and repulsive forces) had to be loose, so as to give priority to obstacles avoidance. The performance of the method was satisfactory and succeeded cooperative behavior of the robots without requirement for explicit coordination or communication.

References

Clerk

& Kennedy

(2002). The Particle Swarm-Explosion, Stability, and Convergence in a Multidimensional Complex Space. IEEE Transactions on Evolutionary Computation, Vol. 6, no. 1

Duflo

(1996). Algorithmes stochastiques, Mathématiques et Applications, Vol. 23, Springer

Golez

& Martinez

(1990). Neural and Automata Networks: Dynamical Behavior and Applications, Kluwer

Guo

& Parker

L.E.

(2002). A distributed and optimal motion planning approach for multiple mobile robots, Proceedings of 2002 IEEE Intl. Conference on Robotics and Automation, pp. 2612–2619, Washington DC, May 2002

Khatib

(1986). Real-time obstacle avoidance for manipulators and mobile robots. International Journal of Robotic Research, Vol. 5, No.1, pp. 90–99

Levine

& Rappel

W.J.

(2000). Self-organization in systems of self-propelled particles, Physical Review E, Vol. 63

Reif

J.H.

& Wang

(1999). Social potential fields: A distributed behvioral control for autonomous robots, Robotics and Autonomous Systems, Elsevier, vol. 27, pp.171–194

Rimon

& Koditscheck

D.E.

(1991). Exact robot navigation using artifical potential functions, IEEE Transactions on Robotics and Automation, vol. 8, pp. 501–518

Rigatos

G.G.

Tzafestas

S.G.

& Evangelidis

G.J.

(2001). Reactive Parking Control of a non-holonomic vehicle via a fuzzy learning automaton. IEE Proceedings on Control Theory and Applications, Vol. pp. 169–180

10.

Rigatos

G.G.

(2003). Fuzzy Stochastic Automata for Intelligent Vehicle Control. IEEE Transactions on Industrial Electronics, Vol. 50, no. 1, pp. 76–79, 2003

11.

Rigatos

G.G.

(2005). Distributed gradient for multi-robot motion planning. ICINCO'05, Proceedings of 2nd Intl. Conference on Informatics in Control, Automation and Robotics, September 2005, Barcelona, Spain.

12.

Rigatos

G.G.

Tzes

A.P.

& Tzafestas

S.G.

(2005). Distributed Stochastic Search for multi-robot cooperative behaviour. IMACS, Proceedings of 2005 Intl. Conference, July 2005, Paris, France.