Seite - 41 - in Proceedings of the OAGM&ARW Joint Workshop - Vision, Automation and Robotics

Fig. 3. Grid selection for the localization, together with the topological map [5]. tions. Each vertex is specified as a full 2D pose in the global reference frame allowing to specify the difference from the robots location to any frame in the graph. Furthermore, each vertexcontainsagridmaprepresenting the localenvironment at this position. It is ensured that every position within the grid map can reach the center. To ensure proper connections of vertices a connection is only made if the combination of both grid maps allow the robot to reach one vertex from the other.Let’sconsider thesimpleexampleofa topologicalmap as it isdepicted inFigure3.Grid11 isclose togrid3,butdue to the wall between these two grids, no connection between grid 11 and grid 3 is made. Thus, the robot knows which traversals are possible in the environment with the help of the grid map. We will exploit this knowledge to select the right grid for localization if the robot moves beyond the area of one grid. Initially, the robot knows its starting location, this is done through the input of the user. After the robot has selected the initial position the vertex which is the closest to the current initial location is chosen. Additionally, the robot should check if it can move between the initial pose to the grid map vertex. Using this vertex, the robot can use the grid map of the vertex to localize itself. This is done with the help of a particle filter [7]. The particle filter uses the grid map to align the current laser measurements with the occupied cells in the grid map. Additionally, the robot uses the GPS signal to localize itself. This is done by anchoring each vertex with a GPS position. Thus, by using the current GPS signal the robot can estimate its position relative to the currently used vertex in the topological map. Using the grid map and the GPS the robot derives an estimation of its current location. If the robot is moving in the grid map the localization can be done with the current grid map. But as we assume a large space of the outdoor environment the robot will at some point reach the border of the grid map. In such a case the robot needs to decide which vertex in the topological map is the next one to localize itself. This is done by checking the distance to each vertex in the topological map which has a connection to the currently used vertex. The vertex with the smallest distance to the current robot pose is used for future localization. Thus, the robot will switch the vertex and the occupancy grid only if it is closer to that vertex than any other vertex which could be reached from the robot. Let’s consider the situation in Figure 3. If the robot is moving from grid 3 to grid 4. It checks the distance from the vertex of grid 3 and the distance of vertex of grid 4. But the robot does not check the distance to the vertex of grid 11 as the robot already knows that there is no possibility that it has traveled from grid 3 to grid 11. If the distance of grid 4 is larger than the distance to grid 3 the robot will use grid 3 for future localization. Due to the use of the connections within the topological map one saves the effort to check all nearby vertexes if they should be used for localization. Furthermore, more important is that the robot will not select a vertex which cannot be reached. Let’s consider the map in Figure 3. Grid 3 and 4 can be on the outside of the building whereas grid 11 is the inside of the building. Thus, if the robot is localized outside of the building it does not make sense that the robot jumps suddenly through the wall inside the building. As we don’t consider grid 11 as an alternative such a jump is not possible. This also allows the robot to move close to the wall of the building without being incorrect localized. IV. NAVIGATION With thehelpof the topologicalmap, the robotcan localize itself. Using this localization, the robot can plan its path to the destination. To do so, the robot uses a hierarchical planningapproach.Asweconsidera large-scaleenvironment the robot is not able to use a grid map of the complete environment. Thus, the robot uses a road map to plan the overall navigation. This allows the robot to plan for the large environment in a fast manner. After a plan is found using the road map the robot use the current grid to search for a mid- level plan within this map to move between different nodes in the roadmap. Finally, the robot uses a local planner to move along the mid-level plan and avoid obstacles which are not present in the grid map. The road map which is used by the robot to generate a high-level plan consists of a graph of nodes which specify locations and edges which describe possible traversals be- tween these nodes. A roadmap together with the high-level plan is depicted in Figure 4. The road map is constructed by considering the distance between the nodes and if the node is collision free. To check if a node is collision free the footprint of the robot and the local grid map of the position to check is used. As the robot, has not specified a complete description of the environment traversability, one uses the positions used during mapping as a seed for the road map calculation. This allows that the robot uses the positions and traversals which were created during mapping. To plan a path within the road map the robot first deter- mines theclosestnodeof the roadmap to its current location. Afterward, the closest node to the destination is determined. The node close to the current position is the start node of the search and the node close to the destination is the goal node of the search. After determining these two nodes the 41