[ca] Aquesta tesi tracta el problema de l'aprenentatge automàtic d'entorns estructurats n robòtica mòbil. Particularment, l'extracció de característiques a partir dels senyals dels sensors, la construcció autònoma de mapes, i l'autolocalització de robots. S'estudien els fonaments matemàtics necessaris per a l'extracció de característiques a partir d'imatges i registres d'un làser, els quals permeten la identificació unívoca dels elements de l'entorn. Els atributs extrets a partir del senyal d'un sol sensor poden ser insuficients quan es volen caracteritzar els elements de l'entorn de forma invariant; això es pot millorar combinant informació de múltiples fonts. Es presenta un nou algorisme per la fusió d'informació complementaria extreta de dos mòduls de visió de baix nivell. Aquesta fusió d'informació produeix descripcions més completes dels objectes de l'entorn, els quals poden ser seguits i apresos dins el context de la robòtica mòbil. Les variacions en les condicions d'il·luminació i les oclusions fan que l'associació de dades en visió per computador sigui una tasca difícil de completar. Tot i això, l'ús de restriccions geomètriques i fotogramètriques permeten reduir la cerca de correspondències entre imatges successives; i al centrar l'atenció en un reduït nombre de característiques, aquestes poden ser seguides en imatges successives, simplificant així el problema d'associació de dades. Es recalquen les tècniques de la geometria de múltiples vistes que són rellevants pel còmput d'una estimació inicial de la posició dels elements de l'entorn, el que permet la reconstrucció del moviment del robot entre imatges successives; situació desitjable quan no existeix odometria o quan las seves lectures són poc fiables. Quan els elements de l'entorn s'han extret i identificat, la segona part del problema consisteix en utilitzar aquestes observacions tant per estimar la posició del robot, com per refinar l'estimació dels mateixos elements de l'entorn. El moviment del robot i les lectures dels sensors es consideren com dos processos estocàstics, i el problema es tracta des del punt de vista de la teoria d'estimació, on el soroll inherent als sensors i al moviment del robot es consideren com a seqüències aleatòries. El principal inconvenient existent en l'ús de tècniques d'estimació pel còmput concurrent de la posició del robot i la construcció d'un mapa, és que fins ara s'ha considerat la seva aplicació únicament en entorns estàtics, i que el seu ús en situacions més realistes ofereix poca robustesa. Es proposa un conjunt de funcions per avaluar la qualitat temporal de les observacions per tal de resoldre les situacions en que les observacions dels elements de l'entorn no siguin consistents en el temps. Es mostra com la utilització d'aquestes proves de qualitat temporal conjuntament amb les proves de compatibilitat espacial milloren els resultats quan es fen servir amb un mètode d'estimació òptima de la construcció concurrent de mapes i l'autolocalització de robots. La idea principal consisteix en emprar un històric dels errors en l'associació de les dades per calcular la possibilitat d'incórrer en nous errors d'associació; i excloure del mapa aquells elements dels quals les observacions no siguin consistents. Es posa especial atenció en el fet que l'eliminació dels elements inconsistents del mapa no violi les propietats dels algorismes de construcció concurrent de mapes i autolocalització descrits en la literatura; és a dir, convergència assimptòtica i correlació completa. Aquesta tesi proporciona també un profund anàlisi del model de construcció concurrent de mapes i autolocalització totalment correlat des d'un punt de vista de la teoria de control de sistemes. Partint del fet que el filtre de Kalman no és més que un estimador òptim, s'analitzen les implicacions de tenir un vector d'estats que es revisa a partir de mesures totalment correladas. Es revela de manera teòrica i amb experiments les limitacions d'utilitzar un enfocament per la construcció concurrent de mapes i l'autolocalització a partir de mesures totalment correladas. El fet de tenir un model parcialment observable inhibeix la reconstrucció total de l'espai d'estats, produint tant mateix una estimació de la posició dels elements de l'entorn que depèn en tot cas de les observacions inicials, i que no garanteix la convergència a una matriu de covariància definida positivament. D'altra banda, el fet de tenir un vector d'estats parcialment controlable fa que, desprès d'un reduït nombre d'iteracions el filtre cregui tenir una estimació perfecta de l'estat dels elements de l'entorn; amb els corresponents guanys de Kalman convergint a zero. Per tant, desprès d'un reduït nombre d'iteracions del filtre, els innovacions no s'utilitzen més. Es mostra com reduir els efectes de la correlació total i de la controlabilitat parcial. A més a més, suposant que el filtre de Kalman és un observador òptim per a la reconstrucció dels estats, és pertinent construir un regulador òptim que permeti conduir el robot el més a prop possible a una trajectòria desitjada durant la construcció d'un mapa. Es mostra com la dualitat existent entre l'observabilitat i la controlabilitat es pot fer servir en el disseny d'aquest regulador òptim. Qualsevol algorisme de construcció concurrent de mapes i autolocalització de robots mòbils que s'ha d'usar en un entorn real ha de ser capaç de relacionar les observacions i els seus corresponents elements del mapa de manera expedita. Algunes de les proves de compatibilitat de les observacions són costoses des del punt de vista de la seva complexitat computacional, i la seva aplicació s'ha de dissenyar amb especial atenció. Es comenten els costos computacionals de les diferents proves de compatibilitat entre observacions; així com altres característiques desitjables de l'estructura de dades que es fa servir per a la construcció del mapa. A més a més es proposen una sèrie de tasques que han de realitzar-se durant l'associació de dades. Començant per les proves de compatibilitat amb un model bàsic dels elements del mapa, i continuant amb la reducció de l'espai de cerca quan es generen hipòtesis d'associació, així com les proves espacial i temporal d'associació de dades. El treball que es presenta en aquesta tesi proposa noves tècniques en àrees de l'enginyera i ciències computacionals, que van des de nous algorismes per la visió per computador, a idees novells de la construcció concurrent de mapes i l'autolocalització de robots mòbils. Les contribucions principals són la proposta d'una nova tècnica per la fusió de dades visuals; la formulació d'un nou algorisme per la construcció concurrent de mapes i l'autolocalització de robots que considera la qualitat temporal dels elements del mapa; nous resultats teòrics en el nivell de reconstrucció possible quan es construeixen mapes a partir d'observacions totalment correladas; i les tècniques necessàries per pal·liar els efectes de l'observabilitat i la controlabilitat parcials, així com els efectes de les no linealitats en la solució del problema de construcció concurrent de mapes i de l'autolocalització.

[en] This thesis focuses on the various aspects of autonomous environment learning for indoor service robots. Particularly, on landmark extraction from sensor data, autonomous map building, and robot localization. To univocally identify landmarks from sensor data, we study several landmark representations, and the mathematical foundation necessary to extract the features that build them from images and laser range data. The features extracted from just one sensor may not suce in the invariant characterization of landmarks and objects, pushing for the combination of information from multiple sources. We present a new algorithm that fuses complementary information from two low level vision modules into coherent object models that can be tracked and learned in a mobile robotics context. Illumination conditions and occlusions are the most prominent artifacts that hinder data association in computer vision. By using photogrammetric and geometric constraints we restrict the search for landmark matches in successive images, and by locking our interest in one or a set of landmarks in the scene, we track those landmarks along successive frames, reducing considerably the data association problem. We concentrate on those tools from the geometry of multiple views that are relevant to the computation of initial landmark location estimates for coarse motion recovery; a desirable characteristic when odometry is not available or is highly unreliable. Once landmarks are accurately extracted and identied, the second part of the problem is to use these observations for the localization of the robot, as well as the renement of the landmark location estimates. We consider robot motion and sensor observations as stochastic processes, and treat the problem from an estimation theoretic point of view, dealing with noise by using probabilistic methods. The main drawback we encounter is that current estimation techniques have been devised for static environments, and that they lack robustness in more realistic situations. To aid in those situations in which landmark observations might not be consistent in time, we propose a new set of temporal landmark quality functions, and show how by incorporating these functions in the data association tests, the overall estimation-theoretic approach to map building and localization is improved. The basic idea consists on using the history of data association mismatches for the computation of the likelihood of future data association, together with the spatial compatibility tests already available. Special attention is paid in that the removal of spurious landmarks from the map does not violate the basic convergence properties of the localization and map building algorithms already described in the literature; namely, asymptotic convergence and full correlation. The thesis also gives an in depth analysis of the fully correlated model to localization and map building from a control systems theory point of view. Considering the fact that the Kalman .lter is nothing else but an optimal observer, we analyze the implications of having a state vector that is being revised by fully correlated noise measurements. We end up revealing theoretically and with experiments the strong limitations of using a fully correlated noise driven estimation theoretic approach to map building and localization in relation to the total number of landmarks used. Partial observability hinders full reconstructibility of the state space, making the .nal map estimate dependant on the initial observations, and does not guarantee convergence to a positive de nite covariance matrix. Partial controllability on the other hand, makes the .lter beleive after a number of iterations, that it has accurate estimates of the landmark states, with their corresponding Kalman gains converging to zero. That is, after a few steps, innovations are useless. We show how to palliate the e.ects of full correlation and partial controllability. Furthermore, given that the Kalman .lter is an optimal observer for the reconstruction of fully correlated states; it seems pertinent to build an optimal regulator in order to keep the robot as close as possible to a desired motion path when building a map. We show also how the duality between observability and controllability can be exploited in designing such an optimal regulator. Any map building and localization algorithm for mobile robotics that is to work in real time must be able to relate observations and model matches in an expeditious way. Some of the landmark compatibility tests are computationally expensive, and their application has to be carefully designed. We touch upon the time complexity issues of the various landmark compatibility tests used, and also on the desirable properties of our chosen map data structure. Furthermore, we propose a series of tasks that must be handled when dealing with landmark data association. From model compatibility tests, to search space reduction and hypothesis formation, to the actual association of observations and models. The work presented in this thesis spans several areas of engineering and computer science, from new computer vision algorithms, to novel ideas in mobile robot localization and map building. The key contributions are the proposal of a new technique to fuse visual data; the formulation of new algorithms to concurrent localization and map building that take into account temporal landmark quality; new theoretical results on the degree of reconstruction possible when building maps from fully correlated observations; and the necessary techniques to palliate partial observability, partial controllability, and the nonlinear e.ects when solving the simultaneous localization and map building problem.