Hierarchical Reactive Behavior and Path Planning

Figure 3: Pathplanner. The shading of cells corresponds to cost. Expensive dark cells are caused by obstacles, such as other robots and walls, and by the defense area that should not be visited by field players. The dark blue cells show the path with the smallest aggregated costs that is computed by a best first search that visits only parts of the grid. White cells need not be considered. Point A is the first significant turn on the path. This point is communicated to the lowest layer in behavior control together with the direction towards point B. The robot drives from start towards A such that it can next turn to B. As the robot approaches the goal, the path is updated and points A and B move closer to the goal.

We use a hierarchy of reactive behaviors to control the robots. Simple behaviors are arranged in layers that work on different time scales. Fast primitive behaviors, such as taxis are implemented in the lowest layer. More complex, but slower behaviors are produced by the higher layers of the system. A more detailed description of our control architecture is given in [1,3]. Since the field is very crowded and significant contact with other robots must be avoided, we implemented a path planner on the second layer of the behavior control system. The path planner finds a path from a start point (the current robot position) to a goal (the desired robot position). Using dynamic programming and best-first search it computes the cheapest path on a grid that avoids obstacles such as other robots or the defense area. Figure 3 illustrates the behavior of the path planner. After the path has been found, the first point A where the path significantly turns is determined and communicated as target position to the lowest control level. As the robot moves towards A, the path is constantly re-planned and the turn point A moves towards the goal.