This thesis considers three related structures on finite sets and outstanding conjectures on two of them. Several new problems and conjectures are stated.A union-closed collection of sets is a collection of sets which contains the union of each pair of sets in the collection. A completely separating system of sets is a collection of sets in which for each pair of elements of the universal set, there exists a set in the collection which contains the first element but not the second, and another set which contains the second element but not the first. An antichain (Sperner Family) is a collection of distinct sets in which no set is a subset of another set in the collection. The size of an antichain is the number of sets in the collection. The volume of an antichain is the sum of the cardinalities of the sets in the collection. A flat antichain is an antichain in which the difference in cardinality between any two sets in the antichain is at most one.The two outstanding conjectures considered are:The union-closed sets conjecture - In any union-closed collection of non-empty sets there is an element of the universal set in at least half of the sets in the collection;The flat antichain conjecture - Given an antichain with size s and volume V, there is a flat antichain with the same size and volume.Union-closed collections are considered in two ways. Improvements are made to the previously known bounds concerning the minimum size of a counterexample to the union-closed sets conjecture. Results are derived on the minimum size of a union-closed collection generated by a given number of k-sets. An ordering on sets is described, called order R and it is conjectured that choosing a collection of m k-sets in order R will always minimise the size of the union-closed collection generated by m k-sets.Several variants on completely separating systems of sets are considered. A ++ / determination is made of the minimum size of such collections, subject to various constraints on the collections. In particular, for each n and k, exact values or bounds are determined for the minimum size of completely separating systems on a n-set in which each set has cardinality k.Antichains are considered in their relationship to completely separating systems and the flat antichain conjecture is shown to be true in certain cases.

Tesis para optar al grado de Magíster en Ciencias de la Ingeniería, Mención Eléctrica / Memoria para optar al título de Ingeniero Civil Eléctrico / Esta tesis se enfoca en resolver el problema del multi-target tracking en ambientes altamente dinámicos, y utilizando robots que poseen baja capacidad de procesamiento y sensores limi- tados. Para esto se utiliza un nuevo método de realizar tracking baso en Random Finite Sets (RFS). La utilización de este método supone diferentes mejoras como la eliminación del data association problem o la utilización de la información negativa de los sensores. La hipótesis que se desea probar es que la utilización de este nuevo método puede obtener mejores resultados que los clásicos métodos de tracking, como el EKF multi-hipótesis. Además se desea demostrar que es posible realizar un tracking de este estilo en robots de poco procesamiento computacional y que este resultado se puede mejorar aún más si un conjunto de robots comparten sus estimaciones para generar una estimación global. Para esto se utiliza el robot Nao, el cual es utilizado en la competencia RoboCup, la cual corresponde a una competencia de fútbol robótico. Es en este escenario donde se implementa un método de tracking, basado en RFS, que se utiliza para ubicar todos los robots de la cancha, con tal de realizar un mapa de obstáculos. La implementación de este método la caracterización de cada sensor del robot, los cuales son utilizados como inputs del sistema. Finalmente, se realizan diversas pruebas, ya sea con robots reales o con simulaciones realistas, la cuales constan de escenarios ficticios y de partidos reales. En cada una de estas, se compara el mapa de obstáculos obtenido con las posiciones reales de los robots con la cancha. Esta comparación se realiza utilizando una medida de distancia especialmente diseñada para comparar conjuntos, llamada OSPA. Los resultados obtenidos demuestran que el método propuesto en esta tesis supera en general a los métodos clásicos, ya sea tanto cualitativa como cuantitativamente. Se pueden observar claramente las ventajas de la utilización negativa de los sensores, así como la no necesidad de resolver el data association problem. También se puede observar la mejora generada al utilizar la información compartida entre robots, lo que genera un mapa de obstáculos más preciso. / Fondecyt 1161500

Probability theory is a branch of mathematics concerned with determining the long run frequency or chance that a given event will occur. This chance is determined by dividing the number of selected events by the number of total events possible, assuming these events are equally likely. Probability theory is simply enumerative combinatorial analysis when applied to finite sets. For a given finite sample space, probability questions are usually "just" a lot of counting. The purpose of this thesis is to provide some in depth analysis of several combinatorial methods, including basic principles of counting, permutations and combinations, by specifically exploring one type of probability problem: C ordered possible elements that are equally likely s independent sampled subjects r distinct elements, where r = 1, 2, 3, …, min (C, s) we want to know P(s subjects utilize exactly r distinct elements). This thesis gives a detailed step by step analysis on techniques used to ultimately finding a general formula to solve the above problem.

Magíster en Ciencias de la Ingeniería, Mención Eléctrica. Ingeniero Civil Eléctrico / Este trabajo trata sobre el diseño e implementación de un sistema de Localización y Mapeo Simultáneo (SLAM) visual usando la teoría de Conjuntos Finitos Aleatorios (RFS), en el que un navegador (e.g. robot, auto, teléfono celular, etc.) utiliza una cámara de vídeo RGB-D para reconstruir la escena a su alrededor y al mismo tiempo descubrir su propia posición. Esta capacidad es relevante para las tecnologías del futuro, que deberán desplazarse sin ayuda externa. Se considera la inclusión de modelos realistas de medición y movimiento, incluyendo la intermitencia de las detecciones de objetos, la presencia de falsos positivos en las mediciones y el ruido en la imagen. Para ello se analizan sistemas basados en la teoría RFS, que es capaz de incluir estos efectos de manera fundamentada, a diferencia de otras alternativas del estado del arte que se basan en heurísticas poco realistas como el conocimiento absoluto de las asociaciones de datos entre mediciones y puntos en el mapa. Se incluye una amplia revisión de la literatura, desde Structure from Motion a Odometría Visual, a los distintos algoritmos para SLAM. Luego, se procede a explicar los detalles de implementación de un sistema flexible para el análisis de algoritmos de SLAM, así como la implementación particular del algoritmo Rao-Blackwellized (RB)-Probability Hypothesis Density (PHD)-SLAM. Se presentan análisis del desempeño de este algoritmo al cambiar las distintas estadísticas que pueden variar en su uso práctico. Se hace una comparación detallada con la alternativa Incremental Smoothing and Mapping (iSAM2), usualmente usada en otros sistemas del estado del arte. Luego, basado en la teoría de Modelos Gráficos Probabilísticos (PGM) que está detrás de iSAM2, se propone un nuevo algoritmo, Loopy PHD-SLAM, capaz de propagar información a lo largo del grafo inducido de manera eficiente, incluyendo las estadísticas de RFS. Con una implementación sencilla como prueba de concepto, se observa la capacidad de este nuevo método de cerrar ciclos y converger a soluciones correctas. / Este trabajo ha sido auspiciado por Conicyt

A teoria de conjuntos por vezes deixada de lado em algumas escolas de ensino mÃdio, constitui-se em um elemento primordial para o entendimento das funÃÃes, em especial. A nÃo abordagem, ou a sua abordagem superficial, deixa no estudante uma lacuna difÃcil de ser suprida em estudos posteriores. AliÃs, a lacuna deixada pode dificultar o desempenho do estudante no ensino superior. Diante desta constataÃÃo, à objetivo principal desta dissertaÃÃo fazer uma leitura dos principais tÃpicos ligados à Teoria de Conjuntos do ensino mÃdio, ao mesmo tempo em que faz uma ponte entre estes e outros pontos nÃo menos importantes, tratando conjuntos em uma linguagem mais acadÃmica. SerÃo abordados desde as propriedades e teoremas relacionados a conjuntos finitos, atà a sua generalizaÃÃo para conjuntos infinitos, culminando com o teorema de Cantor-Schroeder-Bernstein, o Axioma da Escolha, e o Lema de Zorn. Para tantos, realizaram-se pesquisas bibliogrÃficas em fontes variadas. / The set theory sometimes left out in some high schools, is in a key element for understanding the functions in particular. Failure to address this issue or its superficial approach leaves the student a difficult gap to be filled in later studies. Incidentally, the left gap may hinder student performance in higher education. If this is so, is the main objective of this work to a reinterpretation of the main topics linked to the high school set theory, while making a bridge between these and other equally important points dealing with sets in a more academic language. Will be covered from the properties and theorems related to finite sets up its generalization to infinite sets, culminating in the Cantor-Schroeder-Bernstein theorem, the Axiom of Choice and Zornâs Lemma. To this end, there were literature searches in various sources.

Multi-target tracking (MTT) methods estimate the trajectory of targets from noisy measurement; therefore, they can be used to handle the pedestrian-vehicle interaction for a moving vehicle. MTT has an important part in assisting the Automated Driving System and the Advanced Driving Assistance System to avoid pedestrian-vehicle collisions. ADAS and ADS rely on correct estimates of the pedestrians' position and velocity, to avoid collisions or unnecessary emergency breaking of the vehicle. Therefore, to help the risk evaluation in these systems, the MTT needs to provide accurate and robust information of the trajectories (in terms of position and velocity) of the pedestrians in different environments. Several factors can make this problem difficult to handle for instance in crowded environments the pedestrians can suffer from occlusion or missed detection. Classical MTT methods, such as the global nearest neighbour filter, can in crowded environments fail to provide robust and accurate estimates. Therefore, more sophisticated MTT methods should be used to increase the accuracy and robustness and, in general, to improve the tracking of targets close to each other. The aim of this master's thesis is to improve the situational awareness with respect to pedestrians and pedestrian-vehicle interactions. In particular, the task is to investigate if the GM-PHD and the GM-CPHD filter improve pedestrian tracking in urban environments, compared to other methods presented in the literature.  The proposed task can be divided into three parts that deal with different issues. The first part regards the significance of different clustering methods and how the pedestrians are grouped together. The implemented algorithms are the distance partitioning algorithm and the Gaussian mean shift clustering algorithm. The second part regards how modifications of the measurement noise levels and the survival of targets based on the target location, with respect to the vehicle's position, can improve the tracking performance and remove unwanted estimates. Finally, the last part regards the impact the filter estimates have on the tracking performance and how important accurate detections of the pedestrians are to improve the overall tracking. From the result the distance partitioning algorithm is the favourable algorithm, since it does not split larger groups. It is also seen that the proposed filters provide correct estimates of pedestrians in events of occlusion or missed detections but suffer from false estimates close to the ego vehicle due to uncertain detections. For the comparison, regarding the improvements, a classic standard MTT filter applying the global nearest neighbour method for the data association is used as the baseline. To conclude; the GM-CPHD filter proved to be the best out of the two proposed filters in this thesis work and performed better also compared to other methods known in the literature. In particular, its estimates survived for a longer period of time in presence of missed detection or occlusion. The conclusion of this thesis work is that the GM-CPHD filter improves the tracking performance and the situational awareness of the pedestrians.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

<p>Multiple target tracking (MTT) is a major area that occurs in a variety of real world systems. The problem involves the detection and estimation of an unknown number of targets within a scenario space given a sequence of noisy, incomplete measurements. The classic approach to MTT performs data association between individual measurements, however, this step is a computationally complex problem. Recently, a series of algorithms based on Random Finite Set (RFS) theory, that do not require data association, have been introduced. This thesis addresses some of the main deficiencies involved with RFS methods and derives key extensions to improve them for use in real world systems.\\</p> <p>The first contribution is the Weight Partitioned PHD filter. It separates the Probability Hypothesis Density (PHD) surface into partitions that represent the individual state estimates both spatially and proportionally. The partitions are labeled and propagated over several time steps to form continuous track estimates. Multiple variants of the filter are presented. Next, the Multitarget Multi-Bernoulli (MeMBer) filter is extended to allow the tracking of manoeuvring targets. A model state variable is incorporated into the filter framework to estimate the probability of each motion model. The standard implementations are derived. Finally, a new linear variant of the Intensity filter (iFilter) is presented. A Gaussian Mixture approximation provides more computationally efficient implementation of the iFilter.</p> <p>Each of the new algorithms are validated on simulated data using standard multitarget tracking metrics. In each case, the methods improve on several aspects of multitarget tracking in the real world.</p> / Doctor of Engineering (DEng)

The multi-target tracking problem essentially involves the recursive joint estimation of the state of unknown and time-varying number of targets present in a tracking scene, given a series of observations. This problem becomes more challenging because the sequence of observations is noisy and can become corrupted due to miss-detections and false alarms/clutter. Additionally, the detected observations are indistinguishable from clutter. Furthermore, whether the target(s) of interest are point or extended (in terms of spatial extent) poses even more technical challenges. An approach known as random finite sets provides an elegant and rigorous framework for the handling of the multi-target tracking problem. With a random finite sets formulation, both the multi-target states and multi-target observations are modelled as finite set valued random variables, that is, random variables which are random in both the number of elements and the values of the elements themselves. Furthermore, compared to other approaches, the random finite sets approach possesses a desirable characteristic of being free of explicit data association prior to tracking. In addition, a framework is available for dealing with random finite sets and is known as finite sets statistics. In this thesis, advanced signal processing techniques are employed to provide enhancements to and develop new random finite sets based multi-target tracking algorithms for the tracking of both point and extended targets with the aim to improve tracking performance in cluttered environments. To this end, firstly, a new and efficient Kalman-gain aided sequential Monte Carlo probability hypothesis density (KG-SMC-PHD) filter and a cardinalised particle probability hypothesis density (KG-SMC-CPHD) filter are proposed. These filters employ the Kalman- gain approach during weight update to correct predicted particle states by minimising the mean square error between the estimated measurement and the actual measurement received at a given time in order to arrive at a more accurate posterior. This technique identifies and selects those particles belonging to a particular target from a given PHD for state correction during weight computation. The proposed SMC-CPHD filter provides a better estimate of the number of targets. Besides the improved tracking accuracy, fewer particles are required in the proposed approach. Simulation results confirm the improved tracking performance when evaluated with different measures. Secondly, the KG-SMC-(C)PHD filters are particle filter (PF) based and as with PFs, they require a process known as resampling to avoid the problem of degeneracy. This thesis proposes a new resampling scheme to address a problem with the systematic resampling method which causes a high tendency of resampling very low weight particles especially when a large number of resampled particles are required; which in turn affect state estimation. Thirdly, the KG-SMC-(C)PHD filters proposed in this thesis perform filtering and not tracking , that is, they provide only point estimates of target states but do not provide connected estimates of target trajectories from one time step to the next. A new post processing step using game theory as a solution to this filtering - tracking problem is proposed. This approach was named the GTDA method. This method was employed in the KG-SMC-(C)PHD filter as a post processing technique and was evaluated using both simulated and real data obtained using the NI-USRP software defined radio platform in a passive bi-static radar system. Lastly, a new technique for the joint tracking and labelling of multiple extended targets is proposed. To achieve multiple extended target tracking using this technique, models for the target measurement rate, kinematic component and target extension are defined and jointly propagated in time under the generalised labelled multi-Bernoulli (GLMB) filter framework. The GLMB filter is a random finite sets-based filter. In particular, a Poisson mixture variational Bayesian (PMVB) model is developed to simultaneously estimate the measurement rate of multiple extended targets and extended target extension was modelled using B-splines. The proposed method was evaluated with various performance metrics in order to demonstrate its effectiveness in tracking multiple extended targets.