RoboCup 2011 – Rescue Simulation League Team Description MRL (Iran)
Roohollah Mirsharifi, Pooya Deldar Gohardani, Peyman Ardestani, Mostafa Shabani, Siavash Mehrabi
Qazvin Islamic Azad University, Department of Computer Engineering and Information Technology, Mechatronics Research Lab Qazvin, Iran
Abstract This paper describes the main features of the MRL rescue simulation team that is going to participate in RoboCup 2011 competitions. Our goal is enriching previous implementation of agents which has been used in RoboCup2010 based on new kernel. Communication model is now improved and all of the bandwidth available is utilized. Agents' movements are now more reliable and they can move using a Hard-Walking method through partially blocked roads. Moreover a new market-based ambulance agent has been developed. Police agents are now using fuzzy decision-making method. Fire-brigades use Zones for its extinguishing strategy.
Introduction
Since RoboCup 2010, we have been working on the weaknesses of the agent code to get more acquainted with the new simulation kernel. The team faces some major problems during 2010 competitions. Inefficient algorithms stopped agents from working properly. Furthermore we could not adapt our new decision making algorithms with the new kernel. Defective communication and ignoring the noise on the channels was another short coming. All issues are now managed in an issue tracking system. Most of the major issues have been resolved including low performance routing algorithm, noise on channels is now taken into account and all available bandwidth is utilized, low performance TLV-XML model for messaging is replaced with a high performance byte-mapping model, Market-based algorithms for ambulance decision-making and for police task assignment is implemented, fuzzy decision-making algorithm is used for police agents to evaluate paths, fire-brigade agents are using new model for fire-extinguishing using Zones. With all these improvements and the road-map to RoboCup 2011 competitions, we expect to have a very high quality agent program in the near future.
Review of the RoboCup Rescue Simulation Platform
MRL team is now more familiar with the new simulation kernel, last year we tried to contribute to this new kernel in a various ways like bug reporting, map correction and etc. And the experience of RoboCup 2010 and collaboration with other teams improved our knowledge.
Agents
Agents are introduced in the following parts.
Fire-brigade Agent
The most important changes in new simulation kernel is that agents are not able to sense fire from distance and they usually need to get into buildings in order to sense the fire (due to line of sight feature in new kernel), on the other hand agents need accurate information about their surroundings to make proper decisions. To deal with these new changes, we had to modify fire-brigade agents' decision making algorithms to keep track of their environment. For instance one agent always stays in the target burning building to keep other agents informed about the building attributes.
MRL fire-brigade agents always work based on a fire site in order to do the firefighting. But this year we have removed the fire site data structure from our code and the decisions are now made based on fire zone which we used it in previous year beside fire site [1]. In previous year fire sites where selected in the first step then a fire zone included in the fire site was chosen. The problem was that some zones are important individually but not usually in an important fire site.
The prioritization of each fire zone is done by a linear estimation method. This priority depends on some parameters such as total temperature, total fieriness, total area, distance to center and number of civilians around this zone. Fire zones are assigned to a group of fire-brigades; number of fire-brigades needed for each zone is estimated by total area and total temperature. Next step is to choose an appropriate building to extinguish which is done by distance factor. After evaluation of the fire zones, agents choose to extinguish it or they just try to control fire from a direction to minimize damage to the city.
Ambulance Agent
In general, the primary aim of ambulance teams is to rescue civilians. To do so, there are three steps:
First, civilians must be discovered. The second step is to select a set of civilians to rescue. For this selection, many factors are considered: civilians with significant Damage, Buriedness, health point, distance to ambulance teams and distance to the nearest refuge). At the third step by considering the previous properties, proper ambulance teams should be assigned to proper civilians to minimize overall score loss.
To implement the above mentioned steps, with inspiration of the idea of a marketplace, we designed and developed a new solution for this problem based on the below taxonomy of task allocation in multi agent systems which is presented by Gerkey and Mataric [2]. According to this taxonomy, our problem considered as MT-MR-TA so that ambulance teams are able to do some acts at once like rescuing, messaging, discovering environment and so on (MT) and to rescue a civilian there is a need to more than one ambulance team agent (MR) and each time new civilians as new tasks may be discovered (TA). By considering the problem as MT-MR-TA, we decided to use the idea of a marketplace, in which there are sellers, buyers, and goods. We mapped sellers and buyers to ambulance teams and goods to civilians. Like other approaches of using the idea of a marketplace in which the seller put its goods to sell and sells it to the buyer with the best bid, in our approach, in an auction time which is known to all agents, first each agent compute Civilian Amount of Profitability (CAOP) for each victim which is as follows:
$$CAOP = \frac{Damage \times 10000}{HelthPoint \times Buriedness \times TTA}$$
Where TTA (Time to Arrive), is the estimation of the arrival time to the victim. Then sends m number of most valuable pairs of victim-CAOP value as bids to the auctioneer who is an ambulance team agent (AT) or ambulance center and we consider it as leader; after that, unlike other common approaches of market-based strategies in which only one participant can win the auction, in our approach some agents together may won the auction. Here the leader compute the optimal number of ATs to rescue the victim and select the winners of that victim based on their bids and informs the winners of each victim to all. For better understanding you can see figure 2.
To compare the market-based system with other types of task allocation, we implemented Random and Greedy strategies then we compared Market-based system with these strategies and the strategies used by RoboAKUT2010 and RiOne2010 and our previous strategy which used in 2010 rob cup. Parameters for this comparing are score, total saved civilians in refuges and total saved HP of those civilians. This comparing applied in Berlin map with 28 Ambulance Teams, 157 civilians and the results are the average of 5 runs for each strategy.
Police Force Agent
Since the beginning, the most important aspect of our strategy has been dividing the map into several smaller regions with equal size called Partitions. After linear estimation of considered parameters, we evaluate all partition's value and the partition with most value is assigned to an agent to clean thoroughly. Although it was perfect in some cases, after lots of research, now there is no doubt for us that the linear estimation for selecting Partitions and clearing blockades of paths is not the most effective method in all aspects. One of the obvious reasons is that when we have an immediate value change in a parameter at a time, it may lead agents to the wrong decision.
For example suppose that the Blocked Agent is one of the parameter to select a Partition and the Partition with highest number of Blocked Agents has a higher priority in linear estimation. So it may make PF agents to ignore their current partitions and change their positions to another partition with sudden increase in value because of a Fire Brigade or an Ambulance Team Agent which has moved to that partition and got blocked by a blockade. Thus it is probable that they would have lots of futile move between different partitions which is exactly the toughest problem for Police Force agents [1].
Therefore we decided to use another strategy to solve the problems. After implementing different strategies for PF agents in past 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. In addition to the quality, conceptual aspects and suitable experience of using fuzzy decision making strategy for Fire Brigade Agents in previous years and for Police Force agents in Communication-less mode in last year competition, encouraged us to choose this method as a dynamic and Human like decision making to overcome all tough problems of linear estimation which didn't work properly. Among many different methods of Fuzzy logic, we have used Takagi-Sugeno fuzzy inference [9] for this problem. Figure 3 illustrates the input fuzzy membership functions for Sugeno inference system. We define some fuzzy rules based on important parameters influencing Police Force work efficiency as number of Blocked Agents, Blocked Refuges and Fire Sites. As we expected, all test results show the performance improvement of this method over the old one [3, 4].
After using market-based strategy in Ambulance Team agents, we have found it useful for police forces too. Fuzzy strategy task allocation in police force agents had some faults because agents still don't consider other co-workers task, which may lead to wrong decisions. To overcome this problem we used a modified version of distributed auctioning. At the first step, our police force agents select ɱ number of their most valuable tasks using fuzzy strategy without considering others work, afterwards they participate in an auction periodically and send ɱ tasks as their bid. Each agent who is participated in the auction will receive task-agent pairs from bids by a same method for all agents taking following steps, the agent with the lowest bade cost for each task will be the winner and then if an agent won more than one task it will accept the one with highest value and the agent who did not win any task will select a task using fuzzy strategy (Figure 4). After implementation of this idea, we have reached our expected improvement of the proposed approach.
World modeling
(This section contains no standalone text before subsections)
Hard-Walking
The traffic simulator can't always direct the agent through different areas, especially when agents are stocked in areas with blockades. Whenever agents detect they are stocked or traffic simulator can't move them with entity-id hard-walking mode is enabled. A grid is created over areas which are involved in hard-walking and then agents try to find a path through grid's cells using A* method and move using (x, y).
By hard-walking method agent won't usually get stock and they have a smooth move. The grids are also used to evaluate how much of a blockade need to repair to open a road for traffics moves.
Agent coordination and communication
Clearly one of the main problems in RoboCup 2010 competition was our communication model. High processing overhead caused performance issues because of lots of XML parsing activities, so we changed our messaging structure. On the other hand because of dropping and failures (Caused by channel noise), we have to ensure delivery of important messages to target agents. So we added a priority property to messages to have different importance levels.
In previous approach, TLV method [5] had been used for message structure which is really time consuming and has too much processing overhead. After reviewing other teams' descriptions, we decided to use the Roboakut approach [6] to address this issue. One of the most prominent benefits of their approach was its simplicity.
Another improvement is choosing best channels based on bandwidth and type of each agent; message importance and number of repeats is different for each agent and it depends on importance of message for agent. First we sort all channels based on their real-bandwidth and then we assign the appropriate channels to the agents. The real bandwidth is calculated by estimating noise on each channel, a channel-check process is done in beginning of simulation and the noise is estimated. Centers are used as communication centers for prioritization of messages and repeat them based on their priority.
Acknowledgements
We are having our great thanks to Dr. Moosakhani the president of Qazvin Islamic Azad University for his supports.
References
- Mirsharifi, R., Eghbali, M., Deldar Gohardani, P., Mehrabi, S., Vosough, Z.: RoboCupRescue - Simulation League Team (Iran), Team Description Paper, International RoboCup Singapore (2010).
- Gerkey, B. and M. Mataric.: A formal analysis and taxonomy of task allocation I multi-robot systems. International Journal of Robotic Research, vol. 23, (2004) 939–954
- Wolkenhauer, O.: Data Engineering: Fuzzy Mathematics in Systems Theory and Data Analysis. John Wiley & Sons, Inc. ISBNs: 0-471-41656-8 (Hardback); 0-471-22434-0 (2001)
- Tanaka, K., Hua, O.W.: Fuzzy Control Systems Design and Analysis: A Linear Matrix In quality Approach. John Wiley & Sons, Inc. ISBNs: 0-471-32324-1 (Hardback); 0-471- 22459-6 (2001)
- TLV, http://en.wikipedia.org/wiki/Type-length-value. (2011)
- Levent Akın, H., Yılmaz, O., Murat Sevim, M.: RoboCupRescue Simulation League Team (Turkey), Team Description Paper, International RoboCup Singapore (2010).
- 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)
- Theraulaz G., Bonabeau E., Karsai I. and Small P.: Defenition of Stigmergy. http://www.Stigmergicsystems.com/stig_v1/stigrefs/article1.html?540817. (2003)
- Sugeno, M., Industrial applications of fuzzy control, Elsevier Science Pub. Co., (1985)
- Sharbafi, M., Mirsharifi, R., Eghbali, M., P., Mehrabi, S., Vosough, Z.: RoboCupRescue Simulation League Team (Iran), Team Description Paper, International RoboCup Austria (2009).