RoboCup Rescue 2009 Virtual Robot Team Description Paper BamRescue (Iran)

Nader Nikbakht Nasrabadi, Arash Givchi, Kamran Zamanifar

Artificial Intelligence Research Laboratory, Department of Computer Engineering, School of Engineering, University of Isfahan, Isfahan, Iran; Department of Biological Sciences, Faculty of Sciences, University of Isfahan, Isfahan, Iran

http://eng.ui.ac.ir/rescue

Abstract The BamRescue Virtual Robot team is described in this paper. BamRescue intends to develop an intelligent team of heterogeneous robots to manage the elementary tasks of Urban Search and Rescue. Map generation and victim localization of our team as the most important factors of this challenge are based on a real time state graph. Path finding based on this model can lead us to have a subtle navigation while control of the robot will be fostered by this spatial localization idea. Major parts of challenges of the team are focused on autonomy and robotic performance. Ant colony algorithms used for path planning and optimization are finally described in this paper.

Introduction

Disaster rescue as one of the most serious social issues, involve very large numbers of heterogeneous agents in the hostile environment. The intention of the RoboCup Rescue project is to uphold research in this socially significant domain at various levels involving multi-agent team work coordination, physical robotic agents for search and rescue, information infrastructures, personal digital assistants, a standard simulator and decision support systems, evaluation benchmarks for rescue strategies and robotic systems that are all integrated into comprehensive systems of the future.

This problem introduces researchers advanced and interdisciplinary research themes. For disaster researchers, RoboCup Rescue works as a standard basis in order to develop practical comprehensive simulators adding necessary disaster modules. A diverse spectrum of possibilities of this technology will contribute to the creation of the safer social system in the future.

Urban Search And Rescue as a challenging area of robotics research generally requires a heterogeneous team of robots, that combine individual skills, and cooperate to solve the rescue task. The Virtual Robot competition is a test bed for evaluating necessary skills for urban search and rescue, providing several tests like mobility, mapping, victim finding, cooperation and communication.

In this paper mechanisms of controlling and navigation of semi-autonomous robots are introduced. These methods are based on a series of logical algorithms which can lead rescuers to have an accurate and easy-to-understand model of disaster area for further operations. Team coordination, map generation and victim localization as the most important areas in our study are highlighted in this description paper. Path finding based on a real time state graph can lead to have a robust navigation and control of the robot. Victim finding will be faster using this spatial localization idea.

Team Members and Their Contributions

• Nader Nikbakht Communication/Mobility/Victim Identification

• Arash Givchi Coordination/Map Generation

• Kamran Zamanifar Advisor

Control Method and Human-Robot Interface

Each area ―i.e. buildings and other rescue arenas― according to structure and foundation reflects different models of destruction after a natural disaster. BamRescue was based on partial autonomy in which robots could be controlled by an operator if the robot is out of the right way and operator has gained enough information to take control of the robot.

Navigation and control of the robotic team in autonomous mode is based on real time state graph in which its nodes will be created while agents traverse.

For this purpose there has to be a predefined default step length for first moves from base point; after that, the robot can modify or improve the step length based on some factors in the disaster area such as:

• − Type of the arena in which robots make decisions (e.g. indoor or outdoor),
• − Density and congestion of debris,
• − Existence of victims in the arena,
• − Time limit and other real time features.

Base point of the robot is set to graph node number one. Finding the next node is based on some simple rules:

• − If the robot has recognized a victim or any moving object near the node which is now in, next node will be defined and placed near that victim― this is done for saving positions and getting information about the victim.
• − If the robot has not recognized any victim or moving object, it has to go to a node to which there is low congestion of nodes (the robot saves the track it traversed).
• − If the robot is in unidentified situation it can handle a random move based on average size of distance limitations.

In order to cope with preceding rules agents have to save some information:

• 1. It saves some pervious nodes for backtracking and decision makings on node congestions.
• 2. It saves height of the graph from the base point for finding and presenting path to objects it has found.
• 3. If it reaches a visited node; the robot updates the height of the graph up to this node using Floyd algorithm to present the shortest path in the map.

Main plan for victim finding is based on the idea that usually in disaster environments of urban localities victims are located near each and sometimes they join each other to improve chance of survival.

In order to benefit from this assumption, we use spatial locality idea for finding victims. So in our state graph if the robot finds one or some victims in a part of arena then it tries to mark and make its next node in an appropriate range relative to the victims and add this feature to those points for decision making.

Due to our pervious research on autonomous decision making in different arenas, and proposition of real- time state graph, that leaded to If- Then rules which utilized the motion of robots, this year we bring some levels of intelligence to robots cooperating together as a multi-agent system. As a consequence we have to prepare facilities for our agents to communicate with each other in proper and sufficient manner. Beside this idea, one of the ideas we proposed last year as a key factor to victim finding after natural disasters, was using of the "spatial locality of victims", and we have got this idea because of previously gathered statistics and information in real disaster situations, and logical reasons in improving the survival chance gathering in groups; so it is somehow logical to search a defined radius of an area which there are some victims in there.

For extending mentioned ideas we model our world as a layered one, which covers a virtual layer for communication facilities among agents. Hereby, we are going to propose our ant- based path planning which is based on the amount of pheromones which are deposited on virtual roads. The amount of pheromone on paths depends on:

• If there is any victim attached to the nodes of graph.
• How many times the road has been traversed without any block.
• How many debris are in the vicinity of a road.
• Distance and other physical identifications.

Each agent is responsible for updating its current node according to the above conditions where these modifications will be informed locally to others. Pheromone evaporation is one method for modeling the activity of variable environment. The pheromone evaporation is calculated according to the following formula:

$$\tau(r,s) = (1-\alpha)\tau(r,s) + \sum_{k=1}^{m} \Delta \tau_k(r,s)$$

Where is the amount of pheromone in the road between nodes r, s.

is the evaporation rate and is the amount of pheromone newly deposited pheromone from other k agents.

Therefore, communication can be established among agents, not only for reporting victim density in an area, but also for other elements in area which could have impacts on path-planning of each agent. For this purpose we calculate the amount of pheromone to be deposited by each agent by using the weight average of the dependencies which mentioned above. Finding shortest path will become crucial when it comes to finding an out way due to maintenance of each robot or sending robot to an especial point in the arena because of no clear reasons such as guessing whether there are any victims in some regions of arena or not. Our virtual layer which is covered by ant's pheromones will be also feasible for such theses important decision makings by calculations on pheromones which already exist on the layer.

Map generation/printing

As we described in the previous section, when the robot positioned in a new node of the state graph, it scans its surrounding ―360 degrees― to examine the local environment by radiation of sonar range sensor. By each radiation and hit with external objects, the robot will identify the hit point position and marks it with exact (x, y, z) on the map as a relative position of mentioned point. By connecting these different points in the map we can estimate the primitive shape of objects in the arena― figure 1.

The problem of this method is in distinguishing of different objects such as ramp surfaces and vertical surfaces (walls). To solve this problem the robot will radiate its range sensor with same angle and different height (through z axis) to some points of the surface. The number of radiations has to be set by different local information such as Maximum height of external objects that the robot can recognize at its local position (node).

Now it is time to compare each two point's coordination and infer:

• 1. If the hit points have the same x and y values, and the z values of the points are different, the robot will mark them as a vertical object such as wall in the map.
• 2. If coordination is completely different in x, y and z axes the robot marks it as a ramp surface such as a ramp.

For designing the map and depicting the sensed objects in it, we use color strength, traveling from bright to dark (of the same color). In this method for clarification of the map, vertical surfaces points will become darker when the robot becomes nearer to them and ramp surfaces points will become brighter. Therefore by this method we can use color strength as an additional dimension of the map.

Communications

According to the competition rules all communications will use the Wireless Communication Server. Because of the possible delays of the Server and speed limits of data transfer, there might be a significant impact on the robot control performance. Problems associated with wireless communications are solved. BamRescue tries to make the majority of decisions autonomously on the robots to reduce the communication traffic and in order to have a much more reliable simulation.

Robot Locomotion

At the moment the system of locomotion of the main robots of our team is wheeled and tracked system. Talon and P2AT are obviously different in their locomotion capabilities and this lets us have much more flexibility in confrontation of different environmental difficulties. We have started a set of initial tests to check the mobility performance of Talon in ramps, slabs, debris and uneven floors and generally places that need maximal demand on locomotion.

References

1. R. Murphy, J. Casper, M. Micire and J. Hyams, "Mixed-initiative Control of Multiple Heterogeneous Robots for USAR", Technical Report CRASAR-TR2000-11, Center for Robot Assisted Search & Rescue, University of South Florida, 2000.
2. Arnoud Visser, Bayu Slamet, Tijn Schmits, Luis A. Gonz´alez Jaime, and Aksel Ethembabaoglu, "Design decisions of the UvA Rescue 2007 Team on the Challenges of the Virtual Robot competition", Universiteit van Amsterdam (UvA), Intelligent Systems Laboratorium Amsterdam, Amsterdam, Netherlands, 2007.
3. Arnoud Visser, Stefano Carpin and Stephen Balakirsky, "RoboCup Rescue Simulation League Virtual Robots competition, Rules document", First public draft: January 22, 2008.
4. Jijun Wang, Stephen Balakirsky, "USARSim A Game-based Simulation of the NIST Reference Arenas- USARSim Manual 3.1.1", 2007.
5. RoboCup Rescue official website: http://www.robocuprescue.org/.
6. E. Bonabeau, G. Théraulaz, "Swarm smarts", Scientific American, pp. 72-79, 2000.
7. E. Bonabeau, M. Dorigo, and G. Théraulaz, "Swarm intelligence: from natural to artificial systems", Oxford University Press, 1999.