lunedì 20 luglio 2015

Experimenting with decentralized control for swarm shape formation

Abstract

Objective of the project is to experiment with a decentralized control for swarm shape formation in a virtual environment.
Approach taken to the problem is the use of motor schema for aggregation of different behaviour forces used to provide control and autonomy of the swarm in respect of the user and some simple task like obstacle avoidance.
The techniques proposed can be used as an approach to deal with shape formation of virtual entities in videogames or as means to create graphical effects in particle systems.

Introduction

Swarm systems are the one made by a collection of individual entities, all acting on their own to reach a global collective goal. This type of systems are becoming more and more common due to their highly flexibility and ability to react to change, usually inspired by natural biological systems they are now used in a variety of useful applications, like: map building, surveillance, exploration, etc.
For means of adaptability and control, while providing their main functionality, the swarm should be able to preserve or form a defined shape, like a sphere, a grid lattice or a line, moreover shape formation can be the main functionality of the swarm, like in an hunting-like environment where predators forms a circle around the prey. On the matter of swarm robots, shape formation is a topic already discussed in research, where most of the resources are focused on dealing with poor sensors capability and limits imposed by the physical world. Not so much is said about using this decentralized approach as an architecture for building interactive applications, like videogames, simulation environments, etc.
This document wants to focus on the practices used for building an interactive application that simulates shape formation for a group of agents in a predefined environment. We’ll focus on the decentralized approach used for forming a circle with variable diameter size, a simple line, a grid lattice with variable vertical lines and a sparse formation in respect of a fixed distance constraint. We’ll see how using the potential field movement schema we can aggregate different behaviours that offers a high flexibility in respect of coupling with multiple tasks, like obstacle avoidance, preserve separation and react to user control.

Assumptions

Since we are not dealing with robots but simple agents in a virtual environment, strong assumptions are made.
Agents knows their exactly position and rotation in space based on common coordinates of the scene, moreover agents have the ability to locate “peers” among the scene and determinate the exact distance from each of them (i.e. they have a “global” sensing capability as stated in [1] and [2]).
Usage of these pattern formation tec
\hniques can still be used on not-complex physical environment with respect of these assumptions, using gyroscopes and indoor or global positioning systems.

Development

Forming a circle

The method used for forming the shape of a circle is based on the CIRCLE Algorithm proposed in [1]. The objective of this algorithm is to form an approximation of a circle of diameter D, given the ability of the agent to perceive each of his peers.
Each agent R continuously monitors the distance from the furthest agent R’ and from the nearest agent R’’ and calculates the distance d between the two, then acts as follow:
  • Case 1. If d > D, then R moves toward R'.
  • Case 2. If d < D - δ, then R moves away from R'.
  • Case 3. If D - δ < d < D, then R moves away from R'.
Where δ is a small constant.
As [1] states, the form of a circle is assured by these three simple cases if the distribution of the agents in the space is uniform, however we overcome this limit by summing to the vector force that create the circle a separation vector force that distanciates peers.
Figure 1 shows results of the application compared to the ones of [1].

Forming a line

Forming a line segment is one of the simplest formation behaviour, all one agent R needs to do is to detect his nearest right peer r(R) and his nearest left peer l(R) and then move to the middle point of the r(R)l(R) segment. Agents that doesn’t have a right or left peer are the point of the line segment and shouldn’t move. Result of the algorithm as proposed in [1] is shown in figure 2.

Forming a sparse formation

Another interesting topology for a swarm is the one in which it’s parts are never too close, but either not too far apart. Using the dispersion method proposed in [2] one can control a swarm so that it doesn’t form a specific shape, but a more sparse and yet uniform in peer distance formation.
The dispersion method described in [2] was slightly modified to work better in a decentralized fashion and works as follows:
  • For every agent O find the three closest agents A,B and C
  • Initialize a force vector to zero
    • if distance of A from O is > d sum to the force vector an attractive force from O to A
    • if distance of A from O is < d sum to the force vector a repulsive force from A to O
  • do the same for B and C
  • apply the force vector to O
The constant d is a given min distance among peers.
Results of the algorithm are shown in the figure.

Forming a Grid Lattice

Different methods for obtaining a grid formation where experienced, however one only seems to show a better adaptability to change among others and it’s based on the use of a square formation algorithm and the line formation algorithm.
Since every agent has the ability to perceive each of his peers position in space, he can calculate the swarm center with a simple average function, then he can find which agents are the vertex of the grid by evaluating the distance vector of each agent from the center.
  • If the agent computing is a vertex, then he executes the square formation algorithm that constrains the x and z coordinates of the agents to form a square. Consider the agent A  vertex of the square formed by the agents ABCD, where A is the upper left edge, B the upper right and so on. A moves on the z axis so that it’s z is the same as B z, the same thing is done for the x coordinate.
  • If the agent computing is not a vertex he still has to compute the square based on his peers position, then he mentally divides the square in vertical zones, based on a given number v of desired vertical lines. Once the agent knows in which vertical zone of the grid he’s in, he execute the line segment algorithm only considering peers in the same vertical zone. If the agent is the edge of the segment, then he should move so that it’s x is the same as the square vertex.
Given an uniformed distribution of the agents in the space, these method produces a pretty good result, however one can surely notice that selection of the vertical zone is based on the initial position of the agent, so a correct grid needs a new force that can better arrange the agents during the formation.
This method is essentially different from the one proposed by [3] that implies an automatic or user controlled coordination between agents to create the grid. Comparison of the two methods is shown in the figures.

Swarm Control and Behaviour

The use of motor schema revealed fundamental for implementing different forces used for both control based on the user input and autonomous behaviour as evading objects.  

Control Forces

  • Movement: Used to move a selected agent in the scene.
  • Rotation: Makes the agent move around the center of the swarm, due to the algorithms used this force interferes with all the formations except for the circle.
  • Expansion/Contraction: The agent move away or towards the center of the swarm.

Other Forces

  • Formation: The force that permits the agent to form a specific pattern with his peers.
  • Avoidance: A force added when the agent perceives an obstacle on his way, due to the nature of the circle and dispersion algorithm the constraint imposed on a single agent prevents the whole swarm to move towards an obstacle. This isn’t the case for the line and grid formation however, that can move near and through obstacles and then recreate their formation. A trigger can be used for circle and dispersion formation to drop the use of the formation force when they perceive something on their path.
  • Separation: A simple separation force among the peers.

Conclusion

In this document we have presented ways of dealing with shape formation of a swarm in respect of some simple patterns like a circle, a line, a grid lattice and an uniform sparse formation. Building and using the application is a mean for experimenting with swarm control and their properties in a virtual environment.
The usage of a potential field pattern for aggregation of the precalculated forces in play revealed as the basic method to control the swarm with no particular drawbacks experienced.
This decentralized approach offers properties of adaptability to the environment, every agent works on his own in respect of the position of his peers, there’s no explicit leader or reference to other agents, as a result of this, there’s not a single point of failure and no need to update references when an agent is destroyed or created.
As the application is an interesting tool to experience with swarm shape formation, it’s always righteous to remember that problems arises when similar techniques are used in the real physical world.

References

[1] Distributed Algorithms for Formation of Geometric Patterns with Many Mobile Robots of Kazuo Sugihara and lchiro Suzuki*- Journal of Robotic Systems 13(3), 127-139 (1996) John Wiley & Sons, inc.
[2] Dispersion and Line Formation in Artificial Swarm Intelligence DONGHWA JEONG and KIJU LEE, Case Western Reserve University
[3] Decentralized control of multi-agent systems for swarming with a given geometric pattern - Teddy M. Cheng∗, Andrey V. Savkin

Download Link

Windows build of the application
C# class for shape formation