The flexible navigation stack is a set of components that realize specific navigation services to provide a flexibly applicable navigation capability for a service robot. The services defined (service definitions) for the navigation stack are a typical example of the Composition Tier 2 contents of the RobMoSys Ecosystem. This navigation stack can be used with various robot platforms and different kinds of sensors. Moreover, it is able to deal with unstructured and dynamic environments of variable scale. The focus hereinafter is to emphasize the general design choices and architectural decisions of the navigation stack components. After that, the following section provides some technical details and references for the concrete open-source components that can be used already now, e.g. with the Robotino3 platform.
The figure on the right illustrates the three main levels of the navigation stack. These levels describe the shared responsibilities between different parts of the navigation stack. These responsibilities are assigned top down according to the subsidiarity principle (as explained next).
The bottom level defines components (a full list is provided further below) related to the fast and reactive obstacle-avoidance navigation loop. This loop ensures that regardless of where the robot has to move next, this movement will not cause any collisions and the robot will not be commanded to execute a physically invalid movement considering the robot's kinematic and dynamic constraints. Therefore this loop will only command navigation values that never lead to a collision even if these commands might not directly lead toward the next goal (e.g. because of the need to avoid a suddenly appeared obstacle in between). Consequently, this loop might lead to a globally non-optimal, yet collision-free, navigation.
At the middle level, a geometric path planner calculates intermediate way-points based on a grid-map of the current environment. The planner relies on this map, which is updated during the navigation to accommodate for changes in the environment. A localization component estimates the current position of the robot within that maps. Several existing path-planning algorithms (using A* for example) allow the generation of intermediate way-points to be individually approached by the lower obstacle-avoidance level. In contrast to the lower obstacle-avoidance level, this intermediate geometric path planing level has a global view on the mapped environment. This is useful to e.g. avoid local minima (by generating intermediate way-points around them). It is worth mentioning that this intermediate level typically does not generate full trajectories (to be exactly executed by the lower level), but sparse intermediate way-points. These way-points are within a direct line of sight, which allows approaching them individually by the lower level without requiring a map. Overall, this enables a clear separation of concerns between the two lower levels and avoids several disadvantages with respect to wasting resources (due to e.g. too frequent need for path re-planning) continuous velocity changes and too tight (i.e., inflexible and hardly exchangeable) coupling with the lower level.
In some cases, even the intermediate level is not sufficient. For instance, if a robot needs to navigate in an entire building consisting of several floors, maybe connected over elevators, then building a single huge grid map becomes complicated, too inefficient and too resource consuming. In these cases, it is rather reasonable to calculate several smaller grid-maps (e.g. one for each level or room in the building) and to concatenate these grid-maps in a topological map (which is typically a graph). The responsibility of this top level is to provide a logical plan how to navigate through the separated maps, e.g. through levels or rooms of a building.
The separation of the navigation components into these three levels has several advantages. The levels can be composed to individual navigation solutions best fitting the needs of the application or the current environment a robot is navigating in. According to these needs the size of the stack can be changed, with the bottom level being the most versatile and configurable one. For instance, some scenarios might require to manually command a robot using a joystick. In that case, both upper levels would be replaced by a simple joystick driver component, while the collision avoidance level still validates the navigation commands. In other scenarios, a robot might always navigate in a single map only. For that the geometrical path-planner on the middle level (without the topological path planner on top) is fully sufficient. Of course, there are also scenarios where all three levels are needed. Even in these latter cases, components on the individual levels can be flexibly exchanged (even at run-time, while moving) by alternatives because of a clear separation of responsibilities on each level and due to the clear interfaces between the levels. For example, it is possible to exchange free navigation with corridor-based navigation1) to make the robot move only within predefined tracks.
The figure below illustrates the interaction of the navigation components over generic navigation services. While the navigation services are always stable, there are several alternatives for each of the navigation components (see below) that realize the same services but internally implement different algorithms. This decoupling between a component's internal implementation and the component's service-based interaction is a fundamental principle in RobMoSys that enables a flexible reuse (i.e., exchange) of components by alternatives with unique selling points and thus makes the navigation stack flexibly usable in different applications with different requirements with respect to envisioned environments and the used robot platforms.
The navigation stack consists of two hardware-related components, namely Laser and BaseServer. These two components abstract away the used hardware. While the components themselves are specific to a particular platform (e.g. Robotino3, PAL Tiago, etc.), they implement the following services that are platform-independent:
The other three navigation components implement the different capabilities of the navigation stack, namely (1) obstacle avoidance, (2) mapping, and (3) path-planning. Again, similar to the two hardware-related components above, the three components internally implement a specific algorithm and are exchangeable due to the following algorithm-independent service definitions that they individually implement:
Overall, the three navigation components BaseServer, Laser and ObstacleAviodance together realize the lowest obstacle avoidance level (see above). The Mapper, the Planner and optionally the Localization components realize the middle geometric path planning level. Finally, the upper topological path planning level is realized by a symbolic planner component.
The symbolic planner component is not only used for geometric path planning but is a generic component that is used for all kinds of combinatoric problems. This component typically directly interacts with the Task Coordination Level.
The following composition structures are directly related to the realization of the navigation stack: