IEEE TransACTIONS ON ROBOTICS AND AUTOMATION, VOL. 17, NO. 6, DECEMBER 2001

Data Association in Stochastic Mapping Using the Joint Compatibility Test Josй Neira and Juan D. Tardуs

Abstract--In this paper, we address the problem of robust data association for simultaneous vehicle localization and map building. We show that the classical gated nearest neighbor approach, which considers each matching between sensor observations and features independently, ignores the fact that measurement prediction errors are correlated. This leads to easily accepting incorrect matchings when clutter or vehicle errors increase. We propose a new measurement of the joint compatibility of a set of pairings that successfully rejects spurious matchings. We show experimentally that this restrictive criterion can be used to efficiently search for the best solution to data association. Unlike the nearest neighbor, this method provides a robust solution in complex situations, such as cluttered environments or when revisiting previously mapped regions. Index Terms--Data association, Mahalanobis distance, nearest neighbor, stochastic mapping.

I. INTRODUCTION

T HE USE of a sensor mounted on a vehicle to build and update a map of the environment where the vehicle is

navigating poses a specially daunting data association problem. Data association consists of relating sensor observations with the elements included in the map. Obtaining a correct solution

is crucial, because a misassignment causes location estimation

methods, such as the extended Kalman filter (EKF), to diverge [1]. Data association may be posed as a search problem in the

space of observation-feature correspondences [2]. The com-

plexity of finding correspondences between a set of sensor

measurements and map features is exponential on the number

of measurements: if there are

possible pairings for the th

measurement (allowing repetitions and including the possibility

that it be spurious), the correct hypothesis is to be found among

an exponential space of

alternatives. Two main

factors determine the size of the solution space:

1) Clutter: both and are proportional to the density of features in the environment. 2) Imprecision: also grows with the imprecision of the

vehicle location and of the sensor being used.

Manuscript received December 7, 2000; revised July 11, 2001. This paper was recommended for publication by Associate Editor J. Leonard and Editor S. Hutchinson upon evaluation of the reviewers' comments. This work was supported in part by Spanish Direcciуn General de Investigaciуn, project DPI20001265. This paper was presented in part at the IEEE International Conference on Robotics Automation, Workshop W4: mobile robot navigation and Mapping, San Francisco, CA, April 2000. The authors are with the Departamento de Informбtica e Ingenierнa de Sistemas, Universidad de Zaragoza, E-50015 Zaragoza, Spain (e-mail: [email protected]; [email protected]). Publisher Item Identifier S 1042-296X(01)10913-4.

A data association algorithm is composed of two elements: a

test to determine the compatibility between a sensor observation

and a map feature given an estimation of the vehicle location,

and a selection criterion to choose the best matchings among

the set of compatible matchings.

In stochastic mapping [3], this problem is frequently ad-

dressed using the gated nearest neighbor (NN) algorithm, a

classical technique in tracking problems [1]. The normalized

squared innovation test is used to determine compatibility, and

then the NN rule (smallest Mahalanobis distance) is used to

select the best matchings. This technique, sometimes along

with additional heuristics, such as accepting matchings only

for observations with a single candidate map feature, has been

used by many authors [4][7].

The great advantage of this solution, apart from its conceptual

simplicity, is its

computational complexity. However, a

very important fact is being overlooked: the innovations in the

matchings of different observations obtained from the same ve-

hicle position are correlated. As we show in Section III, this

causes the individual innovation compatibility test to be too per-

missive: it easily accepts hypotheses formed by mutually incon-

sistent pairings, which leads to divergence in the estimation of

the state.

The power of this test to detect spurious matchings decreases

as vehicle imprecision or clutter grow. NN is reliable for features

such as segmented walls from laser sensors, where clutter is low

and sensor precision is high, as long as vehicle error is moderate

[5]. However, its reliability quickly plummets as the uncertainty

of features relative to the vehicle increases, as is always the case

when revisiting previously mapped regions after a long loop.

Reliability also plummets when using less precise sensors, such

as sonar [8], or edge-based monocular vision [9].

More robust algorithms have been proposed, such as multi-

tracking, which obtains hypotheses where temporal coherence

is guaranteed. Multitracking actually increases complexity,

since it is necessary to maintain one map per hypothesis [10],

[11]. Sensor-specific solutions, such as visual tracking [12],

can perform local data association very efficiently, but cannot

be used to solve the crucial revisiting problem. Alternative

approaches search for the best solution in the vehicle pose

space rather than in the correspondence space [13][15].

In other approaches, geometric constraints between features

are used to obtain hypotheses with pairwise compatible pairings.

Baley et al. [16] consider relative distances and angles between

points and lines in two laser scans and use a graph theoretic ap-

proach to find the largest number of pairwise compatible pair-

ings. Castellanos and Tardуs [17] also use binary constraints to

localize the robot with an a priori map using an interpretation

1042296X/01$10.00 © 2001 IEEE

NEIRA AND TARDУS: DATA ASSOCIATION IN STOCHASTIC MAPPING USING THE JOINT COMPATIBILITY TEST

891

tree approach. However, pairwise compatibility does not guarantee joint compatibility [2], and additional validations are required. In this work we define a criterion that, taking explicitly into account the correlations between the innovations, determines the joint compatibility of a set of pairings. We show that this criterion is much more restrictive than the individual innovation test, and that it can be efficiently computed. The use of this criterion in a branch and bound (BB) search algorithm results in a very robust solution to data association, with an efficient traversal of the solution space. We compare both the robustness and efficiency of the NN and BB algorithms in an experiment with a Labmate mobile robot equipped with a trinocular vision system, building a map along a loop trajectory of 60 m. We show experimentally that in simple situations both algorithms are robust, with equivalent performances. When there is an increase in clutter and/or imprecision, NN breaks down, while BB maintains its robustness, with a computational cost that is acceptable for real-time applications.

II. THE CLASSICAL NEAREST NEIGHBOR APPROACH

A. Problem Definition

In stochastic mapping [3], [6], the state of a vehicle and

of a set of features

of the environment where

the vehicle is navigating is represented by a vector . Let be

the estimation of the vehicle and feature locations, and the

covariance of the estimation error

which states that the relative location between the measurement

and the corresponding feature must be zero.

The purpose of a data association algorithm is to generate a

hypothesis

that pairs each measurement

with a map feature (when

, the measurement is

considered spurious). This exponential solution space can be

represented as an interpretation tree of levels [2]; each node

at level , called an -interpretation, provides an interpretation

for the first measurements. Each node has

branches,

corresponding to each of the alternative interpretations for mea-

surement (including the possibility that the measurement be

spurious and allowing map feature repetitions in the same hy-

pothesis). Data association algorithms must select in some way

one of the

-interpretations as the correct hy-

pothesis, carrying out validations to determine the compatibility

between sensor measurements and map features. Once a hypoth-

esis has been obtained, it can be used to improve the estimation

of .

B. Individual Compatibility Nearest Neighbor The individual compatibility nearest neighbor (ICNN) simply pairs each measurement with the feature considered most compatible according to (1). Since usually the measurement function is nonlinear, linearization around the current estimation is necessary

(2)

where

...

...

...

...

...

Vector represents the innovation of the pairing between and . From (1) and (2) its covariance can be obtained as

In a similar way, let represent a set of measurements of environment features, obtained using a sensor mounted on the vehicle, affected by white Gaussian noise

(3) The individual compatibility (IC) between and can be determined using an innovation test that measures the Mahalanobis distance as follows:

(4)

...

...

...

...

where is the theoretical value of the observations. A measurement and its corresponding feature are related by an implicit measurement function [18] of the form (1)

where

and is the desired confidence level. This

test, applied to the predicted state, determines the subset of map

features that are compatible with a measurement (and thus

the value of ).

The NN selection criterion for a given measurement con-

sists of choosing among the features that satisfy (4), the one

with the smallest Mahalanobis distance. This algorithm is fre-

quently used given its conceptual simplicity and computational

efficiency: it performs compatibility tests, making it linear

892

IEEE Transactions ON ROBOTICS AND AUTOMATION, VOL. 17, NO. 6, DECEMBER 2001

Fig. 1. Monodimensional robot with two features. Step 1: map creation from two sensor measurements taken from initial position. Step 2: data association problem after 1 m motion with three sensor measurements, y^ spurious. Intervals represent 2 uncertainty bounds.

with the size of the map. For a large , its inversion may be a costly operation. Several methods to calculate lower bounds for have been proposed, which in some cases allow to reject the pairing between and without inverting [19][21].

C. Limitations of the Nearest Neighbor

To illustrate the limitations of this approach, consider the

simple example of a robot that traverses a monodimensional

space, where there are two features (Fig. 1). Assume that this

robot is equipped with a sensor capable of detecting these fea-

tures. At step 1, the robot observes the two features, and they

are included in the stochastic map. At step 2 the robot moves 1

m, and obtains three measurements: , , and (spurious).

The uncertainties in robot motion and sensor measurements are

and

. In this case, we have

In Fig. 2, the big square represents the acceptance re-

gion of IC, and the six small squares represent the uncertainty

of the six main pairing hypotheses (we consider here the ad-

ditional restriction that two measurements cannot come from

the same feature). According to IC, only measurement is

compatible with feature (horizontal axis in Fig. 2), while

both and are compatible with (vertical axis). Thus IC

accepts the two possible hypotheses

and

because their squares intersect the square

region of acceptance. As lies closer to

than , NN

would prefer the second hypothesis, pairing with incor-

rectly.

This occurs because IC considers individual compatibility

between a measurement and a feature. However, individually

compatible pairings are not guaranteed to be jointly compatible

to form a consistent hypothesis. Even if sensor measurements

are independent, correlations in the stochastic map are always

present and cannot be ignored [5]. Furthermore, the predicted

measurements are always correlated because they are affected

by the same robot position error. Graphically this means that,

for a given confidence level, the region of acceptance of the pre-

dicted measurements is an ellipsoidal region instead of a square

Fig. 2. Simulation of a monodimensional robot. Each axis represents the 0 predicted location of a feature with respect to the robot location (x^ x^ 0 and x^ x^ respectively) together with the three actual measurements y^ , y^ and y^ . The big square region represents the uncertainty of each prediction considered independently, while the ellipsoidal region represents this uncertainty considering the correlation between the predictions. Each small group of a square and a circle represents an alternative matching hypothesis, with its measurement uncertainty.

region (Fig. 2). From this perspective, in our example it is clear

that pairings

are not simultaneously ac-

ceptable: the region of uncertainty of this hypothesis (circular,

given that the precision of this sensor has been considered con-

stant) does not intersect the ellipsoidal region of acceptance of

the predicted measurements. Only the region corresponding to

hypothesis

does.

This simple example shows that with ICNN there is a high

risk of obtaining an inconsistent hypothesis and thus updating

the state vector with a set of incompatible measurements, which

will cause EKF to diverge. As vehicle error grows with respect

to sensor error, the ratio between the area of the square and the

area of the ellipse grows (due to the increase in the correla-

tion between the vehicle and the predicted measurements), and

thus the discriminant power of IC decreases. For this reason, the

ICNN algorithm is adequate only when these two conditions are

satisfied

1) The robot error is smaller than the distance between the features, so that it is unlikely that two features pass the IC test for the same observation. 2) Spuriousness is sufficiently low so that it is unlikely that a spurious measurement will fall inside the acceptance region of some feature.

III. OBTAINING CONSISTENT HYPOTHESES

A. Sequential Compatibility Nearest Neighbor

A simple way to assure that the resulting hypothesis

contains jointly compatible pairings is to use a sequential

compatibility nearest neighbor (SCNN) algorithm. Sequen-

tial compatibility (SC) is an innovation test that determines

compatible features for a measurement , given that a hy-

pothesis

, corresponding to pairings

has been established and

NEIRA AND TARDУS: DATA ASSOCIATION IN STOCHASTIC MAPPING USING THE JOINT COMPATIBILITY TEST

893

has been used to obtain an estimation

of the state. If

the Mahalanobis distance , corresponding to a feature

, satisfies (4) given

, the pairing

will be consistent with all pairings in . If this feature is

considered the nearest compatible with measurement , the

measurement can be used to obtain the new estimate of

the state vector and its covariance . In the next iteration, a

pairing for measurement

will be determined by applying

(2) and (4) to the updated state estimation

.

SCNN is an

algorithm, quadratic with the

size of the map: for each of the measurements, SCNN re-

quires evaluating compatibility with the map features, ,

and updating the stochastic map,

(recent works address

the reduction of this complexity [22], [23]). It is appealing be-

cause it guarantees that all pairings belonging to the resulting

hypothesis are jointly compatible. However, it ignores the fact

that these pairings may anyway be incorrect: a feature may be

compatible with an unrelated or spurious sensor measurement

just by chance. In our example, if SCNN tries to pair observation

in the first step, it will pair it incorrectly with (Fig. 2). The

pairing will be used to re-estimate the stochastic map, and no

more pairings will be acceptable in subsequent steps. This risk

increases with clutter, and robot or sensor error. In this greedy

algorithm, the decision to pair a measurement with its most com-

patible feature is never reconsidered, and thus spurious pairings

may be included in the hypothesis and integrated in the state es-

timation, especially during the initial iterations. This leads again

to a reduction in uncertainty with no reduction in error, i.e., in-

consistency.

B. Joint Compatibility Branch and Bound

Reconsideration of the established pairings is necessary to

limit the possibility of accepting a spurious pairing. The prob-

ability that a spurious pairing is jointly compatible with all the

pairings of a given hypothesis decreases as the number of pair-

ings in the hypothesis increases. For this reason, we require a

search algorithm to traverse the interpretation tree in search of

the hypothesis that includes the largest number of jointly com-

patible pairings. SC could be used to restrict the search to tree

nodes representing hypotheses with jointly compatible pairings,

but it requires the update of the whole stochastic map for each

pairing considered,

, which can be computationally very

expensive in a search algorithm.

We use an alternative formulation to establish the consistency

of a hypothesis

, called joint compatibility

(JC), which uses a joint implicit function

, where

...

(7)

...

(8)

The JC of pairings belonging to can be determined using an innovation test on the joint innovation as follows:

(9) (10)

where is the covariance of the joint innovation, is the de-

sired confidence level, and

. The size of both

and increase with the size of hypothesis . This makes

this test potentially expensive to apply. The calculation of lower

bounds of to try to determine whether the hypothesis can

be rejected without inverting is pointless in this case, since

all the pairings in are already known to be individually com-

patible.

In the worst case, verifying the joint compatibility of a set of

pairings in a hypothesis involves the inversion of an

ma-

trix,

. This complexity can be reduced to

using

the fact that joint compatibility can be incrementally evaluated:

given a hypothesis

formed by jointly compatible pairings,

with its corresponding

,

, and

, and given a

pairing

, with corresponding , and , the Ma-

halanobis distance corresponding to can be calculated

as follows.

1) Calculate . From (9) we have that

where According to the partitioning method for matrix inversion [24], matrix can be calculated as

...

(11)

where (5)

...

(6)

894

IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 17, NO. 6, DECEMBER 2001

Fig. 3. Images of the trinocular vision system at step 48 of the robot trajectory. 2) Calculate

(12)

An alternative method for the incremental calculation of the

Mahalanobis distance can be found in [21].

JC is equivalent to SC except for linealization errors if:

satisfies (10), the pairing

is compatible with all pair-

ings in . Using JC has several advantages:

· JC can be tested without recomputing the state , an operation. · The inversion of a growing matrix is avoided. In fact, only the inversion of a constant size matrix is necessary. · Most of the elements involved in the calculation of ( , , ) have been previously computed to assert Individual Compatibility. The joint compatibility branch and bound (JCBB) algorithm proposed in this work traverses the interpretation tree in search of the hypothesis with the largest number of nonnull jointly compatible pairings. This monotonically nondecreasing criterion can be used to bound the search in the interpretation tree [2]. The quality of a node at level , corresponding to a hypothesis , can be defined as the number of nonnull pairings that can be established from the node. In this way, nodes with quality lower than the best available hypothesis are not explored. The nearest neighbor rule using the Mahalanobis distance can be used as heuristic for branching, so that the nodes corresponding to hypotheses with a higher degree of joint compatibility will be explored first. As experiments will show, JC is a very restrictive criterion to traverse the interpretation tree, limiting the combinatorial explosion of the search due to increasing vehicle error.

Fig. 4. Stochastic map obtained during the first 18 steps of the robot trajectory (solid line) and true robot trajectory until step 48 (dashed line), with resulting uncertainty in the robot location after continuing the robot trajectory without updating the stochastic map. A map of the environment (dotted line) is superimposed as reference but not used during the process. IV. EXPERIMENTS A Labmate mobile robot equipped with a trinocular vision system was programmed to perform a loop trajectory of around 60 m. The ground truth for the robot location along the trajectory was obtained using theodolites. Trinocular vision provided a set of two-dimensional (2-D) points corresponding to corners, wall and window frames, etc., obtained by establishing correspondences between vertical edges extracted from the three images (Fig. 3). Continuous localization and map building using this information is fairly straightforward. Thus, we designed an experiment to determine how well the SCNN and JCBB data association algorithms solve the more complex and important revisiting problem. A stochastic map of a corridor was constructed [5] using the information obtained in the first 18 steps of the robot trajectory (Fig. 4). The robot trajectory was continued without updating the stochastic map until the first corridor was visible again (step 48). Fig. 5 depicts the situation from the robot's perspective: the measurements obtained by the trinocular vision

NEIRA AND TARDУS: DATA ASSOCIATION IN STOCHASTIC MAPPING USING THE JOINT COMPATIBILITY TEST

895

(a)

(b)

Fig. 5. The revisiting problem at trajectory step 48: (a) 2-D points obtained by trinocular vision and (b) predicted location of map features with respect to the robot location.

Fig. 6. Solutions for 100 random robot locations using SCNN and JCBB for moderate and for large uncertainty.

system, and the predicted location of map features relative to the robot. It is clear that robot error and environment clutter make the number of candidate features for each measurement large and the situation very confusing. A Monte Carlo simulation was performed to generate 100 random positions at 10 different fractions of the odometry uncertainty at step 48. Both SCNN and JCBB were then executed, and the estimations of the robot location according to the resulting hypotheses were compared with ground truth. In the following, we discuss the results from two perspectives: robustness to robot error and computational efficiency. A. Robustness of SCNN Versus JCBB Fig. 6 shows results for frontal, lateral, and angular ( ) errors 0.15 m, 0.11 m, and 1.4 deg (top) and 1.55 m, 1.16 m, and

14 deg (bottom). It can be seen that SCNN exhibits a great dispersion in the solutions obtained, which becomes more notable as robot error grows. In contrast, the solutions obtained by JCBB remain grouped around the true robot location even for large uncertainty values. In order to measure the robustness of both algorithms to the increase in robot error, the 100 hypotheses obtained by each were compared with the true associations, established by hand. Results [Fig. 7(a)] show that the robustness of SCNN drops quickly with the increase in error, making this algorithm unsuitable for loop closing situations. In contrast, the probability of success of JCBB is always higher than that of SCNN, remaining above 0.9. It should be noted that the JC test is based on the linearization of the relation between the measurements and the state [see

896

IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 17, NO. 6, DECEMBER 2001

(a) Fig. 8. Maximum number of nodes versus position error (2).

(b) Fig. 7. Performance of JCBB and SCNN versus robot position 2 error: (a) fraction of correct hypotheses (with no spurious pairings) obtained and (b) computational cost (in FLOPS).

Fig. 9. Computational cost of the different parts of our JCBB algorithm versus number of observations.

(2)]. JCBB will remain robust to robot error as long the linear approximation is reasonable. Thus, the adequacy of using JCBB is determined by the robot orientation error (in practice, we have found the limit to be around 30 deg). B. Computational Efficiency of SCNN vs. JCBB That JCBB is more robust to an increment of robot error than SCNN was an expected result: JCBB is a back-tracking algorithm, while SCNN is a greedy search algorithm. Given that the cost of SCNN is linear with the number of measurements , the important question is then: is JCBB, an exponential time algorithm, feasible? This essentially depends on two factors: 1) how restrictive JC is to limit the real size of the solution space and 2) how effective the branch and bound is to limit the search for the best solution within this space. Fig. 8 shows the variation in the maximum number of individually compatible nodes, jointly compatible nodes, and visited nodes, all with respect to the increase in error. JC shows to be

a highly restrictive criterion. We can see that the total number of nodes in the solution space grows several orders of magnitude between 0.2 m and 2 m in position error. But this is not the case for the maximum number of jointly compatible nodes and maximum number of nodes visited by branch and bound. This is because the joint compatibility of a certain number of 2-D points fundamentally depends on their relative error (which depends on sensor and map precision), more than on their absolute error (which depends on robot error). Results [Fig. 7(b)] show that the computational cost of SCNN decreases slightly with the increase in robot error, due to the fact that a more probable spurious pairing normally reduces the possibilityof establishing more pairings. Forsmall robotposition error, the cost of JCBB and SCNN are similar. For a moderate error, around 1 m in position and 7 deg in orientation, JCBB executes around twice more flops. For larger errors, up to 2 m and 14 deg, the computational cost of JCBB increases rapidly, although it remains feasible in real time. It is important to note that these results refer to edge-based trinocular vision, an especially difficult data

NEIRA AND TARDУS: DATA ASSOCIATION IN STOCHASTIC MAPPING USING THE JOINT COMPATIBILITY TEST

897

association problem. In simpler cases, such as walls observed with

a laser rangefinder, the method will handle larger errors, up to the

limit imposed by the linearization errors.

Fig. 9 shows the computational cost of JCBB with respect to

the increase in the number of observations . It can be seen that

the cost of establishing individual compatibility and the cost of

updating the stochastic map grow linearly. On the other hand, it

is a known fact that the cost of the interpretation tree search in

the presence of spurious observations grows exponentially [2].

Our experiments show an asymptotic complexity of

.

This means that the number of observations must be limited to

make this algorithm feasible in real time. In practice, selecting

the 10 or 12 more relevant observations (larger or more pre-

cise) guarantees the robustness of the hypothesis obtained by

the JCBB algorithm. Once the map is updated using this hy-

pothesis, the remaining observations can be safely associated

with the SCNN algorithm.

V. CONCLUSION The popular NN algorithm for data association in stochastic mapping is very sensitive to the increase in vehicle and sensor error. Both factors contribute to increase the probability of matching a sensor measurement with an unrelated map feature. Since NN does not reconsider the establishment of a measurement-feature pairing, spurious pairings are easily formed and never reconsidered. We have shown that reconsideration of the validity of pairings is necessary, and thus a constrained search algorithm, such as the JCBB algorithm described in this paper, is required. The combinatorial explosion of this backtracking algorithm with respect to increase in vehicle error is controlled by the use of a restrictive validation mechanism that determines the joint compatibility of a set of pairings in the hypothesis. This greatly reduces the number of nodes in the interpretation tree that must be visited, as the algorithm traverses the tree in higher levels. Experiments show that JCBB is not only more robust than NN algorithms, but also feasible in terms of computational cost. In this work, we have studied the problem of refining an available estimation of the vehicle and feature state. Complementary techniques, applicable when there is no estimation of the vehicle location, will constitute further work.

REFERENCES [1] Y. Bar-Shalom and T. E. Fortmann, Tracking and Data Association. Boston, MA: Academic, 1988. [2] W. E. L. Grimson, Object Recognition by Computer: The Role of Geometric Constraints. Cambridge, MA: MIT press, 1990. [3] R. Smith, M. Self, and P. Cheeseman, "A stochastic map for uncertain spatial relationships," in 4th Int. Symp. Robotics Research, O. Faugeras and G. Giralt, Eds., 1988, pp. 467474. [4] Z. Zhang and O. D. Faugeras, "A 3D world model builder with a mobile robot," Int. J. Robot. Res., vol. 11, no. 4, pp. 269285, 1992. [5] J. A. Castellanos, J. M. M. Montiel, J. Neira, and J. D. Tardуs, "The SPmap: A probabilistic framework for simultaneous localization and map building," IEEE Trans. Robot. Automat., vol. 15, pp. 948953, Oct. 1999. [6] H. J. S. Feder, J. J. Leonard, and C. M. Smith, "Adaptive mobile robot navigation and mapping," Int. J. Robot. Res., vol. 18, no. 7, pp. 650668, 1999. [7] P. M. Newman, "On the structure and solution of the simultaneous localization and map building problem," Ph.D. dissertation, Dept. of Mechanical and Mechatronic Engineering, University of Sydney, March 1999.

[8] J. J. Leonard and R. J. Rikoski, "Incorporation of delayed decision making into stochastic mapping," in Experimental Robotics VII. ser. lecture notes in Control and Information Sciences, D. Rus and S. Singh, Eds. Berlin, Germany: Springer-Verlag, 2001. [9] J. A. Pйrez, J. A. Castellanos, J. M. M. Montiel, J. Neira, and J. D. Tardуs, "Continuous mobile robot localization: Vision vs. laser," in IEEE Int. Conf. Robotics and Automation, Detroit, MI, 1999, pp. 29172923. [10] I. J. Cox and J. J. Leonard, "Modeling a dynamic environment using a multiple hypothesis approach," A. I. J., vol. 66, no. 2, pp. 311344, 1994. [11] C. M. Smith, "Integrating mapping and navigation," Ph.D. dissertation, Department of Ocean Engineering, Massachusetts Institute of Technology, Cambridge, MA, June 1998. [12] X. Lebegue and J. K. Aggarwal, "Generation of architectural CAD models using a mobile robot," in IEEE Int. Conf. Robotics and Automation, San Diego, CA, 1994, pp. 711717. [13] C. F. Olson, "Probabilistic self-localization for Mobile Robots," IEEE Trans. Robot. Automat., vol. 16, pp. 5566, Feb. 2000. [14] S. Thrun, W. Burgand, and D. Fox, "A real-time algorithm for mobile robot mapping with applications to multi-robot and 3D mapping," in IEEE Int. Conf. Robotics and Automation, San Francisco, CA, 2000, pp. 321328. [15] J. S. Gutmann and K. Konolige, "Incremental mapping of large cyclic environments," in IEEE Int. Symp. Computational Intelligence in Robotics and Automation CIRA'1999, 1999, pp. 318325. [16] T. Baley, E. M. Nebot, J. K. Rosenblatt, and H. F. Durrant-Whyte, "Data association for mobile robot navigation: A graph theoretic approach," in IEEE Int. Conf. Robotics and Automation, San Francisco, CA, 2000, pp. 25122517. [17] J. A. Castellanos and J. D. Tardуs, Mobile Robot Localization and Map Building: A Multisensor Fusion Approach. Boston, MA: Kluwer, 1999. [18] J. Neira, J. D. Tardуs, J. Horn, and G. Schmidt, "Fusing range and intensity images for mobile robot localization," IEEE Trans. Robot. Automat., vol. 15, pp. 7684, Apr. 1999. [19] J. B. Collins and J. K. Uhlmann, "Efficient gating in data association with multivariate Gaussian distributed states," IEEE Trans. Aerosp. Electron. Syst., vol. 28, pp. 909916, July 1992. [20] M. J. L. Orr, J. Hallam, and R. B. Fisher, "Fusion through interpretation," in Second Eur. Conf. Computer Vision, 1992. [21] J. M. M. Montiel and L. Montano, "Efficient validation of matching hypotheses using mahalanobis distance," Eng. Applicat. Artif. Intell., vol. 11, no. 3, pp. 439448, 1998. [22] J. J. Leonard and H. J. S. Feder, "A computationally efficient method for large-scale concurrent mapping and localization," in 9th Int. Symp. Robotics Research, D. Koditschek and J. Hollebach, Eds. Snowbird, UT: Springer-Verlag, 2001, pp. 169176. [23] J. E. Guivant and E. M. Nebot, "Optimization of the simultaneous localization and map building algorithm for real-time implementation," IEEE Trans. Robot. Automat., vol. 17, pp. 242257, June 2001. [24] D. A. Harville, Matrix Algebra from a Statistician's Perspective. New York: Springer-Verlag, 1997.

modeling.

Josй Neira was born in Bogotб, Colombia, in 1963. He received the M.S. degree in computer science from the Universidad de los Andes, Colombia, in 1986, and the Ph.D. degree in computer science from the University of Zaragoza, Spain, in 1993. He is Associate Professor in the Departamento de Informбtica e Ingenierнa de Sistemas, University of Zaragoza, where he is in charge of courses in compiler theory, computer vision and mobile robotics. His current research interests include mobile robotics, data association, and environment Juan D. Tardуs was born in Huesca, Spain, in 1961. He received the M.S. and Ph.D. degrees in industrial-Electrical engineering from the University of Zaragoza, Spain, in 1985 and 1991, respectively. He is Associate Professor in the Departamento de Informбtica e Ingenierнa de Sistemas, University of Zaragoza, where he is in charge of courses in real time systems, computer vision and Artificial Intelligence. His current research interests include sensor integration and mobile robotics.

J Neira, JD Tardós

doc.uments.com

About Us :: Privacy Policies :: Terms of Service :: Feedback :: Copyright :: Contact Us :: DMCA Policy

Copyright © 2018 doc.uments.com