RoboCup 2010 – Rescue Simulation League Team Description MRL (Iran)

Roohollah Mirsharifi, Mandana Eghbali, Pooya Deldar Gohardani, Siavash Mehrabi, Zana Vosough

Azad University of Qazvin, Department of Computer Engineering and Information Technology, Mechatronics Research Lab, Qazvin, Iran

http://www.mrl.ir

Abstract This paper describes the main features of the MRL rescue simulation team that is going to participate in RoboCup2010 competitions. Improving previous approaches drawbacks via new artificial intelligence based methods is our main aim. Distributed communication model for communication-limited scenarios and Fuzzy decision making for Police Force agents are our new improvements. Stigmergic coordination between heterogeneous agents is another idea for agents' implementation in the future.

1. Introduction

The most important change in this year competitions is the totally new kernel. Our team has run the new kernel and we are working on porting our previous agent implementation to the new kernel. Meanwhile two main changes is done from our previous team work: First a distributed communication model especially for communication limited scenarios is implemented, Second police force agents decision making is now utilizing a fuzzy decision making strategy.

Our team had some problems in previous year competition above all the communication problem in communication-less scenarios. We have focused on this problem and implemented a new idea for this, a distributed communication model based on meeting points. The experiments on this model show unquestionable results.

The team has utilized fuzzy decision making in fire brigades target selection before [5] and now we want to use it as path selecting for police force agents. In communication-less maps a distributed communication model is designed and we expecting much increase in quality of communication in those scenarios. Stigmergic [1] coordination between different types of agents is also our goal to implement. A reconstruction is made for fire brigade agents and lots of bugs have been solved.

2. Distributed Communication Model

The problem is: each agent has its own information about the real world and is unable to share its information with other agents. To overcome this problem we used short distance communication called "Say" as a basis for a distributed communication model. In this model information flow is rotated either clockwise or counter clockwise. In this model there is several meeting point for agents. Each agent will go to a specific meeting point in specific time period. The rotational meeting for agents will make a distributed communication model with cyclic information flow.

In figure 1 two steps of simple agents meeting strategy to make the communication model is shown. In this figure you can see the yellow points which could be considered as data carrier that have the duty to deliver the data to the data carrier in the neighbor partition and receive its data, the blue cross sign which could be considered as meeting points and the red arrows which describe the meeting point that the data carrier should go for it. The figure 1-(a) is the first step and the figure 2-(b) is the second step of the distributed communication model in each iteration.

3. Stigmergic coordination

Stigmergy [2] is a concept occasionally used in biology to describe the influence on behavior of the persisting environmental effects of previous behavior. It was originally proposed by Grasse to explain some of his observations on termite building behavior. Grasse had observed that worker termites in the presence of particular configurations of a construction (and of other workers) would be stimulated to a high degree of activity, and would tend to add building material to specific parts of the construction. As the construction was changed by these additions, the site of addition of further material would be modified, leading to the progressive growth and completion of the feature; the termites would then switch to constructing another such feature, or would begin a new task apparently triggered by the presence of the completed feature. [3]

The rescue simulation system and real world conditions narrows down the communication chance between agents which lead to lack of enough environmental data, and therefore, hinders efficient decision-making.

Our main goal of using Stigmergy is to achieve better coordination between heterogeneous agents in limited communication environment.

For example, consider this scenario: A Fire Brigade agent must choose between burning building one, empty of civilian and building two holding a civilian. If there was no civilian in the second building, the first building should have been chosen to extinguish first. A centralized system, unconscious of the civilian presence in building two, would definitely choose the first building which would leave the civilian to perish in the second building.

Stigmergy uses the environment as indirect way of communication. In accordance with Stigmergy nature, agents use the environment as an indirect way of communicating with one another. That is: they leave traces of "meaningful" effects on the environment so other agents find those effects and gain more data.

In our strategy, to accomplish task of affecting the environment - sending limited messages -, agents use say channel in communication-less challenges and also use radio channel in normal challenges. This method enables agents to operate by sending minimum messages.

4. Police Force Agent

In the previous year an important aspect of our strategy was dividing the map to regions in equal size which are called partitions. Each partition is evaluated by some Properties (i.e. Blocked Agent Property, Civilian Property, Fire Property, Partition Value Property, Refuge Property, etc.) Each of these properties is related to one important entity of the map. The final goal is to select the best partition. In this method each agent is assigned to an appropriate partition and will do the police force duty as long as the selected partition has the most value for it. That strategy led to some advantages like:

1. PF agents don't assign to any partition.
2. Fully coverage of the map by PF agents.
3. Preventing PF agents from doing redundant works

In that method, each agent was responsible for a partition, but not assigned to it. In other words, if there is a critical path in other partitions so PF agent may try to clear it. In that attitude each agent gives more importance to paths under his supervisory with elevating their parameters values. Thus if there was not any critical path here he can go and help other colleagues.

Hence linear estimation was used for selecting partition and path with highest priority in RoboCup2009. We specified some important parameters of partition as Properties and then calculated a value for each Path. After selecting partition with highest value, the same mechanism is used for selecting path. The value is constructed by following formula:

$$V_{Path} = V_0 + \sum_{n=1}^{number\ of\ Particles} \left(\sum_{n=1}^{number\ of\ Particles} \left(R_n * D_n * C_n + \mu\right)\right) \quad (1)$$

Where $V_0$ is the value of path based on particles, $C_n$ is a coefficient for $N_{th}$ particle which presents the importance of that particle, and n shows the number of particles, $D_n$ is distance of $N_{th}$ particle to this path and $R_n$ is Rank and is about 3/n if h particle is in current partition otherwise it's about 1/n. All of the assumed coefficients were empirical and based on observation of rescue process.

Some types of Particles are:

• Blocked Agent Particle is one of the most important types of particles which consider those agents who are locked by blockades. The most value of coefficient has been considered for these particles because some of blocked agents like Fire brigade and Ambulance Team agents have a key role in Rescue Simulation environment.
• Fire particle is another important type of particles which consider all fire sites of map. Considering to the importance of fires, we evaluate Fire sites with a distinct type of particles.
• Refuge Particles consider Refuges and whole of paths which are around of that. If we have more than once refuge, we dedicate fewer coefficients for those particles.

And in the communication less mode we have two another types of particles too:

1. Time Particle :
2. Partition Particle :

But that method was not perfect in some cases which are described in the following. For example : we had a lot of different particles which all of them had different coefficient, so setting and coordinating of them with each other was very hard. In addition to when we wanted to add a new particle to consider another important type of objects we were faced with a lot of problem because there was possibility which the new particle didn't coordinate with others. With all these different types of particles we decided to choose the most important partitions in the map in each cycle based on values of paths which are important because of mentioned particles. So we had a complex formula to compute overall value for each partition in each cycle [1]. And many parameters which were considered in previous method make interference and unreasonable decisions.

For example we had one parameter which determined effect of time and distance for each path (Time Effect (µ)) which determination of that parameter was a highly complex process.

After implementing different strategies for PF agents in last many years' competitions, we have come to the conclusion that when we have different factors for decision making the most suitable approach to gain better result is using fuzzy method as we used it for Fire brigade agents' decision making in previous years.

This year we have used fuzzy logic as a human like decision making system for PF agents. The linear estimation for selecting Partitions and Paths to clear is not always reliable, because an immediate change of a parameter at a time may lead agents to the wrong decision. For example suppose that Blocked Agent Particle is one of the parameter to select a Partition, and Partition with highest number of Blocked Agents has a higher priority in linear estimation. If PF agents ignore clearing their current partition because another Partition's value decreased immediately because an agent moved to that Partition and got block by a blockade, it is probable that they would have futile move but if they continued their task they won't. And it's exactly that problem which implementing fuzzy method could help us to solve it.

5. Fire Brigade Agents

We have reconstructed our fire brigade agent's code and simplified it so that the bugs and difficulties which we were unable to solve during the years of competing in RoboCup have been solved. We have used utilized java programming techniques like unit test, helper classes and continuous integrations. Many problems have been solved and improved our fire brigade agents' performance. Figure 4 shows the performance of 2010 fire brigade agents.

6. Conclusion

Many new approaches were utilized by MRL in rescue simulation environment, which are inspired from the state-of-the art artificial intelligence contributions. A distributed communication model has implemented that made significant changes in communication and coordination between agents. Police force agent decisions are now made using fuzzy decision making and we are working on stigmergic coordination between agents. We think reconstructing fire brigade agent's code and using the distributed communication model will be keys to win in two new challenges introduced in this year competition.

References

1. Mark Alan Elliott, Stigmergic Collaboration A Theoretical Framework for Mass Collaboration, October 2007, PhD Thesis in University of Melbourne
2. Wilson E.O. , Parunak H., Lutterbek B., Bearwolff M., Gering R.A., Rodriguez M.A., Chiristiansen L.R. , "Stigmergy" , Wikipedia, http://en.wikipedia.org/wiki/Stigmergy ,2009.
3. Theraulaz G. , Bonabeau E., Karsai I. and Small P. , " Defenition of Stigmergy " , http://www.Stigmergicsystems.com/stig\_v1/stigrefs/article1.html?540817 , 2003.
4. Ahmad Sharbafi, M., Lucas, C., AmirGhiasvand, O., Aghazadeh, O. and Toroghi Haghighat, A.: Using Emotional Learning in Rescue Simulation Environment, Transactions on Engineering, Computing and Technology, 13, (2006) 333-337
5. Sharbafi, M.A., Amirghiasvand, O., Ansari S., Aghazadeh, O.: RoboCupRescue Simulation League Team (Iran), Team Description Paper. In Proceedings of the 11th International RoboCup Symposium. Atlanta, USA (2007)
6. Aghazadeh, O., Maziar Ahmad Sharbafi, M. A., Haghighat, A. T.: Implementing Parametric Reinforcement Learning in Robocup Rescue Simulation, RoboCup Symposium, Atalanta, USA, (2007)
7. Sugeno, M.: Industrial applications of fuzzy control, Elsevier Science Pub. Co., (1985)
8. Zadeh, L.A.: Fuzzy sets. Information and Control, Vol. 8, (1965) 338-353