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

robot performs a graph search for the shortest path through theA∗ algorithm [8]. Fig. 4. Road map (green) together with the high-level plan (red) and the low-level plan (blue) [5]. After the robot has generated a high-level plan it generates a mid-level plan on the current grid map to plan to the next node in the roadmapwhich ispartof thehigh-levelplan.The node which is the next one to pass through is determined by the current location of the robot. The robot considers every node as reached which is in a certain range. To determine this node, the robot uses a queue of nodes within the high- level plan. After the head of the queue is in range the robot pops the head from the queue and uses the new head of the queue as the next goal to plan to. Additionally, if the node is the last node in the queue the robot plans to the destination as the high-level plan only ensure that the robot moves near the destination. For the mid-level plan on the current grid map, the robot uses the information of the current grid map to determine if it can traverse a grid cell or not. Using this information, the robot uses its current location together with the next node to find a plan. This plan consists of a sequence of grid map cells to traverse. The sequence is found by using the A∗ algorithm [8]. As the grid map only specifies a limited area of the world the algorithm can determine the path very fast. Additionally, the path which needs to be planned is most of the time short compared to the high-level plan. Using the mid-level plan on the current grid map the robot has derived a path which should lead to the current node of the high-level plan considering the known static objects. As we consider a dynamic environment the robot needs to deal with these obstacles as well. This is done by creating a local plan with the help of the dynamic window approach [9]. The local plan is generated several times per second to allow to react to changes. To plan locally the robot uses a cost map which contains the static obstacles, the information from the horizontal laser scan, the information from the elevation map and information about the grass around the robot. As we argued above one cannot assume that the robot moves on a flat surface. Thus, the robot needs to deal with the uneven ground. Through the construction of an elevation map in a local area, the robot can detect holes and barriers. The elevation map is constructed with the help of the sensor data of the tilted laser. Each of the laser measurements is transformed to specify a position in the world frame. Afterward, the measurement is projected on a grid which defines the height information of the environment. To in cooperate the sensor measurement into the grid a Bayes update per grid cell is used [10]. This allows the robot to deal with the noise of the sensor measurements. After generating the height information one detects holes and barriers by deriving the gradient for each grid cell. Using this gradient one can define a threshold which determines if this hole or barrier is traversable by the robot. If the gradient exceeds a certain limit the robot cannot traverse this grid cell and it is assumed to be a lethal obstacle for the local planner. An example of grid cells which are marked due to a large gradient is depicted in Figure 5. As the elevation map is projected through the gradient into the cost map one can use a standard 2D-planning algorithm to find a local plan. Fig. 5. Detection of edges with the help of the elevation map [5]. Besides the uneven ground, the robot needs also to con- sider the grass to proper navigate in an outdoor environment. During outdoor navigation, the robot should preferably stick to roads and sidewalks. Thus, the robot needs to detect the grass surrounding the robot. To perform this detection, the robot uses the tilted laser scanner. The tilted laser scanner does not only provide the information about the distance from obstacles but it also contains the information about the intensity of the reflection. Using the intensity and the distance one can identify grass in the environment. A simple linear separator is sufficient to detect grass properly. This relation between distance and reflection intensity with the linear separator is depicted in Figure 6. With the help of this classifier, the robot can detect grass in its vicinity. An example of this detection is depicted in Figure 7. Using this information, the robot adds increased costs in the cost map for the local planner on those positions which indicate grass. Thus, the robot avoids the grass if possible but will also traverse it if necessary. By combining the grass, the information of the elevation maps, the laser scan measurements of the horizontal laser as well as the static objects in the map the robot can safely navigate locally. Thus, the robot neither hits an object nor fallsdownastep.Weconsider thesedataonly fora local area around the robot. This has the benefit of a smaller memory footprint for each local cost map but also the drawback that this information cannot be used for localization or high-level navigation. V. RELATED RESEARCH Before we conclude the paper, we discuss some related research. 42