Unstructured dynamic environments as for example pedestrian zones or the corridors of an office building, where humans and other robots move freely without following official rules, pose a particulalry hard challenge for the design of reliable motion controllers that are effective at avoiding collisions and reaching goal locations. Such environments are unpredictable to a large extent and the assumptions made by model predictive control approaches hold only for a short amount of time at best. Fast replanning is the only way of reacting to unforeseen events such as the sudden change of direction of a nearby agent, or the appearance of an obstacle in the sensor range that is already on collision course. Fast replanning, however, also implies short computation times that do not suffice for the computation of a detailed plan all the way to the target, which in return can result in oscillatory motions and imprisonment in local minima. Due to this reason, two-tiered navigation controllers emerged that compute a high-level plan at a slow rate all the way to the target (e. g., the shortest path), and follow the plan with a short-sighted, low-level controller that cares for the path following and collision avoidance at a high frequency. The work of Willow Garage [1]} constitutes an extensive test of this control paradigm where a vanilla A* search was used to find the shortest path in an occupancy map and an intermediate target along this path serves as a local goal for the Dynamic Window Approach (DWA) [2]} that follows the path and avoids collisions.
<FIGURE>