Impossibles 2007 Team Description RoboCup Rescue Simulation

Jafar Habibi, Alireza Nowroozi, Ahmad Boorghany Farahany, Moslem Habibi, Soheil Hassas Yeganeh, Seyyed Hossein Mortazavi, Mohammad Salehe, Mostafa Vafadoost

Sharif University of Technology, Department of Computer Engineering

Abstract The RoboCup International competition held annually has become a stage for those interested in artificial intelligence to come together and take part in this ever growing event. The RoboCup Rescue league is one of the many existing leagues which the Impossibles team is participating in. This documentation presents a brief introduction to the Impossibles Teams efforts to find scientific solutions to the problems posed by the Rescue Simulation. We have used various CS algorithms in our code, including emotional decision making, world graph modeling and probabilistic theories.

1 Introduction

In the Rescue Simulation, robotic agents compromising Ambulances, Police and Firefighters must save civilians and stop the destruction of a city hit by an Earthquake. Firefighters control the spread of fire, Police agents clear blocked paths and the Ambulance agents rescue civilians from beneath the rubbles of buildings. The simulation must match real world limits and problems as accurately as possible, in the hope that eventually these agents can be used in real life to help in disaster areas.

The goal of the Impossibles team is further research into these areas and testing new and classical algorithms to get the results desired, also the team has in mind that Iran is one the worlds most earthquake prone countries and such major earthquakes, as the not so long ago earthquake in Bam showed, can cause massive economical and more importantly human losses. Our motivation therefore comes from the need our country has to counter such disasters and our hope to find a scientific solution for that need.

This paper is separated into two main parts, first in Technical Mechanisms we explain some common but important techniques used by all agents, then in Decision Making algorithms utilized in the decision making process are presented.

2 Technical Mechanisms

We make use of many essential mechanisms which play an important role in our decision making, but are kept separate from the decision making process.

Here we list some of the more notable ones:

2.1 Radar

Most of the information gathered by the agents is of what they sense in their surroundings, but many restrictions apply to this information gathering, for example each agent can only see a radius of 10 meters, which keeping in mind the large scale of the maps, is a pretty small section. Even this minimal information is only gathered at the start and end of a trip, so no information is gathered in between. Such restrictions mean that each agent can only act on information which is very partial and at most times old, which is not a very efficient way of making decisions. Our solution to this problem is that the information gathered by each agent is passed on to all agents, we call this the radar.

The radar has three phases, in the first phase all agents send any new information to their respected headquarters. In the second phase the headquarters send this information to each other and in the last stage the combined info is sent to all. This may seem like a simple mechanism, but some serious problems arise which we have solved.

First of all, the three phases of the radar need the decision making to start with some delay so that decisions are made on complete information. These phases need to be refined so as this delay is minimal. Second, the information that needs to be send is usually more than the limit an agent can fit into a tell command. Two solutions exist for this problem, first of all only information about events which have changed from what is kept in our world model are sent (New Info), secondly headquarters must merge all the new information they receive before sending them, so that repetitive information is not sent.

This creates many possibilities for the team, also keep in mind that this mechanism acts at the start of each new cycle automatically and is completely separate from the decision making. If the headquarters are inactive (as in the maps lacking centers) then each of the three agents types create their own individual radars, so three smaller versions of the radar system are created and used by each agent type. Also at a specific time and place representatives of each agent type meet to give their radar information to each other so all their radars are updated. We call this the rendezvous tactic.

2.2 Disaster Environment Prediction

One of the best ways to deal with the disaster which has taken place in the simulation is to predict what events will unfold in the next few cycles. We usually encounter this problem in separate parts of the decision making mechanisms. Our solution is that by collecting these predictions and placing them in the proper structure we can get a good sense of what our world model will be like in the near future and prevent repetitive tasks being performed.

By concentrating on this system we can utilize it to use prediction techniques with maximum efficiency and also find a mechanism to learn how disaster events spread in the city.

2.3 Offline Search

Keeping in mind that our final goal is saving civilians, scouting unexplored parts of the map to find trapped civilians is of the outmost importance. If we place our agents in the smallest collection of points from which the whole map is visible we can scout the map in the shortest time possible.

This is a dominating set problem and because it is a NP one, we need to use approximation solutions to finds its answer online as the game is being executed. For maps explored before (the major maps) we can find these points in advance, and use their locations during the game. So if all the important points of recon are found the whole map is visible to our agents.

3 Decision Making

[Section content continues below in subsections]

3.1 Decision Making Architecture

We are trying to use a three layered decision making system. This decision making system has a tree structure with three levels or authorities which works in normal and emergency situations. Agents are leaves of the decision tree, parent of each group of leaves is their corresponding headquarters, and root of the tree is a coordinator who has the greatest authority. These are headquarters that make general decisions and specify general duty of their agents. Now, agents of each headquarter must decide themselves and find the best way that they can perform command of their office.

In order to make it obvious, consider police forces and their headquarters. Headquarters of the police forces command each team of them to go to specific regions of the map for unblocking the blocked roads. Now each group of police agents should find a good way to those places and when arriving to the mission regions they should find a good solution to do their operations. Note that these teams can have a commander from themselves which lead team members for some jobs and control them at some operations. There are some times that different kinds of agents do not make a good teamwork, they are not supported by the others and all of the agents do not follow a suitable program. At these times we need a coordinator whose job is to make different groups work together in an organized way to achieve the goal and make the whole job effective. Consider that the coordinators decisions are strategic and their frequency is lower than headquarters.

3.2 Priority

During the simulation each of the rescue agents have tasks they must perform which are spread throughout the city. Agents must decide which of these tasks should be carried out first, this has a significant impact on the rescue process and can even be considered as one of the most vital sections we need to consider.

Keeping in mind the whole disaster situation we can use Central Processing and Distributed Processing or a mixture of both these methods to specify the importance of each task for the agents. We are trying to assign the tasks to the agents in the best possible way, and in this process we must keep in mind the importance of the task, its duration and the time taken to switch tasks. Also it is important to note that a tasks importance changes as time passes.

The algorithm used for this purpose is centralized and its results are sent to the agents. Each agent must perform the task that is assigned to it. This assignment problem is pretty complicated and can be considered as a case of the assignment algorithm in graphs. So to solve it in an acceptable time we must use approximation algorithms. Studying recent researches done in this field we saw a resemblance between this problem and the Bicriteria[1] and Steiner tree[2] problems. By modeling our problem using discrete mathematics and using papers published in these fields we found an acceptable and approximate algorithm that fulfills our needs.

3.3 Emotional Inspiration and Emergency Decision Making Approach

Recent neurological findings indicate a vital role emotions play in decision making, understanding and learning. Emotions affect most of rational thinking mechanisms[3]. Among different emotions, stress is a special one and its influence on the mental functionality and physical and mental performance is not ignorable.

Based on the various researches done on the functionality of stress, decision making in emergency situation is completely different than normal and business decision making. In normal situations, decision maker considers different options and choices, analyzes strength and weakness of each of them carefully and finally makes up his or her mind. In emergency situations, because of time pressure, he selects the best way immediately based on his experiences. In a study of decision making by fire ground commanders, it is reported that they were not making choices, considering alternatives or assessing probabilities. They saw themselves as acting and reacting on the basis of prior experience[4]. Therefore, there is a possibility to decide correctly and increase system performance by experience and its retrieval in emergency situations. Such decision making process is called naturalistic decision making (NDM) process[5] which is different than the analytical decision making process practiced by business managers[6].

In this project we have introduced an emotional structure for decision making. The new structure is constructed by adding decision making module which operates under stress, to the old system which operates in normal situation. The module operating in emergency situations will control the system when it is stressful and by using its past experience does what had been done at that time.

The proposed idea can be briefly explained as some modules which are added to the previous decision making system enabling system for decision making in emergency situations. These modules are Stress sensor module and Emergency decision making module which the latter has two sub-modules: Similar past experienced case exist and Revise the solution based on reusing the past case. Also, there can be some optional modules: Evaluate proposed solutions and Retain current case. You can see the proposed structure in figure 1.

4 Future Works

The Impossibles team intends to implement fresh ideas into its decision making after completely finishing the above mentioned parts and tuning them for maximum performance. For example some of the decision making algorithms are weight based and using reinforcement learning can have an immense effect on their results. Also in priority assignment our goal is to create and use some very unique ideas that have not been done before, including genetic-algorithms.

References

[1] Horst W.Hamacher, Stefan Ruzika, Stevanus A.Tjandra: Algorithms for timedependant bicriteria shortest path problems [2] David S. Johnson, Maria Minkoff, Steven Philips: The prize collecting Steiner tree problem: Theory and Practice [3] Damasio, A.: Descartess Error: Emotion, Reason, and the Human Brain. Rockefeller University Press, New York, United States. 1994. [4] Klein, G., Orasanu, J., Galderwood, R. and Zsambok C.: Decision Making in Actions: Models and Methods. Ablex Publishing Corp., New Jersey, United States, 1993. [5] Klein, G.: The current status of naturalistic decision making framework. Decision Making under stress: Emerging themes and applications, R. Flin, E. Salas, M. Strub and L. Martin, (Eds.), pp. 13-25, Ashgate Publishing Ltd, UNITED KINGDOM, 1997. [6] Orasanu, J.: Stress and naturalistic decision making: strengthening the weak links, In Decision making under stress, R. Flin, E. Salas, M. Strub and L. Martin, (Eds), Ashgate Publishing, United States, pp. 43-66, 1997. [7] Habibi, J., Fathi, A., Hassanpour, S., Ghodsi, M., Sadjadi, B., Vaezi, H., Valipour, M.: Impossibles Team Description, 2005.