Lessons Learned in Integration for Sensor-Based Robot Navigation Systems

Abstract

This paper presents our work of integration during the last years within the context of sensor-based robot navigation systems. In our motion system, as in many others, there are functionalities involved such as modeling, planning or motion control, which have to be integrated within an architecture. This paper addresses this problematic. Furthermore, we also discuss the lessons learned while: (i) designing, testing and validating techniques that implement the functionalities of the navigation system, (ii) building the architecture of integration, and (iii) using the system on several robots equipped with different sensors in different laboratories.

Keywords

Mobile robots Sensor-Based Robot Navigation Robot Architectures and Integration

1. Introduction

Robots are being developed that operate under a wide variety of conditions including unknown, unstructured and dynamic scenarios. Mobility in such scenarios is a key issue to increase the degree of autonomy of a robotic system since it is the basis to incorporate more subsystems and functionalities. Thus, the performance of the motion system strongly affects the task carried out by the vehicle. The capabilities required for the navigation of an autonomous robot are tied up with the specific application and vehicle. For example, the a priori knowledge, the sensor information, the motion constraints of the vehicle or the computational power. This usually leads to the development of specific navigation systems to accommodate the requirements of each application.

One important issue is to bound the scope of the mobility system, which is related to the differences between global and local navigation systems (Fig. 1). In fact, the concerns of these systems are different. For instance, for global systems, the construction of accurate models and the tracking of the position of the vehicle are important to create global plans and to guarantee motion convergence, while real-time execution is not. However, for local systems, simpler local models and rough planning are enough, while motion constraints related to real-time or to the vehicle such as shape, kinematics and dynamics are important to guarantee robust obstacle avoidance.

Fig. 1.

Global vs Local Sensor-Based Navigation

Nevertheless, the mobility aspect is inherently related with some functionalities necessary for a fully autonomous operation (modeling, planning and reaction). More precisely, the topic of motion in evolving environments includes issues such as knowledge representation (model construction), deliberation and reactivity. Hybrid systems (Arkin, R., 1989) attempt to combine these paradigms by including the best of the artificial intelligence to represent and use the knowledge, with the best reactivity, robustness, adaptation and flexibility. Basically these schemes combine a planner (deliberation) and a reactor (execution). This work focuses on local navigation, where hybrid approaches have been used in several systems (Ulrich, I. & Borenstein, J., 2000), (Brock, O. & Khatib, O., 1999), (Stachniss, C. & Burgard, W., 2002) or (Philipsen, R. & Siegwart, R., 2003). Our integration scheme follows this approach combining modeling, planning and reactivity:

Model builder: construction of a model of the environment (to increase the spatial domain of the. planner and used as local memory for obstacle avoidance) and tracking of the vehicle position.

Planner: extraction of the connectivity of the free space to increase the spatial domain of the solution (for instance used to avoid the trap situations).

Reactive motion: collision-free motion generation.

In this context the integration of functionalities plays a crucial role. On one hand, the three issues enumerated above are active research areas where the community continuously proposes new methods improving the current state of the art. Thus, the integration architecture must allow a quick module replacement with the most appropriated technologies for each module (they might have different properties that allow to address problems with different nature within the same context). On the other hand, all functionalities must be integrated within an architecture for specification, coordination and failure detection and recovery. The integration must have a clear specification of the interaction of the modules and time constraints. Everything together favors the portability between different platforms and sensors and the easy module replacement to add or change technologies. These are important issues when dealing with vehicles with different geometries or kinematics, or different sensors like cameras, lasers or ultrasounds. Furthermore, the architecture reduces the effort required to upgrade, test and validate new developments.

Existing works only address partially the integration issues of these navigation systems (Ulrich, I. & Borenstein, J., 2000), (Brock, O. & Khatib, O., 1999), (Stachniss, C. & Burgard, W., 2002) or (Philipsen, R. & Siegwart, R., 2003). This paper presents the evolution of our work during the last years within the context of local sensor-based navigation systems focusing on those aspects related to the integration architecture. Moreover, we show experimental results obtained with different real robots that illustrate the benefits of using an architecture of integration.

The work is organized as follows: first we present the evolution of our navigation system in Section 2. Section 3 describes the architecture. Section 4 presents the experimental results and Section 5 the conclusions.

2. Evolution of the sensor-based navigation system

The objective of a local motion system is to drive the vehicle among locations while avoiding collisions with obstacles. The operation is governed by a perception -action process repeated at a high frequency (Fig. 1). Sensors gather information of the environment (obstacles) and the robot. This information is then processed to compute the motion. The vehicle executes the motion and the process restarts. The result is an on-line sequence of motions that drives the vehicle to the destination without collisions. In this section we provide an historical perspective of the selection of the techniques, which are closely related with the problems that might be addressed to design a sensor-based navigation system (Table 1).

Table 1.
A summarized evolution of the sensor-based navigation system

Modalities

M1 M2 M3 M4 M5 M6

Modeling – Local laser memory Binary local grid Binary local grid Binary local grid IDC Probabilistic map Object tracking MbICP

Planning – – NF1 NF1 Gap navigation D*

Reaction PFM ND ND ND+Abs. Layers or MG ND+Abs. Layers or MG ND+Abs. Layers or MG

Architecture No No Yes Yes Yes Yes

	Modalities
Modeling	–	Local laser memory	Binary local grid	Binary local grid	Binary local grid IDC	Probabilistic map Object tracking MbICP
Planning	–	–	NF1	NF1	Gap navigation	D*
Reaction	PFM	ND	ND	ND+Abs. Layers or MG	ND+Abs. Layers or MG	ND+Abs. Layers or MG
Architecture	No	No	Yes	Yes	Yes	Yes

2.1 The seed of motion: M1

Some years ago we started to deal with the mobility problem of autonomous robots. For obstacle avoidance, we selected a potential field method (PFM in short) (Khatib, O., 1986). Our experience with this obstacle avoidance method (Montano, L. & Asensio, J.R., 1997) confirmed the problems that were described for this type of methods (Koren, Y. & Borenstein, J., 1991). In fact, at that time many methods exhibited problems to address the motion in troublesome scenarios. Thus, we understood that the first step was to design a method to close the research gap of reactive motion in dense, complex and cluttered scenarios.

2.2 Motion in Troublesome scenarios M2

To address this issue we developed the Nearness Diagram Navigation method (ND) (Minguez, J. & Montano, L., 2004). This technique employs a “divide and conquer” strategy to simplify the navigation by identifying situations and applying the corresponding motion laws. The set of situations represents all the cases between robot positions, obstacles and the goal (navigational situations). In addition, for each of these cases a motion law (action) is associated. Thus, this technique avoids most of the problems that other techniques present in complex navigation situations (see (Minguez, J. & Montano, L., 2004) for a discussion on this topic).

With this new technique, we were able to address motion in places where it was difficult to maneuver vehicles. However, the problems of trap situations and cyclic behaviors were unavoidable due to the local nature of the obstacle avoidance methods.

2.3 Trap situations and cyclic behaviors: M3

With this problematic in mind, we realized that it was necessary to integrate local planning with obstacle avoidance. Besides, building a local model would also increase the spatial domain of the planner while acting as a memory for the obstacle avoidance method (sensor visibility constraints). The necessity of integrating these functionalities was the beginning of the work described in this paper. We proposed the Global Nearness Diagram Navigation (GND), (Minguez, J. & Montano, L., 2005).

The GND implements a hybrid architecture with three layers (modeling, planning and reaction). The modeler constructs a representation of the environment integrating the sensory information, which is the base for the rest of modules. We used a robot-centred binary occupancy grid updated whenever a new sensory measurement is available. The planner computes tactical information to direct the vehicle. We implemented the Navigation Function 1 (NF1), (Barraquand, J. & Latombe, J.C., 1989), which is free of potential minima, can work on a grid (existing representation), and can be efficiently executed in real time. The reactor (obstacle avoidance) computes the collision free motion. We used the ND since it is efficient and robust in environments with little space to maneuver.

The key result was the integration of the modules in a unified system (Section 4 provides a detailed description of the architecture). This integration concentrates the best of the deliberative and reactive worlds, since the planning information helps to guide the motion toward zones without traps, and the reactive component quickly directs the execution according to the evolution of the environment. The advantage of this system was to perform robust and trustworthy navigation in difficult scenarios.

2.4 The vehicle constraints: M4

At this moment, we addressed the portability of the motion system to different platforms. In order to generate robust obstacle avoidance, the vehicle constraints (shape, kinematics and dynamics) could not be ignored. For this reason we included the vehicle constraints within the obstacle avoidance paradigm with the Abstraction Layers (Minguez, J.; Montano, L. & Santos-Victor, J., 2005) and (Minguez, J. & Montano, L., 2003); and a Motion Generator (MG) (Minguez, J & Montano, L., 2002).

The ND and many existing techniques assume that the robot is a point free of any constraint (omnidirectional motion). The idea behind the Abstraction Layers is to abstract these constraints the collision avoidance methods. The solution is to encapsulate the constraints within the spatial representation. By doing this, we transform the three-dimensional obstacle avoidance problem with shape, kinematics and dynamic constraints into the simpler problem of moving a point in a two dimensional space without constraints (usual approximation in obstacle avoidance). Thus, many existing methods that do not address these constraints can be applied in this representation. The consequence is that the methods take into account the vehicle constraints without being redesigned (the information is implicitly represented in the application space). Alternatively, the motion generator MG is based on a dynamic motion controller that converts the solution of the obstacle avoidance method into a command that complies with the vehicle kinematics and dynamics.

With these new techniques integrated in the previous system, we took into account the vehicle constraints in the obstacle avoidance module. In parallel, we ameliorated our previous ND version leading to the ND+ (Minguez, J.; Osuna, J. & Montano, L., 2004). The ND+ method improved the previous method with new navigational situations and a new design of the motion laws. Another advantage of the ND+ method is its efficiency that liberates computational resources for the other modules of the architecture.

2.5 Local correction of the vehicle localization and time requirements: M5

At this point in time, the precision of the localization of the vehicle became a serious limitation. In order to deal with vehicles with bad odometry information, it was necessary to correct the robot pose. Models built only with odometry accumulate errors. As the model is the base of the planning and obstacle avoidance methods, it strongly affects the performance of the system. At this point, time constraints were another important issue. The planning method was computationally very demanding and we investigated more efficient planners that do not penalize the reactivity and modeling performance of the system.

To improve the localization of the vehicle, we integrated a scan matching technique that improves the odometry readings using the information provided by the sensors. We used the Iterative Dual Correspondence (IDC) algorithm (Lu, F. & Milios, E., 1997). This technique does not require extracting any specific kind of features and, consequently, is well suited to unstructured environments. Although these techniques do not guarantee global consistency in the model, its precision is enough to build the local map needed by the other modules.

Furthermore, we developed a planner (Minguez, J.; Montesano, L. & Montano, L., 2004) independently but similar to the Gap Navigation Trees (Tovar, B.; Guilamo, L. & LaValle, S.M., 2004). The idea behind this planner is to construct a graph of reachable points of the space, instead of an analytical path as many classical planners do. The graph contains enough tactical information to avoid the trap situations. The advantage of this planner is the computation time since in average is more efficient than computing a path from scratch with a navigation function.

2.6 Dynamic scenarios: M6

The previous systems do not differentiate between the static structure of the environment and the moving objects.

Reactivity against changes in the environment is achieved through a high sensing frequency. However, when dealing with dynamic scenarios, taking into account the nature of the obstacles might ameliorate the performance of the system. A reliable solution must address both: a module able to model the static and dynamic parts of the scenario, and a way to use this information within the system.

First, we designed a modeling module that carries out the detection and tracking of moving objects and the mapping of the static parts at the same time (Montesano, L.; Minguez, J. & Montano, L., 2005). We used a maximum likelihood approach that complies with the spatial and time constraints of the local navigation system. As a result we obtain a map of static obstacles and a separate map of dynamic objects and their velocities. Within this process, we integrated a new scan matching (Minguez, J.; Lamiraux, F. & Montesano, L. 2005), the Metric-based Iterative Closest Point (MbICP), that ameliorates the IDC performance.

The other modules selectively use the dynamic/static information of the modeler. The role of the tactical planner is to determine at each cycle the main cruise to direct the vehicle. Therefore, the planner only uses the map of static features. The obstacle avoidance method generates the collision-free motion to align the vehicle toward the cruise (computed by the planner). Here we use the map of static obstacles, since all the obstacles included in the map must be avoided. Furthermore, we use information of the dynamic obstacles, but taking advantage of their velocity by projecting their position to the collision point with the vehicle.

At the same time we explored the use of the D* Lite planner (Koenig, S. & Likhachev, M., 2002). The principle of this planner is to locally modify the previous path (available from the previous step) using only the changes in the environment. This strategy is by far more efficient than re-computing the path from scratch This is the current state of the art of our system.

3. Architecture design

This section describes the architecture of the navigation system focusing on those aspects related with the integration of the different functionalities and their interactions. The system has been designed to work on a single node. This is because many applications in which autonomous motion systems operate are safety-critical (Storey, N., 1996) and involve real-time constraints. Furthermore, the modules are executed synchronously. This is important to avoid inconsistencies in time that would arise using asynchronous strategies (the model is used for local planning and obstacle avoidance and must be consistent in time with both modules). Fig. 2 presents an overview of the high level architecture. It represents the three main processing modules and the control and data flows between them. The control flow follows the modeler-planner-reactor sequence and progress unidirectionally from the modeler toward the planner and obstacle avoidance modules.

Fig. 2.

Overview of the architecture: interaction between modules and data flows

The exact data structures of depend on the technologies used (see Table 1). These structures define the interactions and dependencies among the modules. Replacing a module requires complying with the interface and usually does not require redefining it. For instance, sets of points are a common way to represent obstacles for several obstacle avoidance methods (modeler-reactor interface). The interface between the planner and reactor is a subgoal location (tactical information). With respect to the modeler-planner interface, we use a grid. Although there exist many other representations, grids are commonly used to compute navigation functions and are able to represent dense information. The bandwidth required by each flow varies depending on the modules but remains reasonable (under kilobytes per second).

The class diagram of Fig. 3 shows the static design of our motion system. The proposed design can be reused to implement a sensor-based motion system as the one described in this paper.

Fig. 3.

Class diagram of the architecture

So as to comply with the time constraints and close the motion control loop at the desired sensor rate, we assigned timeouts to the UpdateMap() and ComputePath() methods. Its main purpose is to assure that the obstacle avoidance module is executed every cycle. This is important since the motion of the system is always generated by the avoidance method (assuring collision free motion). The scenario of Fig. 4 shows the main loop iteration of the system in the case where the timeouts are not launched.

Fig. 4.

Scenario of an iteration and time constraint.

The system also has to manage failures (Fig. 2). Currently, our architecture includes the following ones:

Hardware failure: In case of bad operation of the sensors or the engines, an emergency stop is executed stopping the vehicle as fast as possible.

Modeling module failure: Failures of this module are hard to identify and depend on the implementation. When a failure occurs or the time out is launched, the strategy is to use odometry to keep track of the vehicle position and to re-initialize the map with the last measurement.

Planning module failure: A failure of this module arises when the planner does not find a solution, either because it does not exist (for example when the goal falls on an obstacle) or because the time out is launched. In this case the information of the planner is not used and the obstacle avoidance tries to move the vehicle directly toward the goal.

Reactive module failure: This failure occurs when the robot is completely surrounded by obstacles and there are no areas of motion free of collision. The vehicle does not progress until a new passage is detected.

Summarizing, the architecture decouples the functional modules necessary for the motion generation and assures their correct interaction and coordination. It also specifies the interfaces with the external modules and hardware devices. The benefits of the integration within the architecture are: (i) to ease the integration of research works developed by different people, (ii) to improve the software engineering processes specially the final stages of the software life cycle, (iii) to facilitate portability issues.

4. Experimental validation

The purpose of this section is to demonstrate that the navigation system successfully carries out the motion task and to show some of the benefits of the architecture: (i) how the architecture allows to easily replace modules and to stay in the cutting edge technologies for local sensor-based motion systems, and (ii) to discuss the portability among different platforms on the basis of the experimental validation obtained in different laboratories (Fig. 5).

Fig. 5.

Some of the platforms where the motion system has been integrated

Firstly, we integrated and tested the system in seven robots at three different laboratories (Minguez, J. & Montano, L., 2002). Fig. 5 shows some of the vehicles where the motion system has been used. In all the cases, the results were very satisfactory from the motion execution point of view. The vehicles successfully achieved the motion task in unknown, unstructured and dynamic scenarios, where maneuvering was a determinant factor.

One of these implementations has been used daily in a museum for several months (Clodic, A.; Fleury, S.; Alami, R.; Herrb, M. & Chatila, R., 2005), and others are daily used for demonstrations (Alami, R.; Belousov, I.; Fleury, S.; Herb, M.; Ingrand, F.; Minguez, J. & Morisset, B., 2000) and (Montesano, L.; Minguez, J. & Montano, L., 2005).

Secondly, with this architecture we have been able to integrate our on going research. This is a key issue in developing time. Thanks to this architecture we have been able to design, integrate, test and validate more than 20 technologies in the last four years in our robots and in robots of other laboratories (Table 1 and Fig. 5).

Thirdly, another issue is the portability among different vehicles. This includes the following aspects:

Vehicle constraints: the shapes of the robots are circular, square or rectangular. The kinematics are holonomic or differential-drive. The dynamics are also different for all the vehicles.

Sensors: used sensors include ultrasounds, 2D and 3D range finders and a stereovision system.

Operating systems and computer capabilities: different operating systems (Linux, Solaris, VxWorks or Windows) were installed in the robots. The power of the on board computers ranged from a single Pentium II at 200MHz to a Pentium IV at 800MHz.

In order to integrate the navigation system in the different vehicles, the first important issue was to take into account the vehicle shape, kinematics and dynamics for obstacle avoidance. This is important since the vehicles where the motion system was tested had different geometries like circular, square or rectangular. Furthermore the vehicles ranged from omnidirectional to differential-drive, and all of them had very different dynamics. These facts impose different constraints in the motion planning aspect that have to be taken into account. This was easily achieved with the architecture by activating/deactivating the abstraction layers or the motion generator that take into account these issues.

In the vehicles used in the experiments the sensors ranged from ultrasounds and lasers to cameras. The usage of different sensors required using the appropriate sensor interfaces. Nevertheless, if the type of data needed a specific processing, the modeling module had to be replaced too. For instance, for the lasers we used the solution described in this paper and we adopted other solutions for the ultrasounds (Borenstein, J. & Koren, Y., 1991) and for the cameras (Haddad, H.; Khatib, M.; Lacroix, S. & Chatila, R., 1998). This is important since the information given by these three sensors is far different and any of them requires a processing step. The important point is that changes affected only to the model builder and the corresponding interfaces.

5. Conclusions

In this paper we have proposed an architecture to integrate the functionalities required to perform local sensor-based navigation. The architecture decouples the main functionalities of the system, defines their interfaces and assures their correct interactions. It provides a framework to continuously upgrade the system with new developments in the field, to ease the development process and to migrate it among different platforms. Currently we are transferring some of the functionalities described in the paper to the Stage/Player project¹. We understand that this is a clear indicator of the maturity of the techniques and their successful integration in many different systems.

In addition, we have presented an historical perspective of the technologies and their main characteristics together with the lessons we learned. The requirements extracted from our experience during the development of the motion system (portability, real time constraints, adaptability, modularity) led to the design proposed in the paper.

Footnotes

Acknowledgments

We thank José Merseguer for the fruitful comments and discussions in preparing this manuscript. This work was partially supported by MCYT DPI2003-7986.

1

References

Alami

Belousov

Fleury

Herb

Ingrand

Minguez

& Morisset

(2000). Diligent: Towards a human-friendly navigation system. In IEEE-RSJ Int. Conf. on Intelligent Robots and Systems, pages 2094–2100, Takamatsu, Japan.

Arkin

(1989). Towards the unification of navigational planning and reactive control. In Working Notes of the AIII Spring Symposium on Robot Navigation, pages 1–6, Stanford University.

Barraquand

& Latombe

J.C.

(1989). On nonholonomic mobile robots and optimal maneuvering. In Intelligent Symposium on Intelligent Control, pages 340–346, Albany.

Borenstein

& Koren

(1991). Histogramic in-Motion Mapping for Mobile Robot Obstacle Avoidance. IEEE Journal on Robotics and Automation, 7(4):535–539.

Brock

& Khatib

(1999). High-Speed Navigation Using the Global Dynamic Window Approach. In IEEE Int. Conf. on Robotics and Automation, pages 341–346, Detroit, MI.

Clodic

Fleury

Alami

Herrb

& Chatila

(2005). Supervision and interaction: Analysis from an autonomous tour-guide robot deployment. In International Conference on Advanced Robotics, Seattle, USA.

Haddad

Khatib

Lacroix

& Chatila

(1998). Reactive Navigation in Outdoor Environments Using Potential Fields. In IEEE Int. Conf. on Robotics and Automation, volume 2, pages 1232–1237, Leuven, Belgium.

Khatib

(1986). Real-Time Obstacle Avoidance for Manipulators and Mobile Robots. Int. Journal of Robotics Research, 5:90–98.

Koenig

& Likhachev

(2002). Improved fast replanning for robot navigation in unknown terrain. In International Conference on Robotics and Automation, Washington, USA.

10.

Koren

& Borenstein

(1991). Potential Field Methods and Their Inherent Limitations for Mobile Robot Navigation. In IEEE Int. Conf. on Robotics and Automation, volume 2, pages 1398–1404, Sacramento, CA, 1991.

11.

& Milios

(1997). Robot pose estimation in unknown environments by matching 2d range scans. Intelligent and Robotic Systems, 18:249–275.

12.

Minguez

& Montano

(2002). Robot Navigation in Very Complex Dense and Cluttered Indoor/Outdoor Environments. In 15th IFAC World Congress, Barcelona, Spain.

13.

Minguez

& Montano

(2003). The Ego-KinoDynamic Space: Collision Avoidance for any Shape Mobile Robots with Kinematic and Dynamic Constraints. In IEEE-RSJ Int. Conf. on Intelligent Robots and Systems, Las Vegas, USA.

14.

Minguez

& Montano

(2004). Nearness Diagram (ND) Navigation: Collision Avoidance in Troublesome Scenarios. IEEE Transactions on Robotics and Automation, 20(1):45–59.

15.

Minguez

& Montano

(2005). Autonomous sensor-based motion control in unknown, dynamic and troublesome scenarios. Journal of Robotics and Autonomous Systems, (Elsevier), 52(4), 290–311.

16.

Minguez

Montano

& Santos-Victor

(2005). Abstracting the Vehicle Shape and Kinematic Constraints from the Obstacle Avoidance Methods. To appear in J. on Autonomous Robots.

17.

Minguez

Montesano

& Montano

(2004). An architecture for sensor-based navigation in realistic dynamic and troublesome scenarios. In IEEE Int. Conf. on Intelligent Robot and Systems, Sendai, Japan.

18.

Minguez

Osuna

& Montano

(2004). A Divide and Conquer Strategy to Achieve Reactive Collision Avoidance in Troublesome Scenarios. In IEEE International Conference on Robotics and Automation, Minessota, USA.

19.

Minguez

Lamiraux

& Montesano

(2005). Metric-Based Scan Matching Algorithms for Mobile Robot Displacement Estimation. In IEEE International Conference on Robotics and Automation. Barcelona, Spain.

20.

Montano

& Asensio

J.R.

(1997). Real-Time Robot Navigation in Unstructured Environments Using a 3D Laser Rangefinder. In IEEERSJ Int. Conf. on Intelligent Robots and Systems, volume 2, pages 526–532, Grenoble, France.

21.

Montesano

Minguez

& Montano

(2005). Modeling the static and the dynamic parts of the environment to improve sensor-based navigation. In IEEE International Conference on Robotics and Automation.

22.

Philipsen

& Siegwart

(2003). Smooth and efficient obstacle avoidance for a tour guide robot. In IEEE Int. Conf. on Robotics and Automation, Taipei, Taiwan.

23.

Stachniss

& Burgard

(2002). An Integrated Approach to Goaldirected Obstacle Avoidance under Dynamic Constraints for Dynamic Environments. In IEEE-RSJ Int. Conf. on Intelligent Robots and Systems, pages 508–513, Switzerland.

24.

Storey

(1996). Safety-Critical Computers Systems. Reading, MA: Addison-Wesley.

25.

Tovar

Guilamo

& LaValle

S.M.

(2004). Gap navigation trees: Minimal representation for visibility-based tasks. In Workshop on the Algorithmic Foundations of Robotics.

26.

Ulrich

& Borenstein

(2000). VFH∗: Local Obstacle Avoidance with Look-Ahead Verification. In IEEE Int. Conf. on Robotics and Automation, pages 2505–2511, San Francisco, USA.