Intelligent robot navigation using a sparse distributed memory

Abstract

The dream of building intelligent machines dates back thousands of years. However, despite the huge advancements in science and technology, modern robots are still fit only to very specific tasks. There are no general-purpose robots able to learn and perform any kind of task the way humans do. Part of the problem arises from the fact that the concept of intelligence is not clearly defined, implying that researchers are pursuing a moving target. This work reviews some important concepts about intelligence, then presents a system which navigates a robot using visual memories stored into an associative memory. The system is intelligent, in the sense that it selects only relevant images and data to store, and infers new routes from the known paths. Many algorithms have already been proposed to navigate mobile robots. In this work the goal is to use a Sparse Distributed Memory (SDM), a kind of associative memory proposed by Pentti Kanerva, based on the properties of high dimensional binary spaces. Some characteristics of SDMs are that they are very immune to noisy data, can deal with incomplete information, can learn on a single pass and naturally forget older memories when close to their maximum capacity. They work very well on high dimensional spaces, and are also appropriate to work with sequences of events, where each event is associated with its successor or predecessor. The SDM naturally confers on the robot many characteristics of the human memory, thus being a powerful and general model, comparable to or better than other navigation methods. The goal of the work described was to build a system that can navigate a robot using sequences of visual memories stored into a sparse distributed memory. During a supervised learning stage, the robot acquires images from its built-in front camera. Selected grabbed images are stored into the SDM. Each image is accompanied with some additional information, such as the motion the robot performed just after capturing it, the number of the sequence and the position of the image in the sequence. That makes it possible for the robot to repeat the same path autonomously later. A simple algorithm that uses a block matching technique was also implemented, to correct small horizontal drifts that may occur during autonomous robot navigation. In order to make the system more robust and improve the quality of the raw images, they can be equalised or contrast stretched before being passed on to the SDM. The proposed approach works very well. However, as soon as the system was implemented and the first tests were run, one major problem arose. The SDM model is suitable to work with random boolean data. Nonetheless, sensorial data is often encoded using the natural binary code. In the case of the images used for navigation, each pixel is represented by an 8-bit graylevel. The dimension of the pixel space is, therefore, the integer interval [0, 255], not boolean. The difference of methods used to capture the information and to process it into the SDM affects the performance of the SDM. In order to get a better insight into the problem and overcome it, four different operation modes were implemented, three using the Hamming distance and one using an arithmetic distance. The performance of the SDM was tested for all four methods, in the domains of robot navigation and manipulation. To the best of the author’s knowledge, this is the first time those comparisons were performed, and that is one major contribution of the present work. Since the SDM was proposed in the 1980s, it has been subject to intense research and many authors have proposed improvements. However, so far it was not clear how robust the SDM would be in practice, specially in the task of robot navigation. In the present work, different versions of the SDM were tested facing different problems that robots typically have to face in order to navigate by using visual information. That includes strong illumination changes, scenario changes and memory overflow. That is another important contribution of this work, since this is possibly the first time such tests have been performed. Finally, the last major contribution of this work is an algorithm to build a topological representation of the environment using images and a SDM. The SDM was used both to store the images and as a pattern recognition tool to detect overlaps of paths. Using that topological representation it was possible to plan new routes, different from the ones that were taught. The results show that the method proposed is appropriate to successfully navigate mobile robots, based on visual memories, and the arithmetic SDM shows the best performance at the lowest computational cost.

O sonho de construir máquinas inteligentes data de há milhares de anos. No entanto, e apesar dos grandes avanços científicos e tecnológicos, mesmo os mais modernos robôs ainda são desenvolvidos apenas para tarefas muito específicas. Não há robôs “genéricos”, capazes de aprender e fazer qualquer tarefa da mesma forma que os humanos normalmente fazem. Parte do problema decorre do facto de ainda não haver uma definição clara do que é a inteligência. Este trabalho apresenta uma revisão dos mais importantes conceitos sobre o que é a inteligência. Depois apresenta um sistema que um robô navega usando memórias visuais, guardadas numa memória associativa. O sistema é inteligente, no sentido que selecciona apenas as imagens e dados mais importantes para guardar na memória, e infere novos caminhos partindo daqueles que já conhece. Já foram propostos muitos algoritmos para navegar robôs móveis. Neste trabalho o objectivo foi usar uma Memória Esparsa Distribuída (SDM), um tipo de memória associativa proposta por Pentti Kanerva, baseada nas propriedades de espaços binários de elevada dimensão. Algumas das suas mais importantes características são o facto de serem muito tolerantes a informação com grandes quantidades de ruído, poderem lidar com informação incompleta, poderem aprender numa única passagem (one-shot) e esquecerem naturalmente memórias mais antigas. Além disso, as SDMs são naturalmente apropriadas para trabalhar com vectores de elevada dimensão e sequências de eventos, onde cada evento é associado ao respectivo sucessor ou predecessor. Assim, a SDM confere naturalmente ao robô algumas características da memória humana, sendo um modelo poderoso e generalista, comparável ou potencialmente melhor do que outros modelos de navegação de robô geralmente utilizados. O objecto do presente trabalho foi a construção de um sistema para navegar um robô usando sequências de memórias visuais gravadas numa memória esparsa distribuída. Durante uma fase de aprendizagem supervisionada, o robô adquire imagens de uma câmara frontal. Imagens consideradas relevantes são guardadas na SDM. Com cada imagem é gravada também informação adicional, que inclui o movimento que o robô executou quando a imagem foi capturada, o número da sequência (caminho) e a posição da imagem na sequência. Usando essa informação, o robô é posteriormente capaz de repetir o mesmo caminho autonomamente. Um algoritmo simples, baseado numa técnica de comparação de blocos (block matching), permite detectar e corrigir pequenos desvios (drifts) que possam ocorrer durante a navegação autónoma. De forma a tornar o sistema mais robusto e melhorar a qualidade das imagens, estas podem ser equalizadas ou normalizadas (contrast stretched) antes de serem gravadas na SDM. O método descrito anteriormente produz bons resultados. Contudo, logo que o sistema foi implementado e executados os primeiros testes, detectou-se um problema importante. O problema tem a ver com o facto da SDM ser apropriada para funcionar em espaços booleanos. No entanto, a informação sensorial dos robôs normalmente não é booleana: é codificada usando o código binário natural. No caso das imagens em níveis de cinza usadas neste trabalho, cada pixel é representado por um número de 8 bits. A dimensão do espaço de um pixel é, portanto, o intervalo inteiro [0, 255], não um espaço booleano. Esta diferença de métodos de codificaçãoo usada para recolher a informação dos sensores e para processá-la dentro da SDM afecta significativamente o desempenho da memória. De forma a compreender melhor o problema e resolvê-lo, foram implementados quatro modos de operação da memória, correspondendo a quatro codificações diferentes da informação manipulada. O desempenho do sistema foi testado para cada um dos quatro modos, nos domínios da navegação e da manipulação robótica. Essa é uma das contribuições mais importantes deste trabalho. Desde que a SDM foi originalmente proposta, na década de 80 do século XX, foram construídos vários modelos e publicadas várias propostas de melhoria do modelo original. No entanto, até ao momento não eram claras as potencialidades e limites da memória, especialmente na tarefa de navegar um robô com base em memórias visuais. Neste trabalho, as várias versões da SDM foram testadas em situações que são problemas típicos da navegação baseada em imagens. Designadamente, situações de variação da iluminação, alterações do cenário e saturação da memória. Essa é outra importante contribuição desta tese. Finalmente, a última contribuição deste trabalho é um algoritmo para construir uma representação topológica do ambiente usando as imagens e a SDM. A SDM é usada simultaneamente para guardar as imagens capturadas e como ferramenta de reconhecimento de padrões para detectar sobreposição de trajectórias. Desta forma, foi possível usar a representação topológica para planear trajectórias novas, diferentes das ensinadas. Os resultados mostram que o método proposto é adequado para guiar robôs móveis, baseados em memórias visuais, e que a SDM aritmética exibe o melhor desempenho com o menor custo computacional.