IUT Team Description Paper Virtual Robots Competition – Graz 2009

Maryam Mokhtari, Maziar Palhang

Artificial Intelligence Lab, Electrical and Computer Engineering Department, Isfahan University of Technology, Isfahan, Iran

Abstract In this paper the main methods used in design and implementation of IUT Virtual Robot Team in RoboCup Competitions 2009 are described. Some special methods are as follows: Using a Graph-based topological map accompanied with an Uncertainty Grid Map used in exploration, path-planning and robots cooperation; a SLAM method for mapping and localization based on Kalman Filter; a Tree-based Rendezvous algorithm used to cover distance limitation; a Mean-Shift algorithm used in image segmentation and a backpropagation neural network to learn skin colors used for victim detection.

Introduction

Robotics as one of the important and attractive areas in Artificial Intelligence, has received lots of attentions for many years. Especially in recent decades, increasingly more efforts have been put into bringing robots to real world applications. In RoboCup Rescue League a disaster scene is designed and some Rescue robots should navigate environment and find victims. After some years of performing RoboCup Rescue Competitions, first Virtual Robot League has started in 2006. Not only larger and more diverse environments can be designed in simulation, but also teams are free from hardware complications. This is the first time we are going to participate in Virtual Robot League.

Specific robots are commonly P2AT, P2DX, zerg and AirRobot. Our platform is Windows Vista and our program is implemented in Visual Studio 2008 with C#.

This paper has been structured as follows: In section 2, Localization & Mapping is described. Section 3 illustrates how the victims are detected. In addition of VictSensor an Omnidirectional camera is used and a Neural Network is trained to detect skin colors. Section 4 describes Communications and how to cover Distance Limitation problem by a Tree-Based Rendezvous Algorithm. In section 5 Navigation, Exploration and Path-Planning are described. A Graph-Based topological map is used accompanied with an Uncertainty Grid Map, easy to be shared and used among robots, and in Exploration and Path-Planning. Section 6 presents innovations in approaches and finally section 7 is a conclusion of this paper.

2 Localization and Mapping

For localization and mapping, SLAM (Simultaneous Localization and Mapping) is used based on Kalman Filtering. Map Merging and Loop Closing are main challenges in SLAM [1].

2.1 Mapping

Two maps are generated: Map1 is an Occupancy-Grid map with exact metric information in GeoTiff format [2]. But also another topological Graph-based map is generated in parallel and is used directly in path-planning and exploration. In this map named Map2, nodes show important places like crossroads or open doors. It can be detected by gaps among sensor outputs [3]. This map is used to be shared among robots for planning their navigation. The advantage of this map is its compactness and simplicity for being shared and used by robots [4]. Another advantage is that saving 3D aspects of important landmarks is easy, in contrary with Occupancy Grid Map when it is generated in a 2D plane.

2.2 Localization

Scan-Matching is used for localization [5]. This method is more accurate than odometry [6]. Odometry error is two high, but it is not ignored completely in our design. Also to save rotations, INS sensor is used [7]. Scan-Matching is more similar to what a human does, when he tries to memorize the path he passed to find his location. So this method is comparatively more natural.

3 Victim Detection

In addition of VictSensor, an omnidirectional camera is used for victim detection. The image obtained from robots' cameras cannot be used directly. It should be converted to a Bird-Eye view [8].

To do this conversion a reverse action should be done: A projection plane for flat image is considered. A formula for converting a flat image to an omnidirectional image is used from [8]. For every pixel in the flat image the function computes coordinates of the corresponding location in the omnidirectional image using the formula; therefore every pixel in the flat image has a correspondent pixel from omnidirectional image. Maybe pixels obtained from omnidirectional image become floating point numbers. The integer pixels values are computed using bilinear interpolation [9]. This reversing approach guaranties for every pixel of flat image to have a single value.

To find victims "Skin Color" detection in the pictures is used. Skin color may be different in various victims, lighting conditions, etc. An RGB color space is not a good one, because illumination could not be detected and eliminated in RGB color space. An HSV color space could be a good one. In this space the chromaticity values depend on the dominant wavelength and saturation, independent of the luminance [10]. But at last HSL color space was chosen in our design; it is similar to HSV, but the intuitive notion of "saturation" and "lightness" as two independent parameters could be better reflected in HSL color space [11]. This is shown in Fig. 1.

Detection is not used on original images, but on a segmented one. Segmentation could eliminate noisy parts from result. Mean-Shift algorithm is used for image segmentation [12]. Fig. 3. shows victim detection using skin color detection on a sample image from DM-USAR-yellow-250 arena. In this sample a kind of color confliction is shown, when body skin color of victim is very similar to ground color and human eyes also cannot completely identify the difference from color alone. But it could be distinguished in our application using HSL color space. Final result after using segmentation algorithm is shown in Fig. 2. (d), when victim body is properly detected.

4 Communications

To cover Distance Limitation problem a Rendezvous algorithm is used [13]. Robots should be able to manage their time to be on meeting points on exact time and share their information among each other. One of the problems of finding good places for meeting points is because of unknown environment and location of robots [14]. This problem is solved by SLAM.

When constant meeting points are used, a major problem occurs: If meetings are appointed in long time partitions, an agent suffers from lacking an updated shared map until it meets another agent. If meetings are appointed in short time partitions, robot times are wasted for going to and returning from meeting points instead of exploring the environment. Hence a suitable clock time is defined for meetings according to robots' speeds, extent of environment, etc.

Another effort is done to cover problem of wasting robots' time on coming back to meeting points: Instead of a constant meeting point, a "Tree-based Rendezvous" is devised.

5 Navigation & Exploration

Many efforts have been done in the field of multi-robot exploration. Minimizing the overall exploration time is the main goal in these approaches. The key problem to be solved in the context of multiple robots is to choose appropriate target points for the individual robots so that they simultaneously explore different regions of the environment [15], [16].

To have a successful exploration, we have designed an "Uncertainty Grid Map". This map is named as Map3. Uncertainty Grid Map is accompanied with Map2 (our graphbased map).

At the first time when a robot is spawned in the ground, the grid containing the robot takes a zero number and its direct neighbors take number 1 and direct neighbors to these grids takes number 2 and go on. It means in this grid map a farther grid location from robot has greater number and greater score to be explored, because it has less accurate information. Using these discrete values of a grid map instead of continues values are efficient because of having smaller computation space and less complexity. This map is shared among all robots.

Targets for every robot should be defined. An efficient "Non-Conflicting Dynamic Target Definition" algorithm is prepared using our Uncertainty Grid Map accompanied with Graph-based Map. The nearest robot to each target should be found with D* algorithm. D* is a dynamic version of A* specialized for mobile robots and path-planning [17].

6 Innovations

Many of the approaches mentioned above are IUT team innovations. Like: Generating and Updating an Uncertainty Grid Map, Non-Conflicting Dynamic Target Definition using Uncertainty Grid Map accompanied with Graph-based Map and Tree-based Rendezvous algorithm.

7 Conclusion

In this paper, the main decisions of IUT team were described. Some of the important decisions are about SLAM based on Kalman filtering, designing a suitable communication method like Tree-based Rendezvous algorithm to overcome distance limitation, use camera suits in victim detection, segmenting image with mean-shift algorithm; using a back-propagation neural network to learn skin color and finally using a graph-based topological map accompanied with an Uncertainty Grid Map and a Non-Conflicting Dynamic Target Definition to have a good navigation and explore more important places in the environment and a D* algorithm for path-planning.

References

1. Thrun S.,: Robotic mapping, A survey. In G. Lakemeyer and B. Nebel, editors, Exploring Artificial Intelligence in the New Millenium. Morgan Kaufmann (2002).
2. Visser A., Carpin S., Balakirsky S. and Scrapper C., : RoboCup Rescue Simulation League - Virtual Robots competition - Rules document, (2009), http://www.robocuprescue.org/wiki/images/Rules2009v2.pdf.
3. Shen H., Qian C. and Li Xu X.,: Design decisions of the SEU-RedSun Rescue 2008 Team on the Challenges of the Virtual Robot competition, In Proceedings of the 12th RoboCup Symposium (2008).
4. Redleaf Kedrowski, P.: Development and Implementation of a Self-Building Global Map for Autonomous Navigation*, MSC Thesis, Virginia Polytechnic Institute and State University (2001).
5. Slamet, B., Pfingsthorn, M.: ManifoldSLAM: a Multi-Agent Simultaneous Localization and Mapping System for the RoboCup Rescue Virtual Robots Competition. Master's thesis, Universiteit van Amsterdam (2006).
6. Pfingsthorn, M., Slamet, B., Visser, A.: A Scalable Hybrid Multi-Robot SLAM method for Highly Detailed Maps. In: Proceedings of the 11th RoboCup International Symposium. (2007).
7. Wang, J., Balakirsky, S.: USARsim-manual3.1.1. (2007)
8. Roebert S., Creating a bird-eye view map using an omnidirectional. camera, Bachelor's thesis, Universiteit van Amsterdam (2008).
9. Wikipedia, The free encyclopedia, http://en.wikipedia.org/wiki/Bilinear_interpolation
10. Jain R., Kasturi R., Schunck B., Machine Vision, McGraw Hill, 1995.
11. Wikipedia, The free encyclopedia, http://en.wikipedia.org/wiki/HSL_and_HSV
12. Comanicui D. and Meer P.,: Mean shift: a robust approach toward feature space analysis, IEEE Trans. Pattern Anal. Mach. Intell. 24 (2002).
13. Roy, N., Dudek, G.: Collaborative robot exploration and rendezvous: Algorithms, performance bounds and observations. Journal of Autonomous Robots 11(2) (2001) 117 – 136
14. Lin J. and Morse A. S., The Multi-Agent Rendezvous Problem-The Asynchronous Case, Proceeding of the 43rd IEEE Conference on Decision and Control (2004).
15. Burgard W., Moors M., Stachniss C., and Schneider F., Coordinated multi-robot exploration. IEEE Transactions on Robotics. v21 i3. (2005) pp. 376-378.
16. Burgard W., Moors M., Fox D., Simmons R. and Thrun S.,: Collaborative multi-robot exploration, In Proceedings of IEEE International Conference on Robotics and Automation (ICRA'2000) vol. 1 (2000), pp. 476–481.
17. Likhachev M., Ferguson D., Gordon G., Stentz A., Thrun S.,: Anytime dynamic A*: An anytime, replanning algorithm, In Proceeding of the International Conference on Automated Planning and Scheduling, ICAPS, (2005).