View Original PDF

SEU-RedSun Team Description Paper for Virtual Robot Competition 2010

MENG Wei, GAO Tianyou, MAO Wei

School of Electronic, Southeast University, Nanjing 211189, China; Department of Physics, Southeast University, Nanjing 211189, China

Abstract Most work of SEU-RedSun VR Team is concentrated on SLAM and multi-robot coordination for the RoboCup-2010 competition. This paper shortly describes 3D SLAM in all-terra situation, path planning, exploration, communication and multi-robot coordination.

Introduction

The missions we have to complete in Robocup rescue competition are challenging. Therefore, a team of robots that dynamically combines individual capabilities and cooperatively solves the task seems to be the best solution. Our multi-robot system will demonstrate the progress of the skills necessary for urban search and rescue, including mapping, mobility, victim finding, communication and cooperation skills. This paper focuses on several competitive aspects of our multi-robot system regarding the challenges of the 2010 competition.

Our Goal

Despite of the strong reduction of the number of allowed robots in this year's competition, our goal will not significantly change. The aim of our team is to develop a flexible system in which all kinds of rescue robots can make decisions by themselves,and this system should be portable enough so that we can transplant it to real robots with minor extra work. The system was designed to have a hierarchical structure, with each component functioning independently. The robots all have the ability for mobility, exploring, victim finding and communication. Robots can make decisions on their own, but we also attach much importance to multi-robot coordination in order for more efficient task allocation and more orderly group movement. After all, in some special circumstances,robots may also be controlled by human operators through the Wireless Communication Server.

3D SLAM in All-Terra Situation

In the 2009 Graz competition, our team used only 2D laser range scanners to acquire environment information, and it performed quite well in the flat, structural environment. However, when the terrain is tough and rugged, which is common in disaster scene and outdoor environment, the current method behaves unsatisfactorily, for the reduction in accuracy of sensors.

This year, considering the reduction of available vehicle types to P3AT and ATRV only, we focus on the implementation of 3D SLAM algorithm based on them. Since the information obtained from single sensor or robot is inevitably seldom complete and accurate enough to build the desired global map, we consider a SLAM algorithm based on the already well developed Line Feature Extraction and Matching method together with some techniques in the field of Multi-Source Information Fusion.

In the former method, the robot get a coarse position estimation from its affiliate odemetry, then by extracting line features in the environment from the laser scanner and matching them with the corresponding features in the last cycle, the position estimation will be corrected into a higher accuracy. Since every single robot of the available types is equipped with LMS Laser Scanner, sonar and camera, we make different use of them. Sonar rings are used to give a rough assessment of the circumstance, when they detect a terra rough enough or grand obstacle, the mission is passed to the 3D Laser Scanner to get accurate stereoscopic vision by employing the algorithm in computer vision to construct 3D image from segmented 2D projection data, the camera is used when special issue such as encountering a dubious victim occurs.

Multi-Robot system is engaged in our project, thus information fusion techniques based on the DSmT theory are considered to be adopted in the local maps merging procedure, in order to provide a global grid description of the disaster space. On the other hand, as the in the all-terra situation, the quality of the extracted feature can unexpectedly decrease, we plan to take the EKF or Markov methods to help improve the reliance of the actual features, hence raise the efficiency of data association.

Path Planning and Exploration

The automatic exploration of robots is implemented by searching for gaps and then covering the gaps. Topological Map which can be extracted from the Grid Map got in SLAM will be used in path planing. As the characteristic algorithm of gap search, A* and Artificial Potential Field(APF) was used. But both A* algorithm and Artificial Potential Field algorithm have obvious shortcoming. While the combination of both can resolve the problem. So we use the the result of A* as the intermediate point to be the target of APF and then use the APF to decide the way to move.

In multi-robot system, local path planning is more than bypass obstacles. For example,chaos can happen when a crowed of robots all intend to pass a narrow door. This problem will be discussed in section Multi-robot Coordination.

Fig. 1. Gaps(Red Points) and Topological Map
Fig. 1. Gaps(Red Points) and Topological Map

Communication

As a distributed system, wireless communication is always an important part of a high performance Virtual Rescue Robot Team's architecture. Our team's communication module is constructed to transfer messages of several kinds including:

  1. Human operator's control messages
  2. Disaster space messages which are used to share the updating information among all agents
  3. Some global parameters decided by the base station
  4. Cooperation messages which is crucial in the designed multi-robot system
  5. Probable victim messages

The basic architecture of the communication system is shown in Fig. 2. Each robot sends its current information of internal state and environment to the base station, where this information are parsed, then the base station generates and addresses localization messages and certain strategy-level dictations to the robots, and also selects the information to update the global description of the disaster space. Note that every single robot also maintains a data structure recording local disaster space.

As mentioned above, we focus on the coordination inside the multi-robot system, so an extended communication architecture will be proposed for a better performance in the collective navigation practice. Our primary goal is to maintain the efficiency of exploration in a communication-limited situation. Since the infrastructure of wireless communication cannot be altered, we are trying to use some mathematical techniques in graph theory to make full use of the single robots as relay stations to maximize the exploration coverage.

Fig. 2. Communication System
Fig. 2. Communication System

Multi-robot coordination

This section covers multi-robot coordination strategies.

Task Allocation

We use an architecture called Arena to handle the task allocation problem in multi-robot exploration. First,we plan the best paths for robots and then allocate the tasks to robots that can reach them most quickly. Second ,we choose the robot-task pair that maximizes the utility function. When there are no unassinged robots or unllocated tasks,one task allocation ends.

Collision Avoidance

In the local path planning of multi-robot coordination,collision,blocking and deadlock among robots are problems which must be solved in order for efficient exploration. We think that the root cause of these conditions is the absence of rules, a robot only consider its own action,regardless of the movements of companions. Therefore, we try to introduce some traffic rules to make the robot group more orderly.

Specifically,we handle an emergency like this:

  1. Determine the priority of each robot. Greatest utility function is ensured and different robots can't have the same priority.
  2. The robot with highest priority will pass directly. Regarding other robots as ordinary obstacles,it can use the method mentioned in section Path Planning to plan path.
  3. Others will make necessary sacrifices according to the robot's relative positions to them:
    • If robot B is directly ahead of robot A in area 4, then A halves its speed;
    • If robot B is directly ahead of robot A in area 1, then A stops;
    • If the left side(area 2) of robot A exists another robot(B),then A turns right with θ angle and the speed is set to maximum;
    • If the right side(area 3) of robot A exists another robot(B),then A turns right with θ angle and the speed is set to maximum;
    • If any robot stops for more than time τ , then the robot turn right with 2θ angle and the speed is set to maximum.
  4. Repeat steps 1-3 until the emergency disappears.
Fig. 3. Relative position
Fig. 3. Relative position

Application in real robots

Our school persistently pay great attention to real robot rescue research. In Fig. 4, our rescue robot is performing a task. Most of the code running on the real robot platform is transplanted from the virtual robot program. As mentioned in section Our Goal, we consciously care for the portability of virtual robot program. Also,we pay attention to the performance of our program to meet real-time demand in real robot rescue.

Fig. 4. Our robot is performing rescue tasks
Fig. 4. Our robot is performing rescue tasks

Conclusion and Future works

In this paper, we introduced several highlights of our current team. The methods we implemented SLAM, path planning, exploration, communication and multirobot coordination are described. The results achieved by SEU-RedSun team provide hope for the future. However, there is much work to be done. Among them,information merge is the most outstanding one. Besides,after several years' development, our code becomes redundant and incomprehensible. A code refactor will be carried out so that others can easily study our code.

References

  1. JIA Meng Lei: Arena:A multi-robot coordination mechanism combining task allocation and path planning
  2. Sebastian Thrun, Wolfram Burgard, Dieter Fox: Probabilistic Robotics,MIT Press (2005)
  3. Miguel Julia, Oscar Reinoso, Arturo Gil, Monica Ballesta, Luis Paya: A hybrid solution to the multi-robot integrated exploration problem
  4. Unknown: Applications of Artificial Intelligence(2010)
  5. Martijn N. Rooker, Andreas Birk: Multi-robot exploration under the constrains of wireless networking,Control Engineering Practice 15(2007)
  6. Stefano Carpin, Andreas Birk, Viktoras Jucikas: On map merging,Robotics and Autonomous Systems 53(2005)
  7. Kai Lingemann, Andreas Nuchter, Joachim Hertzberg, Hartmut Surmann: High-speed laser localization for mobile robots,Robotics and Autonomous Systems 51(2005)
  8. Robert Graowski, Pradeep Khosla, Howie Choset: Autonomous Exploration via Regions of Interest,Proceedings of the 2003 IEEE/RSJ Intl. Conference on Intelligent Robots and Systems Las Vegas, Nevada October 2003
  9. Wang, J., Balakirsky S.: USARsim-manual3.1.1,2007