A Qualitative Approach to Sensor Data Fusion for Mobile Robot Navigation

1 Introduction

Often metrical information (from either sensory cues or models) is either incomplete, inaccurate or hard to in­ terpret and navigation using purely quantitative tech­ niques is fragile [Elfes, 1987; Leonard and Durrant­ Whyte, 1992]. Quantitative models tend to produce ei­ ther descriptions which are too accurate for the task at hand or, in the case when information is incomplete, no descriptions at all. Robust navigation is possible only when the robot is able to construct accurate models ap­ propriate to the detail of its sensing information. A qual­ itative description of the processes can be sufficient to constrain the robot to perform to a certain specification

This work is supported by EPSRC grants GR/J/46067 and GR/J/57773.

(i.e. avoid collisions and move along a corridor) without over constraining and forcing the robot to follow exacting metrical descriptions. However, qualitative descriptions can be ambiguous. In such circumstances quantitative information can be used to constrain the models further.

Qualitative navigation, where the emphasis is on building, maintaining and planning with topological de­ scriptions of the environment have been studied [Dai , 1993; Kuipers and Byun, 1991]. These approaches gener­ ally rely on the identification of distinctive objects (land­ marks) which are either individual features or places. These landmarks are inter-connected by procedural in­ formation describing travel routes between them. The choice of landmark is sensor dependent since different modalities detect different significant features in the en­ vironment. It is important, therefore, to avoid a central composite representation. We adopt a sensor centric rep­ resentation and reason with qualitative abstractions of the sensor cues.

Sensor data fusion can be viewed as the assimilation of constraints from two or more information sources whether quantitatively described using statistics, nu­ meric intervals or qualitative information describing rel­ ative changes. Their conjunction is a more refined esti­ mate of the parameter. An empty conjunction signifies either an incomplete model or a faulty sensor. We use the qualitative inference engine QSim [Kuipers, 1993] to infer the qualitative behaviours of sensory cues and then show how information can be assimilated at the qualita­ tive and quantitative levels.

We apply our approach to the sonar range sensing do­ main and demonstrate data fusion between propriocep­ tive and external sensing modalities. In section 2 we in­ troduce the sonar model. Then, in section 3 we present the qualitative model of how sonar cues are related to odometric (translational motion) and gyrometric (rota­ tional motion) proprioceptive cues . Finally, we will show how these models can be used to (a) infer the rules of navigation and (b) fuse senor maps at both the qualita­ tive and quantitative levels. Throughout we will refer to a real robot application and illustrate using real data.

2 The Sonar Model

For a typical in-air sonar there is no obvious direct cor­ respondence between the environment and the recorded range measurements. Figure 1, for example, shows a sonar scan of a simple environment. However, from this scan it can be seen that the range measurements for re­ flections perpendicular to the walls at a, b, c and d in the figure, the edge at e and corners at/, g and h are in close correspondence to distance between the sensor at + and the reflectors. Further, range values are equal over a range of bearings each side of these points. This phe­ nomenon has been noted in [Kuc and Siegel, 1987] and [Leonard and Durrant-Whyte, 1992] and the latter has coined the phrase the region of constant depth (RCD) . An RCD is a contiguous sequence of bearings with equal range values (RCD formations in the sonar map for a room in Figure 1 and a robot at'+', are shown in bold). They are formed because the sonar beam is wide and during a sweep scan a tiny part of the reflector is vis­ ible over a finite sequence of bearings. Since the sonar wavelength is large compared to reflector surface fluctua­ tions walls behave like specular (i.e. mirror like) objects. Imagine walking through the room depicted in Figure 1. When walking towards location Y, for example, the RCD at a would move abreast of the observer. The edge at h would appear to move away from the observer.

As a robot moves through the environment the RCDs move predictably. RCDs formed by reflections from walls move tangentially with the wall and abreast of the robot. Corner and edge RCDs rotate about the point of re­ flection. This is apparent in Figure 2 which shows the overlay of a set of RCDs taken from various positions in the environment. What is evident here is that the door-frame at i, which is not an obviously significant feature in a global geometric map, is the most signif­ icant feature to a sonar. Conversely, the wall at c is significant in geometric terms, but is very weak to a sonar . Leonard [1992] demonstrates how a robot can navigate by tracking RCDs as the robot moves. The es­ sential point here is that the information obtained by a sonar does not correspond well with the underlying ge-

'

ometry of the environment. However, the information (i .e. RCDs) are predictable and have motion patterns which are well understood consequences of the under­ lying physics of the sensing process. In Section 3 we show how RCD range and bearing information to the same feature at different locations can be related to the robot's translational and rotational speed by two ordi­ nary differential equations.

3 The Qualitative Model

Leonard [1992] introduces a unified description of plane, edge and corner sonar reflectors. This is the generalised cylinder in which planes are cylinders with infinite radius and edges and corners are cylinders with zero radius. Equations 1 and 2 relate the radius of a cylinder r and

the perpendicular distance from its surface R to a robot moving with translational speed 8 8 ~ and rotational speed ¥t (see Figure 3) .

These equations form the basis for qualitative navi­ gation. From these we can use qualitative simulation techniques to construct a set of qualitative rules which can be used to constrain the qualitative interpretation of sensor measurements.

QSim [Kuipers 1 1993] is a qualitative simulation pack­ age which generates qualitative behaviours from qualita­ tive descriptions of the continuously differentiable equa­ tions governing the system and guarantees soundness though not completeness. Variable values are denoted by landmarks and intervals between landmarks and variable derivatives are either increasing (inc) , decreasing (dec) or steady ( std) . We shall use the notation ( Qv Qd) to de­ note a qualitative variable with value Qv and derivative Qd.

To implement the interpretation of qualitative sensor cues, QSim was extended to deal with persistently in­ finite variables. QSim treats infinities as point values and, therefore, a variable cannot remain at infinity and be decreasing simultaneously. It is not possible to rep­ resent plane reflectors in such a system since (R + r) in Equations 1 and 2 is infinite but not necessarily constant. In general , we want to allow behaviours for A(t) when A(t) = limx-.ooX + B(t) and A(t) remains infinite but ~~ < 0 or ~~ > 0. This is achieved by allowing the in­ finity landmarks to be both successors and predecessors of themselves in QSim quantity spaces.

Each variable in Equations 1 and 2 is assigned sensor centric landmarks. The angle type landmarks charac­ terise orientation: left, forward, right and behind. The quantity spaces are shown in table 1. The zero angle landmark means forward in QSim notation. The reflec­ tor type landmarks 0 and inf denote edges (and corners) and planes respectively.

Figure 4 shows the qualitative behaviours obtained from Equations 1 and 2 for a robot moving with zero angular velocity (i.e. ¢J = (0 std)) towards a plane

RangeR Reflector bearing 8 Travel bearing ~ Reflector type r Travel distance D { 0, in£ } { behind*, right, 0, left , behind } { behind*, right, 0, left , behind } { 0, inf} { 0, in£}

and past a cylinder and an edge. The top three graphs in Figure 4 ( behl) show the qualitative behaviour for the case of the plane RCD. In the top left graph behl-var-r:reflector-type, the generalised cylinder radius is infinite and steady corresponding to a plane reflector. Graph behl-var-R:range shows that the range value de­ creases and graph behl-var- Th:bearing shows us that the bearing () to the plane remains constant . For plane re­ flectors the RCD moves tangentially to the reflector and abreast of the robot and this is the reason why () , in this case, is constant.

The second row of graphs ( beh2) describe the be­ haviour of an edge (or corner) RCD. In the middle left graph beh2-var-r:refiector-type, the generalised cylinder radius is zero and steady corresponding to an edge reflec­ tor. In beh2-var-R:range we see that the range gradually decreases until some time point t1 and then increases in­ definitely. This corresponds to a robot moving towards a point like object fixed in space, passing close to it and then moving away from it . In graph beh2-var-th:bearing we can see that this RCD moves gradually further to the left and then recedes behind. The third row of graphs ( beh3) shows the RCD behaviour for an arbitrary cylin­ der of finite radius.

In general, purely qualitative information is insuffi­ cient to differentiate reflector types for small odometric displacements. It is impossible to determine, for exam­ ple, whether a change in bearing is due to the motion of an edge or noisy data from a plane reflection. However, numerical information can be used to distinguish these cases. Using Q2 [Kuipers, 1993] we can estimate nu­ merical bounds for future bearing readings from current values for each type of reflector and thus disambiguate the types of observed reflectors. This is crucial for navi­ gation by feature tracking.

4 Qualitative Navigation

In the previous section we demonstrated that a robot can predict the behaviour of RCDs from a qualitative relationship between its sensor cues. In this section we show how this mechanism can be used in path planning by utilising a sensor centric behavioural description of the robots motion towards a goal state. The robot nav­ igates by following single reflectors or moving between pairs of reflectors and so we are interested in the mo­ tion of single RCDs and the differential motion of RCDs between pairs of reflectors. This approach can be imple­ mented as a generic two object qualitative differential equation. We illustrate this by showing how a robot can plan qualitatively to pass between two objects by pre­ dicting its sensor cue behaviours under the constraint that collisions should be avoided (i.e. R=O is a QSim unreachable condition).

Figure 5 shows a plane (P) lying initially frontal-left and a narrow cylinder ( C with r = 0) lying to the frontal­ right of the robot . The goal is to pass between both ob­ jects without colliding with either. The goal state is that the plane is left-rear and the cylinder is right-rear. We build a combined two object qualitative differential equa­ tion from Equations 1 and 2 in which both range-bearing pairs are related by shared translational and rotational speed variables. We constrain the envisionment further by insisting that the speed and angular velocities remain constant.

One possible QSim generated behaviour is shown in · Figure 6. The robot turn rate ¥t is shown in the bot­ tom left graph and indicates that the robot should maintain a gradual turn to the right. The robot would ex­ pect to observe decreasing range cue values to both the cylinder and the plane initially (i.e. in graphs Rl :range and R2:range R1 = R2 = ((0 in f) dec)) in the time interval (tO t2)). The bearing of both features would gradually increase until the robot finds itself at its clos­ est approach to both features simultaneously (i.e. where the range values are steady at time t2). At this stage the plane would be parallel to the direction of motion since 82 = left . The robot would then observe R1 and R2 begin to increase and 82 = ((left behind) inc) in­ dicating that it has turned away from the plane and is moving away from both objects. The top left plot in figure 6 shows the rate of change of the angle sub tended by the plane and cylinder RCDs at the robot. As ex­ pected for motion between two objects this angle should increase throughout the simulation. In summary, this is a specification of a path which allows the robot to safely navigate between the plane and the cylinder by keeping the cylinder to its right and the plane to its left.

5 Quantitative Sensor Data Fusion

In section 3 we described how landmark values from each of the sensory modalities can constrain the allowed val­ ues and directions of change of other landmarks. In this section we show how numeric information can be included in the assimilation process in situations when qualitative information is ambiguous .

Since the radius of a cylinder can take values close to 0 or infinity the cylinder RCD can behave very much like an edge or a plane RCD. It is necessary, therefore, to utilise more information about the cylinder in order to use it for tracking purposes. By determining the radius of the cylinder numerically the robot is able to predict numeric values for its future sonar range and bearing cues. Such numeric constraints can be used to constrain both the estimated qualitative and estimated quantitative values of the sensory cues for the other sensors in the system.

To illustrate this, Figure 7 shows range-bearing plots for the robot at positions A, B and C in the environ­ ment shown in figure 8. Feature X is a cylindrical re­ flector near the centre of the room. The robot moves in a straight line a distance Odo E [1.1, 1.2] between each position, starting at A. At each position it records the range and bearing to the cylinder at X. Table 2 shows the sonar range and bearing to the cylinder at each position A, B and C. The notation [L, U] denotes a closed interval on the reals with lower-bound L and upper-bound U.

Using Q2 (a derivative of QSim), it is possible to nav­ igate by tracking the cylinder. Information obtained at positions A and B can be used to infer numerical bounds for the radius r of the cylinder. These bounds can then be used to estimate numeric bounds for its range and bearing when the robot is at position C.

Q2 predicts the radius of the cylinder r E [0.0, 1.05) after observing it from positions A and B. This esti­ mate is then fed back into QSim with the range and bearing coordinates to the cylinder from position B . The Q2 generated estimates from position C are range Rc E [0.90, 2.93) and bearing Be E [-2.88, -1.79) which are consistent with the measured values in table 2. The QSim plots for range and bearing are shown in figure 9. In this figure the robot is at position B at time TO and position C at time T3 .

Further information can be gleaned from the quanti­ tative constraints. For example, it is clear from figure 9 that the robot achieved its closest approach to the cylin­ der between positions B and C (at time tl) .

6 Conclusion

RCDs within the same class (i.e. edge type or plane type) exhibit identical qualitative behaviours. Reason­ ing with such invariants can be useful in situations where quantitative approaches are fragile. However, although qualitative interpretations of sensory cues is advantageous it can only complement and not replace the quan­ titative information available.

We have demonstrated that qualitative descriptions of sensor cues can be used in the sensor fusion and nav­ igation tasks. In [Reece and Durrant-Whyte, 1995] we apply this approach to the map building and localisation problems.

Acknowledgements

We would like to thank Prof. B. Kuipers for provid­ ing the QSim software and J . Leonard for providing the ultrasonic sonar data.