Simulation of Natural Phenomena

Simulation of multi-agent objects inspired by Ants Behavior
Ant colonies attracted scientists because of their ability to collectively achieve complex tasks through self-organization processes based on simple rules. It is believed that such collectively technique is the main reason for the survival of such small insects through millions of years on earth despite the drastic changes in environment and living conditions through history. Imitating this behavior, computer scientists and engineers are interested in building ants-like agents (e.g. ants-robots) that has limited sensing and computational capabilities, but are simple to design, easy to program, and cheap to build. This makes it feasible to deploy groups of such agents, in places inaccessible otherwise, and take advantage of the resulting fault tolerance, parallelism, and collectively achievement of a certain goal.  One of the most interesting ants behaviors is the highly optimized path that ants follow, in their foraging, between the source of food and the colony's nest. The ants decision is controlled by imitating and following of trails of a chemical substance, called pheromone. When there is a choice among several alternative paths, ants choose a path in a probabilistic way, based on the pheromone concentration over the possible paths. This mechanism allows the selection of the shortest path among several ones. Hence, the pheromone concentration on those paths increase more rapidly and they attract more ants. This process of indirect communication relies on a positive feedback mechanism and depends on the environment characteristics, e.g. colony size, food type, number of food sources and the nature of the environment on which the ants are moving. Such optimized behavior inspired several applications, for example: traveling salesman problem, the quadratic assignment problem, the job shop scheduling problem, the graph coloring problem, the vehicle routing problem, and network routing algorithm with digital pheromone which used by British Telecommunications PLC in London to solve routing problem and to find the shortest path.

4. Group cooperation for achieving goals

Simulation of multi-agent objects inspired by Ants Behavior

How Real Ants Behave?

1. Complex problems could be solved by cooperative simple tasks

2. Shortest path: from food to colony

Solving difficult (NP) optimization problems:

a. Traveling Salesman problem
b. Network routing problem
c. Graph coloring problem
d. Distributed work (Robotics)

Simulation of multi-agent objects inspired by Ants Behavior

What can we learn?

A

max

> A

t

?

 

1. Ants Birth-Death Process

Initialize: Colony

Enough food?

Create Ant

No

No

Simulation of multi-agent objects inspired by Ants Behavior

The Model

2. Food Creation Process

Initialize: Food

F

max

> F

t

?

Create Food

No

Simulation of multi-agent objects inspired by Ants Behavior

The Model

3. Ant, Food, Pheromone positions

Pheromone

Simulation of multi-agent objects inspired by Ants Behavior

The Model

Possible food

Ant

Upper Part

Left Part

Right Part

Down Part

4. Pheromone feeling

100

)

(

100

%

%

1

,

,

neighbor

Direction

own

t

y

x

t

y

x

D

 

Pheromone

D

Pheromone

Pheromone

+

=

-

Simulation of multi-agent objects inspired by Ants Behavior

The Model

5. Pheromone Spread Relationship

Initialize: pos

pherm > 0?

Spread

Decrease

Calculate new pherm

No

Initialize: pos

pherm > 0?

Spread

Decrease

Calculate new pherm

No

To Position

From Position

From Ant

Simulation of multi-agent objects inspired by Ants Behavior

The Model

6. Ants Actions

At any position: ants move forward, turn right, turn left, pick food or rest

At colony: ants put food or rest

If far from colony ants must back to colony

Ants always spread pheromone

Simulation of multi-agent objects inspired by Ants Behavior

The Model

 

8. Ants behavior chart

Initialize: Ant

In Colony?

P(X)=?

Move

Turn/R

Turn/L

Rest

Pick

Have food?

Put food

Yes

Yes

Yes

Food found?

Have food?

Spread ph

Spread pr

Spread ph

Decre. Life

Yes

Simulation of multi-agent objects inspired by Ants Behavior

The Model

Calculate: Pheromone,
Food, and Probability

No

No

No

No

1. Control Panel

Simulation of multi-agent objects inspired by Ants Behavior

The Simulation

2. System Initialization

Simulation of multi-agent objects inspired by Ants Behavior

The Simulation

3. Pheromone Dependency Initialization

Simulation of multi-agent objects inspired by Ants Behavior

The Simulation

4. Environment Pheromone Condition Initialization

Squared Environment Condition

Normal Environment Condition

Framed Environment Condition

Simple 2-Squared Environment Condition

Lined Environment Condition

Simulation of multi-agent objects inspired by Ants Behavior

The Simulation

5. System Components

c. Ants

d. Food

a. Environment

b. Colony

e. Pheromone

Simulation of multi-agent objects inspired by Ants Behavior

The Simulation

6. Ants Grouping Property

Strong pheromone area

Colony area

Simulation of multi-agent objects inspired by Ants Behavior

The Simulation

7. Simulation Information

Environment Information

Traced Ant Information

Pheromone Information

Random Walk Information

Simulation of multi-agent objects inspired by Ants Behavior

The Simulation

8. Random Walk

Simulation of multi-agent objects inspired by Ants Behavior

The Simulation

9. Graphical Representation

Simulation of multi-agent objects inspired by Ants Behavior

The Simulation

1. Vehicle Routing Problem (VRP)

VRP is a distribution problem in which trucks are based at
a warehouse (depot) and are required to visit a set of
customers. Each customer has a demand and a geographic
location. The objective is to minimize the total distance
traveled by all trucks. The sum of demands of customers
served by a truck cannot exceed the truck capacity. The
demand of a customer cannot be split among two or more
trucks.

Simulation of multi-agent objects inspired by Ants Behavior

Application

2. VRP Simulation: initialization

Warehouse

Customers

Simulation of multi-agent objects inspired by Ants Behavior

Application

3. VRP Simulation: Result

Simulation of multi-agent objects inspired by Ants Behavior

Application