5.2 Miljøets suksessfaktor
5.2.1 Forutsetninger for et suksessfullt utviklingsmiljø
na lista P:
1. Esta passagem já foi descoberta anteriormente e é descrita em relação ao ambiente onde o robô está. Em outras palavras, significa dizer que o robô reencontrou uma passagem do seu ambiente atual;
2. Esta passagem já foi descoberta anteriormente, mas é descrita em relação a um outro ambiente já inserido no mapa;
3. A passagem que o robô descobriu não existe na lista P. Portanto, ela leva o robô para um outro ambiente desconhecido.
Primeiro tem-se que verificar se esta passagem descoberta recentemente foi anterior- mente determinada e pertence ao ambiente atual do robô. Para isso, deve-se percorrer a lista P e procurar todos os elementos que foram criados em relação a ake que coincidam com pl+1, verificando a sobreposição de passagens já explicada. Ou seja, deve-se procu-
rar algum elemento em P, cujo parâmetro e1 do vetor passagem (equação 3.3) represente
o ambiente ake que haja uma sobreposição de representação. Caso essa passagem exista, então não há necessidade de inserção de pl+1na lista de passagens P.
Se esta passagem não existir em P, então é possível que haja alguma passagem que foi definida em relação a algum outro elemento aide A, com i= 1, 2, . . ., k − 1, e que seja capaz de levar o robô desse ambiente ai até o ambiente ak atual. Ou seja, pode existir alguma passagem em P cuja etiqueta e2represente o elemento ak. Se existir, então deve- se descrever a passagem pl+1 em relação ao ambiente representado por e1 e verificar a
sobreposição com a passagem encontrada em P. Se houver esta sobreposição, então esta passagem também já foi anteriormente encontrada, mas em um outro ambiente do mapa. Do mesmo modo adotado para o primeiro caso, não há necessidade de inclusão de pl+1
em P.
Caso todos estes testes sejam falsos, então a passagem pl+1 leva o robô para um am-
biente desconhecido ak+1. Porém, é necessário também verificar se esta passagem não
está incluída na fila F criada para monitorar estes ambientes desconhecidos (ver algo- ritmo 3.1). Para isto, basta apenas fazer uma busca simples para descartar essa possibi- lidade, procurando se há alguma passagem em F descrita em termos de ak e verificar se ocorre sobreposição. Assim, em caso afirmativo, não há necessidade de inserir esta pas- sagem na fila. O algoritmo 3.5 apresenta os passos utilizados para verificar se é preciso inserir uma determinada passagem p na fila F. Observa-se que este algoritmo é próprio para passagens recém-descobertas que podem conduzir o robô para um possível ambiente local desconhecido. Caso esta passagem p tenha sido atravessada, pode-se facilmente incluí-la na lista P, executando apenas uma comparação com todos os elementos existen- tes para descartar a possibilidade de dupla representação.
3.5
Considerações
O mapeamento de um ambiente de trabalho por um robô móvel autônomo não é uma tarefa simples. Ela envolve o tratamento de diversos fatores para que o resultado obtido
54 CAPÍTULO 3. METODOLOGIA DO MAPEAMENTO HÍBRIDO
Para cada passagem pjda lista P, fazer:
Se parâmetro e1da passagem pjfor igual ao ambiente atual do robô, então: Verificar sobreposição da passagem pjcom p;
Se taxa de sobreposição for maior que um limite pré-especificado, então: Passagem já existe! Não há necessidade de inserção de elemento. Fim
Fim
Se parâmetro e2da passagem pjfor igual ao ambiente atual do robô, então: Descrever pjem relação ao ambiente atual;
Verificar sobreposição da passagem pjcom p;
Se taxa de sobreposição for maior que um limite pré-especificado, então: Passagem já existe! Não há necessidade de inserção de elemento. Fim
Fim Fim
Para cada passagem pjda fila F, fazer:
Se parâmetro e1da passagem pjfor igual ao ambiente atual do robô, então: Verificar sobreposição da passagem pjcom p;
Se taxa de sobreposição for maior que um limite pré-especificado, então: Passagem já existe! Não há necessidade de inserção de elemento. Fim
Fim Fim
Inserir p em F .
Algoritmo 3.5: Verificação da necessidade de inserção de elemento na fila de passagens
3.5. CONSIDERAÇÕES 55
seja adequado para que robô tenha a capacidade de realizar tarefas que dependem de uma representação do local de trabalho.
Embora haja várias soluções propostas, ainda não se conseguiu uma metodologia que se destacasse em todos os aspectos diante das demais para a construção do mapa. As incertezas presentes no robô e em seus sensores são o grande problema. Nos últimos anos uma especial atenção foi dada ao tratamento probabilístico do problema, o que permitiu uma solução simultânea para as tarefas de mapeamento e localização.
No entanto, outras abordagens podem perfeitamente ser aplicadas. Por exemplo, rea- lizar a construção on-line de um mapa híbrido da maneira aqui apresentada. Representar um ambiente de trabalho tanto como um grafo quanto como um mapa métrico já é bas- tante utilizado na literatura. Contudo, a proposta desta tese busca ser simples o bastante para tornar-se uma alternativa aos trabalhos que exigem um maior rigor matemático e esforço computacional.
Os mapas métricos locais consistem na descrição de figuras geométricas que melhor se assemelham ao espaço livre da sala ou corredor. O importante é que estes mapas são calculados de forma descorrelacionada uns dos outros, permitindo que os erros acumula- dos na localização do robô durante a exploração de um ambiente não afetem o cálculo da figura geométrica para a representação de outro ambiente.
Cada mapa métrico representado desta forma compacta é um vértice do mapa topoló- gico. As passagens existentes entre as salas e corredores são as arestas entre estes nós do grafo. Este tipo de representação é baseada na topologia do ambiente. O espaço ocupado na memória do robô por este mapa híbrido é pequeno. E através dele o robô pode executar diversos tipos de tarefas, nos mais diferentes tipos de abstração.
A construção do mapa topológico é baseada em uma exploração em largura do ambi- ente. Cada vez que um vértice é descoberto (ou a geometria do espaço local é calculada), procede-se com uma redefinição nos valores de alguns dos parâmetros da figura geomé- trica encontrada para que todo o mapa métrico seja coerente e represente adequadamente todo o ambiente. Esta redefinição utiliza determinadas posições conhecidas globalmente e denominadas como âncoras, para que os mapas locais descorrelacionados fossem unidos. Por fim, viu-se também que é necessário que o robô realize comparações entre os elementos métricos do mapa (especificamente os ambientes e passagens) com o objetivo de obter um resultado final mais preciso. O parâmetro de comparação utilizado foi a taxa de sobreposição entre os elementos.
Assim, as considerações gerais deste capítulo são que esta proposta de mapeamento apresentada é simples e compacta em vários aspectos, permitindo a sua utilização em robôs móveis autônomos. Embora não haja um tratamento direto das incertezas, as simu- lações no capítulo 5 dão uma melhor idéia da viabilidade da proposta. O próximo capítulo trata da obtenção dos parâmetros métricos que descrevem o espaço livre de uma sala ou corredor.
Capítulo 4
Representação Métrica Local
Em uma representação híbrida de um ambiente, o robô móvel deve ser capaz de ma- pear o seu espaço de trabalho, representando-o através de uma estrutura que possa arma- zenar todas as suas características e relações métricas e por uma outra parte que descreva de forma mais qualitativa este mesmo ambiente.
Há diversas formas de apresentar este mapa híbrido. As maiores correntes fazem com que o robô mantenha duas representações simultâneas. No entanto, outros trabalhos uti- lizam uma representação topológica enriquecida com informações métricas, as quais são suficientes para descrever localmente o espaço de trabalho do robô, como por exemplo: um grafo cujos vértices armazenam informações métricas ou um pequeno mapa métrico local. Com este tipo de representação, obter o mapa métrico global torna-se uma tarefa trivial, dado o grafo da topologia do espaço de trabalho do robô. Uma análise mais con- ceitual das representações híbridas foi realizada por Buschka e Saffiotti (2004).
As informações sobre a geometria local podem ser tanto armazenadas na forma de uma grade de ocupação local, como exemplificado por Buschka e Saffiotti (2004), quanto por um mapa das principais características do ambiente, como linhas retas por exemplo [Tomatis et al. 2003].
A representação híbrida aqui adotada consiste em manter duas listas. A primeira armazena todas as informações métricas dos ambientes locais, ou espaços abertos, como definido por Fabrizi e Saffiotti (2002) (salas e corredores de um ambiente de trabalho interno, por exemplo). Na segunda lista são guardadas todas as informações relativas às passagens existentes entre estes ambientes.
Uma das características desta proposta é utilizar um prévio conhecimento abstrato de que os espaços abertos locais podem ter os seus limites descritos por uma figura ge- ométrica simples e parametrizável. Assim, o objetivo do mapeamento métrico local é determinar todos os parâmetros que descrevem esta figura geométrica. Embora o ambi- ente seja completamente desconhecido, considerar esta abstração inicial não invalida o método proposto. Vale ressaltar que o ambiente investigado é interno e semi-estruturado, como interior de casas ou laboratórios, o que permite a utilização desta suposição inicial. Dessa forma, o mapa métrico local consiste simplesmente em obter e manter as in- formações necessárias para descrever uma figura geométrica única, a qual seja capaz de delimitar o espaço livre do robô. Isto o diferencia das propostas mais usuais que utilizam segmentos de retas para descrever a métrica local. Este capítulo apresenta o método utili-
58 CAPÍTULO 4. REPRESENTAÇÃO MÉTRICA LOCAL
zado para obter esta representação geométrica local. Para isso, é utilizado um algoritmo inspirado na transformada generalizada de Hough. Esta transformada generalizada con- siste em uma variação do algoritmo padrão de Hough. Ela é apropriada para descrever curvas que não possuem representação analítica conhecida.
4.1
Transformada de Hough Padrão
A transformada de Hough é um algoritmo originalmente proposto para determinar curvas que possuem descrição analítica conhecida a partir de pontos extraídos de uma imagem digital [Gonzalez e Woods 2000]. É uma ferramenta bastante utilizada na área de processamento de imagens.
Normalmente, a transformada é aplicada para determinação de linhas retas, as quais podem ser descritas pela seguinte equação:
y= a · x + b (4.1)
Dado um conjunto de pixels em uma imagem, a escolha da reta que melhor se ajusta a estes pontos é feita por um simples processo de votação. O ponto de partida consiste em trabalhar no espaço dos parâmetros de reta(a, b), e não no espaço cartesiano.
Este espaço de parâmetros é então discretizado, daí o atrativo computacional para a aplicação do método. Cada ponto(ap, bq) deste espaço corresponde a uma reta no plano cartesiano. Se a equação paramétrica da reta for reescrita como:
b= −a · x + y (4.2)
então pode-se verificar que para cada ponto(xi, yj) (correspondente a um pixel na ima- gem) há uma solução particular(ap, bq) dentro de limites pré-estabelecidos [amin, amax] e
[bmin, bmax] no espaço de parâmetros.
Para contar o número de ocorrências de cada uma das soluções é utilizada uma matriz comumente chamada de acumuladora. Inicialmente, todos os elementos desta matriz são iguais a zero. Para um determinado ponto (xi, yj) do conjunto de dados fornecido, se houver uma solução particular então há o incremento no elemento da matriz acumuladora que mapeia o espaço de parâmetros. Ou seja, se a seguinte igualdade for verdadeira:
bq= apxi+ yj (4.3)
então o elemento da matriz acumuladora correspondente ao ponto(ap, bq) do espaço de parâmetros recebe um voto, ou é incrementado:
A(p, q) = A(p, q) + 1 (4.4)
Após todos os possíveis pontos terem sido observados na imagem e todas as possíveis soluções terem sido votadas na matriz acumuladora, então basta realizar nesta matriz a busca pelo elemento que recebeu o maior número de votos (elemento de maior valor na matriz), e verificar qual o ponto(ap, bq) correspondente do espaço de parâmetros foi
4.1. TRANSFORMADA DE HOUGH PADRÃO 59
escolhido.
Esta transformada de Hough é um procedimento simples e a precisão do seu resultado depende da discretização adotada para o espaço de parâmetros.
O grande problema deste método como aqui foi apresentado reside na escolha dos intervalos dos parâmetros. Devido a equação 4.1 estar em função das coordenadas, os parâmetros a e b podem assumir infinitos valores (por exemplo: se a tangente do ângulo de inclinação da reta tender para o infinito, o ponto que a reta intercepta o eixo y tenderá para menos infinito). Desta forma, opta-se por trabalhar com a equação da reta na sua forma normal, que é dada por:
ρ = x cos(θ) + y sin(θ) (4.5)
ondeρ é a distância entre a origem e a reta, e θ é a seu ângulo de inclinação da perpen-
dicular com o eixo positivo x (ver figura 4.1). A matriz acumuladora deve ser modificada no algoritmo para contar o número de soluções para esta nova forma paramétrica, uma vez que o novo espaço de parâmetros é(ρ, θ).
x y
ρ θ
Figura 4.1: Parametrização da reta com distânciaρ e inclinação θ.
Para demonstrar a qualidade do resultado fornecido pela transformada de Hough para retas, com a modificação necessária para utilizar a equação parametrizada, a figura 4.2 apresenta um conjunto de pontos (x, y) e a a reta obtida pela aplicação do método apre-
sentado.
As figuras 4.3 e 4.4 apresentam, respectivamente, a matriz acumuladora e os picos obtidos com o procedimento de voto (incremento no espaço de Hough) para este exemplo em particular.
O algoritmo padrão de Hough tem sofrido várias adaptações objetivando a sua me- lhoria em termos de esforço computacional. Por exemplo, o trabalho de Cha et al. (2006) descreve uma nova extensão para a transformada de Hough com o intuito de detectar segmentos de retas. Para isso, os autores expandiram o espaço de Hough em mais uma
60 CAPÍTULO 4. REPRESENTAÇÃO MÉTRICA LOCAL x y 0.7 0.9 1.1 1.3 1.5 1.7 1.9 2.1 2.3 2.5 1.8 2.0 2.2 2.4 2.6 2.8 3.0 3.2 + + + + + + × × × × × ×
Figura 4.2: Reta obtida através da transformada de Hough para um conjunto de pontos
(x, y).
dimensão. Isto contribuiu para a determinação do comprimento dos segmentos de retas que seriam detectados (notar que o algoritmo padrão retorna uma linha reta, e não um segmento de reta). Uma segunda contribuição do trabalho de Cha et al. (2006) é a utili- zação de abordagem probabilística para montar o espaço de Hough. Ou seja, os autores utilizaram informações sobre a probabilidade de um determinado pixel da imagem fazer parte, ou não, de uma região cujo formato característico deseja-se encontrar (por exemplo: um segmento de reta, para este caso específico). Esta metodologia melhora a acurácia do método, pois os valores máximos na acumuladora são destacados. A aplicação prática do seu trabalho foi para imagens aéreas de topos de edifícios.
Abordagens visando a melhoria da detecção de picos no espaço de Hough também são freqüentemente apresentadas. O trabalho de Furukawa e Shinagawa (2003) mostrou uma metodologia que evita picos espúrios no espaço de Hough. Para isto, os autores analisaram a distribuição de valores em torno destes picos utilizando um operador deno- minado por eles de “borboleta”, por causa do formato da região de interesse no espaço de Hough, que corresponde ao ponto de encontro das várias senóides quando vistas na matriz acumuladora (ver a figura 4.3, por exemplo). Este operador detecta as elevações existentes, remove as contribuições de ruídos e, por fim, retorna o valor daquela região de maior interesse. A remoção dos valores adicionados por elementos espúreos é realizada por análise probabilística.
Matas et al. (2000) apresentaram um método para detecção de retas usando uma outra forma de transformada de Hough probabilística. Ela foi baseada na análise da diferença
4.1. TRANSFORMADA DE HOUGH PADRÃO 61
Índice do raio
Índice do ângulo
Matriz acumuladora (espaço de Hough)
10 20 30 40 50 60 70 80 90 10 20 30 40 50
Figura 4.3: Matriz acumuladora após a aplicação da transformada de Hough para o con- junto de pontos apresentado na figura 4.2.
Raio Ângulo (rad) Voto 0 1 2 3 4 5 6 −1.0 −0.6 −0.2 0.2 0.6 1.0 1.4 1.8 2.2 1.5 1.9 2.3 2.7 3.1
62 CAPÍTULO 4. REPRESENTAÇÃO MÉTRICA LOCAL
na fração do número de votos necessário para se obter um resultado apropriado (uma reta, neste caso), com diferentes pontos de suporte (pontos que pertencem à característica dese- jada na imagem). O objetivo foi minimizar a proporção de pontos utilizados no processo de incremento da célula na matriz acumuladora.
4.1.1
Aplicações em Localização e Mapeamento por Robôs
No âmbito da robótica móvel, a transformada é uma ferramenta utilizada para, entre outras coisas, auxiliar a localização do robô, como realizado por Bezerra et al. (2004) ou por Großmann e Poli (2001), ou para obter a descrição do ambiente local [Anoussaki e Kyriakopoulos 1999]. Deve-se ressaltar que os pontos utilizados para o algoritmo também podem tanto ser obtidos por imagens do ambiente, com seu respectivo tratamento, como por sensores de distância, como sonares ou lasers.
Também há outros tipos de aplicações além destas que foram relatadas. Por exemplo, Sun e Nelson (2002) utilizaram a transformada de Hough para a detecção do núcleo de células para auxiliar um sistema micro-robótico de injeção de DNA.
Bezerra et al. (2004) usaram o algoritmo de Hough para detecção de retas no piso do ambiente de trabalho do robô. O cruzamento destas retas era utilizado como referência (marcos naturais) para efetuar a correção da pose do robô estimada por odometria, uma vez que a posição das marcas reais no ambiente eram conhecidas. As informações eram coletadas por uma câmera de vídeo.
No trabalho de Großmann e Poli (2001), o procedimento de determinar a pose do robô era executado diretamente no espaço de Hough. Para isso, realizava-se um matching entre um mapa de referência e informações obtidas dos sensores de distância. Ou seja, sendo o ambiente descrito por um mapa de características, as quais eram formadas por segmentos de retas, eles determinavam os parâmetros das retas que se ajustavam às informações sensoriais e realizavam a comparação entre informações. Com isso, a pose do robô era determinada.
O trabalho de Iocchi e Nardi (2002) foi bastante similar à proposta de Großmann e Poli (2001). Porém, a diferença residiu no fato deles utilizarem a transformada generalizada de Hough, e não o algoritmo padrão aplicado para retas. Eles também consideraram que o ambiente era representado por elementos poligonais e que uma boa estimativa da pose do robô era calculada a cada instante. Uma vez que a comparação no espaço de Hough era realizada, e a pose do robô determinada, um filtro estendido de Kalman era aplicado para fundir esta informação com a pose obtida por odometria. Esta comparação foi denominada pelos autores de localização de Hough.
Anoussaki e Kyriakopoulos (1999) construiram um mapa de características formado por segmentos de retas utilizando a transformada de Hough para retas. Os pontos coleta- dos do ambiente eram provenientes de lasers. Para que eles pudessem efetivamente obter uma série de segmentos de retas para descrever o ambiente do robô (relembrando que a transformada retorna uma reta e não um segmento de reta), foi aplicado um método de agrupamento de pontos baseando-se na distância entre cada ponto e seus vizinhos. Hop- penot et al. (2000) apresentou uma forma de descrever as paredes do ambiente onde o robô atuava, também utilizando a transformada padrão de Hough. Além disso eles aplicaram