Kjennetegn på suksessfulle utviklingsmiljøer

Dando continuidade a um trabalho anterior [Fabrizi e Saffiotti 2000], Fabrizi e Saffiotti (2002) enriqueceram a representação topológica obtida a partir de uma grade de ocupação com informações métricas, tais como posição do centro do espaço livre, largura, altura e orientação em relação a um referencial comum. Este trabalho de Fabrizi e Saffiotti (2000) foi um dos principais influenciadores das abordagens apresentadas nesta tese.

Como visto no capítulo 1, um dos objetivos aqui apresentados é fazer com que o robô crie uma representação topológica na qual os nós representem as salas e corredores de um ambiente interno e as arestas representem as passagens entre as salas. Estes vértices e arestas armazenam informações métricas relativas ao ambiente local representado. Dessa forma, o mapa aqui construído é similar ao apresentada por Fabrizi e Saffiotti (2002). A representação proposta possui informações sobre a geometria de cada espaço local, o que permite a reconstrução do mapa na forma métrica. No entanto, ressalta-se que embora o objetivo final seja o mesmo, os meios utilizados para obter o mapa são distintos. Fabrizi e Saffiotti (2002) geram o grafo após o robô ter explorado todo o ambiente e ter construído uma grade de ocupação. A abordagem desta tese gera o mapa topológico iterativamente, ou seja, para cada nova sala investigada, um novo vértice é inserido no grafo.

Uma outra diferença é que a morfologia matemática foi utilizada como ferramenta para criar o grafo no trabalho de Fabrizi e Saffiotti (2000), e as informações métricas das salas são obtidas pelo cálculo dos momentos na grade gerada, enquanto que o mapa aqui proposto é gerado pela exploração do ambiente e tem as informações métricas obtidas por um método inspirado na transformada generalizada de Hough.

Similarmente a Fabrizi e Saffiotti (2002), Laviers e Peterson (2004) apresentaram uma idéia de mapeamento cognitivo que habilita o robô determinar a sua posição em termos abstratos. Os seus objetivos gerais são bastante próximos aos apresentados no capítulo 1: (1) representar o ambiente de trabalho do robô através de uma estrutura compacta e (2) permitir que o robô se localize de forma métrica e abstrata simultaneamente. Para isso, Laviers e Peterson (2004) utilizaram a abordagem híbrida, em que os nós do mapa to- pológico são segmentos de retas armazenados em uma estrutura denominada Absolute

Space Representation. Esta estrutura parte do pressuposto que cada ambiente local é in-

dependente de todos os outros. A construção deste tipo de mapa também é incremental: para cada espaço local o procedimento de obtenção das estruturas geométricas que dão o caráter métrico da representação é repetido e um novo nó é adicionado na representação topológica. As diferenças entre os dois trabalhos residem em:

1. O tipo de metodologia e ferramenta utilizada para obter a parte métrica: a proposta desta tese sugere a utilização direta da informação dada por um sensor de alcance qualquer (sonar ou laser) e a utilização do método de votação inspirado na transfor- mada generalizada de Hough para obter a figura geométrica que melhor se adaptar às informações sensoriais; o artigo de Laviers e Peterson (2004) propõe, inicial- mente, a utilização de uma grade local para representar o espaço local. Esta grade local é montada segundo os princípios do trabalho de Borenstein et al. (1996). Em seguida, uma série de procedimentos são utilizados para, a partir desta representa- ção matricial, obter um conjunto de pontos(x, y) que devem ser reordenados para a

2.1. MAPEAMENTO GLOBAL 19

aplicação do método dos mínimos quadrados. Com isso, determina-se um conjunto de retas que representa metricamente o espaço local onde está o robô.

2. O tipo de elemento geométrico usado para a parte métrica da representação híbrida: aqui é usada uma figura geométrica simples para representar todo o espaço local. É necessário partir de um prévio conhecimento abstrato de que os ambientes internos são semi-estruturados e que sejam facilmente representados por essa figura. O tra- balho de Laviers e Peterson (2004) usa linhas retas para aproximar os limites dos espaços locais.

Sobre a construção do mapa topológico e o tratamento utilizado para as incertezas sen- soriais e do robô, o artigo não foi específico. Deste modo não é possível realizar uma comparação mais detalhada.

Um mapa baseado na topologia do ambiente [e.g. Fabrizi e Saffiotti 2000, Fabrizi e Saffiotti 2002] também foi utilizado por Galindo et al. (2005). Eles propuseram uma abor- dagem para permitir que um robô móvel construa uma representação híbrida adicionada de informações semânticas. Estas informações semânticas são obtidas por visão compu- tacional. Elas consistem na atribuição de etiquetas (ou símbolos) para objetos percebidos pelo robô dentro do ambiente explorado. Por exemplo, os autores definem um conjunto de características para que se possa reconhecer uma cama, uma banheira, etc. Com isto, cada ambiente também pode receber uma etiqueta especial de acordo com a presença des- tes símbolos mais básicos. A forma como o robô faz a ligação entre a informação sensorial e a informação semântica é chamada de anchoring [Coradeschi e Saffiotti 2003].

Bandera et al. (2001) e Poncela et al. (2002) seguiram o mesmo procedimento adotado por Fabrizi e Saffiotti para obter uma representação híbrida. Eles partem de uma represen- tação em grade e obtêm uma outra topológica. O trabalho apresenta um esquema de nave- gação para fazer um robô percorrer eficientemente o ambiente desconhecido. O algoritmo de exploração utiliza informações previamente adquiridas para otimizar a construção do mapa. O grande diferencial destes trabalhos é que as relações geométricas entre as áreas não-exploradas são mantidas na representação topológica. Dessa forma, o grafo contém as áreas desconhecidas do ambiente e o procedimento de exploração do ambiente é man- tido enquanto houver conectividade entre vértices que representam áreas não-exploradas e vértices que estão associados a regiões já representadas.

Para construir este mapa híbrido, eles criaram uma representação em grade. Porém, visando a redução da memória ocupada para o armazenamento, eles trabalharam com uma estrutura de resolução variável. Assim, tendo esta grade, os autores agregaram células vi- zinhas que possuiam o mesmo valor e as associaram aos nós do mapa topológico. Este mapa era então formado por uma estrutura em árvores, onde cada nível correspondia a uma determinada resolução da grade. Embora tenham adotado procedimentos para ma- pear diferentes do apresentado nesta tese, os trabalhos de Bandera et al. (2001) e Poncela et al. (2002) geram a representação híbrida de maneira incremental.

Pelo apresentado, o padrão para obter mapas híbridos consiste em coletar informações sensoriais, abstrair uma representação métrica e, por fim, armazenar estes dados em uma estrutura topológica. Porém Kuipers e Byun (1991) propuseram uma outra alternativa de mapeamento híbrido. Inicialmente eles criam todo o mapa topológico para, em seguida,

20 CAPÍTULO 2. MAPEAMENTO DE AMBIENTES POR ROBÔS AUTÔNOMOS

obter as informações métricas do ambiente utilizando o grafo gerado como rota para ex- plorar o ambiente. Este mapa topológico era construído através de medidas sensoriais e estratégias de controle. Por exemplo, quando o robô navegava por um corredor, ele utili- zava as leituras do sensores de alcance para que pudesse controlar e manter uma distância específica das paredes. Esta metodologia de Kuipers e Byun (1991) apresentou uma série de vantagens como eliminação de erro acumulativo de localização (o mapa topológico não era construído com informações métricas, mas sim utilizando informações sensoriais e de controle), o movimento do robô era guiado por controle realimentado, a navegação não dependia da geometria do ambiente e da identificação correta de lugares anterior- mente explorados. Embora o artigo de Kuipers e Byun (1991) apresentasse resultados bem estabelecidos e tivesse sido referência para vários outros trabalhos que mapeiam um ambiente de forma híbrida, partindo da representação topológica para a métrica [Kuipers et al. 2004] ou da métrica para a topológica [Fabrizi e Saffiotti 2000], esta tese adota o mapeamento híbrido com a construção simultânea dos dois tipos de representação.

No trabalho de Kuipers et al. (2004) é apresentada uma melhoria do mapeamento híbrido de Kuipers e Byun (1991). Nele, a parte topológica representa o ambiente global e a parte métrica representa ambientes locais (nós do grafo). Esta representação métrica é por grade de ocupação construída com o auxílio do filtro de partículas [Thrun et al. 2000] para localização do robô.

Muitas vezes, mapas híbridos podem ser formados por metodologias distintas de um mesmo tipo de representação. Por exemplo, o artigo de Lerasle et al. (2003) apresentou uma representação de ambientes internos utilizando uma descrição estocástica [Smith et al. 1990]. Os objetos utilizados como referência foram marcas retangulares naturais do ambiente, como janelas, quadros e portas. O grafo foi do tipo generalizado de Voronöi, o qual também poderia ser enriquecido com a observação destes objetos.

Boada et al. (2004) também apresentaram uma proposta de mapeamento híbrido, de- nominada por eles como topo-geométrico, cujo objetivo era auxiliar a resolução dos pro- blemas de localização, planejamento de caminho e navegação. A idéia principal era re- presentar o ambiente como um grafo formado pela união de vários diagramas locais de Voronöi (ou mapas locais), construídos a partir de informações de sensores lasers. Em- bora estes mapas locais fossem grafos que representassem a conectividade do espaço livre do robô, tanto os nós quanto os arcos consistiam em informações métricas. Estas infor- mações eram as posições(x, y) e a distância entre tais pontos e os obstáculos locais. Isto

trouxe a vantagem de eliminar ambigüidades e melhorou o processo de localização. Além disso, cada diagrama local foi associado a um modelo cognitivo que representasse uma estrutura particular de um ambiente interno típico de escritórios, como corredores, jun- ções, etc. Dessa forma, com este tipo de representação híbrida, o artigo apresentou um algoritmo para localização do robô utilizando modelos markovianos.

Proposta semelhante foi apresentada por Victorino e Rives (2004). Eles utilizaram um mapa híbrido composto de um diagrama de Voronöi e de informações métricas lo- cais. O diagrama era criado através de exploração baseada nas informações sensoriais. Ele consistia em uma lista de pontos de bifurcação. Ou seja, pontos onde o robô podia seguir diferentes caminhos. Além desta lista, havia um conjunto de características que descreviam a topologia local do ambiente. Para que Victorino e Rives (2004) gerassem