Effectiveness of Agents' Communication using Pheromone in RoboCup Rescue Simulation System

Hisayuki Sasaoka

Asahikawa National College of Technology

http://sourceforge.net/projects/roborescue/ · http://rc-oz.sourceforge.jp/pukiwiki/

Abstract Ant Colony System is one of powerful meta-heuristics algorithms in multi-agent system. We have known that the algorithm is one of swarm intelligence algorithms and some researchers have reported the effectiveness of some applications with them. We have developed fire-brigade agents with proposed method in RoboCup Rescue Simulation system. The final goal of our research is an achievement of co-operations for hetero-type agents in the multi-agent system. In this research for implementation for one type of agents is the first step of this goal. Then I have reported results of evaluation experiments using the agents. This paper has presented acquiring method for agents' actions with our proposed method based on MAX-MIN Ant System algorithm.

Introduction

Some researchers have reported the effectiveness of systems installed swarm intelligence algorithms [1], [2], [3]. Ant Colony Optimization (ACO) and Ant Colony System (ACS) have become a very successful and widely used in some applications. These algorithms have been used in some types of application programs [4], [5], [6].

In real ants' feeding actions [7], [8], [9], they are able to find the shortest path from a food source to their nest by pheromone information. Pheromone is one of chemical materials and ants deposit pheromone on a path between a food source to their nest and it becomes one candidate solution. In a case that some ants trail a path deposited pheromone, the candidate is reinforced. Moreover pheromone disappears into air as time progresses. Ants have done these processes iteratively. The behavior of real ants has inspired ACO and ACS. The system based on ACO and ACS are used artificial ants cooperate to the solution of a problem by exchanging information via pheromone.

There are a lot of distributed constraint satisfiability problems. One of them is a traveling salesperson problem and another is a network routing problems and so on. However, they have no noise for solving and all of distances between each city are given in advance. Moreover their situations have never changed for each simulation steps. However situations or outer information in environment is always changing in the real world, dynamically. In some cases, we are disable to know cues to solve a problem in advance. In other case, some outer noise gets information erased or interpolation them. On the other hand, in a situation of RoboCup rescue simulation system, agents need to handle huge amount of information and take actions dynamically. Therefore, a simulation system of RoboCup rescue is a very good test bed for multiagent research.

In this paper, we would like to propose our proposed method based on MAX-MIN Ant System algorithm [10] and apply to agents of fire brigade agents in my team on RoboCup Rescue Simulation System [11], [12].

Related Works

In this section, I would like to explain basic idea of ACO and the related works and show a multi-agent system of RoboCup Rescue Simulation.

Ant Colony Optimization

Agent programs which run based on ACO have decided their actions by a probabilistic value and a generated random value. In each step they have calculated the values and have taken one choice. The probabilistic value is calculated by formula (1).

$$p_{ij}^{k}(t) = \begin{cases} \frac{\left[\tau_{ij}(t)\right]^{\alpha} \left[\eta_{ij}\right]^{\beta}}{\sum_{l \in J_{i}^{k}} \left[\tau_{il}(t)\right]^{\alpha} \left[\eta_{il}\right]^{\beta}} & (if \ j \in J_{i}^{k}) \ 0 & (in \text{ other case}) \end{cases} \dots (1)$$

In this formula, a value of $\tau_{ij}$ means the value of associated pheromone trail on arc (i,j). A value of i means a current position in a simulation field. A value of j means a choice to move to the position. On the other hand, a value of $\eta_{ij}$ means a heuristic value which is available a priori, $\alpha$ and $\beta$ are two parameters which are determined by a relative influence of pheromone trail and the heuristic information. The value of $\eta_{ij}$ has to be decided in advance.

Pheromone trails are updated and pheromone evaporation is able to be calculated by formula (2).

$$\tau_{ij}(t) \leftarrow (1-\rho)\tau_{ij}(t) + \Delta \tau_{ij}^{k}(t) \qquad \cdots (2)$$

his value of $\rho$ means the pheromone evaporation rate, which is between 0 and 1. A value of $\Delta \tau$ is amount of deposited pheromone and is calculated by formula (3). A value of Q is scored by results of agents' action.

$$\Delta \tau_{ij}(t) = \begin{cases} \sum_{k=1}^{m} \frac{Q}{L^{k}(t)} & (if (i, j) \in L) \ 0 & (other) \end{cases}$$ (3)

MAX-MIN Ant System

Stützle, T. and Hoos, H.H. proposed MAX-MIN Ant System (MMAS) [10]. It derived from Ant System and achieved an improved performance compared to AS and to other improved versions of AS for the TSP. The basic ideas are below,

• 1. only one ant who is the best in the process is allowed to update pheromone tr ails
• 2. pheromone trail values are restricted
• 3. trails are initialized to their maximum value.

Our Approach

In our proposed algorithm, the range of pheromone trail value is decided by hand from preliminary experiment. Moreover, we have confirmed that there is a noise of pheromone trail in the initial step of updating pheromone trails. Then, our algorithm has calculated by equal (2)' in the initial step. This ρinit aims to cut down effect from the noise and the value is also decided by hand.

$$\tau_{ij}(t) \leftarrow (1-\rho)\tau_{ij}(t) + \rho_{init}\Delta\tau_{ij}^{k}(t) \qquad \cdots (2)$$

This improvement is different from our previous study [13].

Evaluation Experiment I

We have developed experimental agents based on sample agents whose source codes are included Robocup rescue simulator-package file [11], [12]. We have prepared three different types of fire-brigade agents. They are below,

Type-A) agents are equal to base fire-brigade agents.

Type-B) agents are implemented our proposed algorithm.

Type-C) agents are implemented our proposed algorithm. Moreover they select only best path calculated by pheromone's concentrate.

We have run agents 1500 steps on a test map, which is for five times on simulation term. The map is also included Robocup rescue simulation simulator-package file.

TABLE I Results of evaluation experiment-I

Procedures

We have developed experimental agents based on sample agents whose source codes are included Robocup rescue simulator-package file [11], [12]. We have prepared three different types of fire-brigade agents. They are below,

Type-A) agents are equal to base fire-brigade agents.

Type-B) agents are implemented our proposed algorithm.

Type-C) agents are implemented our proposed algorithm. Moreover they select only best path calculated by pheromone's concentrate.

We have run agents 1500 steps on a test map, which is for five times on simulation term. The map is also included Robocup rescue simulation simulator-package file.

Results

A score of the map is 117.828 points at the start of simulation. Table II shows results.Other types of agents are equal to sample agents in RoboCup rescue simulation simulator-package file.

Scores of these trials are shown in TABLE II. In this table, the average score 18.763 point with Type-B is better than other agents, slightly. Moreover the best score is 20.840 points with Type-B. From this result, we have confirmed the effectiveness of our algorithm.

Evaluation Experiment II

We have prepared four different types of fire-brigade teams constructed by agent Type-A, Type-B and Type-C. They are below,

• Team-D) has fire-brigade agent Type-A(about 50%), Type-B(about 25%) and Type-C(about 25%).
• Team-E) has fire-brigade agent Type-B(about 50%), Type-A(about 25%) and Type-C(about 25%).
• Team-F) has fire-brigade agent Type-C(about 50%), Type-A(about 25%) and Type-B(about 25%).
• Team-G) has fire-brigade agent Type-A(about 33%), Type-B(about 34%) and Type-B(about 33%).

Procedures

We have prepared four different types of fire-brigade teams constructed by agent Type-A, Type-B and Type-C. They are below,

• Team-D) has fire-brigade agent Type-A(about 50%), Type-B(about 25%) and Type-C(about 25%).
• Team-E) has fire-brigade agent Type-B(about 50%), Type-A(about 25%) and Type-C(about 25%).
• Team-F) has fire-brigade agent Type-C(about 50%), Type-A(about 25%) and Type-B(about 25%).
• Team-G) has fire-brigade agent Type-A(about 33%), Type-B(about 34%) and Type-B(about 33%).

Results

Scores of these trials are shown in TABLE II. In this table, the average score 19.691 point with Team-F is better than other teams, slightly. Moreover the best score is 21.612 points with Team-F. From this result, we have confirmed the effectiveness of our algorithm.

TABLE II Results of evaluation experiment-II

CONSIDERATION

Fig. 1 shows one screen caption which the agents have a difficulty in actions for firefighting by our fire-brigade agents and civilian agents by ambulance agents. The reason in this situation is that some blockades on this road are disturbing and these agents are disenable to go through. Then there is a heavy traffic jam on the point. We can see red circle in Fig. 1.

On the other hands, Fig. 2 shows another screen caption of removing some blockades on the same point of the road in another trial. In this case, agents are enable to go through and they success in their jobs. We can see blue circle in Fig. 2. However, in this research, our agents do not communicate between different types of agents. In the near future, we have a plan to discuss the method of communication using our method between these agents.

Conclusion

This paper has presented the proposal and reported the effectiveness of updating pheromone trails in agents with ACO. We have a plan to develop agents installed ACO algorithm on hetero-type agents in RoboCup Rescue Simulation System.

Acknowledgments

We have developed our experimental system with the agent, which is based on source codes included in packages of simulator-package file [11], [12]. This work was supported by Grant-in-Aid for Scientific Research (C) (KAKENHI 23500196).

References

1. Dorigo, M., Stützle, T.: Ant Colony Optimization, The MIT Press, (2004).
2. Bonabeau, E., Dorigo, M., Theraulaz, G.:Swarm Intelligence From Naturak ti Artificial Systems, Oxford University Press( 1999 )
3. Bonabeau, E., Dorigo, M., Theraulaz, G.: Inspiration for optimization from social insect behaviour, Nature, Vol. 406, Number 6791, pp. 39-42 (6 July 2000).
4. Hernandez, H., Blum, C., Moore, J. H.: Ant Colony Optimization for Energy-Efficient Broadcasting in Ad-Hoc Networks, in Proc. 6th International Conference, ANTS 2008, Brussels, pp.25 –36(2008).
5. D'Acierno, L., Montella, De Lucia, B. F.: A Stochastic Traffic Assignt Algorithm Based Ant Colony Optimisation, in Proc. 5th International Conference, ANTS 2006, Brussels, pp.25 – 36(2006).
6. Balaprakash, P., Birattari, M., Stützle, T., Dorigo,, M.: Estimation-based ant colony optimization and local search for the probabilistic traveling salesman problem, Journal of Swarm Intelligence, vol. 3, Springer, pp. 223–242(2008).
7. Gordon, D. M.: Ants at work, THE FREE PRESS, New York (1999).
8. Keller, L. and Gordon, E.: the lives of Ants, Oxford University Press Inc., New York (2009).
9. Wilson, E. O. and Duran, J. G.: Kingdom of ants, The John Hopkins University Press, Baltimore, (2010).
10. Stützle, T. and Hoos, H.H. MAX-MIN ant system. Future Generation Computer System 16(8), pp.889-914(2000).
11. RoboCup Rescue Simulation Project Homepage, http://sourceforge.net/projects/roborescue/
12. RoboCup Simulation League Spring Competition 2011 in the 73th National Convention of Information Processing Society Japan, http://rc-oz.sourceforge.jp/pukiwiki/
13. Sasaoka, H.: RoboCup Rescue 2011 Rescue Simulation League Team Description anct_resq_2011, in Proc. of RoboCup 2011, (2011).