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

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

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.

<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.

La détection et le pistage de cibles de surface, maritimes ou terrestres, constituent l’un des champs d’application de la surveillance par radar aéroporté. Dans ce contexte spécifique, il s’agit d’estimer les trajectoires d’un ou de plusieurs objets mobiles au cours du temps à partir de mesures radar bruitées. Cependant, plusieurs contraintes s’additionnent au problème d’estimation des trajectoires :1. le nombre d’objets présents dans la région d’intérêt est inconnu et peut évoluer au cours du temps,2. les mesures fournies par le radar ne correspondent pas toutes à des objets mobiles car certaines sont dues à l’environnement ; il s’agit de fausses alarmes,3. une mesure n’est pas toujours disponible pour chaque objet à chaque instant ; il s’agit de non-détections,4. les cibles de surface peuvent être très diverses en termes de capacité de manoeuvre.Pour tenir compte des trois premières exigences, les modèles d’ensembles finis aléatoires peuvent être envisagés pour procéder aux estimations simultanées du nombre d’objets et de leur trajectoire dans un formalisme bayésien. Pour répondre à la quatrième contrainte, une classification des objets à pister peut s’avérer utile. Aussi, dans le cadre de cette thèse, nous nous intéressons à deux traitements adaptatifs qui intègrent ces deux principes.Tout d’abord, nous proposons une approche conjointe de pistage et de classification dédiée au cas d’un objet évoluant en présence de fausses alarmes. Notre contribution réside dans le développement d’un algorithme incorporant un filtre fondé sur un ensemble fini aléatoire de Bernoulli. L’algorithme résultant combine robustesse aux fausses alarmes et capacité à classer l’objet. Cette classification peut être renforcée grâce à l’estimation d’un paramètre discriminant comme la longueur, qui est déduite d’une mesure d’étalement distance.Le second traitement adaptatif présenté dans cette thèse est une technique de pistage de groupes de cibles dont les mouvements sont coordonnés. Chaque groupe est caractérisé par un paramètre commun définissant la coordination des mouvements de ses cibles. Cependant, ces dernières conservent une capacité de manoeuvre propre par rapport à la dynamique de groupe. S’appuyant sur le formalisme des ensembles finis aléatoires, la solution proposée modélise hiérarchiquement la configuration multi-groupes multi-cibles. Au niveau supérieur, la situation globale est représentée par un ensemble fini aléatoire dont les éléments correspondent aux groupes de cibles. Ils sont constitués du paramètredu groupe et d’un ensemble fini aléatoire multi-cibles. Ce dernier contient les vecteurs d’état des cibles du groupe dont le nombre peut évoluer au cours du temps. L’algorithme d’estimation développé est lui-aussi organisé de manière hiérarchique. Un filtre multi-Bernoulli labélisé (LMB) permet d’estimer le nombre de groupes, puis pour chacun d’entre eux, leur probabilité d’existence ainsi que leur paramètre commun. Pour ce faire, le filtre LMB interagit avec un banc de filtres multi-cibles qui opèrent conditionnellement à une hypothèse de groupe. Chaque filtre multi-cibles estime le nombre et les vecteurs d’état des objets du groupe. Cette approche permet de fournir à l’opérationnel des informations sur la situation tactique. / Detecting and tracking maritime or ground targets is one of the application fields for surveillance by airborne radar systems. In this specific context, the goal is to estimate the trajectories of one or more moving objects over time by using noisy radar measurements. However, several constraints have to be considered in addition to the problem of estimating trajectories:1. the number of objects inside the region of interest is unknown and may change over time,2. the measurements provided by the radar can arise from the environment and do not necessarily correspond to a mobile object; the phenomenon is called false detection,3. a measurement is not always available for each object; the phenomenon is called non-detection,4. the maneuverability depends on the surface targets.Concerning the three first points, random finite set models can be considered to simultaneously estimate the number of objects and their trajectories in a Bayesian formalism. To deal with the fourth constraint, a classification of the objects to be tracked can be useful. During this PhD thesis, we developped two adaptive approaches that take into account both principles.First of all, we propose a joint target tracking and classification method dedicated to an object with the presence of false detections. Our contribution is to incorporate a filter based on a Bernoulli random finite set. The resulting algorithm combines robustness to the false detections and the ability to classify the object. This classification can exploit the estimation of a discriminating parameter such as the target length that can be deduced from a target length extent measurement.The second adaptive approach presented in this PhD dissertation aims at tracking target groups whose movements are coordinated. Each group is characterized by a common parameter defining the coordination of the movements of its targets. However, the targets keep their own capabilities of maneuvering relatively to the group dynamics. Based on the random finite sets formalism, the proposed solution represents the multi-target multi-group configuration hierarchically. At the top level, the overall situation is modeled by a random finite set whose elements correspond to the target groups. They consist of the common parameter of the group and a multi-target random finite set. The latter contains the state vectors of the targets of the group whose number may change over time. The estimation algorithm developed is also organized hierarchically. A labeled multi-Bernoulli filter (LMB) makes it possible to estimate the number of groups, and for each of them, to obtain their probability of existence as well as their common parameter. For this purpose, the LMB filter interacts with a bank of multi-target filters working conditionally to a group hypothesis. Each multi-target filter estimates the number and state vectors of the objects in the group. This approach provides operational information on the tactical situation.