Modelling dynamic obstacles using occupancy Markov chain mapping and SVM classification

December 4, 2023

Na área de sistemas autónomos, um dos principais tópicos de estudo é a construção de mapas de locais inicialmente desconhecidos. Várias abordagens foram desenvolvidas com sucesso para endereçar este problema, particularmente quando aplicado a robôs móveis capazes de construir um mapa a duas dimensões de um espaço interior, mas estas não são robustas em ambientes dinâmicos que são mais complexos e incluem objetos que se movem nas mais variadas escalas de tempo. Com este desafio em mente, propomos formas de representar e detetar o dinamismo presente no ambiente assumindo que a localização é conhecida a priori. É utilizado um método que calcula a taxa de movimentação de cada ponto do mapa com base na ocupação detetada e consoante a janela de tempo aplicável. As janelas de tempo permitem que sejam detetados objetos com dinamismos muito diferentes, desde objetos que se movem constantemente até obstáculos quase estáticos. Para representar a taxa de movimentação, cada célula do mapa é modelada por uma cadeia de Markov com dois estados - Ocupado e Livre - e os dados que permitem estimar os parâmetros de cada modelo são guardados em várias grelhas paralelas. É usada a Estimativa de Máxima Verosimilhança dos parâmetros das cadeias de Markov e proposto um método escalável de cálculo aproximado para tratar dados em falta. Os resultados desta tese mostram como diferentes estimadores se comportam consoante o volume de dados em falta e como classificadores baseados em Máquinas de Vectores de Suporte podem contribuir para a correta classificação de obstáculos dinâmicos. In the field of autonomous systems, one of the main topics of study is the construction of maps of initially unknown locations. Several approaches have been successfully developed to solve this problem, especially when applied to mobile robots capable of constructing a two-dimensional map of an indoor space, but these are not robust in dynamic environments that are more complex and include objects moving at different time scales. With this challenge in mind, we propose ways to represent and detect the dynamism present in the environment assuming that the location is known a priori. We use a method that calculates the movement rate of each point on the map based on the detected occupancy and depending on the applicable time-window. Time-windows allow objects with very different dynamisms to be detected, from constantly moving objects to almost static obstacles. To represent the movement rate, each cell on the map is modeled by a Markov chain with two states - Occupied and Free - and we store in several parallel grids the data that allows estimating the parameters of each model. Maximum Likelihood Estimation of Markov chain parameters is used, and a scalable approximate calculation method is proposed to handle missing data. The results of this thesis show how different estimators behave depending on the volume of missing data and how classifiers based on Support Vector Machines can contribute to the correct classification of dynamic obstacles.

Authors in the community:

• 

  R

  Ricardo João Ferreira Barreiros

  ist163968

Supervisors of this institution:

• 

  R

  Rodrigo Martins de Matos Ventura

  ist13950

203841212

Mestrado em Engenharia Eletrotécnica e de Computadores

electrical-engineering-electronic-engineering-information-engineering - Electrical engineering, electronic engineering, information engineering

Keywords

• Occupancy Grid Mapping
• Markov Chains
• Maximum Likelihood Estimation (MLE)
• Support Vector Machines (SVM)
• Mapeamento em Grelha de Ocupação
• Cadeias de Markov
• Estimativa de Máxima Verosimilhança (MLE)
• Máquinas de Vectores de Suporte (SVM)

eng - English

Instituto Superior Técnico