The York Scriveners’ prompt copy

Em forma de procedimento o mapeamento em Grade de Ocupação pode ser arranjado de acordo com o Algoritmo 1. O pseudocódigo apresentado está baseado no exemplo exposto por Thrun et al. (2005).

Algoritmo 1: mapeamento_em_grade_de_ocupação(_{ℓt_n−1_},xt,zt)

Entrada:_{ℓt_n−1_{}, x}t, zt.

Saída:_{ℓt_n}.

para cada célula mnpertence ao mapa faça

se mnestá dentro do campo de visão do sensor então

calcule p(mn|zt, xt) (modelo inverso do sensor);

atualize o valor da célula mncom ℓtn= log

p(mn|xt,zt) 1−p(mn|xt,zt)− log 1−p(mn) p(mn) + ℓtn−1; senão ℓt_n= ℓt−1 n ; fim se fim para

O algoritmo apresenta como dados de entrada_{ℓt_n−1_{}, que são os valores de ocupação} de todas as células calculados previamente, xt, que é vetor com a posição e orientação

do robô e zt, que é o resultado da medição sensorial; e como saída{ℓtn} que representa

os valores de ocupação atualizados. Existe um laço que varre todas as células do mapa e testa se estão no campo visual do sensor do robô. Caso a célula esteja sendo alcançada pelo sensor o seu valor de ocupação é atualizado de acordo com o modelo adotado para o sensor através da Equação 4.10. Senão, permanece com o valor de ocupação previamente calculado no passo t_{− 1.}

Não há necessidade de varrer todo o mapa em grade para verificar células dentro ou fora do campo de visão do sensor. Na prática, se faz uma heurística simples para que somente as células alcançadas pelo sensor sejam percorridas e atualizadas, evitando assim, maior tempo de processamento.

4.1.3

Trabalhos Relacionados

Uma importante característica do mapeamento em Grade de Ocupação é que ele pode ser realizado por robôs com distintos sensores. A construção de um mapa em grade não se restringe a um determinado tipo de sensor. Investigando os sensores mais citados nesse trabalho (sonar, lasers e câmeras), é fácil encontrar na literatura inúmeras referên- cias que mensionam a construção de mapas em grade com esses dispositivos. Como já declarado em um capítulo anterior, os primeiros trabalhos em Grade de Ocupação surgi- ram na década de 1980 [Elfes 1987][Moravec 1988][Elfes 1989]. Esses primeiros estudos foram elaborados com robôs equipados com sonares. Ainda hoje esses sensores são uti- lizados nesse tipo mapeamento, apesar de eles apresentarem significantes falhas em suas medições. Gupta et al. (2007), por exemplo, utilizaram o mapeamento em Grade de Ocu- pação a partir de informações coletadas por sonares para mapear ambientes dinâmicos. Uma rede neural é aplicada para que as mudanças percebidas no ambiente sejam tratadas de forma adequada e expressas corretamente no mapa em grade.

4.1. GRADE DE OCUPAÇÃO 39

Porém, os sonares estão desuso por conta de suas deficiências, pelo barateamento de sensores mais precisos e pelo desenvolvimento de novas alternativas para a percepção de ambientes. Outra opção para mapeamento em grade é o uso de lasers. Esses são sensores precisos, de longo alcance e que podem fornecer dados suficientes para se al- cançar a construção de mapas bem detalhados. Alguns trabalhos com laser podem ser citados. Konrad et al. (2011), por exemplo, implementaram um sistema de mapeamento em Grade de Ocupação de grandes áreas através um veículo equipado com um laser. Já Shi et al. (2010), apresentaram uma técnica de mapeamento semântico a partir de uma Grade de Ocupação criada com dados captados por um laser. Os autores apresentaram o mapa semântico em grade chamado de Semantic Grid Map, cujo o objetivo é facilitar a classificação de ambientes em corredores ou salas (escritórios).

O uso de câmeras na construção de mapas em Grade de Ocupação é bem frequente nas pesquisas mais atuais. Esses dispositivos se destacam pelo seu baixo custo e pela grande quantidade de informações que podem ser aproveitadas a partir de uma coleta de dados. Desde sistemas monoculares até sistemas omnidirecionais podem ser aplicados na montagem de mapas em Grade de Ocupação. Choi & Oh (2006), por exemplo, aplicaram a técnica de sonar visual às imagens capturadas por um sistema de visão monocular e fizeram a associação desses dados de distância através de um algoritmo baseado na técnica chamada Iterative Closest Point (ICP), para produzir um mapa em Grade de Ocupação.

Em seu trabalho de doutorado, Santana (2011) utilizou um robô equipado com uma única câmera na construção de um mapa híbrido de características e Grade de Ocupação. Enquanto um procedimento de localização e mapeamento simultâneos está sendo exe- cutado sobre um mapa de características, uma estrutura em Grade de Ocupação 2D foi construída em paralelo a partir de informações de imagens segmentadas. De acordo com o autor, o mapa em grade serve para realização de um planejamento de caminhos com desvio de obstáculos de forma mais direta.

Quando se trata de sistemas de visão estéreo em mapeamento em Grade de Ocupação, deve-se voltar no tempo e mencionar o trabalho de Moravec (1996). Este foi o primeiro trabalho em Grade de Ocupação com visão estéreo. Além disso, Moravec (1996) também introduziu a ideia da Grade de Ocupação tridimensional chamada no trabalho de Grade de Evidência (Evidence Grid), por ser baseada na Teoria da Evidência de Dempster-Shafer, diferente da abordagem Bayesiana proposta por Elfes (1989).

Vários trabalhos mais recentes que destacam o uso de sistemas de visão estéreo po- dem ser citados. No trabalho de Andert (2009), por exemplo, um aeromodelo munido de um sistema estéreo foi utilizado para mapear ambientes externos em uma Grade de Ocupação tridimensional. Este trabalho mostra com certa profundidade uma interessante abordagem na construção de mapas em Grade de Ocupação 3D. Em outro interessante trabalho, Gallelos & Rives (2010) implementaram o mapeamento em Grade de Ocupação em um robô provido de um laser e uma câmera omnidirecional.

Diversas são as possibilidades de sensores utilizados no mapeamento em Grade de Ocupação, incluindo a fusão de informações providas de distintas fontes. Uma nova e eficiente alternativa no mapeamento em Grade de Ocupação surge com o uso do Mi- crosoft Kinect (câmeras RGB-D), um dispositivo que combina uma câmera com sensor infravermelho em uma única estrutura. Várias são as pesquisas que se aproveitam dessa

interessante combinação de informações para realizar o mapeamento de ambientes seja em Grade de Ocupação ou em outras forma de representação [Georgiev et al. 2011, Pirker et al. 2011, Einhorn et al. 2011]. Já existem bibliotecas de código livre com compatibil- idade para diferentes plataformas que atraem ainda mais o uso desses dispositivos em pesquisas na Robótica.

São inúmeras as possibilidades de aplicação dos mapas em Grade de Ocupação, aqui foram mencionados apenas alguns exemplos, porém vários outros trabalhos podem ser encontrados na literatura. Thrun et al. (2005) afirmaram que a principal utilidade da téc- nica de mapeamento em Grade de Ocupação está no pós-processamento, ou seja, no que se pode realizar a partir do mapa resultante. Com o processo de mapeamento concluído a Grade de Ocupação pode ser útil para várias aplicações como: planejamento de caminhos, navegação, desvio de obstáculos, localização, entre outras.

Por exemplo, Lai e colegas [Lai et al. 2006] implementaram um método prático de planejamento de caminhos para robôs móveis em ambientes desconhecidos. Eles uti- lizaram uma instância modificada do algoritmo A* sobre um mapa em Grade de Ocupação parcialmente construído para realizar um planejamento de caminhos de forma incremen- tal. A cada nova medição sensorial incorporada ao mapa o algoritmo busca o melhor ca- minho a ser seguido. Os autores apresentaram no final do trabalho inúmeros experimentos ratificando a factibilidade do método proposto. Cherubini & Chaumette (2011) apresen- taram em seu trabalho um framework para navegação e desvio de obstáculos baseado em um sistema de fusão sensorial composto por uma câmera e um laser. A navegação con- siste em seguir um caminho tomado a partir de um conjunto de imagens, enquanto que o desvio de obstáculos é realizado com o auxílio de um mapa em grade construído a partir do sensor laser.

No contexto do problema de localização, Dryanovski et al. (2011) apresentaram uma abordagem para solucionar o problema do robô sequestrado. A abordagem proposta uti- liza um mapa em Grade de Ocupação para representar os dados sensoriais capturados por um sensor laser. Tal mapa é posteriormente utilizado em conjunto com outras técnicas para inferir uma localização precisa para o robô.

Um dos grandes desafios no mapeamento em Grade de Ocupação está no mapea- mento de ambientes muito grandes ou mesmo no mapeamento de ambientes com riqueza de detalhes. Essas duas possibilidades introduzem um ponto fundamental no mapeamento em Grade de Ocupação, que por muitas vezes é fortemente assinalado como a principal desvantagem dessa abordagem: o custo computacional. O mapeamento de ambientes com grandes dimensões e o mapeamento detalhado requerem um razoável poder computa- cional para serem construídos e processados, além de necessitarem de uma grande quan- tidade de memória para serem armazenados principalmente em uma representação 3D. Diante desses problemas, ultimamente surgiram pesquisas que lidam diretamente esses fatores para encontrar uma solução plausível.

Dryanovski e colegas [Dryanovski et al. 2011] apresentaram uma abordagem para o mapeamento 3D usando uma Grade de Ocupação multi-volume ou MVOG (Multi-Volume

Occupancy Grid). A MVOG armazena explicitamente informações sobre a ocupação de

espaços 3D. Essa proposta supera as abordagens tradicionais probabilísticas existentes de mapeamento 3D em termos de uso de memória, devido ao fato de que as observações

4.2. MAPAS DE ELEVAÇÃO 41

sensoriais são agrupadas em volumes verticais contínuos para economizar espaço. O desempenho da abordagem proposta é analisado por meio de experimentos em ambientes interiores e exteriores com um robô aéreo.

Ainda dentro das representações tridimensionais, Wurm et al. (2010) expuseram uma abordagem para a modelagem de ambientes 3D baseados em octrees utilizando uma esti- mativa de ocupação probabilística denominada de OctoMap. A técnica utilizada é capaz de representar modelos 3D completos, incluindo áreas livres e desconhecidas. A abor- dagem foi bem avaliada utilizando-se diferentes conjuntos de dados reais e simulados. Os resultados demonstram que a proposta é útil para modelar os dados probabilisticamente, enquanto, ao mesmo tempo, mantem a exigência de memória no mínimo.

Outra interessante pesquisa publicada por Einhorn et al. (2011), traz uma nova técnica de mapeamento de ambientes que escolhe a resolução de cada célula adaptativamente pela fusão ou divisão das células, de acordo com uma modelagem estatística apresentada pelos pesquisadores. Os autores argumentam que essa abordagem permite uma implementação mais genérica de mapas 2D, 3D e até de mais alta dimensão usando o mesmo algoritmo. Com essa ideia é possível diminuir o custo computacional relativo ao armazenamento de um mapa em grade pela fusão de células com medições idênticas.

4.2

Mapas de Elevação

A representação em grade de ocupação é uma interessante ferramenta para representar informações sobre de ocupação de lugares de um ambiente. E pode ser utilizada também na representação de informações tridimensionais. Desde a década de 1996 com Moravec (1996), pouco depois do surgimento do mapeamento em grade de ocupação 2D, até anos mais atuais, como no trabalho de Andert (2009), pesquisadores introduziram a ideia de modelar o espaço tridimensional dos robôs em uma grade de ocupação 3D.

O mapeamento tridimensional dos ambientes foi pensado principalmente para os ca- sos onde o terreno de navegação dos robôs não é plano, e nos casos onde é necessário que seja realizada uma navegação precisa entre os objetos, considerando a altura deles dentro de um ambiente. Além disso, Liu et al. (2001) apresentam duas importantes vantagens que justificam a construção de modelos 3D. Primeira, mapas 3D facilitam a solução do problema da associação de dados, visto que os modelos 3D são mais ricos que os 2D, portanto apresentam menos ambiguidades. Isso facilita a identificação e distinção de lu- gares no processo de mapeamento. Segunda, os mapas 3D são interessantes quando o mapeamento também for utilizado em outras atividades. Modelos 3D são muito mais adequados para os usuários remotos interessados no interior de um edifício tais como ar- quitetos, equipes de resgate humanos, ou bombeiros que gostariam de se familiarizar com um ambiente antes de entrar.

Porém, existe uma grande dificuldade no mapeamento 3D quando o objetivo é repre- sentar o ambiente em uma grade de ocupação tridimensional, principalmente ambientes com grandes dimensões. Perceba que para isso seria necessária uma estrutura 3D onde cada lugar do ambiente tridimensional seria representado por um cubo, também chamado de voxel (em inglês, volumetric pixel), o que pode representar a necessidade uma de grande quantidade de processamento e memória na construção e armazenamento desse

mapa (ver Figura 4.4). Desconsiderando qualquer tipo de otimização, uma estrutura para armazenar a grade 3D mostrada na Figura 4.4 deveria conter pelo menos 216 elementos (12x6x3).

12

6

3

Figura 4.4: Ilustração da representação em grade de ocupação 3D.

Para evitar essa grande demanda de recursos de processamento e memória, alguns pesquisadores propuseram uma solução já usada no mapeamento de terrenos por imagens de radares, os mapas de elevação ou mapas 2,5-D. Os mapas de elevação são úteis para modelar o espaço 3D de um robô móvel, de uma maneira compacta. Esta representação mantem uma grade bidimensional, onde cada célula armazena a altura ou elevação do terreno no ponto mapeado [Pfaff et al. 2007] (Figura 4.5). Usando o mesmo exemplo da Figura 4.4, uma grade de elevação para representar a mesma situação deveria conter pelo menos 72 (12x6) elementos, onde cada elemento teria um valor de elevação associado, indicando a altura dos obstáculos.

A modelagem e interpretação dos dados sensoriais para a construção desse tipo de mapa não é guiada por uma formulação padrão, como no caso dos mapas baseados em grade de ocupação no âmbito da robótica. Diferentes formulações são propostas para a inicialização e atualização dos valores de elevação das células, a partir de distintos sen- sores. Aqui, será focada a abordagem baseada no Filtro de Kalman, a mesma ferramenta utilizada por Pfaff et al. (2007).

4.2.1

Filtro de Kalman

O Filtro de Kalman (FK) é um conjunto de equações matemáticas as quais definem um processo eficiente de estimação, minizando o erro de estado. Através da análise da variável denominada variável de observação, outra variável não observável, a variável de estado, pode ser estimada eficientemente [Kalman 1960]. O Filtro de Kalman padrão presupõe que uma determinada variável a ser estimada tenha seu modelo linear e que possa ser descrito sob a forma de um sistema de equações de estado (Equação 4.14).

4.2. MAPAS DE ELEVAÇÃO 43 5 3 h 2 1 h 71 h 2 h 1 h 12 6

Figura 4.5: Representação em grade de ocupação 2.5D. É necessária uma estrutura de dados de 72 elementos para mapear o ambiente ilustrado.

 st= Atst−1+ Btut+δt

zt= Ctst+γt

(4.14)

Onde s_{∈ R}n é o vetor de estados do sistema; ut ∈ Rl é o vetor das entradas de sinais de

controle; zt ∈ Rm é o vetor com as medições sensoriais; a matriz At, de tamanho n× n

é a matriz de transição de estados; Bt, de dimensões n× l, é a matriz de coeficientes de

entrada; a matriz Ct, de tamanho m× n, é chamada de matriz de observação; δt ∈ Rn

representa o vetor de ruídos do processo eγt∈ Rmé o vetor de erros de medição; t e t− 1

representam os instantes de tempo atual e anterior respectivamente.

O filtro é dividido em duas etapas: predição e atualização. A etapa de predição uti- liza o modelo evolutivo do sistema e as propriedades estatísticas dos ruídos presentes no sistema. Já a etapa de atualização leva em conta medições sensoriais para computar uma nova estimativa atualizada dos dados estimados na predição. O Algoritmo 2 mostra os passos do Filtro de Kalman padrão. As entadas do algoritmo são: o estado do sistema

µt−1 no tempo instante anterior; a matriz de covariância Σt−1, que descreve o ruído de

estado no instante t_{− 1; os sinais de controle u}t; e as medições zt. A saída será uma

estimativa atualizada do estado, µt, e sua convariância,Σt.

Algoritmo 2: Filtro de Kalman Entrada: µt−1,Σt−1,ut, zt 1 Saída: µt,Σt 2 ¯µt= Atµt−1+ Btut; 3 ¯ Σt = AtΣt−1AtT+ Rt; 4 Kt = ¯ΣtCTt (CtΣ¯tCtT+ Qt)−1; 5 µt= ¯µt+ Kt(zt− Ct¯µt); 6 Σt = (I − KtCt) ¯Σt 7

As linas 3 e 4 compõem a etapa de predição, onde é realizada a computação do estado do sistema ¯µt e os ruídos inerentes ao mesmo ¯Σt, considerando o estado passado. A

média ¯µt é conseguida pela aplicação do sinal de controle ut ao modelo determinístico

de transição de estado. A covariância, ¯Σt, é calculada através da matriz de transição de

estado At, a qual expressa a dependência entre o estado atual com o estado anterior. As

linhas de 5 a 7 fazem parte da etapa de atualização, onde ¯µt é transformada em µt pela

incorporação da medição zt. A variável Kt, chamada de ganho de Kalman, especifica o

quanto uma nova medição influencia na nova estimativa do estado, µt, e sua variânciaΣt.

No contexto do mapa de elevação as variáveis a serem estimadas são a elevação de uma célula, representada pela média µ0:t, e sua variância,σ2_0:t, considerando o histórico

das estimativas passadas. O passo de predição do Filtro de Kalman não causa modifi- cações nos valores de elevação e variância previamente calculados, visto que esta etapa não considera as novas medições de altura e variância realizadas. Logo, a predição pode ser descrita pelas Equações 4.15 e 4.16.

¯µ0:t = µ0:t−1 (4.15)

¯

σ2

0:t =σ20:t−1 (4.16)

A cada nova medição do sistema visual devem ser derivadas a altura de um lugar, agora representada por ht, e sua variância,σ2t, que serão inseridas na etapa de atualização

da formulação do Filtro de Kalman para gerar uma nova estimativa da elevação da célula e sua variância. Na fase de atualização, o primeiro passo do algoritmo é o cálculo do ganho de Kalman, Kt, como descrito na linha 5 do Algoritmo 2. Considera-se Ct= 1, pois não

influencia o valor da medição sensorial, e Qt =σ2t a variância dessa nova medição. Com

isso, o cálculo de Kt passa a ser feito pela Equação 4.17.

Kt= ¯ σ2 0:t ¯ σ2 0:t+σt2 (4.17)

Ou, aplicando-se as igualdades das Equações 4.15 e 4.16, tem-se a Equação 4.18:

Kt= σ2 0:t₋₁ σ2 0:t−1+σ2t (4.18)

Neste ponto, as novas estimativas da elevação, µ0:t, e sua variância,σ2_0:t, podem ser calcu-

ladas, levando-se em conta a nova medição sensorial, ht, tomada no tempo t, e sua variân-

ciaσ2_t. A partir das equações descritas nas linhas 6 e 7 do Algoritmo 2, pode-se deduzir as expressões de atualização descritas pelas Equações 4.19 e 4.20, as quais computam as novas estimativas de elevação de uma célula e sua variância, utilizando-se o ganho de Kalman dado pela Equação 4.18 e fazendo-se as devidas manipulalções matemáticas.

µ0:t= σ2 tµ0:t−1+σ20:t−1ht σ2 0:t−1+σ2t (4.19)

4.2. MAPAS DE ELEVAÇÃO 45 σ2 0:t = σ2 0:t−1σ2t σ2 0:t−1+σt2 (4.20)

4.2.2

Trabalhos Relacionados

Os primeiros trabalhos baseados em mapas de elevação no contexto da robótica foram apresentados por Bares et al. (1989) e Hebert et al. (1989). Estes trabalhos estão voltados à navegação de robôs ou sondas planetárias com pernas. A partir das ideias apresentadas nessas investigações novas pesquisas foram surgindo.

Assim como nos mapas em grade de ocupação, diferentes sensores podem ser utiliza- dos para o mapeamento em grade de elevação, porém se destacam os lasers e as câmeras. Ye & Borenstein (2003) propõem um algoritmo para adquirir mapas de elevação com um veículo móvel equipado com um sensor laser. Eles apresentaram a formulação de uma filtragem especial para eliminar erros de medição ou ruídos do sensor laser e dos movimentos do robô. Em uma pesquisa mais recente, Kwon et al. (2010) também apre- sentaram sua proposta para representação de ambientes com mapas de elevação a partir de informações de um laser. Eles utilizam o mapa para realizar a localização do robô com o método de Monte Carlo (Monte Carlo Localization) com base na associação de dados sensoriais com o mapa adquirido.

Quando a principal fonte sensorial são as câmera, várias técnicas podem ser encon- tradas na literatura. Lacroix et al. (2002) extraíram um mapa de elevação a partir de imagens estéreo com o objetivo final de prover a navegação outdoor de um robô. Já Hygounenc et al. (2004) construíram um mapa de elevação com um dirigível autônomo provido de um sistema de visão estéreo. Eles propuseram um algoritmo para detecção de características e realizar a correspondência ou matching entre mapas localmente construí- dos usando essas características. Cappalunga et al. (2010) implementaram um sistema de mapeamento em mapa de elevação com visão estéreo, onde eles se fundamentaram em um algoritmo biologicamente inspirado para segmentar pontos no terreno.

Como já mencionado, a construção dos mapas de elevação não obedece a uma formu- lação básica como é o caso das grades de ocupação. Por esse motivo, diferentes aborda- gens são adotadas na construção desse tipo de representação. Aqui, serão evidenciadas duas interessantes abordagens estocásticas, a primeira proposta por Pfaff et al. (2007) e a segunda apresentada por Marks et al. (2009). Pfaff et al. (2007) apresentam a construção de mapas de elevação baseado em sensor laser. Em sua proposta, os autores consideram uma abordagem probabilística baseada no Filtro de Kalman para construir o mapa. A atribuição de valores de elevação à cada célula do mapa é calculada e atualizada a cada nova medição de elevação provida pelos sensores, além disso, uma medida de variância,

In document Interjections in late Middle English play texts : A multi-variable pragmatic approach (sider 110-113)