Amsterdam Oxford Joint Rescue Forces Team Description Paper Virtual Robot competition Rescue Simulation League RoboCup 2009

Arnoud Visser, Gideon Emile Maillette de Buy Wenniger, Hanne Nijhuis, Fares Alnajar, Bram Huijten, Maarten van der Velden, Wouter Josemans, Bas Terwijn, Christiaan Walraven, Quang Nguyen, Radoslaw Sobolewski, Helen Flynn, Magda Jankowska, Julian de Hoog

Universiteit van Amsterdam, Science Park 107, 1098 XG Amsterdam, NL; Oxford University Computing Laboratory, Parks Road, Oxford OX1 3QD, UK

http://www.jointrescueforces.eu

Abstract With the progress made in active exploration, the robots of the Joint Rescue Forces are capable of making deliberative decisions about the distributing exploration locations over the team. To navigate autonomously towards those locations, the robots gradually aggregate their experience in a traversability map. This traversability map can be used as basis to calculate an optimal path towards a goal. Robots equipped with both camera and laser-range scanners can learn a visual classifier of free space, which could be used by robots without laser-range scanners to navigate through the environment. Part of our algorithms have been validated on the Nomad Super Scout II robot available in our laboratory.

Introduction

The RoboCup Rescue competitions provide benchmarks for evaluating robot platforms' usability in disaster mitigation. Research groups should demonstrate their ability to deploy a team of robots that explore a devastated area and locate victims. The Virtual Robots competition, part of the Rescue Simulation League, is a platform to experiment with multi-robot algorithms for robot systems with advanced sensory and mobility capabilities. The developed algorithms should be directly portable to fieldable systems, as demonstrated by several of the participating teams [1].

The shared interest in the application of machine learning techniques to multi-robot settings [2] has led to a joint effort between the laboratories of Oxford and Amsterdam.

1 Team Members

UsarCommander was originally developed by Bayu Slamet and all other contributions have been built into his framework. Many other team members [3–6] have contributed on perception and control algorithms inside this framework.

The following contributions have been made this year:

Arnoud Visser : research portfolio [2], exploration algorithms [7], communication protocol [8], geometry, mapping test

Gideon Maillette de Buy Wenniger : image interpretation, learning to visually recognize free space [9]

Hanne Nijhuis, Fares Alnajar : teleoperation test, waypoint navigation with AirRobot [10]

Bram Huijten, Maarten van der Velden, Wouter Josemans : generation and usage of traversability maps, A* path-planning

Bas Terwijn : interface to the Nomad Super Scout II robot, software performance analysis

Quang Nguyen : visual range scanner.

Christiaan Walraven : map evaluation.

Radoslaw Sobolewski : mobility challenges with Kenaf robot.

Helen Flynn : automated map attribution

Magda Jankowska : map stitching

Julian de Hoog : user interface, hybrid autonomy, multi-robot exploration, communication roles [11], deployment test

2 Scan Matching

The possibilities for active exploration are heavily dependent on a correct estimation of a map of the environment. Many advanced techniques that aim to detect and correct error accumulation have been put forward by SLAM researchers. Although these SLAM techniques have proven very effective in achieving their objective, they are usually only effective once errors have already accumulated. With a robust scan matching algorithm the localization error is minimal, and the effort to detect and correct errors can be reduced to a minimum. Several scan matching algorithms are available in our code, but during the 2009 competition the WSM algorithm [12] will be used, based on the robustness reported in [13].

3 Localization and Mapping

The mapping algorithm of the Joint Rescue Forces is based on the manifold approach [14]. Globally, the manifold relies on a graph structure that grows with the amount of explored area. Nodes are added to the graph to represent local properties of newly explored areas. Links represent navigable paths from one node to the next.

The graph structure means that it is possible to maintain multiple disconnected maps. In the context of SLAM for multiple robots, this makes it possible to communicate the graphs and to have one disconnected map for each robot. The result is illustrated in Fig. 1, where the maps of two robots are merged into a single map for the operator. Also note the nice distribution of the exploration effort (fully autonomous) between the two robots. The graph structure of the manifold can be easily converted into occupancy grids with standard rendering techniques, as demonstrated in [13].

4 Traversability Map

An important aspect for a mobile robot is to have a good estimate of the quality of the terrain, before navigation decisions are made. An occupancy grid (the probability that an obstacle is present) is a good initial estimate, but this estimate is based on a 2D-range scan on a fixed height. The quality of the terrain can be misjudged, for instance by obstacles present on a different height. More fundamentally, there can be obstacles present which are extremely difficult to perceive (e.g. quicksand, tripwires), even when the output of many advanced sensors is combined. At the end, the ultimate way to learn the terrain quality is to try it out. In essence, the mobility experience of the robot is collected as a function of its position. The mobility success T can be measured with different metrics. During an exploration run several mobility features are stored in the nodes of the map. Currently, these features are the requested $v^r$ and measured speed $v_m$. Additional features could be added, such as the tilting angle experienced by the Inertial Navigation System (INS). Those features are mapped onto a range between 0 to 255 by a utility function. The currently applied utility function is a linear relationship, as defined in Eq. 1:

$$T = 255 \frac{|v_m|}{|v_r|}$$

, with $T = 0$ when $|v_r| = 0$ and $T = 255$ when $\frac{|v_m|}{|v_r|} \ge 1$ (1)

The result is a traversability map which in the beginning mainly reflects the traveled paths (see Fig. 2), but when the experience of multiple robots from multiple runs is aggregated, the traversability map should gradually cover the map of free space.

5 Path Planning

A robot can use a map, such as an a priori map, an occupancy grid map or a traversability map, to plan a safe path from a start position to a goal. Currently, two path-planning algorithms are available in our environment; a breadth-first algorithm [15] and an A* algorithm [16]. In both algorithms different types of maps can be included in the calculation of the distance measure g(), which calculates the 'real' costs to travel to an intermediate point on the path. The heuristic function h() will estimate the distance to the goal, which can be a simple Euclidian distance (without notion of obstacles or traversability). Both algorithms are based on graph-search, but the difference between both algorithms is the way in which the graph is expanded. For the breadth-first algorithm all neighbouring grid cells (not considered before) are expanded, which is equivalent with using a first-in-first-out (FIFO) queue. For the A* algorithm all neighbouring grid cells are added to a priority queue, and the search continues with the most promising node (which doesn't have to be neighbour). The sorting of the priority queue is based on the distance measure f() = g() + h(). This algorithm is illustrated in Alg. 1.

Data: the traversability map m, the start point s, the target point t
Result: the optimal path p from location s to the location t
closed = EmptyList();
open = EmptyPriorityQueue(s);
while Not IsEmpty(open) do
   c = HighestPriority(open);
   if h(c, t) <  then
       Return p(c);
   end
   if Not IsMember(closed,c) then
       closed.Add(c);
       for each neighbor(c,n) do
           dn = g(s, c, m) + h(n, t);
           p(n) = p(c) + n;
           QueueSortAdd(open,n,dn);
       end
   end
end
Return EmptyList();

Algorithm 1: The A* algorithm for the path-planning with the real travel cost g() calculated on the traversability map, and the heuristic travel cost h() calculated with the Euclidian distance.

6 Multi-Robot Exploration and Communication

In our previous work, an exploration approach was demonstrated which made a selection between a small number of frontiers, based on the information gain available beyond those frontiers [17]. Each robot may calculate the balance between movement costs and information gain for itself and for each of its teammates. Consequently an optimal robot-frontier assignment can be determined in which robots assign themselves to frontiers, and no frontier is explored by more than one robot. The result is efficient, fully autonomous multi-robot exploration.

Including communication success into this exploration approach [8] means that robots will prefer frontiers from which they can likely communicate to frontiers that are likely to be out of range. However, frontiers that are out of range are just as important to explore, and require additional consideration. Two possible solutions are:

1. to visit the area of interest, and then physically return to the ComStation to transmit the new knowledge
2. to visit the area of interest, and then transmit the new knowledge to the ComStation via multi-hop communication using team members

The second solution described above may be implemented by using a rolebased approach: robots may dynamically become explorers or relays as part of the ongoing exploration effort. A relay need not be stationary – it may follow an exploring robot for some time, and periodically return to transmit new knowledge to the ComStation (see Fig. 3). It is hoped that the ensuing team behavior allows for exploration deep into the environment, even in areas that are far beyond the team's initial range.

7 Free Space detection

Camera images can be used for teleoperation and to detect victims. Camera images can also be used as independent information to detect free space. Range scanners, which are typically used as primary means to detect free space, are active sensors which have a limited range and a limited field of view. Additionally, active sensors are relatively heavy and consume considerable amounts of energy, which makes them less attractive for small mobile robots. In contrast, the limit of a visual sensor range can lie as far as the horizon and omnidirectional vision methods can provide a 360◦ view of the environment. A method to identify free space based on visual sensor data could well expand the environment observation quality of a rescue robot.

As part of this year's effort, two visual free space classifiers were trained using a laser-range scanner as reference [9]. The same laser-range data, acquired elsewhere on the map, is used as ground truth to test the precision and recall of these free space classifiers. This training and testing was performed both in simulation (see Fig. 7) and on a collected dataset.

8 Conclusion

This paper summarizes improvements in the robot control environment of the Amsterdam Oxford Joint Rescue Team since RoboCup 2008 in Suzhou. This progress was demonstrated at the Latin American Robotics Competition, where the first prize was won with fully autonomous exploration. At the German Open 2009 competition the teleoperation test was won thanks to the application of AirRobots, the mapping test was won based on the robust WSM algorithm and the deployment test was won thanks to the autonomous exploration algorithm. More important, the progress is well documented in a number of publications in international robotics conferences.

References

1. Balakirsky, S., Carpin, S., Kleiner, A., Lewis, M., Visser, A., Wang, J., Ziparo, V.A.: Towards heterogeneous robot teams for disaster mitigation: Results and Performance Metrics from RoboCup Rescue. Journal of Field Robotics 24 (2007) 943–967
2. Visser, A., de Hoog, J.: Amsterdam Oxford Joint Rescue Forces Realistic Simulations to aid research and education in advanced Robot Control algorithms. In: Proc. of the Scientific ICT Research Event Netherlands (SIREN 2008). (2008) 22
3. Pfingsthorn, M., Slamet, B., Visser, A., Vlassis, N.: UvA Rescue Team 2006; RoboCup Rescue - Simulation League. In: Proc. CD of the 10th RoboCup International Symposium. (2006)
4. Visser, A., Slamet, B., Schmits, T., Gonz´alez Jaime, L.A., Ethembabaoglu, A.: Design decisions of the UvA Rescue 2007 Team on the Challenges of the Virtual Robot competition. In: Proc. 4th International Workshop on Synthetic Simulation and Robotics to Mitigate Earthquake Disaster. (2007) 20–26
5. Visser, A., Schmits, T., Roebert, S., de Hoog, J.: Amsterdam Oxford Joint Rescue Forces - Team Description Paper - RoboCup 2008. In: Proc. CD of the 12th RoboCup International Symposium. (2008)
6. Visser, A., Schmits, T., Roebert, S., Maillette de Buy Wenniger, G., de Hoog, J.: Amsterdam Oxford Joint Rescue Forces - Team Description Paper - Latin American RoboCup Open 2008. In: Proc. of the 5th IEEE Latin American Robotics Competition (LARC 2008). (2008)
7. Visser, A., Slamet, B.A.: Balancing the Information Gain Against the Movement Cost for Multi-robot Frontier Exploration. In: European Robotics Symposium 2008. Springer Tracts in Advanced Robotics, Springer-Verlag (2008) 43–52
8. Visser, A., Slamet, B.A.: Including communication success in the estimation of information gain for multi-robot exploration. In: 6th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks and Workshops (WiOPT 2008), IEEE Publishing (2008) 680–687
9. Maillette de Buy Wenniger, G., Schmits, T.: Identifying Free Space in a Robot Bird-Eye View. Report, Universiteit van Amsterdam (2008)
10. Alnajar, F., Nijhuis, H., Visser, A.: Coordinated action in a Heterogeneous Rescue Team. In: Proceedings of the 13th RoboCup International Symposium. (2009) To be published in the Lecture Notes on Artificial Intelligence series.
11. de Hoog, J., Cameron, S., Visser, A.: Robotic Search-and-Rescue: An integrated approach. In: Proc. of the Oxford University Computing Laboratory student conference 2008. Number RR-08-10 in OUCL (2008) 28–29
12. Pfister, S.T., Kriechbaum, K.L., Roumeliotis, S.I., Burdick, J.W.: Weighted line fitting algorithms for mobile robot map building and efficient data representation. (2003) 1667–1674
13. Pfingsthorn, M., Slamet, B.A., Visser, A.: A Scalable Hybrid Multi-Robot SLAM method for Highly Detailed Maps. In: RoboCup 2007: Robot Soccer World Cup XI. Volume 5001 of Lecture Notes on Artificial Intelligence., Springer-Verlag (2008) 457–464
14. Howard, A., Sukhatme, G.S., Matari´c, M.J.: Multi-robot mapping using manifold representations. Proceedings of the IEEE 94 (2006) 1360–1369
15. Moore, E.F.: The shortest path through a maze. In: Proc. of the International Symposium on the Theory of Switching, Harvard University Press (1959) 285–292
16. Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics 4 (1968) 100–107
17. Visser, A., Xingrui-Ji, van Ittersum, M., Gonz´alez Jaime, L.A., Stancu, L.A.: Beyond frontier exploration. In: RoboCup 2007: Robot Soccer World Cup XI. Volume 5001 of Lecture Notes in Artificial Intelligence., Springer-Verlag (2008) 113–123