View Original PDF

UvA Rescue Team 2006 RoboCup Rescue - Simulation League

Max Pfingsthorn, Bayu Slamet, Arnoud Visser, Nikos Vlassis

University of Amsterdam Kruislaan 403, 1098 SJ Amsterdam The Netherlands

Abstract The UvA Rescue Team will participate in the RoboCup Rescue Simulation League by employing a Simultaneous Planning, Localization and Mapping (SPLAM) approach. This approach augments traditional SLAM approaches with Planning in order to accomplish the set tasks. In this approach SLAM is modeled as one of the potential subgoals that may enable completion of the overall task. The benefit of this approach is that the quality of Localization and/or Mapping is regarded with respect to the tasks to achieve, which will gauge the optimization policy towards completing the task as a whole. Since victim detection is considered part of the exploration problem, we consider an approach based on the SPLAM paradigm as complete.

1 Introduction

The UvA Rescue Team will represent the Dutch University of Amsterdam at the simulation league of the RoboCup Rescue competition of 2006. Our research interest focuses on multi-agent Simultaneous Planning, Localization and Mapping (SPLAM). This is an approach that augments the traditional SLAM approaches [1] with planning methods. The Planning module is targeted at accomplishing higher-level tasks, where Localization and Mapping are potential sub-goals that enable subsequent goals.

Since the problem posed by the RoboCup Rescue league is basically an exploration problem, we focus on exactly that aspect of the competition. Our approach integrates RFID, Sonar and Laser Scanner readings into a consistent and highly accurate shared 3D map. From this map and several extracted topological features, we generate a representation suitable for use in a POMDP [2] [3] which is used in the Planning module.

Integrating diverse sensor data in one consistent representation has great advantages for dealing with the Urban Search and Rescue problem. Most of all, recent SLAM approaches can be used on this representation and the diversity of error sources of the sensory input may decrease the search space for the optimal map. Especially RFID readings will help here. Victim locations become a part of the map instead of being superimposed.

We have chosen to employ a homogenous team of the robust P2AT robots. This choice was mainly inspired by the large payload of sensors these robots can carry. We like their capability to easily overcome most small obstacles and to navigate up the tilted ramps that connect different floors in the simulated buildings.

Each robot carries 3D Laser Range scanners which produce 2.5D pictures of the surroundings. In addition, each robot will have the ability to deploy its own RFID tags along its path and read other robots' tags as well. Below a complete list of sensors we will use on our robots:

    1. Two 3D Range Scanners, pointed in opposing direction for a 360 degree 2.5D image
    1. An RFID sensor to read victim, robot and other RFID tags
    1. Five Human Motion sensors, arranged in an arc in the front
    1. Three Sound sensors, distributed across the robot's body
    1. 12 Sonar range finders
    1. An Inertial Navigational Unit (INU) used as a compass
    1. An Odometry Sensor
Fig. 1. The simulated P2AT robot.
Fig. 1. The simulated P2AT robot.

2 Localization and Mapping

Our team of robots will incorporate a multi-agent SLAM algorithm. The map will be shared by all agents and they jointly build up and improve this shared map. Many SLAM techniques that have been put forward by researchers to date are based on 2D representations like occupancy grids [4] [5] [6]. To accommodate for a multi-level environment in 3D one could incorporate multiple local representations in 2D into a topological organization like is done in Atlas [7] or Howard's manifold-based approach [8].

However, we have chosen to employ a new approach that is based on a true 3D representation. Using a 3D laser range scanner we will obtain points in 3D. For localization purposes we will just use the range scans obtained in horizontal direction, this allows us to use existing odometry-corrected 2D localization algorithms like the one employed by [5]. For the map representation however we will use the points obtained in all directions and project them in the shared 3D map representation. In cases where the robot does not move on a planar surface, like when changing from a floor onto a ramp, a 3D scan matching method is used. Using standard techniques (e.g. [9] [10]) we extract higher-level abstractions from the point clouds.

Another aspect to highlight is the way SLAM is treated within the context of SPLAM. For the planning part, mapping and exploration are just some of the tasks that can be executed in order to accomplish the task as a whole. Instead of finding optimal map quality and localization accuracy by themselves, SPLAM evaluates these with respect to the overall task.

Loop closure has proven to be a tough challenge in SLAM as it heavily relies on data association, which is typically a hard problem and requires advanced pattern recognition techniques. In the virtual rescue league however, some tools are provided that greatly reduce the data association problem. Each robot can be equipped with a RFID releaser which allows the robot to drop RFID tags. Using a RFID sensor these beacons can later be detected and the unique ID associated with the RFID is returned. This will reduce the association error significantly, only the sensor noise remains as a dominant error source. Most victims will also carry such an RFID tag and they can be detected in similar fashion.

3 Planning

Recently, POMDP representations have been developed that can incorporate continuous state spaces and actions [11]. Planning algorithms such as [12] [13] can be used to solve these POMDPs efficiently. Our approach utilizes these algorithms to generate a local plan in order to keep planning close to real-time. We have designed the planning and the execution of the plan as two parallel processes, so that the agent always has a plan to execute and so that planning happens continuously. This is necessary since we only have a local plan, which is close to optimal only around the position of the robot where the plan was made. Ideally, the robot will have a new local plan ready before leaving the area in which the previous plan was close to the optimal plan.

Extra information, such as frontiers [14] or victim locations can be used as a heuristic to further approximate the optimal plan.

Fig. 2. Our rescue team in action.
Fig. 2. Our rescue team in action.

3.1 Map Feature Extraction

In order to convert the 3D map into a usable ground for planning, ground planes and safe areas are extracted. This is done using an efficient implementation of the 3D Hough Transform [9] [10]. This transform will detect any planes in the map and, according to criteria such as steepness and extend in the map, our approach will classify them as ground planes or wall planes. The area where the map coincides with the extracted ground planes will be marked as safe.

Other features of the map are frontiers, which are discontinuities in the map where known unexplored space lies directly next to know free space. These are easily identified during map creation and have been used successfully in similar approaches [15].

3.2 Goals

The agents pursue predefined goals. These goals include the aspects of exploration, victim location verification and map enhancement. These goals are expressed in the reward function of the generated POMDP. This reward function changes over time as the map changes, new victims are found and old victims are verified.

The Exploration goal is dependent on frontiers present in the map. The agent will be given high reward when it can observe something beyond a frontier. The Victim Verification goal gives medium reward for visiting a non-verified victim location closely. The Map Enhancement is very similar to the Victim Verification goal, but it works with a different kind of RFID tag which is used later for map quality measurement as well as tags the agents deploy themselves.

Fig. 3. Plane extraction and classification
Fig. 3. Plane extraction and classification

References

  1. Thrun, S.: Robotic Mapping: A Survey. CMU (2002)
  2. Kaelbling, L.P., Littman, M.L., Cassandra, A.R.: Planning and acting in partially observable stochastic domains. Artif. Intell. 101(1-2) (1998) 99–134
  3. Simmons, R., Koenig, S.: Probabilistic robot navigation in partially observable environments. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI '95). (1995) 1080 – 1087
  4. Thrun, S., Fox, D., Burgard, W.: A Probabilistic Approach to Concurrent Mapping and Localization for Mobile Robots. Machine Learning, vol. 31, pp. 29.53 (1998)
  5. M. Montemerlo, S. Thrun, D.K., Wegbreit, B.: Fastslam: A factored solution to the simultaneous localization and mapping problem. In: Proc. of the AAAI National Conference on Articial Intelligence, Edmonton, Canada (2002)
  6. Frese, U., Duckett, T.: A multigrid approach for accelerating relaxation-based slam. In: Proc. of the IJCAI Workshop Reas. w. Uncert. in Rob., pp. 3946. (2003)
  7. M. Bosse, P. Newman, J.L., Teller, S.: An atlas framework for scalable mapping. In: Int. J. of Robot. Res. 23, pp. 1113-1139. (December 2004)
  8. A. Howard, Gaurav, S.S., Mataric, M.J.: Multi-robot mapping using manifold representations. In: IEEE International Conference on Robotics and Automation, pp 4198–4203, New Orleans, Louisiana (April 2004)
  9. Duda, R.O., Hart, P.E.: Use of the hough transformation to detect lines and curves in pictures. Commun. ACM 15(1) (1972) 11–15
  10. Zaharia, T., Preteux, F.J.: Hough transform-based 3d mesh retrieval. In Latecki, L.J., Mount, D.M., Wu, A.Y., Melter, R.A., eds.: ;. Volume 4476., SPIE (2001) 175–185
  11. Porta, J.M., Spaan, M.T.J., Vlassis, N.: Robot planning in partially observable continuous domains. In: Robotics: Science and Systems, Cambridge, MA, USA, MIT (2005)
  12. Smith, T., Simmons, R.: Heuristic search value iteration for pomdps. In: Proc. of UAI 2004, Banff, Alberta (2004)
  13. Spaan, M.T.J., Vlassis, N.: Perseus: Randomized point-based value iteration for pomdps. Journal of Artificial Intelligence Research 24 (2005) 195–220
  14. B.Yamauchi: Frontier-based approach for autonomous exploration. In: Proc. of IEEE Int. Symposium on Comp. Int., Robotics and Automation, pp 146151. (1997)
  15. Burgard, W., Moors, M., Stachniss, C., Schneider, F.: Coordinated multi-robot exploration. IEEE Transactions on Robotics 21(3) (2005) 376–378