Fuzzy Inductive Reasoning (FIR) is a modelling and simulation methodology capable of generating a qualitative input-output model of a system from real-valued trajectories of its physical variables. The functioning basis of FIR is to qualitatively learn the behaviour of a system from its past real data. This is an interesting feature when dealing with ill-defined, usually large-scale systems, for which an accurate description is not available but only data trajectories of the process.FIR finds in a (huge) search space model the so-called optimal mask that indicates which variables best explain any given output. Unfortunately, any algorithm that can find the optimal mask is necessarily of exponential complexity, i.e., the number of masks to be visited grows exponentially with the number of available input variables. This makes the FIR methodology, in its actual implementation, impractical for those cases in which it would be most useful, i.e., large-scale systems.The thesis discusses whether sub-optimal search algorithms or methods of pre-simplifying a large-scale system are most suitable for dealing effectively and efficiently with the problem of deriving qualitative FIR models for them. The mask search space of FIR must be reduced in order to compute a model of a large-scale system in an affordable amount of time. To this aim, basically two lines of thought are given in the present dissertation. The first one is to directly simplify the candidate mask that is proposed to FIR. This can be done either directly, by reducing the number of input variables to the FIR model, or indirectly, using sub-optimal mask search algorithms. Two new sub-optimal mask search algorithms are proposed. The first method is another variant of a hill-climbing technique, which results in a high-quality mask while still converging in polynomial time. The second method is a new variant of a statistical approach that is based on spectral coherence functions.The second line of research in this dissertation is to obtain a decomposition of the system into subsystems. This would allow obtaining a model of the system from its subsystems, which in turn reduces the computational time needed for the overall effort. Given a k-variable system, the cost of computing a unique k-variable model is much higher than computing a set of p models of jp < k variables. With these complementary lines of work, two complete methodologies can be proposed, each of which enables the construction of qualitative models of complex systems. The former, based in simplifying the number of potential inputs to the FIR models, is an energy-based method, capable of detecting the variables at given delays that are more closely related to the considered output of the system. The latter proposes a decomposition of the overall system into subsystems. With the research presented in this thesis, the FIR modelling capabilities have been extended with capabilities for modelling large-scale systems within a reasonable time.

La navegació en entorns desconeguts no estructurats és encara un problema obert en el camp de la robòtica. En aquesta tesi presentem una aproximació per a la navegació de robots basada en la combinació de navegació basada en landmarks, representació fuzzy d'angles i distàncies i una coordinació multiagent basada en un mecanisme de dites. L'objectiu de la tesi ha sigut desenvolupar un sistema de navegació robust amb sentit de l'orientació per a entorns no estructurats usant informació visual.Per tal d'assolir aquest objectiu, hem centrat els nostres esforços en dues línies d'investigació: mètodes de navegació i construcció de mapes, i arquitectures de control per a robots autònoms.Pel que fa als mètodes de navegació i construcció de mapes, hem extès el treball presentat per Prescott per tal que es pugui utilitzar amb informació fuzzy sobre la localitazció dels landmarks. A part d'aquesta extensió, tambés hem desenvolupat mètodes per a calcular objectius alternatius, necessaris quan el robot troba el camí bloquejat.Pel que fa a l'arquitectura de control, hem proposat una arquitectura general que utilitza un mecanisme de dites per a coordinar un grup de sistemes que controlen el robot. Aquest mecanisme pot ser usat en diferents nivells de l'arquitectura. En el nostre cas l'hem usat per a coordinar els tres sistemes del robot (Navegació, Pilot i Visió), i tambés per a coordinar els agents que composen el sistema de Navegació. Usant aquest mecanisme de dites, l'acció que executa el robot és la més ben valorada en cada instant. D'aquesta manera, i si els agents fan les dites d'una manera racional, la dinàmica de les dites porta el robot a executar les accions necessàries per tal d'arribar a l'objectiu indicat. L'avantatge d'utilitzar aquest mecanisme és que no cal imposar una jerarquia entre els sistemes, com passa en l'arquitectura de subsumpció, si no que aquesta jerarquia canvia dinàmicament, depenent de la situació en què es troba el robot i les característiques de l'entorn.Hem obtingut resultats satisfactoris, tant en simulació com en experimentació amb un robot real, que confirmen que el sistema de navegació és capaç de construir un mapa d'un entorn desconegut i utlitzar-lo per a moure el robot d'una posició inicial a un objectiu donat. L'experimentació tambés ha mostrat que el sistema de coordinació basat en dites que hem dissenyat produeix el comportament global d'executar les accions necessàries en cada instant per tal d'arribar a l'objectiu. / Navigation in unknown unstructured environments is still a difficult open problem in the field of robotics. In this PhD thesis we present a novel approach for robot navigation based on the combination of landmark-based navigation, fuzzy distances and angles representation and multiagent coordination based on a bidding mechanism. The objective has been to have a robust navigation system with orientation sense for unstructured environments using visual information.To achieve such objective we have focused our efforts on two main threads: navigation and mapping methods, and control architectures for autonomous robots.Regarding the navigation and mapping task, we have extended the work presented by Prescott, so that it can be used with fuzzy information about the locations of landmarks in the environment. Together with this extension, we have also developed methods to compute diverting targets, needed by the robot when it gets blocked.Regarding the control architecture, we have proposed a general architecture that uses a bidding mechanism to coordinate a group of systems that control the robot. This mechanism can be used at different levels of the control architecture. In our case, we have used it to coordinate the three systems of the robot (Navigation, Pilot and Vision systems) and also to coordinate the agents that compose the Navigation system itself. Using this bidding mechanism the action actually being executed by the robot is the most valued one at each point in time, so, given that the agents bid rationally, the dynamics of the biddings would lead the robot to execute the necessary actions in order to reach a given target. The advantage of using such mechanism is that there is no need to create a hierarchy, such in the subsumption architecture, but it is dynamically changing depending on the specific situation of the robot and the characteristics of the environment.We have obtained successful results, both on simulation and on real experimentation, showing that the mapping system is capable of building a map of an unknown environment and use this information to move the robot from a starting point to a given target. The experimentation also showed that the bidding mechanism we designed for controlling the robot produces the overall behavior of executing the proper action at each moment in order to reach the target.

La propiedad de generalización de una máquina de aprendizaje, es decir su capacidad para emitir una respuesta correcta ante una nueva entrada semejante a aquellas con las que ha sido entrenada, es la característica principal que se busca en los sistemas conexionistas supervisados y sirve de justificación en la elección de los principios inductivos y el tipo de estructuras de aprendizaje para elaborar el presente estudio.La regularización o penalización es uno de estos principios que favorecen a nivel teórico la generalización, sobre el cual se ha desarrollado un método de cálculo directo de la matriz de regularización cuando se utiliza como estabilizador un operador diferencial de segundo grado, precisamente aquel que minimiza el grado de convexidad de la función solución, evitando así y el proceso iterativo de cálculo de la matriz hessiana y fijando el tipo de núcleo a ser utilizado.Los nexos de unión entre la regularización y el principio de minimización del riesgo estructural así como las excelentes características teóricas mostradas por este ´ ultimo principio trabajando, por definición, sobre conjuntos finitos de datos y expandiendo su solución sobre un número pequeño de núcleos, han llevado a desplazar el foco de trabajo de numerosos investigadoreshacia las máquinas de soporte vectorial, su materialización procedimental. En este contexto, se ha desarrollado una máquina que permite extender de forma natural el comportamiento binario de estas máquinas núcleo de margen máximo sobre problemas de clasificación hacia una solución ternaria m´asacorde con la estructura geométrica de los datos, en especial en las situaciones habituales de espacios de salida que poseen más de dos clases. El uso de la nueva arquitectura, bautizada K-SVCR,en problemas de multiclasificación resulta más adecuado que las reducciones estándares de problemas multiclase sobre máquinas biclasificadoras en estructuras en paralelo o arbóreas puesto que cada nodo de dicotomía considera todo el espacio de entrenamiento y se fuerza al hiperplano de separación a considerar la estructura geométrica de los patrones de entrenamiento. En especial, se demuestra la robustez del nuevo método ante fallos en las predicciones de algunos de sus nodos de trabajo cuando se considera un tipo especial de combinación de estas respuestas. La nueva arquitectura de multiclasificación ha sido modificada con posterioridad para ser implementada sobre un problema de clasificación con características independientes, la ordenación o problema de aprendizaje de preferencias. Sus prestaciones son evaluadas sobre una aplicación financiera en la determinación de riesgos crediticios. Finalmente, una aplicación de categorización o discriminación de escenarios de depuración donde incide el efecto de la temporalidad sirve también como ejemplo de funcionamiento. / The property of generalization of a learning machine, i.e. its capacity to emit a correct answer on a new similar input to those with wich it has been trained, is the basic behavior looked for in the supervised connexionists systems and it serves as justification in the selection of the inductive principles and the type of learning structures to ellaborate the present study.The penalty is one of these principles that favor at theoretical level the generalization, on which a method of direct calculation of the regularization matrix when a second degree differential operator is used like stabilizer, indeed that diminishing the convexity degree of the solution function, avoiding therefore the iterative process of calculation of the Hessian matrix, has been developed and fixing the type of kernel to be used. Links between regularization and the structural risk minimization principle as well as the excellent theoretical characteristics shown by this last principle working, by definition, on finite data sets and expanding their solution on a small number of kernels, have taken to move the center of study of numerous investigators towards the support vector machines, their procedural materialization. In this context, a machine that allows to extend of natural form the binary behavior of these maximum margin ker-nel machines on classification problems towards an agreed ternary solution with the geometric structure of the data has been developed, in special in the habitual situations of output spaces having more than two classes.The use of the new architecture, named K-SVCR, in multiclassification problems is more suitable than the standard reductions from multiclass problems on biclass machines in tree or parallel structures, since each di-chotomie node considers all the training space and force to the hyperplane of separation to consider the geometric structure of the training patterns.In special, the robustness of the new method is demostrated on failures in the predictions of some of its working nodes when a special type of combination of these answers is considered.The new architecture of multiclassification has been modified later to be implemented on a classification problem with independent characteristics, the ordenation or learning of preferences problem. Their benefits are evaluated on a financial application in the determination of credit risks. Finally, an application of categorization in waste water plant scenes, where the temporality affects, also serves like operation example.

Esta obra es una contribución al campo de la Complejidad de la Demostración, que estudia la complejidad de los sistemas de demostración en términos de los recursos necesarios para demostrar o refutar fórmulas proposicionales. La Complejidad de la Demostración es un interesante campo relacionado con otros campos de la Informática como la Complejidad Computacional o la Demostración Automática entre otros. Esta obra se centra en medidas de complejidad para sistemas de demostración refutacionales para fórmulas en FNC. Consideramos varios sistemas de demostración, concretamente Resolución, R(k) y Planos Secantes y nuestros resultados hacen referencia a las medidas de complejidad de tamaño y espacio.Mejoramos separaciones de tamaño anteriores entre las versiones generales y arbóreas de Resolución y Planos Secantes. Para hacerlo, extendemos una cota inferior de tamaño para circuitos monótonos booleanos de Ran y McKenzie a circuitos monótonos reales. Este tipo de separaciones es interesante porque algunos demostradores automáticos se basan en la versión arbórea de sistemas de demostración, por tanto la separación indica que no es siempre una buena idea restringirnos a la versión arbórea.Tras la reciente aparición de R(k), que es un sistema de demostración entre Resolución y Frege con profundidad acotada, era importante estudiar cuan potente es y su relación con otros sistemas de demostración. Resolvemos un problema abierto propuesto por Krajícek, concretamente mostramos que R(2) no tiene la propiedad de la interpolación monónota factible. Para hacerlo, mostramos que R(2) es estrictamente más potente que Resolución.Una pregunta natural es averiguar si se pueden separar sucesivos niveles de R(k) o R(k) arbóreo. Mostramos separaciones exponenciales entre niveles sucesivos de lo que podemos llamar la jerarquía R(k) arbórea. Esto significa que hay formulas que requieren refutaciones de tamaño exponencial en R(k) arbóreo, pero tienen refutaciones de tamaño polinómico en R(k+1) arbóreo. Propusimos una nueva definición de espacio para Resolución mejorando la anterior de Kleine-Büning y Lettmann. Dimos resultados generales sobre el espacio para Resolución y Resolución arbórea y también una caracterización combinatoria del espacio para Resolución arbórea usando un juego con dos adversarios para fórmulas en FNC. La caracterización permite demostrar cotas inferiores de espacio para la Resolución arbórea sin necesidad de usar el concepto de Resolución o Resolución arbórea. Durante mucho tiempo no se supo si el espacio para Resolución y Resolución arbórea coincidían o no. Hemos demostrado que no coinciden al haber dado la primera separación entre el espacio para Resolución y Resolución arbórea.También hemos estudiado el espacio para R(k). Demostramos que al igual que pasaba con el tamaño, R(k) arbóreo también forma una jerarquía respecto alespacio. Por tanto, hay fórmulas que necesitan espacio casi lineal en R(k) arbóreo mientras que tienen refutaciones en R(k+1) arbóreo con espacio contante. Extendemos todas las cotas inferiores de espacio para Resolución conocidas a R(k) de una forma sencilla y unificada, que también sirve para Resolución, usando el concepto de satisfactibilidad dinámica presentado en esta obra. / This work is a contribution to the field of Proof Complexity, which studies the complexity of proof systems in terms of the resources needed to prove or refute propositional formulas. Proof Complexity is an interesting field which has several connections to other fields of Computer Science like Computational Complexity or Automatic Theorem Proving among others. This work focuses in complexity measures for refutational proof systems for CNF formulas. We consider several proof systems, namely Resolution, R(k) and Cutting Planes and our results concern mainly to the size and space complexity measures. We improve previous size separations between treelike and general versions of Resolution and Cutting Planes. To do so we extend a size lower bound for monotone boolean circuits by Raz and McKenzie, to monotone real circuits. This kind of separations is interesting because some automated theorem provers rely on the treelike version of proof systems, so the separations show that is not always a good idea to restrict to the treelike version. After the recent apparition of R(k) which is a proof system lying between Resolution and bounded-depth Frege it was important to study how powerful it is and its relation with other proof systems. We solve an open problem posed by Krajícek, namely we show that R(2) does not have the feasible monotone interpolation property. To do so, we show that R(2) is strictly more powerful than Resolution. A natural question is to find out whether we can separate successive levels of R(k) or treelike R(k). We show exponential separations between successive levels of what we can call now the treelike R(k) hierarchy. That means that there are formulas that require exponential size treelike R(k) refutations whereas they have polynomial size treelike R(k+1) refutations. We have proposed a new definition for Resolution space improving a previous one from Kleine-Büning and Lettmann. We give general results for Resolution and treelike Resolution space and also a combinatorial characterization of treelike Resolution space via a Player-Adversary game over CNF formulas. The characterization allows to prove lower bounds for treelike Resolution space with no need to use the concept of Resolution or Resolution refutations at all. For a long time it was not known whether Resolution space and treelike Resolution space coincided or not. We have answered this question in the negative because we give the first space separation from Resolution to treelike Resolution. We have also studied space for R(k). We show that, as happened with respect to size, treelike R(k) forms a hierarchy respect to space. So, there are formulas that require nearly linear space for treelike R(k) whereas they have constant space treelike R(k+1) refutations. We extend all known Resolution space lower bounds to R(k) in an easier and unified way, that also holds for Resolution, using the concept of dynamical satisfiability introduced in this work.

In a commercial Internet, the traffic behavior is determined by the contracts between the ISPs and the users, where a user can be a dial-up user, or one corporate network or a group of individual customers or networks. Since the user is the entity with whom the contract is signed, it should also be the unit to which network resources are allocated. However, while much research in the past has been directed to fair resource allocations for flows (e.g. maxmin fairness and proportional fairness), much less effort has been invested on fair allocation of resources for users. The work done in this thesis tries to fill this gap: we study how to share fairly the network resources among users, when a user can possibly send several flows through different paths.The first part of the thesis focuses on the definition of a fairness criterion for the above problem: user maxmin fairness. The proposed criterion is based on the concepts of utility and welfare developed in the field of political science and political economics. We subdivide the problem of fairly allocating the network resources among users in two subproblems: 1) achieve fairness with respect to the utility experienced by the different users (inter-user fairness) and 2) achieve fairness with respect to the utility experienced by the different flows of a user (intra-user fairness). User maxmin fairness is the result of combining the two welfare functions that solve these two subproblems.Along with the user maxmin fairness criterion, in this thesis we propose a mechanism to implement it: the User Fair Queuing (UFQ) mechanism. In UFQ, a user is allowed to assign any label values to his packets to indicate their relative priority. At the ingress, an algorithm is used to control these labels assigned by the user. We have shown mathematically that: (a) the proposed label control does not allow the asymptotic throughput of a user to exceed its fair rate, and (b) if users label their packets in order to maximize their level of satisfaction or utility, then the resulting bandwidth allocation is user maxmin fair.In the last part of the thesis, we propose a network architecture for the Internet: the User Fair Differentiation (UFD) architecture. The UFD architecture extends the UFQ mechanism in such a way that its good features for resource sharing are preserved. In addition, UFD provides service differentiation, inter-domain communication, real-time traffic support and extensions for multicast and wireless. The fact that neither admission control nor signaling are required strongly contributes to the simplicity of UFD. The fact that no per-user state is kept at core nodes makes the proposed architecture scalable.The performance of the UFD architecture has been extensively evaluated via simulations and a prototype implementation. Both simulation and experimental results have validated the architecture proposed in this thesis.

Aquesta tesi presenta una nova metodologia per resoldre problemes de presa de decisions. Hemestudiat els casos en què cal considerar més d'un criteri. Aquests tipus de mètodes de decisió esconeixen com MCDM (Multiple Criteria Decision Making), o també MCDA (Multiple CriteriaDecision Aid). La diferència entre simplement "prendre decisions" o "ajudar a prendredecisions" recau en si el mètode es dissenya per recomanar la decisió a prendre o si tambéinclou elements que permeten entendre com es prenen les decisions en un cert context. La nostraproposta inclou elements dels dos plantejaments. D'una banda, hem intentat que la persona queha d'usar el mètode no necessiti aprendre tècniques complexes abans de poder-lo aplicar a casosreals. D'altra banda, el mètode no és una caixa negra, sinó que l'usuari rep informació sobrecaracterístiques de les dades que ha de tenir en compte abans de fer la decisió final.ClusDM és un mètode de presa de decisions pensat per resoldre dos tipus concrets deproblemes: (i) ordenar un conjunt d'alternatives de la millor a la pitjor, (ii) seleccionar lesmillors alternatives del conjunt. La dificultat d'aquest procés recau en que cal maximitzardiversos criteris parcials (i normalment no correlacionats) al mateix temps. A la tesi es pottrobar un resum de les diferents aproximacions a aquest tipus de problemes de decisió. Nomésdestacar que el nostre mètode segueix les bases de la Teoria de la Utilitat.Els mètodes clàssics consideren només criteris numèrics. Diferents extensions a aquests modelss'han anat desenvolupant durant els últims anys. En aquesta tesis ens hem plantejat lapossibilitat de tenir criteris que utilitzin diferents tipus de valors. A més, hem afegit dues fases ala metodologia habitual (que té una fase d'agregació i una d'ordenació), que són: l'explicaciódel resultat i l'avaluació de la qualitat.La "Fase d'explicació" està dedicada a assignar un terme lingüístic per descriure cadaalternativa segons la seva posició en el ranking. L'ús de vocabularis qualitatius facilita lacomprensió del resultat. El significat dels diferents termes usats ve donat per una funció denegació. Aquesta representació es basa en contrastar el significat d'un terme amb el dels termesoposats (els seus antònims).La "Fase d'Avaluació de la Qualitat" analitza a fons els resultats intermedis obtinguts en elsdiferents passos del procés i intenta mesurar l'error acumulat. ClusDM proporciona diversesmesures de qualitat parcial per cada fase del procés, de manera que l'usuari tingui constància dela confiança que pot donar al resultat final que doni el sistema. / This thesis presents a new methodology for decision making. In particular, we have studied theproblems that consider more than one criterion, which is known as Multiple Criteria DecisionMaking (MDCM) or Multiple Criteria Decision Aid (MCDA). The difference relies on the factof imitating the behaviour of the decision maker (i.e. develop a method that makes decisions) orgiving to the decision maker some additional information that allows him to understand themechanism of solving decisions (i.e. the decision maker can learn from the use of the method).Our proposal fits better in the MCDA approach, but has also similarities with the MCDMperspective. On one hand, the method we have designed is independent enough to not require adeep understanding of the process by the decision maker. On the other hand, we have carefullystudied the process and the method is able to extract knowledge about the decision problem,which is given to the user to let him know any special characteristics of the data analysed.ClusDM is a new method to solve multicriteria decision problems. It is able to find a ranking ofalternatives or to select the best ones. This process is not easy since usually it is not possible tomaximise all the partial profits (i.e.criteria) at the same time. In the thesis we present anoverview of the large amount of methods developed to solve this problem. We follow the utilitytheory approach.Classical methods consider only numerical criteria. Some extensions allow the consideration ofother scales, such as, fuzzy or ordinal values, but usually they are required to have a commonscale for all criteria. This thesis faces the problem of managing different types of criteria at thesame time. Methods following the utility approach consider two steps to sort a decisionproblem out: the aggregation and the ranking. We have included some additional steps in orderto improve the process: (i) the explanation phase and (ii) the quality measurement phase.In the "Explanation Phase", special attention is devoted to give an appropriate linguisticdescription of the ranking. The necessity to give a qualitatively described result has been arguedby different authors. The rationale behind this belief is that human decision makers understandbetter a linguistic statement characterising the selected alternative (or ranking of alternatives)than a numerical result or even a membership function. In this context, a new negation-basedsemantics has been studied. The key idea is that we can infer the meaning of a term knowing theterms that express an opposite value. The use of this new semantics representation seemsappropriate to obtain a result that can be easily understood by the decision maker.In the "Quality Measurement Phase", different quality measures for each stage of the processare calculated. With these measures we can give an overall value of the trustworthiness of thefinal result. This kind of information is very useful for the decision maker in order to pay moreor less attention to the recommendations of the system.

Les contribucions d'aquesta tesi uneixen dues disciplines: ciències ambientals (específicament, gestió d'aigües residuals) i informàtica (específicament, intel·ligència artificial). El tractament d'aigües residuals com a disciplina opera fent servir un rang de diferents enfocaments i mètodes que inclouen: control manual, control automàtic on-line, modelat numèric o no-numèric, models estadístics i simulacions. La tesi caracteritza la recerca interdisciplinària de tècniques d'intel·ligència artificial (raonament basat en regles, raonament basat en casos, ontologies i planificació) a sistemes de suport a la decisió a l'entorn ambiental. El disseny de l'arquitectura d'aquesta aplicació, el sistema OntoWEDSS, augmenta els sistemes clàsics de raonament existents (raonament basat en regles i basat en casos) amb una ontologia de domini per a la gestió de plantes de tractament d'aigües residuals. La integració de l'ontologia WaWO recentment creada proporciona a OntoWEDSS una major flexibilitat en la capacitat de gestió. La construcció del sistema de suport a la decisió OntoWEDSS es basa en l'estudi d'un cas específic, però el sistema també és d'interès general ja que l'arquitectura basada en l'ontologia pot aplicar-se a qualsevol estació depuradora i, a un nivell apropiat d'abstracció, a altres dominis ambientals. El sistema OntoWEDSS millora la diagnosi de l'estat de l'estació depuradora, proporciona suport a la solució de complexes problemes relacionats amb aigües residuals, i facilita el modelatge del coneixement i la seva reutilització mitjançant l'ontologia WaWO. En particular, a la investigació s'han aconseguit els següents objectius: (1) la millora del modelatge de la informació sobre processos de tractament d'aigües residuals i la clarificació de part de la confusió existent en la terminologia del domini, (2) la incorporació de coneixement microbiològic (referent al procés del tractament i modelat mitjançant una ontologia) dins del procés de raonament, (3) la creació d'un sistema de suport a la decisió amb tres nivells (percepció, diagnosi i suport a la decisió) que combina coneixement mitjançant una nova integració entre KBSs i ontologies, proporcionant millors resultats, (4) la eliminació d'obstacles existents en el raonament, obtinguda utilitzant el nou coneixement microbiològic codificat a l'estructura jeràrquica i a les relacions de l'ontologia, (5) la representació de relacions causa-efecte, degut a la implementació d'un conjunt de relacions que permeten a l'ontologia deduir automàticament la resposta a qüestions sobre el domini d'aigües residuals. OntoWEDSS està implementada en el llenguatge de programació LISP, fent servir el software Allegro Common LISP. S'ha dut a terme una avaluació focalitzada del sistema, basada en la valoració de la capacitat de resposta a situacions problemàtiques específiques, obtenint-se bons resultats. / Las contribuciones de esta tesis unen dos disciplinas: ciencias ambientales (específicamente, gestión de aguas residuales) e informática (específicamente, inteligencia artificial). El tratamiento de aguas residuales como disciplina opera utilizando un rango de diferentes enfoques y métodos que incluye: control automático on-line, modelado numérico o no-numérico, razonamiento basado en reglas, razonamiento basado en casos, soporte a la decisión y planificación. La tesis caracteriza una aplicación interdisciplinaria de técnicas de inteligencia artificial a sistemas de soporte a la decisión en el dominio ambiental. El diseño de la arquitectura de esta aplicación, el sistema OntoWEDSS, aumenta los sistemas híbridos de razonamiento ya existentes (razonamiento basado en reglas y basado en casos) con una ontología de dominio para la gestión de plantas de tratamiento de aguas residuales. La integración de la ontología WaWO, de nueva creación, proporciona a OntoWEDSS una mayor flexibilidad en la capacidad de gestión. La construcción del sistema de soporte a la decisión OntoWEDSS se basa en el estudio de un caso específico, pero el sistema resulta también es de interés general puesto que la arquitectura basada en ontologías puede aplicarse a cualquier planta de tratamiento de aguas residuales y, a un nivel apropiado de abstracción, a otros dominios ambientales. El sistema OntoWEDSS mejora la diagnosis del estado de la planta de tratamiento, proporciona soporte a la resolución de complejos problemas relacionados con aguas residuales, y facilita el modelado del conocimiento y su reutilización mediante la ontología WaWO. En particular, la investigación ha alcanzado los siguientes objetivos: (1) la mejora del modelado de la información sobre procesos de tratamiento de aguas residuales y la clarificación de parte de la confusión existente en la terminología relacionada, (2) la incorporación de conocimiento microbiológico (referente al proceso del tratamiento y modelado mediante una ontología) dentro del proceso de razonamiento, (3) la creación de un sistema de soporte a la decisión con tres estratos (percepción, diagnosis y soporte a la decisión) que combina conocimiento mediante una novedosa integración entre KBSs y ontologías, proporcionando mejores resultados, (4) la eliminación de obstáculos existentes en el razonamiento, hallada utilizando el nuevo conocimiento microbiológico codificado en la estructura jerárquica y las relaciones de la ontología, (5) la representación de relaciones causa-efecto, debido a la implementación de un conjunto de relaciones que permiten a la ontología deducir automáticamente la respuesta a cuestiones sobre el dominio de aguas residuales. OntoWEDSS está implementada en el lenguaje de programación LISP, usando el software Allegro Common LISP. Se ha llevado a cabo una evaluación enfocada del sistema, basada en la valoración de la capacidad de respuesta a situaciones problemáticas específicas, obteniéndose buenos resultados. / The contributions of this thesis bridge two disciplines: environmental science (specifically, wastewater management) and computer science (specifically, artificial intelligence). Wastewater management as a discipline operates using a range of different approaches and methods which include: manual control, on-line automatic control, numerical or non-numerical models, statistical models and simulation models. The thesis characterizes an interdisciplinary research on artificial intelligence techniques (rule-based reasoning, case-based reasoning, ontologies and planning) applied to environmental decision-support systems. The integrated architecture's design of this application, the OntoWEDSS system, augments classic reasoning systems (rule-based reasoning and case-based reasoning) with a domain ontology about the management of wastewater treatment plants. The integration of the newly created WaWO ontology provides a more flexible management capability to OntoWEDSS. The construction of the OntoWEDSS decision support system is based on a specific case study but the system is also of general interest, given that its ontology-underpinned architecture can be applied to any wastewater treatment plant and, at an appropriate level of abstraction, to other environmental domains. The OntoWEDSS system improves the diagnosis of the state of a treatment plant, provides support for wastewater-related complex problem-solving, and facilitates knowledge modeling and reuse by means of the WaWO ontology. The following research targets have been achieved in particular: (1) the improvement of the modeling of the information about wastewater treatment processes and the clarification of a part of the existing terminological confusion in the domain, (2) the incorporation of ontology-modeled microbiological knowledge related to the treatment process into the reasoning process, (3) the creation of a decision support system with three layers (perception, diagnosis and decision support) which combines knowledge through a novel integration between KBSs and ontologies, providing better results, (4) the solution of existing reasoning-impasses, found using the new microbiological knowledge encoded in the hierarchical structure and the relations of the ontology, (5) the representation of cause-effect relations, due to the implementation of a set of relations that enable the ontology to automatically deduce the answer to questions about the wastewater domain. OntoWEDSS is implemented in the LISP programming language, using Allegro Common LISP software. A focused evaluation of the system, founded on the assessment of the capacity of response to specific problematic situations, has been carried out and has given fine results. / Questa tesi contribuisce alla intersezione di due discipline: le scienze ambientali (specificamente, la gestione delle acque di rifiuto) e la informatica (specificamente, la intelligenza artificiale). Nel trattamento delle acque di rifiuto come disciplina si utilizzano diversi metodi, che includono: controllo manuale, controllo automatico on-line, modelli numerici o non-numerici e simulazioni. La tesi caratterizza un'applicazione interdisciplinare di tecniche di intelligenza artificiale a sistemi di aiuto alla decisione in campo ambientale. L'architettura di questa applicazione, il sistema OntoWEDSS, amplia i sistemi di ragionamento ibrido esistenti (ragionamento basato su un sistema di regole, ragionamento basato sull'esperienza, aiuto alla decisione e pianificazione) con un'ontologia di dominio per la gestione di depuratori di acque di rifiuto. L'integrazione dell'ontologia WaWO, di nuova creazione, fornisce a OntoWEDSS una maggiore flessibilità nella sua capacità di gestione. La costruzione del sistema OntoWEDSS si basa sullo studio di un caso specifico, però il sistema risulta anche di interesse generale dato che l'architettura basata su un'ontologia può essere applicata a un qualsiasi depuratore e, considerando un adeguato livello d'astrazione, ad altri domini ambientali. Il sistema OntoWEDSS migliora la diagnosi dello stato del depuratore, fornisce aiuto alla soluzione di problemi complessi relazionati con le acque di rifiuto e facilita la modellizzazione della conoscenza e la sua riutilizzazione mediante l'ontologia WaWO. In particolare, la ricerca realizzata ha raggiunto i seguenti obiettivi: (1) il miglioramento dell'informazione sui processi di depurazione e il chiarimento di parte della confusione esistente nella terminologia relativa, (2) l'incorporazione di conoscenza microbiologica (riguardo al processo di depurazione e mediante la modellizzazione ontologica) nel processo di ragionamento, (3) la creazione di un sistema di aiuto alla decisione con tre livelli (percezione, diagnosi e aiuto alla decisione) che combina la informazione mediante un nuovo tipo d'integrazione tra classici sistemi basati sulla conoscenza e ontologie, proporzionando risultati migliori, (4) l'eliminazione di alcuni ostacoli esistenti nel ragionamento, ottenuta utilizzando la nuova conoscenza microbiologica codificata nella struttura gerarchica e nelle relazioni dell'ontologia, (5) la rappresentazione di relazioni causa-effetto del mondo reale attraverso l'implementazione di un insieme di relazioni ontologiche che permettono di dedurre automaticamente le risposte a domande sul dominio delle acque di rifiuto. OntoWEDSS è implementata nel linguaggio di programmazione LISP, usando il software Allegro Common LISP. È stata realizzata una valutazione del sistema basata sulla stima della capacità di risposta a situazioni problematiche specifiche e si sono ottenuti risultati soddisfacenti.

Las memorias caché fueron incorporadas en los microprocesadores ya desde los primeros tiempos, y representan la solución más común para tratar la diferencia de velocidad entre el procesador y la memoria. Sin embargo, muchos estudios señalan que la capacidad de almacenamiento de la caché es malgastada muchas veces, lo cual tiene un impacto directo en el rendimiento del procesador. Aunque una caché está diseñada para explotar diferentes tipos de localidad, todas la referencias a memoria son tratadas de la misma forma, ignorando comportamientos particulares de localidad. El uso restringido de la información de localidad para cada acceso a memoria puede limitar la eficiencia de la cache. En esta tesis se demuestra como un análisis de localidad de datos puede ayudar al investigador a entender dónde y porqué ocurren los fallos de caché, y proponer entonces diferentes técnicas que hacen uso de esta información con el objetivo de mejorar el rendimiento de la memoria caché. Proponemos técnicas en las cuales la información de localidad obtenida por el analizador de localidad es pasada desde el compilador al hardware a través del ISA para guiar el manejo de los accesos a memoria.Hemos desarrollado un análisis estático de localidad de datos. Este análisis está basado en los vectores de reuso y contiene los tres típicos pasos: reuso, volumen y análisis de interferencias. Comparado con trabajos previos, tanto el análisis de volúmenes como el de interferencias ha sido mejorado utilizando información de profiling así como un análisis de interferencias más preciso. El analizador de localidad de datos propuesto ha sido incluido como un paso más en un compilador de investigación. Los resultados demuestran que, para aplicaciones numéricas, el análisis es muy preciso y el overhead de cálculo es bajo. Este análisis es la base para todas las otras partes de la tesis. Además, para algunas propuestas en la última parte de la tesis, hemos usado un análisis de localidad de datos basado en las ecuaciones de fallos de cache. Este análisis, aunque requiere más tiempo de cálculo, es más preciso y más apropiado para cachés asociativas por conjuntos. El uso de dos análisis de localidad diferentes también demuestra que las propuestas arquitectónicas de esta tesis son independientes del análisis de localidad particular utilizado.Después de mostrar la precisión del análisis, lo hemos utilizado para estudiar el comportamiento de localidad exhibido por los programas SPECfp95. Este tipo de análisis es necesario antes de proponer alguna nueva técnica ya que ayuda al investigador a entender porqué ocurren los fallos de caché. Se muestra que con el análisis propuesto se puede estudiar de forma muy precisa la localidad de un programa y detectar donde estan los "puntos negros" así como la razón de estos fallos en cache. Este estudio del comportamiento de localidad de diferentes programas es la base y motivación para las diferentes técnicas propuestas en esta tesis para mejorar el rendimiento de la memoria.Así, usando el análisis de localidad de datos y basándonos en los resultados obtenidos después de analizar el comportamiento de localidad de un conjunto de programas, proponemos utilizar este análisis con el objetivo de guiar tres técnicas diferentes: (i) manejo de caches multimódulo, (ii) prebúsqueda software para bucles con planificación módulo, y (iii) planificación de instrucciones de arquitecturas VLIW clusterizadas.El primer uso del análisis de localidad propuesto es el manejo de una novedosa organización de caché. Esta caché soporta bypass y/o está compuesta por diferentes módulos, cada uno orientado a explotar un tipo particular de localidad. La mayor diferencia de esta caché con respecto propuestas previas es que la decisión de "cachear" o no, o en qué módulo un nuevo bloque es almacenado, está controlado por algunos bits en las instrucciones de memoria ("pistas" de localidad). Estas "pistas" (hints) son fijadas en tiempo de compilación utilizando el análisis de localidad propuesto. Así, la complejidad del manejo de esta caché se mantiene bajo ya que no requiere ningún hardware adicional. Los resultados demuestran que cachés más pequeñas con un manejo más inteligente pueden funcionar tan bien (o mejor) que cachés convencionales más grandes.Hemos utilizado también el análisis de localidad para estudiar la interacción entre la segmentación software y la prebúsqueda software. La segmentación software es una técnica muy efectiva para la planificación de código en bucles (principalmente en aplicaciones numéricas en procesadores VLIW). El esquema más popular de prebúsqueda software se llama planificación módulo. Muchos trabajos sobre planificación módulo se pueden encontrar en la literatura, pero casi todos ellos consideran una suposición crítica: consideran un comportamiento optimista de la cache (en otras palabras, usan siempre la latencia de acierto cuando planifican instrucciones de memoria). Así, los resultados que presentan ignoran los efectos del bloqueo debido a dependencias con instrucciones de memoria. En esta parte de la tesis mostramos que esta suposición puede llevar a planificaciones cuyo rendimiento es bastante más bajo cuando se considera una memoria real. Nosotros proponemos un algoritmo para planificar instrucciones de memoria en bucles con planificación módulo. Hemos estudiado diferentes estrategias de prebúsqueda software y finalmente hemos propuesto un algoritmo que realiza prebúsqueda basándose en el análisis de localidad y en la forma del grafo de dependencias del bucle. Los resultados obtenidos demuestran que el esquema propuesto mejora el rendimiento de las otras heurísticas ya que obtiene un mejor compromiso entre tiempo de cálculo y de bloqueo.Finalmente, el último uso del análisis de localidad estudiado en esta tesis es para guiar un planificador de instrucciones para arquitecturas VLIW clusterizadas. Las arquitecturas clusterizadas están siendo una tendencia común en el diseño de procesadores empotrados/DSP. Típicamente, el núcleo de estos procesadores está basado en un diseño VLIW el cual particiona tanto el banco de registros como las unidades funcionales. En este trabajo vamos un paso más allá y también hacemos la partición de la memoria caché. En este caso, tanto las comunicaciones entre registros como entre memorias han de ser consideradas. Nosotros proponemos un algoritmo que realiza la partición del grafo así como la planificación de instrucciones en un único paso en lugar de hacerlo secuencialmente, lo cual se demuestra que es más efectivo. Este algoritmo es mejorado añadiendo una análisis basado en las ecuaciones de fallos de cache con el objetivo de guiar en la planificación de las instrucciones de memoria para reducir no solo comunicaciones entre registros, sino también fallos de cache. / Cache memories were incorporated in microprocessors in the early times and represent the most common solution to deal with the gap between processor and memory speeds. However, many studies point out that the cache storage capacity is wasted many times, which means a direct impact in processor performance. Although a cache is designed to exploit different types of locality, all memory references are handled in the same way, ignoring particular locality behaviors. The restricted use of the locality information for each memory access can limit the effectivity of the cache. In this thesis we show how a data locality analysis can help the researcher to understand where and why cache misses occur, and then to propose different techniques that make use of this information in order to improve the performance of cache memory. We propose techniques in which locality information obtained by the locality analyzer is passed from the compiler to the hardware through the ISA to guide the management of memory accesses.We have developed a static data locality analysis. This analysis is based on reuse vectors and performs the three typical steps: reuse, volume and interfere analysis. Compared with previous works, both volume and interference analysis have been improved by using profile information as well as a more precise inter-ference analysis. The proposed data locality analyzer has been inserted as another pass in a research compiler. Results show that for numerical applications the analysis is very accurate and the computing overhead is low. This analysis is the base for all other parts of the thesis. In addition, for some proposals in the last part of the thesis we have used a data locality analysis based on cache miss equations. This analysis, although more time consuming, is more accurate and more appropriate for set-associative caches. The usage of two different locality analyzers also shows that the architectural proposals of this thesis are independent from the particular locality analysis.After showing the accuracy of the analysis, we have used it to study the locality behavior exhibited by the SPECfp95 programs. This kind of analysis is necessary before proposing any new technique since can help the researcher to understand why cache misses occur. We show that with the proposed analysis we can study very accurately the locality of a program and detect where the hot spots are as well as the reason for these misses. This study of the locality behavior of different programs is the base and motivation for the different techniques proposed in this thesis to improve the memory performance.Thus, using the data locality analysis and based on the results obtained after analyzing the locality behavior of a set of programs, we propose to use this analysis in order to guide three different techniques: (i) management of multi-module caches, (ii) software prefetching for modulo scheduled loops, and (iii) instruction scheduling for clustered VLIW architectures.The first use of the proposed data locality analysis is to manage a novel cache organization. This cache supports bypassing and/or is composed of different modules, each one oriented to exploit a particular type of locality. The main difference of this cache with respect to previous proposals is that the decision of caching or not, or in which module a new fetched block is allocated is managed by some bits in memory instructions (locality hints). These hints are set at compile time using the proposed locality analysis. Thus, the management complexity of this cache is kept low since no additional hardware is required. Results show that smaller caches with a smart management can perform as well as (or better than) bigger conventional caches.We have also used the locality analysis to study the interaction between software pipelining and software prefetching. Software pipelining has been shown to be a very effective scheduling technique for loops (mainly in numerical applications for VLIW processors). The most popular scheme for software pipelining is called modulo scheduling. Many works on modulo scheduling can be found in the literature, but almost all of them make a critical assumption: they consider an optimistic behavior of the cache (in other words, they use the hit latency when a memory instruction is scheduled). Thus, the results they present ignore the effect of stalls due to dependences with memory instructions. In this part of the thesis we show that this assumption can lead to schedules whose performance is rather low when a real memory is considered. Thus, we propose an algorithm to schedule memory instructions in modulo scheduled loops. We have studied different software prefetching strategies and finally proposed an algorithm that performs prefetching based on the locality analysis and the shape of the loop dependence graph. Results obtained shows that the proposed scheme outperforms other heuristic approaches since it achieves a better trade-off between compute and stall time than the others. Finally, the last use of the locality analysis studied in this thesis is to guide an instruction scheduler for a clustered VLIW architecture. Clustered architectures are becoming a common trend in the design of embedded/DSP processors. Typically, the core of these processors is based on a VLIW design which partitionates both register file and functional units. In this work we go a step beyond and also make a partition of the cache memory. Then, both inter-register and inter-memory communications have to be taken into account. We propose an algorithm that performs both graph partition and instruction scheduling in a single step instead of doing it sequentially, which is shown to be more effective. This algorithm is improved by adding an analysis based on the cache miss equations in order to guide the scheduling of memory instructions in clusters with the aim of reducing not only inter-register communications, but also cache misses.

En los últimos años, el diseño de procesadores de altas prestaciones ha progresado a lo largo de dos corrientes de investigación: incrementar la profundidad del pipeline para permitir mayores frecuencias de reloj, y ensanchar el pipeline para permitir la ejecución paralela de un mayor numero de instrucciones. Diseñar un procesador de altas prestaciones implica balancear todos los componentes del procesador para asegurar que el rendimiento global no esta limitado por ningún componente individual. Esto quiere decir que si dotamos al procesador de una unidad de ejecución mas rápida, hay que asegurarse de que podemos hacer fetch y decodificar instrucciones a una velocidad suficiente para mantener ocupada a esa unidad de ejecución.Esta tesis explora los retos presentados por el diseño de la unidad de fetch desde dos puntos de vista: el diseño de un software mas adecuado para las arquitecturas de fetch ya existente, y el diseño de un hardware adaptado a las características especiales del nuevo software que hemos generado.Nuestra aproximación al diseño de un suevo software ha sido la propuesta de un nuevo algoritmo de reordenación de código que no solo pretende mejorar el rendimiento de la cache de instrucciones, sino que al mismo tiempo pretende incrementar la anchura efectiva de la unidad de fetch. Usando información sobre el comportamiento del programa (profile data), encadenamos los bloques básicos del programa de forma que los saltos condicionales tendrán tendencia a ser no tomados, lo cual favorece la ejecución secuencial del código. Una vez hemos organizado los bloques básicos en estas trazas, mapeamos las diferentes trazas en memoria de forma que minimicen la cantidad de espacio requerida para el código realmente útil, y los conflictos en memoria de este código. Además de describir el algoritmo, hemos realizado un análisis en detalle del impacto de estas optimizaciones sobre los diferentes aspectos del rendimiento de la unidad de fetch: la latencia de memoria, la anchura efectiva de la unidad de fetch, y la capacidad de predicción del predictor de saltos.Basado en el análisis realizado sobre el comportamiento de los códigos optimizados, proponemos también una modificacion del mecanismo de la trace cache que pretende realizar un uso mas efectivo del escaso espacio de almacenaje disponible. Este mecanismo utiliza la trace cache únicamente para almacenar aquellas trazas que no podrían ser proporcionadas por la cache de instrucciones en un único ciclo.También basado en el conocimiento adquirido sobre el comportamiento de los códigos optimizados, proponemos un nuevo predictor de saltos que hace un uso extensivo de la misma información que se uso para reordenar el código, pero en este caso se usa para mejorar la precisión del predictor de saltos.Finalmente, proponemos una nueva arquitectura para la unidad de fetch del procesador basada en explotar las características especiales de los códigos optimizados. Nuestra arquitectura tiene un nivel de complejidad muy bajo, similar al de una arquitectura capaz de leer un único bloque básico por ciclo, pero ofrece un rendimiento muy superior, siendo comparable al de una trace cache, mucho mas costosa y compleja.

Aquesta Tesi que pretén proporcionar un conjunt de tècniques per enfrontar-se al problema que suposa la variació del color en les imatges preses des d'una plataforma mòbil per causa del canvi en les condicions d'il·luminació entre diverses vistes d'una certa escena preses en diferents instants i posicions. També tracta el problema de la segmentació de imatges de color per a poder-les utilitzar en tasques associades a les capacitats d'un robot mòbil, com ara la identificació d'objectes o la recuperació d'imatges d'una gran base de dades.Per dur a terme aquests objectius, primerament s'estableix matemàticament la transformació entre colors degut a variacions d'il·luminació. Així es proposa un model continu per la generació del senyal de color com a generalització natural d'altres propostes anteriors. D'aquesta manera es pot estudiar matemàticament i amb generalitat les condicions per l'existència, unicitat i bon comportament de les solucions, i expressar qualsevol tipus d'aplicació entre colors, independentment del tipus de discretització. Així, queda palès la relació íntima entre el problema de la invariància de color i el de la recuperació espectral, que també es planteja a la pràctica. El model desenvolupat es contrasta numèricament amb els de regressió lineal, en termes d'errors de predicció.Un cop establert el model general, s'opta per un model lineal simplificat a l'hora de realitzar els càlculs pràctics i permet alleugerir el nombre dels mateixos. En particular, el mètode proposat es basa en trobar la transformació més probable entre dues imatges a partir del càlcul d'un conjunt de transformacions possibles i de l'estimació de la freqüència i grau d'efectivitat de cadascuna d'elles. Posteriorment, es selecciona el millor candidat d'acord amb la seva versemblança. L'aplicació resultant serveix per transformar els colors de la imatge tal i com es veuria sota les condicions d'il·luminació canòniques.Una vegada el color de les imatges d'una mateixa escena es manté constant, cal procedir a la seva segmentació per extreure'n la informació corresponent a les regions amb color homogeni. En aquesta Tesi es suggereix un algorisme basat en la partició de l'arbre d'expansió mínima d'una imatge mitjançant una mesura local de la probabilitat de les unions entre components. La idea és arribar a una segmentació coherent amb les regions reals, compromís entre particions amb moltes components (sobresegmentades) i amb molt poques (subsegmentades). Un altre objectiu és que l'algorisme sigui prou ràpid com per ser útil en aplicacions de robòtica mòbil. Aquesta característica s'assoleix amb un plantejament local del creixement de regions, tot i que el resultat presenti caràcters globals (color). La possible sobresegmentació es suavitza gràcies al factor probabilístic introduït.L'algorisme de segmentació també hauria de generar segmentacions estables en el temps. Així, l'algorisme referit s'ha ampliat incloent-hi un pas intermedi entre segmentacions que permet de relacionar regions semblants en imatges diferents i propagar cap endavant els reagrupaments de regions fets en anteriors imatges, així si en una imatge unes regions s'agrupen formant-ne una de sola, les regions corresponents en la imatge següent també s'han d'agrupar juntes. D'aquesta manera, dues segmentacions correlatives s'assemblen i es pot mantenir estable la segmentació d'una seqüència.Finalment, es planteja el problema de comparar imatges a partir del seu contingut. Aquesta Tesi es concentra només en la informació de color i, a més de investigar la millor distància entre segmentacions, es busca també mostrar com la invariància de color afecta les segmentacions.Els resultats obtinguts per cada objectiu proposat en aquesta Tesi avalen els punts de vista defensats, i mostren la utilitat dels algorismes, així com el model de color tant per la recuperació espectral com pel càlcul explícit de les transformacions entre colors. / This Thesis endeavors providing a set of techniques for facing the problem of color variation in images taken from a mobile platform and caused by the change in the conditions of lighting among several views of a certain scene taken at different instants and positions. It also treats the problem of segmenting color images in order to use them in tasks associated with the capacities of a mobile robot, such as object identification or image retrieval from a large database.In order to carry out these goals, first transformation among colors due to light variations is mathematically established. Thus, a continuous model for the generation of color is proposed as a natural generalization of other former models. In this way, conditions for the existence, uniqueness, and good behavior of the solutions can be mathematically studied with a great generality, and any type of applications among colors can be expressed independently of the discretization scheme applied. Thus, the intimate relation among the problem of color invariance and that of spectral recovery is made evident and studied in practice too. The developed model is numerically contrasted with those of a least squares linear regression in terms of prediction errors.Once the general model is established, a simplified linear version is chosen instead for carrying out the practical calculations while lightening the number of them. In particular, the proposed method is based on finding the likeliest transformation between two images from the calculation of a set of feasible transformations and the estimation of the frequency and the effectiveness degree of each of them. Later, the best candidate is selected in accordance with its likelihood. The resulting application is then able to transform the image colors as they would be seen under the canonical light.After keeping the image colors from a scene constant, it is necessary to proceed to their segmentation to extract information corresponding to regions with homogeneous colors. In this Thesis, an algorithm based on the partition of the minimum spanning tree of an image through a local measure of the likelihood of the unions among components is suggested. The idea is to arrive at a segmentation coherent with the real regions, a trade-off between partitions with many component (oversegmented) and those with fewer components (subsegmented).Another goal is that of obtaining an algorithm fast enough to be useful in applications of mobile robotics. This characteristic is attained by a local approach to region growing, even though the result still shows global feature (color). The possible oversegmentation is softened thanks to a probabilistic factor.The segmentation algorithm should also generate stable segmentations through time. Thus, the aforementioned algorithm has been widened by including an intermediate step that allows to relate similar regions in different images and to propagate forwards the regrouping of regions made in previous images. This way, if in some image some regions are grouped forming only one bigger region, the corresponding regions in the following image will also be grouped together. In this way, two correlatives segmentations resemble each other, keeping the whole segmented sequence stabler.Finally, the problem of comparing images via their content is also studied in this Thesis, focusing on the color information and, besides investigating which is for our aims the best distance between segmentation, also showing how color constancy affects segmentations. The results obtained in each of the goals proposed in this Thesis guarantee the exposed points of view, and show the utility of the algorithms suggested, as well as the color model for the spectral recovery and the explicit calculation of the transformations among colors.