This paper introduces the hypergraph transversal problem along with thefollowing iterative solutions: naive, branch and bound, and dynamic exponentialtime (NC-D). Odometers are introduced along with the functions that manipulatethem. The traditional definitions of hyperedge, hypergraph, etc., are redefined interms of odometers and lists. All algorithms and functions necessary to implementthe solution are presented along with techniques to validate and test the results.Lastly, parallelization advanced applications, and future research directions areexamined.

Aquesta tesi està inspirada en els agents naturals per tal de planificar de manera dinàmica la navegació d'un robot diferencial de dues rodes. Les dades dels sistemes de percepció són integrades dins una graella d'ocupació de l'entorn local del robot. La planificació de les trajectòries es fa considerant la configuració desitjada del robot, així com els vértexs més significatius dels obstacles més propers. En el seguiment de les trajectòries s'utilitzen tècniques locals de control predictiu basades en el model, amb horitzons de predicció inferiors a un segon. La metodologia emprada és validada mitjançant nombrosos experiments. / In this thesis are used natural agents for dinamic navigation of a differential driven wheeled mobile robot. The perception data are integrated on a local occupancy grid framework where planar floor model is assumed. The path-planning is done by considering the local desired configuration, as well as the meaningful local obstacle vertexes. The trajectory-tracking is implemented by using LMPC (local model predictive control) techniques, with prediction horizons of less than one second. Many experiments are tested in order to report the validity of the prosed methodology.

Machine learning algorithms have had breakthroughs in many areas in the last decades. The hardest task, to solve with machine learning, was solving tasks that humans solve intuitively, e.g. understanding natural language or recognizing specific objects in images. To overcome these problems is to allow the computer to learn from experience, instead of implementing a pre-written program to solve the problem at hand - that is how Neural Networks came to be. Neural Network is widely used in image analysis, and object detection algorithms have evolved considerably in the last years. Two of these algorithms are Faster Region-basedConvolutional Neural Networks(Faster R-CNN) and You Only Look Once(YOLO). The purpose of this thesis is to evaluate and benchmark state-of-the-art object detection methods and then analyze their performance based on reading information from images. The information that we aim to extract is digital and analog digits from the odometer of a car, this will be done through object recognition and region-based image analysis. Our models will be compared to the open-source Optical Character Recognition(OCR) model Tesseract, which is in production by the Stockholm-based company Greater Than. In this project we will take a more modern approach and focus on two object detection models, Faster R-CNN and YOLO. When training these models, we will use transfer learning. This means that we will use models that are pre-trained, in our case on a dataset called ImageNet, specifically for object detection. We will then use the TRODO dataset to train these models further, this dataset consists of 2 389 images of car odometers. The models are then evaluated through the measures of mean average precision(mAP), prediction accuracy, and Levenshtein Distance. Our findings are that the object detection models are out-performing Tesseract for all measurements. The highest mAP and accuracy is attained by Faster R-CNN while the best results, regarding Levenshtein distance, are achieved by a YOLO model. The final result is clear, both of our approaches have more diversity and are far better thanTesseract, for solving this specific problem.

[pt] Um diagrama de Bratteli B é um objeto combinatório representado por um grafo dividido em infinitos níveis, cada um com número finito de vértices e de arestas entre vértices de níveis consecutivos. Além disso, todo vértice possui ligação com vértices dos níveis precedente e sucessor. Estudamos, do ponto de vista topológico, o espaço dos caminhos infinitos formados pelas arestas de um diagrama de Bratteli, denotado por XB. Estabelecemos uma relação de equivalência neste espaço, denominada AF. Quando é possível definir uma ordem parcial em XB o diagrama é dito ordenado; neste caso, definimos um homeomorfismo em XB denominado de função de Bratteli-Vershik. Consideramos sistemas dinâmicos minimais definidos em conjuntos de Cantor e associamos a estes diagramas de Bratteli ordenados. Um exemplo paradigmático de um conjunto de Cantor é o espaço das sequências infinitas formadas por 00s e 10s, munido de uma métrica apropriada. Neste espaço são definidas as funções odômetro. Definimos a relação de equivalência orbital, na qual duas sequências são equivalentes se estão na mesma órbita do odômetro, e a relação de equivalência de caudas, onde duas sequências são equivalentes se a partir de alguma entrada elas são iguais. Estudamos como estas duas relações estão relacionadas. Provamos que o odômetro diádico é um homeomorfismo minimal definido em um conjunto de Cantor e, portanto, pode ser associado a um diagrama de Bratteli ordenado. Uma relação de equivalência é dita étale quando admite uma topologia gerada por uma ação local. Dois exemplos são as relações AF e orbital. Dada uma relação de equivalência étale R em um espaço X, definimos um invariante algébrico D(X,R). Construímos o grupo de dimensão de um diagrama de Bratteli. Provamos, então, que dado um diagrama de Bratteli B, seu grupo de dimensão é isomorfo a D(XB,RB), onde RB é relação AF de B. Finalmente, estudamos sob quais condições um grupo abeliano ordenado é o grupo de dimensão de um diagrama de Bratteli. Esta dissertação é baseada no livro de Ian F. Putnam Cantor minimal systems, publicado em University Lecture Series, 70. American Mathematical Society, Providence, RI, 2018. [6]. / [en] A Bratteli diagram B is a combinatorial object represented by a graph divided into infinite levels, each level with a finite number of vertices and edges between vertices of consecutive levels. Moreover, every vertex is connected to vertices of the preceding and successor levels. We study, from a topological point of view, the space of infinite paths formed by the edges of a Bratteli diagram, denoted by XB. We establish an equivalence relation on this space, called the AF relation. When it is possible to define a partial order in XB the Bratteli diagram is called ordered; in this case, we define a homeomorphism on XB called the Bratteli-Vershik function. We consider minimal dynamic systems defined on Cantor sets and associate to these systems ordered Bratteli diagrams. A paradigmatic example of a Cantor set is the space of the infinite sequences formed by 00s and 10s, equipped with an appropriate metric. In this space, are defined the odometer functions. We define the orbital equivalence relation, in which two elements of the Cantor set are equivalent if they are in the same orbit of the odometer, and the tail equivalence relation, where two sequences are equivalents if they differ in only finitely many entries. We study how these equivalence relations are related. We prove that the dyadic odometer is a minimal homeomorphism and, therefore, it can be associated to a ordered Bratteli diagram. An equivalence relation is called étale if it admits a topology generated by a local action. Two examples are the AF equivalence relation and the orbital equivalence relation above. Given an étale equivalence relation R on a space X, we define an algebraic invariant D(X,R). We construct the dimension group of a Bratteli diagram. Then, we prove that given a Bratteli diagram B, its dimension group is isomorphic to D(XB,RB), where RB is the AF equivalence relation of B. Finally, we study under which conditions an ordered abelian group is the dimension group for some Bratteli diagram. This master thesis is based on the book by Ian F. Putnam Cantor minimal systems, published in University Lecture Series, 70. American Mathematical Society, Providence, RI, 2018. [6].