View Original PDF

PoAReT Team Description Paper

Francesco Amigoni, Alberto Quattrini Li, Giuseppe Andrea Ferraro, Federico Marini, Alessandro Maria Rizzi, Sajjad Salehi

Artificial Intelligence and Robotics Laboratory, Politecnico di Milano, Italy

http://home.dei.polimi.it/amigoni/research/PoAReT.html

Abstract This paper summarizes the main features of the PoAReT (Politecnico di Milano Autonomous Robotic Rescue Team) system that will participate in the Virtual Robot competition of the Rescue Simulation League at RoboCup 2013. The paper summarizes the structure of the 2012 system and introduces some improvements for the 2013 system.

1 Introduction

In this paper, we first summarize the main features of the PoAReT (Politecnico di Milano Autonomous Robotic Rescue Team) team that won the Virtual Robot competition of the Rescue Simulation League at RoboCup 2012. Then, we show some of the new features we intend to introduce for the Virtual Robot competition of the Rescue Simulation League at RoboCup 2013. The new version of the PoAReT system is developed by four MSc students in Computer Engineering at the Politecnico di Milano. Further information about the team, including a link to the source code and the list of past and present members is available at http://home.dei.polimi.it/amigoni/research/PoAReT.html.

In developing PoAReT, we push along the autonomy axis, attempting to equip the robotic system with methods that enable its autonomous operation for extended periods. At the same time, the role of human operator is not neglected, but is empowered by the autonomous features of the system. This approach allowed the PoAReT team to win the Virtual Robot competition at RoboCup 2012. This year, introducing the new features, we aim at further improving the performance of the PoAReT system.

Besides the base station, our PoAReT system is composed of mobile platforms (typically the Pioneer All Terrain robot P3AT, but also Kenafs and Air-Robots; however in the following we will refer to P3AT), equipped with laser range finders (with a 360° horizontal field of view around each robot, possibly obtained with two laser range finders mounted back-to-back) and with a camera. Laser range finders are used to build a geometrical map of the environment that is represented with two sets of line segments. The first set contains the line segments that represent (the edges of) perceived obstacles. The second set contains the line segments that represent the frontiers, namely the boundaries between the known and the unknown portions of the environment. The camera is used to detect victims in the environment.

The main cycle of activities of the PoAReT system is: (a) building a geometrical map of the environment composed of line segments, (b) selecting the most convenient frontiers to reach, and (c) coordinating the allocation of robots to the frontiers. A distinguishing feature of our system is that it (d) maintains a semantic map of the environment that labels areas of the geometrical map with human-like names, like 'room' or 'corridor'. At the same time, the system performs (f) the detection of victims on the basis of the images returned by the onboard cameras and (g) the interaction with the human operator via the user interface. Exploiting semantic maps, the PoAReT system is expected to exhibit a high level of autonomy in selecting the interesting frontiers to reach and in allocating them to available robots. Also the interaction with the user could be improved by availability of semantic maps, enabling the interpretation of human-level commands like "always send two robots along corridors".

In the following of this paper, we first describe the overall architecture of the PoAReT system, then we give a brief description of the individual modules developed last year that perform activities (a)-(g), and finally we discuss the innovative features introduced this year for improving the performance of the system.

2 Overview of the PoAReT System

The architecture of our system is organized in two different types of processes, one related to the base station and one related to the mobile robots, to have a clear separation between their functionalities.

The base station embeds the user interface module. It displays data to the user and accepts commands from the user to control the spawned robots. The base station process can spawn new robots in USARSim: for each robot, a new independent process is created and started. The processes of the base station and of the robots communicate only through WSS and do not share any memory space, as required by the rules for the competition. A distance vector routing protocol [1] is implemented to deliver messages. This protocol calculates the routing tables for every robot in a dynamic and distributed way, considering the performance of a connection in terms of the number of hops for the messages. Messages can be delivered either in a non-reliable or in a reliable way, used for critical information and implemented with the usage of message queues. Although in principle there is no need to maintain a direct connection between robots and base station (robots explore autonomously and, when connection is re-established, they can report to the base station and share collected information with other robots), the routing protocol maintains indirect connectivity between robots and base station in order to extend the operative range of the human operator.

The robot process is structured in seven different modules, each one related to a high-level functionality: motion control, path planning, SLAM, semantic mapping, victim detection, exploration, and coordination. Almost all of these modules are threads that communicate through a queue system. The main of the above modules are described in the following section.

Fig. 1 shows the PoAReT system architecture. The base station module is in green, while the mobile robot modules are in yellow.

3 Main Features of the 2012 PoAReT System

This section outlines the main modules of the PoAReT system used in the Virtual Robot competition of the Rescue Simulation League at RoboCup 2012 (see [2] and [3] for further information).

First, we briefly discuss the motion control module, which is straightforward, given the locomotion model of P3AT, and the path planning module. Path planning is usually invoked to reach a position with a path that lies entirely in the known space (usually, the position is a frontier between known and unknown space). The algorithm we use is RRT [4] in a graph whose vertices are allowed poses of the robot (e.g., where the robot does not collide with any obstacle) and edges are the elementary (visibility) paths between them.

In our team, the simultaneous localization and mapping (SLAM) problem is tackled by adopting a feature-based method similar to that described in [5]. The SLAM module associates the line segments of a laser scan (points of a scan are approximated with line segments by using the split and merge algorithm [6]) to the the linear features in the map, with respect to distance measures, such as those described in [7, 8]. Then, the module executes an Iterative Closest Line (ICL) algorithm (like [8]) with constraints on the maximum rotation and on the maximum translation to align the scan and the map. All the line segments of a scan are added to the map; periodically a test is carried out to determine whether there is enough evidence to support the hypothesis of two previously associated line segments being in fact the same; if so, they are merged. For example, Fig. 2 shows the geometrical map built by the PoAReT system for the environment of the Day 2 of the 2012 Virtual Robot competition.

The semantic mapping module performs a semantic classification of places and works in parallel with the SLAM module. This module takes as input the line segment map of an indoor environment (updated by the SLAM module) and tries to extract more information than the basic geometrical features, exploiting prior knowledge on the typical structure of buildings. Our approach extends that presented in [9] and [10] to line segment maps. The mapped area is divided into single rooms, identifying the area that belongs to each room and the doorways that divide the rooms (an example of doorway is shown in Fig. 2). Later, each room can be classified according to its own characteristic, as a small room, a large room, or a corridor.

The exploration module selects new frontiers to explore, in order to discover the largest possible amount of the environment within the time allowed in the competition. This module evaluates the frontiers by assigning them utilities and, finally, calls the coordination module to find an allocation of robots to the frontiers. We employ an exploration strategy that exploits the geometrical and semantic information gathered by the robots. We take inspiration from [11], where the authors achieve a good exploration performance by distinguishing if the robot is in a hallway or in a room. In our system, we integrate this semantic information into a framework, called Multi-Criteria Decision-Making (MCDM), that is described in [12].

The coordination module is responsible of allocating tasks to the robots. The mechanism we use is market-based and sets up auctions in which tasks (i.e., frontiers to reach) are auctioned to robots [13]. These market-based mechanisms provide a well-known mean to bypass problems like unreliable wireless connections or robot malfunctions. An experimental analysis of the relationships between exploration and coordination is reported in [14].

The victim detection module is responsible for searching victims inside the competition environment. It works by analysing images coming from the robots' cameras and classifying them according to the presence or absence of victims. In the first case, the victim detection module signals the human operator. We implemented a skin detector using HSV (Hue, Saturation, Value) color space, followed by a version of the Viola-Jones algorithm [15], a well-known image analysis method already used by many teams in previous editions of the competition.

Finally, the User Interface (UI) module allows a single operator to control a relatively large group of robots (up to a dozen) in an easy way. It reduces the workload of the operator and increases her/his situation awareness. These two objectives are reached by our UI through a mixed-initiative approach [16]. Specifically, the interaction is enhanced with the introduction of high-level commands that limit the cognitive cost for the operator and exploit the full automation of the system. Fig. 3 shows the UI in action. Clockwise from the top-left of the image: camera thumbnails (for monitoring and selecting robots), teleoperation commands (for directly controlling the selected robot), information about the selected robot (camera view, battery level, connected robots), interactive map (used for issuing control actions and integrated with both semantic mapping and victim detection). Finally, the message manager that shows, sorts, and filters messages from the robots is displayed at the bottom of the image.

4 New Features of 2013 PoAReT System

This section outlines the improvements and new features of the PoAReT system introduced for the Virtual Robot competition of the Rescue Simulation League at RoboCup 2013.

First, the path planning module that is improved in such a way the number of situations in which robots get stuck is reduced. The approach used for path planning in the 2012 PoAReT system can be considered single query, namely only a single pair of initial-goal points is given, and RRT searches until it either finds a solution or fails. Other approaches can be considered multiple query, as a data structure is built to be used for finding efficient solutions for many initial-goal pairs. One of the multiple-query algorithms is based on Probabilistic RoadMaps (PRMs) and first constructs a graph (the roadmap), representing a rich set of collision-free trajectories, and then answers queries by computing a shortest path that connects the initial state with a final state through the roadmap [17, Chapter 5].

Second, the maps built by different robots are not merged together, as it is evident from the map shown in Fig. 2, where the same wall is represented by many line segments. So, currently, each robot builds up its own local map based on the sensor readings acquired during the exploration process. To better exploit the knowledge available to each robot, we use some of map merging techniques (e.g., [18–20]) to deal with constructing a global map maintained by the base station that is more than a simple union of local maps. The approach works with a segment-based representation of the map, contrasting most of the works in literature which deal with grid-based representations (except [20]).

Third, we work on a method for fast detection of frontiers for reducing computational time needed for computing frontiers in a map. Needless to say, in frontier-based exploration, it is fundamental to identify frontiers between known and unknown portions of the space, where robots are sent to. We take inspiration from [21], where the authors propose two algorithms that process only the new laser readings data to detect new frontiers. Even in this case, we have to adapt the methods considering line segment maps, instead of grid-based maps.

Finally, some other features that will be improved in the new version of the PoAReT system include: a refinement of the distance vector routing protocol and a better management of the Kenafs and AirRobots.

5 Conclusion

This paper has both summarized the main features of the PoAReT system for the Virtual Robot competition of the Rescue Simulation League at RoboCup 2012 and shown the new features introduced for the same competition at RoboCup 2013. Among the innovative features added to the new version of the PoAReT system, we highlight an efficient map merging working on segment-based maps to have a better global representation of the environment used for coordinating robots and an improved frontier detection that reduces the computational time for finding frontiers. Overall, our contributions are intended to increase autonomy and performance of robotic systems for rescue operations.

Fig. 1. PoAReT system architecture.
Fig. 1. PoAReT system architecture.
Fig. 2. The geometrical map built by the PoAReT system on Day 2 of the 2012 competition. The solid line segments represent obstacles, the dashed line segments represent the frontiers, and the blue triangles represent the positions of the robots.
Fig. 2. The geometrical map built by the PoAReT system on Day 2 of the 2012 competition. The solid line segments represent obstacles, the dashed line segments represent the frontiers, and the blue triangles represent the positions of the robots.
Fig. 3. PoAReT user interface.
Fig. 3. PoAReT user interface.

References

  1. Comer, D.: Internetworking with TCP/IP Volume 1. Addison-Wesley (2006)
  2. Amigoni, F., Caltieri, A., Cipolleschi, R., Conconi, G., Giusto, M., Luperto, M., Mazuran, M.: PoAReT Team Description Paper. RoboCup2012 CD (2012)
  3. Amigoni, F., Visser, A., Tsushima, M.: RoboCup 2012 Rescue Simulation League winners. In: Proc. RoboCup. (2012)
  4. LaValle, A., Kuffner, J.: Rapidly-exploring random trees: Progress and prospects. In Donald, B., Lynch, K., Rus, D., eds.: Algorithmic and Computational Robotics: New Directions. (2001) 293–308
  5. Garulli, A., Giannitrapani, A., Rossi, A., Vicino, A.: Simultaneous localization and map building using linear features. In: Proc. ECMR. (2005) 44–49
  6. Nguyen, V., Gächter, S., Martinelli, A., Tomatis, N., Siegwart, R.: A comparison of line extraction algorithms using 2d range data for indoor mobile robotics. Autonomous Robots 23(2) (2007) 97–111
  7. Elseberg, J., Creed, R., Lakaemper, R.: A line segment based system for 2D global mapping. In: Proc. ICRA. (2010) 3924–3931
  8. Li, Q., Griffiths, J.: Iterative closest geometric objects registration. Computers & Mathematics with Applications 40(10-11) (2000) 1171–1188
  9. Pronobis, A., Martinez Mozos, O., Caputo, B., Jensfelt, P.: Multi-modal semantic place classification. International Journal of Robotics Research 29(2-3) (2009) 298–320
  10. Martinez Mozos, O.: Semantic Labeling of Places with Mobile Robots. Springer-Verlag (2010)
  11. C. Stachniss, O.M.M., Burgard, W.: Speeding up multi-robot exploration by considering semantic place information. In: Proc. ICRA. (2006) 1692–1697
  12. Basilico, N., Amigoni, F.: Exploration strategies based on multi-criteria decision making for searching environments in rescue operations. Autonomous Robots 31(4) (2011) 401–417
  13. Zlot, R., Stentz, A., Dias, M.B., Thayer, S.: Multi-robot exploration controlled by a market economy. In: Proc. ICRA. (2002) 3016–3023
  14. Amigoni, F., Basilico, N., Quattrini Li, A.: How much worth is coordination of mobile robots for exploration in search and rescue? In: Proc. RoboCup. (2012)
  15. Viola, P., Jones, J.J.: Robust real-time face detection. International Journal of Computer Vision 57(2) (2004) 137–154
  16. Wang, J., Lewis, M.: Human control for cooperating robot teams. In: Proc. HRI. (2007) 9–16
  17. LaValle, S.M.: Planning algorithms. Cambridge University Press (2006)
  18. Konolige, K., Fox, D., Limketkai, B., Ko, J., Stewart, B.: Map merging for distributed robot navigation. In: Proc. IROS. (2003) 212–217
  19. Birk, A., Carpin, S.: Merging occupancy grid maps from multiple robots. Proc. IEEE 94(7) (2006) 1384–1397
  20. Lakaemper, R., Latecki, L., Wolter, D.: Incremental multi-robot mapping. In: Proc. IROS. (2005) 3846–3851
  21. Keidar, M., Kaminka, G.A.: Robot exploration with fast frontier detection: theory and experiments. Proc. AAMAS (2012) 113–120