RoboCup 2009 -Rescue Simulation League Virtual Robot Team Description CSU YunLu (China)

Ya Liu, Fu Jiang, Xiaoyong Zhang, Jun Peng, MinWu

Central South University, School of Information Science and Engineering, 22 South Shaoshan Road, Tianxin District, Changsha, Hunan 410075, China

http://robocup.csu.edu.cn/en/index.htm

Abstract The CSU Yunlu team aims at the development of an intelligent team of heterogeneous robots that explore an unknown environment quickly and completely. A common system structure is designed to guide robots' behavior to make each robot know how to response clearly and regularly. Under this structure, Fuzzy logic approach is proposed to conquer the challenges in mapping and localization so that the robots can map and locate the environment accurately. And some new approaches, such as hybrid path planning algorithm, fuzzy reinforcement Q-learning, etc, are also used in this system. This paper shortly describes the main features and implementation of the CSU Yunlu virtual robots simulation.

Introduction

The Virtual Robot competition aims to foster research in cooperative multirobot systems engaged in urban search and rescue missions. Robots and sensors used in the competition are closed to the platform and devices currently used in physical robots. These features attract us deeply and we built the CSU Yunlu team for this competition.

According to the challenges the competition brings in some problems, such as system structure designing and team strategies. We aim to develop the CSU Yunlu team of heterogeneous robots to explore as quickly and completely as they can, simultaneity, map the environment accurately.

Our team consists of two types of robots: the P2DX and the Talon. Both P2DX and Talon are equipped with frontal range scanners and sonar, INUs, RFID and victim sensors, but they are different in mobility capabilities, which makes the team adapt to environmental features well.

To guide robots' behavior, we designed a common system structure for the heterogeneous robots, in which different functions are defined. Under this structure, was proposed Fuzzy logic and Bayesian approach to locate and map the explored environment with high accuracy. Furthermore, coordination and cooperation among robots were also considered, to enhance the quality of exploration.

System Structure

Both the two types of robots adopt the same structure shown in fig.1. The function of each module is described as follows.

Environment: The Environment module represents the 3D physical information of the disaster environment, which includes plain furnishings in a building, obstacles, and victims etc.

Perception: For the robots, the Perception module is used for the robots to sense the outside environment by various sensors, such as laser range scanner, INU, odometry sensor, sonar and Laser Scanner readings, RFID, and so on.

Mapping Localization: By processing the data of image or distance got from the Perception module, the Mapping Localization model is used to build up an accurate metric map, in which the global location of the explored surrounding is determined, and the surrounding information explored respectively by each robot are integrated.

Info-Storage: The Info-Storage stores the latest explored environment information which comes from the Mapping Localization module, including the location of the victims, the blocked roads, house structure, etc. The Info-Storage can be used by all robots to determine their next action. Also, the information it stores can be increased and updated.

Victim Detection/Obstacle Detection: These two modules are used to recognize and locate the victims or the obstacles. By the sensors, combining with the useful information having been acquired, robots can easily detect the victims and the obstacles.

Navigation and Exploration: According to the recognized victims or obstacles, integrating with other useful information, the robots use the Navigation and Exploration module to make decision for their consequent actions. If the robots find out a victim, to obtain more accurate image and some other data, they will get near to the victim according to the Move towards Victim sub module. If there have obstacles nearby, the Avoid Obstacle sub module is chosen. Otherwise, the robot will continue exploring the un-known environment with the guidance of the Exploration sub module is used to make.

Coordination: In order to successfully explore and navigate in the area and to avoid duplicate efforts in searching the same areas, robots need to coordinate the team robots. And the coordination and cooperation are the aspects we most concerned about.

According to the structure introduced above, each robot can be aware of what to do in the unknown environment for accurately and effectively exploration. Due to the functional framework defined in the system structure, it can be easily reused by other types of virtual robots and the physical robots in the real world with little modification in the functions realization.

Victim Detection

To identify the victims, the reports from the victim sensors are verified. Generally, the robots change their body direction pointing against their targets and move towards the victims[1]. If the readings of the sonar or laser range scanners are lower than a safety threshold, it means there are obstacles nearby, so the robots need to avoid obstacles. There are three conditions: when the obstacles are located at one side of the robots, the robots turn to opposite direction; when the obstacles are at their both sides, they move ahead only if the alleyway is safe in front; If there are obstacles in front of them, the robots need withdraw to the place without obstacles and turn backwards, then chose other directions to move. Otherwise, when the readings are higher than the safety threshold, the robots can move towards the target smoothly.

We also adopted emotional learning to solve this problem; the sensor is "trained" by being placed in front of moving "victims" and false positive. Then the sensor is designed with some new knowledge base offline. Therefore, the sensor can obtain more effective information in the process of moving of robot.

Localization and Mapping

Localization can be sub-divided into the problems of global position estimation and local position tracking. Fuzzy logic[2] is adopted to affect these two problems.

We use a grid based approach in which a robot's location is represented by its belief or confidence that it stands at a certain point in this grid. At each of these grid points, the robot specifies a value between zero and one which represents its confidence that it is located on that grid point.

Various of sensor measurements carried out by the robot may provide it with its confidence in its location at each grid point. This confidence function would be constructed a-priori based on the known accuracy and precision of the sensor. The robot will typically have multiple sensors on it which will give it their independent confidence functions of its location. The robot can then combine all of these with its own confidence in its location to obtain its new confidence in its location. This combination will be done using Fuzzy Logic and heuristic rules [3] instead of strict probabilistic rules.

In the problem of global position estimation, the robot has been set a priori information about the accuracy and precision of these sensors. i.e. if the robot gets a reading from the sensor, it has the means to construct a map of the confidence, the sensor reading provides, in the robot's location at every grid point. As an example consider the AmigoBot which is being used in our laboratory. Given a map of the environment, the robot can use the sonar sensors mounted on it to measure the distance from various walls. Having made a measurement, this knowledge about its accuracy can be used to convert it into a confidence function for the robot position. In addition the robot may have some a priori confidence in its position on the map. This confidence may be due to the robot having kept track of its past movements. In the case that it knows the environment map but has no idea about its own position in the environment, it may set the confidence level at every grid point to a single low value (say 0.1) to represent its ignorance of its own position. The node then combines these two confidence functions using heuristic Fuzzy rules. To do this, the confidence level at each grid point is fuzzified into three categories, high, medium and low.

In the local position tracking, the robot's motion control devices should provide the robot with information as to how far it has traveled in which direction. The accuracy of this information is again a function of the hardware used and should be known a priori. For example, a specific motion controller, when commanded to travel a feet in the x-direction will be able to achieve the same to an accuracy of a feet and 0 degrees. This capacity of the controller is known a priori.

The ability for a single robot to map any significant area is difficult, especially for robots at this scale. However, a group of robots can be equipped with similar sensors to cover more area in less time than a single robot. During operation, each robot collects information locally about its surroundings. This data is transmitted to the team leader where it is used to build a local map centric to that robot. The team leader (or human operator) can utilize the robot's local map information to direct the robot around obstacles investigate anomalies or generate new paths. When the positions of all robots in the group are obtained, we use an occupancy grid Bayesian mapping algorithm to combine the sensor data from multiple robots with different sensing modalities.

Path planning and Exploration

To guarantee effective search, the robots must explore unknown environment as quickly and completely as they can[4], simultaneity, minimize the overlapping of explored areas.

When exploration begins, a set of different initial azimuths for exploration are pre-assigned evenly for the robots, which will help to avoid overlapped area during their respective exploration. Each robot is responsible for exploration by path planning in a disjointed area predefined and modified in real-time according to the latest map information shared with others. The robots explore towards their azimuths and keep that roughly unchangeable until they reach the boundary of the surroundings. In this case, they will turn clockwise until there are unknown surroundings for them, and move towards the opposite azimuth of the original. During the exploration, if the surroundings are never explored before, they will stop for a moment, rotate their cameras to search for victims and collect surroundings image data. Otherwise, they will move straightforward ahead.

Because that the areas explored by other robots are changed in real-time, to be aware of the latest unexplored surroundings and make corresponding modification on one's exploration directions, the robot will share a common real-time map information provided by the Info-Storage which enable it to determine its exploration direction without conflicting with others.

Simultaneity, We combined an Artificial Immune based Path Planning Strategy and an Improved Ant Colony Optimization based Path Planning Strategy, which were both used in rescue agent simulation system, used to resolve the path planning and exploration problem.

By the hybrid path planning strategy, the robots can explore regularly in the unknown environment. However, to realize the real-time modification during the exploration, an efficient cooperation among robots is required, which will be introduced in the next section.

Cooperation and Coordination

In complex dynamic MAS with uncertainty, every intelligent robot is autonomous. They may have different knowledge, goals, intentions, and actions; therefore, when put in the same environment, the conflicts over resources, goals, and actions are unavoidable. In order to successfully explore and navigate in the area and to avoid duplicate efforts in searching the same areas and to eliminate conflicts in their actions and reasonably distribute their goals and resources, robots need to cooperate and coordinate with the team robots[5][6], so that they can achieve their individual goals in a consistent and harmony manner.

This paper suggests using the improved fuzzy Q-learning algorithm, to establish a coordination model. The model has a two-layer structure, the coordination layer and action layer. The objective is to achieve a coordinated and autonomous action for the intelligent robot.

The action layer is in charge of the action learning of the intelligent robot and executes the action decisions from the coordination layer. It consists of three parts: the state monitor, action execution unit, and action library. The state monitor senses the robot's state information from the environment and provides that to the coordination layer. The action library is a collection of the intelligent robot's possible actions, which will be provided to the coordination layer to process. The action execution unit executes the action handed down from the coordination layer, which makes decision based on the current environment states.

The major part in the coordination layer is the coordination decision maker. It analyzes and makes decision of the action of the robot, and then hands down to the action layer to execute and change the environment. After receiving the intelligent robot's states and possible actions from the action layer, the coordination decision maker first fuzzifies the states to obtain the fuzzy space of the robot. Then, it uses the Q-learning algorithm to evaluate the actions of other robots and learn their action strategy in order to modify its own action, resolve conflicts, and reach a better action decision.

The fuzzy Q-learning algorithm uses the fuzzy logic to fuzzilize the continuous state space of the intelligent robot, so that the size of the state space is reduced. In one time step, many fuzzy states with different degrees can be observed. The intelligent robot makes a smooth transition from the current state to the next state. It generates a continuous action sequence and resolves the learning problem of a complex multiple intelligent robot environment. Based on this algorithm, a new multiple intelligent robot coordination model is suggested. When a robot is making action decision, it considers the effects of other robots' actions. The actions chosen by other robots are evaluated first. Using fuzzy Q-learning algorithm to learn their action strategies, the robot's own action is then modified accordingly to achieve autonomous coordination in each intelligent robot.

Previous Relevant Work and Publications

We started participating in the virtual robot competition last year. But we have researched agent rescue for many years, and gained a lot of experience, which in favor of the research of virtual robot. In the last year, we adopted several new methods for virtual robot. To guide robots' behavior, we designed a common system structure for the heterogeneous robots, in which different functions are defined.

Under this structure, we proposed an A-SLAM approach to map and locate the explored environment with high accuracy, while an ADPPE exploration strategy was adopted for efficient exploration. Furthermore, the cooperation among robots was considered enhance the quality of exploration. But these methods not have good effects and we didn't get good performance last year, so we adopted some methods which we had used in rescue agent competition.

In the past few years we had published some papers about rescue strategies, which list as follows.

Peng, J., Mu, M., Guo, R.: Study of neural network disturbance learning and application in RoboCup. High Technology Letters. 203–206 (2007)

Wu, M., Zhang, X.Y., Peng, J., Lin, K.C.: A Collaboration Method of MAS Based on Information Fusion and its Application in RoboCupRescue Simulation Sytem. In: Proceedings of the 2007 International Symposium on Collaborative Technologies and Systems, IEEE Press, Orlando, USA (2007)

Peng, J., Liu, M., Lin, K.C.: A Coordination Model Using Fuzzy Reinforcement Learning for Multi-agent. In: Proceedings of the 2007 International Symposium on Collaborative Technologies and Systems, IEEE Press,Orlando, USA(2007) Peng, J., Wu, M., Zhang, X., Xie, Y., Jiang, F., Liu, Y.: A collaborative Multi-Agent model with knowledge-based communication for the RoboCupRescue simulation. In: Proceedings of the 2006 International Symposium on Collaborative Technologies and Systems, pp. 341–348. IEEE Press, Washington, DC, USA (2006)

Peng, J., Ding, C.Y.: Realization of Formation Strategy in RoboCup. In: Proceedings of 2006 International Conference on Artificial Intelligence, beijing (2006) Peng, J., Liu, Y., Zhang, X., Wu, M.: State Prediction based Dynamic Cooperation Algorithm in Multi-agent System. Journal of System Simulation. 5511–5515 (2008)

Conclusion

The CSU Yunlu Virtual Team works in the well designed system structure and has the robots guided effectively. Through the proposed Fuzzy logic approach, the robots can map the explored environment and locate it accurately, while the hybrid exploration strategy enables them to explore quickly and completely. To prevent repeated explore among robots, cooperation and coordination strategies are adopted, which enable the whole team work harmoniously and efficiently.

Acknowledgment

This project has been carried out with the help of many individuals and support from School of Information Science and engineering, Central South University. Particularly, the author would like to acknowledge the support of Professor Weihua Gui and Min Wu.

Thanks Steel for its source code, we made modification based on it.

Thanks VIRTUAL-IUB, Freiburg and UvA, they give us a lot of inspiration.

References

1. Carevic, D.: Multitarget Detection and Estimation Based on Passive Multilateral TDOAs of Transient Signals. IEEE Transactions on Signal Processing. 418–424 (2008)
2. Lau, H., Chan, T.M., Tsui, W.T.: Item-Location Assignment Using Fuzzy Logic Guided Genetic Algorithms. IEEE Transactions on Evolutionary Computation. 765–780 (2008)
3. Grabowski, R., Navarro-Serment, L., Paredis, C., Khosla,P.: Item-Location Assignment Using Fuzzy Logic Guided Genetic Algorithms. Journal of Autonomous Robots. (2000)
4. Petres, C., Pailhas, Y., Patron, P., Petillot, Y., Evans, J., Lane, D.: Multitarget Detection and Estimation Based on Passive Multilateral TDOAs of Transient Signals. Path Planning for Autonomous Underwater Vehicles. 331–341 (2007)
5. Peng, J., Wu, M., Zhang, X.Y., Xie, Y., Jiang, F., Liu, Y.: A collaborative Multi-Agent model with knowledge-based communication for the RoboCupRescue simulation. In: Proceedings of the 2006 International Symposium on Collaborative Technologies and Systems, pp. 341–348. IEEE Press, Washington, DC, USA (2006)
6. Peng, J., Liu, M., Lin, K.C.: A Coordination Model Using Fuzzy Reinforcement Learning for Multi-agent. In: Proceedings of the 2007 International Symposium on Collaborative Technologies and Systems, IEEE Press,Orlando, USA(2007)