Mauro Filipe Rodrigues Queirósintranet.dei.uminho.pt/gdmi/galeria/temas/pdf/40523.pdf · Mauro Filipe Rodrigues Queirós Planeamento de Caminhos para Robôs Móveis Autónomos em

Mauro Filipe Rodrigues Queirós

Planeamento de Caminhos paraRobôs Móveis Autónomos emAmbientes Conhecidos e Estruturados

Mau

ro F

ilipe

Rodr

igues

Que

irós

novembro de 2014UMin

ho |

201

4Pl

anea

men

to d

e C

amin

hos

para

Rob

ôs M

óvei

s Au

tóno

mos

em A

mbi

ente

s C

onhe

cido

s e

Estr

utur

ados

Universidade do MinhoEscola de Engenharia

novembro de 2014

Dissertação de MestradoCiclo de Estudos Integrados Conducentes ao Grau deMestre em Engenharia Eletrónica Industrial e Computadores

Trabalho efetuado sob a orientação doProfessor Doutor Sérgio Paulo Carvalho Monteiro

Mauro Filipe Rodrigues Queirós

Planeamento de Caminhos paraRobôs Móveis Autónomos emAmbientes Conhecidos e Estruturados

Universidade do MinhoEscola de Engenharia

Agradecimentos

A elaboração desta dissertação só foi possível graças ao contributo, de formadireta ou indireta, de algumas pessoas às quais gostaria de expressar o meuagradecimento.

Em primeiro lugar, devo agradecer ao meu orientador, Doutor SérgioMonteiro, a sua disponibilidade, os conhecimentos transmitidos e as palavrasde incentivo constantes que foram essenciais para o desenrolar do projeto.

Agradeço também a todos os colegas e amigos que contribuíram para odesenvolvimento desta dissertação, bem como a todos aqueles que conheci eme acompanharam neste percurso académico.

Por último, mas não menos importante, um profundo reconhecimento àminha família, em especial aos meus pais, avós e irmã, pelo apoio incondicio-nal, incentivo e paciência ao longo destes anos. Dedico o mesmo sentimentoaos meus amigos mais próximos.

i

Esta página foi intencionalmente deixada em branco!

Resumo

Este projeto de dissertação aborda o problema do planeamento de caminhospara robôs móveis autónomos que operam em ambientes conhecidos e comobstáculos dinâmicos. O planeamento de caminhos visa, de uma forma geral,permitir a um robô gerar um caminho entre dois pontos de um mapa daforma mais eficiente possível e de maneira a não colidir com obstáculos. Noscasos em que existem vários robôs no mesmo ambiente, também é necessárioque exista coordenação entre eles. Este projeto visa o estudo particular daaplicação de métodos de planeamento de caminhos em carrinhos de comprasautónomos e inteligentes, que operam em ambientes semelhantes aos queexistem em superfícies comerciais.

Para permitir aos robôs planearem os seus percursos da melhor forma,exploraram-se diferentes metodologias de planeamento de caminhos, sendoque foram analisadas as vantagens e desvantagens de cada uma delas nocontexto deste projeto. Para representar o ambiente, foi decidido usar ummapa decomposto em células de igual tamanho. Para encontrar um cami-nho a partir dessa representação do mapa, foram selecionados e analisadoscom maior detalhe alguns algoritmos de busca, como o A* e o D* Lite. Oalgoritmo A*, juntamente com a distância de Manhattan como custo heurís-tico, foi o escolhido para gerar caminhos em ambientes semelhantes aos deum supermercado, mesmo nos casos em que existem obstáculos dinâmicos.Para os robôs seguirem o caminho planeado e, ao mesmo tempo, reagirema obstáculos desconhecidos em tempo real, decidiu-se utilizar um métodolocal em conjunto com esses métodos globais, de forma a criar um modelohíbrido mais robusto. O método local escolhido foi o método dos atratoresdinâmicos. A utilização deste método local permite também suavizar o ca-minho percorrido pelos robôs. Por último, para permitir a cada robô seguiro seu caminho de forma coordenada com o dos outros robôs, foram testadasdiferentes metodologias, selecionando-se o planeamento priorizado para umaimplementação final.

Palavras-chave: planeamento de caminhos, robôs móveis autónomos,algoritmos de busca, múltiplos robôs

iii


Abstract

This dissertation addresses the path planning problem for autonomous mo-bile robots operating in known environments with dynamic obstacles. Inits most general form, the task is to plan a path between a start positionand a goal position that avoids obstacles in some environment, in the mostefficient way. A mechanism of coordination is also required when there aremultiple robots in the same environment. This project aims to study theparticular application of path planning methods in autonomous and intel-ligent shopping carts, which operate in similar environments to those thatexist in supermarkets.

In order to enable a set of robots to plan their paths in the best possi-ble way, several path planning methods were explored and the advantagesand disadvantages of each one were analyzed, in the context of this pro-ject. A cell decomposition method with regular grids was used to model theenvironment. With the purpose of getting a path from that environmentmodelling, some search algorithms, such as A* and D* Lite, were selectedand analyzed in more detail. The A* algorithm, used with the Manhattandistance as an heuristic leading to the goal position, was the chosen methodfor creating paths in supermarket similar environments, even in cases wheredynamic obstacles exist. The robots are able to follow the planned pathsand react to unknown obstacles in real time, using a local method in addi-tion to those global methods, producing a more robust hybrid method. Anattractor dynamics approach was used to implement this local navigation.This local method also leads to smooth trajectories. Finally, in order toallow each robot to follow its path in a coordinated manner with the otherrobots, some methodologies were explored and for the final implementation,prioritized planning was the selected one.

Keywords: path planning, mobile robots, search algorithms, multiplerobots

v


Siglas e Abreviaturas

A* A Star

CAD Computer-aided Design

D* D Star

FM Fast Marching

FM2 Fast Marching Square

GPS Global Positioning System

i.e. Isto é

IFR International Federation of Robotics

LPA* Lifelong Planning A*

PRM Probabilistic Roadmaps

rhs Right hand side

RRT Rapidly Exploring Random Trees

vii


Conteúdo

1 Introdução 11.1 Enquadramento . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Objetivos da dissertação . . . . . . . . . . . . . . . . . . . . . 31.3 Descrição do problema . . . . . . . . . . . . . . . . . . . . . . 51.4 Estrutura da dissertação . . . . . . . . . . . . . . . . . . . . . 6

2 Fundamentos e Estado de Arte 72.1 Espaço de trabalho . . . . . . . . . . . . . . . . . . . . . . . . 72.2 Métodos roadmap . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2.1 Grafos de visibilidade . . . . . . . . . . . . . . . . . . 92.2.2 Diagramas de Voronoi . . . . . . . . . . . . . . . . . . 10

2.3 Métodos de decomposição por células . . . . . . . . . . . . . . 102.3.1 Método exato de decomposição por células . . . . . . 112.3.2 Método aproximado de decomposição por células . . . 112.3.3 Decomposição por células usando quadtrees . . . . . . 12

2.4 Campos potenciais . . . . . . . . . . . . . . . . . . . . . . . . 122.4.1 Fast Marching . . . . . . . . . . . . . . . . . . . . . . 14

2.5 Métodos probabilísticos . . . . . . . . . . . . . . . . . . . . . 152.5.1 RRT - Rapidly Exploring Random Trees . . . . . . . . 152.5.2 PRM - Probabilistic Roadmap . . . . . . . . . . . . . 16

2.6 Algoritmos de busca . . . . . . . . . . . . . . . . . . . . . . . 172.6.1 Algoritmo de Dijkstra . . . . . . . . . . . . . . . . . . 182.6.2 Algoritmo A* . . . . . . . . . . . . . . . . . . . . . . . 192.6.3 Algoritmos dinâmicos . . . . . . . . . . . . . . . . . . 22

2.7 Métodos locais . . . . . . . . . . . . . . . . . . . . . . . . . . 252.7.1 Algoritmos Bug . . . . . . . . . . . . . . . . . . . . . . 262.7.2 Atratores dinâmicos . . . . . . . . . . . . . . . . . . . 27

2.8 Múltiplos robôs . . . . . . . . . . . . . . . . . . . . . . . . . . 312.8.1 Métodos básicos . . . . . . . . . . . . . . . . . . . . . 322.8.2 Planeamento descentralizado . . . . . . . . . . . . . . 332.8.3 Planeamento centralizado . . . . . . . . . . . . . . . . 35

2.9 Discussão do estado de arte . . . . . . . . . . . . . . . . . . . 35

ix

3 Implementação 393.1 Ferramenta de simulação . . . . . . . . . . . . . . . . . . . . . 393.2 Detalhes da implementação . . . . . . . . . . . . . . . . . . . 433.3 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

4 Planeamento para um Único Robô 534.1 Resolução do mapa . . . . . . . . . . . . . . . . . . . . . . . . 534.2 Custos heurísticos . . . . . . . . . . . . . . . . . . . . . . . . 554.3 Planeamento inicial . . . . . . . . . . . . . . . . . . . . . . . . 574.4 Atratores dinâmicos . . . . . . . . . . . . . . . . . . . . . . . 594.5 Replaneamento . . . . . . . . . . . . . . . . . . . . . . . . . . 634.6 Discussão dos resultados . . . . . . . . . . . . . . . . . . . . . 67

5 Planeamento para Vários Robôs 695.1 Sem comunicação . . . . . . . . . . . . . . . . . . . . . . . . . 705.2 Com comunicação . . . . . . . . . . . . . . . . . . . . . . . . 75

5.2.1 Planeamento priorizado . . . . . . . . . . . . . . . . . 765.3 Discussão dos resultados . . . . . . . . . . . . . . . . . . . . . 80

6 Conclusões e Trabalho Futuro 83

7 Bibliografia 87

A Algoritmos 93A.1 Algoritmo de Dijkstra . . . . . . . . . . . . . . . . . . . . . . 93A.2 Algoritmo A* . . . . . . . . . . . . . . . . . . . . . . . . . . . 94A.3 Algoritmo LPA* . . . . . . . . . . . . . . . . . . . . . . . . . 95A.4 Algoritmo D* Lite . . . . . . . . . . . . . . . . . . . . . . . . 97

Lista de Figuras

1.1 Robôs de serviço. . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 GPS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Carrinhos de compras autónomos numa superfície comercial. 31.4 Etapas no planeamento de caminhos. . . . . . . . . . . . . . . 4

2.1 Graus de liberdade do robô. . . . . . . . . . . . . . . . . . . . 82.2 Expansão de obstáculos. . . . . . . . . . . . . . . . . . . . . . 92.3 Métodos roadmap. . . . . . . . . . . . . . . . . . . . . . . . . 102.4 Métodos de decomposição por células. . . . . . . . . . . . . . 112.5 Decomposição por células utilizando quadtrees. . . . . . . . . 122.6 Campos potenciais. . . . . . . . . . . . . . . . . . . . . . . . . 132.7 Comparação entre os métodos FM2 e FM2*. . . . . . . . . . 152.8 Caminho obtido utilizando o Algoritmo RRT. . . . . . . . . . 162.9 Busca Breadth-First. . . . . . . . . . . . . . . . . . . . . . . . 182.10 Busca Depth-First. . . . . . . . . . . . . . . . . . . . . . . . . 182.11 Custo do movimento entre células adjacentes. . . . . . . . . . 202.12 Comparação entre uma pesquisa Dijkstra e A*. . . . . . . . . 212.13 Carro autónimo da Google. . . . . . . . . . . . . . . . . . . . 222.14 Sonda Spirit em solo marciano. . . . . . . . . . . . . . . . . . 232.15 Custo do movimento entre nós adjacentes. Situação em que

existe caminho livre entre dois nós. . . . . . . . . . . . . . . . 242.16 Custo do movimento entre nós adjacentes. Situação em que

deixa de existir caminho livre entre dois nós. . . . . . . . . . 242.17 Informação armazenada por cada nó quando usado o LPA*. . 252.18 Caminho produzido utilizando os algoritmos Bug1 e Bug2. . . 262.19 Caminho produzido utilizando o algoritmo Tangent Bug. . . . 272.20 Robô move-se para o alvo utilizando o método dos atratores

dinâmicos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.21 Forças que orientam a direção de navegação do robô quando

é utilizado o método dos atratores dinâmicos. . . . . . . . . . 312.22 Importância da ordem de prioridades no planeamento priori-

zado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.23 Dois robôs num corredor estreito pretendem trocar de posição. 35

xi

3.1 Modelo cliente/servidor do Player/Stage. . . . . . . . . . . . 403.2 Robô Pioneer 2DX no Stage. . . . . . . . . . . . . . . . . . . 413.3 Sonares frontais do Pioneer 2DX. . . . . . . . . . . . . . . . . 413.4 Deteção da posição de um obstáculo através de um laser. . . 423.5 Deteção de um obstáculo através da câmara de deteção de

cores. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433.6 Robô Pioneer 2DX e alguns obstáculos num ambiente produ-

zido pelo Stage. . . . . . . . . . . . . . . . . . . . . . . . . . . 433.7 Interligação entre os diferentes métodos usados para controlar

o movimento do robô. . . . . . . . . . . . . . . . . . . . . . . 443.8 Representação de um ambiente através de uma matriz binária. 443.9 Suavização do caminho percorrido pelo robô. . . . . . . . . . 453.10 Robô a contornar um obstáculo. . . . . . . . . . . . . . . . . 463.11 Replaneamento de um caminho quando um novo obstáculo é

detetado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463.12 Fluxograma da forma como o robô navega em direção ao

ponto-alvo final. . . . . . . . . . . . . . . . . . . . . . . . . . 473.13 Interface gráfica utilizada em conjunto com o Player/Stage. . 483.14 Deteção de obstáculos a partir das leituras do laser do robô. . 493.15 Células expandidas usando diferentes algoritmos. . . . . . . . 493.16 2 robôs detetam-se utilizando a câmara de deteção de cores. . 50

4.1 Decomposição do mapa em células de igual tamanho. . . . . . 544.2 Obstáculos num ambiente dividido em células. . . . . . . . . . 544.3 Cenários utilizados para comparar custos heurísticos. . . . . . 554.4 Cenários utilizados para comparar os resultados obtidos no

planeamento inicial. . . . . . . . . . . . . . . . . . . . . . . . 574.5 Robô a dirigir-se para o próximo alvo. . . . . . . . . . . . . . 604.6 Obstáculo entre o robô e o próximo alvo. . . . . . . . . . . . . 604.7 Robô segue o seu percurso ao mesmo tempo que evita a colisão

com obstáculos. . . . . . . . . . . . . . . . . . . . . . . . . . . 614.8 Robô tenta contornar obstáculo e replaneia caminho. . . . . . 624.9 Influência do tempo de replaneamento no caminho final per-

corrido. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624.10 Robô a contornar um pequeno obstáculo. . . . . . . . . . . . 634.11 Número de células expandidas para replanear um caminho

quando existe um pequeno obstáculo a bloquear o caminhooriginal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

4.12 Tempo necessário para encontrar um caminho quando existeum pequeno obstáculo a bloquear o caminho original. . . . . 64

4.13 Obstáculo a obstruir a passagem do robô. . . . . . . . . . . . 654.14 Número de células expandidas para replanear um caminho

quando um obstáculo bloqueia totalmente o caminho original. 65

4.15 Tempo necessário pelo algoritmo para encontrar um caminhoquando um obstáculo bloqueia totalmente o caminho original. 65

4.16 Mapa com obstáculos inicialmente desconhecidos pelo robô. . 664.17 Caminho planeado e caminho percorrido num cenário com

obstáculos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

5.1 Robôs navegam num ambiente semelhante ao de um super-mercado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.2 Uma colisão é evitada entre dois robôs, que depois não con-seguem seguir o trajeto previsto. . . . . . . . . . . . . . . . . 71

5.3 Vários robôs aglomeram-se na mesma zona do mapa. . . . . . 715.4 Uma colisão é evitada com sucesso entre dois robôs. . . . . . 725.5 Uma colisão é evitada entre dois robôs, que depois seguem a

mesma direção de navegação. . . . . . . . . . . . . . . . . . . 735.6 Distâncias de segurança em torno do robô quando usada a

câmara de deteção de cores. . . . . . . . . . . . . . . . . . . . 735.7 Robô deteta outro robô através da sua câmara e toma a de-

cisão de parar. . . . . . . . . . . . . . . . . . . . . . . . . . . 745.8 Fluxograma das estratégias adotadas quando outro robô é

detetado pela câmara. . . . . . . . . . . . . . . . . . . . . . . 755.9 Robôs num cruzamento utilizam a câmara de deteção de cores

para coordenarem o seu movimento. . . . . . . . . . . . . . . 765.10 Fluxograma da comunicação entre robôs durante o planea-

mento priorizado. . . . . . . . . . . . . . . . . . . . . . . . . . 785.11 Robô com menor prioridade compara a sua trajetória com a

do outro robô e toma a decisão de parar. . . . . . . . . . . . . 795.12 Trajetos percorridos por três robôs entre os seus pontos inicial

e final utilizando o planeamento priorizado. . . . . . . . . . . 795.13 Robôs cruzam-se na mesma zona e seguem o seu percurso

utilizando o planeamento priorizado. . . . . . . . . . . . . . . 80


Lista de Tabelas

4.1 Comparação entre diferentes custos heurísticos nos três cená-rios em teste. . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

4.2 Resultados obtidos para o planeamento inicial no cenário apre-sentado na figura 4.4a. . . . . . . . . . . . . . . . . . . . . . . 58

4.3 Resultados obtidos para o planeamento inicial no cenário apre-sentado na figura 4.4b. . . . . . . . . . . . . . . . . . . . . . . 58

4.4 Resultados obtidos para o replaneamento em diferentes zonasno cenário da figura 4.16. . . . . . . . . . . . . . . . . . . . . 67

5.1 Tipos de mensagens trocadas entre robôs. . . . . . . . . . . . 775.2 Resultados obtidos quando usado o planeamento priorizado

na situação apresentada na figura 5.13. . . . . . . . . . . . . . 80

xv


Capítulo 1

Introdução

1.1 Enquadramento

Nas últimas décadas tem existido uma grande evolução nas áreas da robóticae automação. Segundo a Federação Internacional da Robótica (IFR), 2013foi mesmo o ano com mais robôs industriais e de serviço vendidos [1]. Até2008, cerca de 65000 robôs de serviço para uso profissional foram vendidosdurante um período de 12 anos, enquanto que nos últimos 5 anos foramvendidos cerca de 100000. Isto demonstra o crescimento desta área. A IFRestima também que nos próximos tempos a venda deste tipo de produtoscontinue a crescer, prevendo-se mesmo que nos próximos três anos sejamvendidos 134500 novos robôs de serviço para uso profissional.

Os robôs de serviço são robôs não industriais, tipicamente móveis, e quesão normalmente associados com a ajuda a tarefas realizadas por humanosem ambientes interiores, sendo capazes de navegar e de se adaptarem aosambientes onde atuam. Os aspiradores autónomos, os robôs corta-relvase os robôs assistentes em hospitais são exemplos de robôs de serviço (verfigura 1.1). Os dois primeiros utilizam os seus sensores para navegar nosseus ambientes-alvo enquanto se desviam de obstáculos. Os robôs assisten-tes em hospitais, por sua vez, realizam um vasto leque de tarefas, desde otransporte de resíduos, até à entrega de comida e medicamentos. Estes as-sistentes hospitalares são capazes de escolher o melhor caminho para atingirum determinado local e de utilizarem os seus sensores para se desviaremde obstáculos e alterarem o percurso planeado caso necessário. Estes robôsrealizam tarefas de localização, desvio de obstáculos e planeamento de ca-minhos. Esta última tarefa é uma componente fundamental em qualquerrobô móvel autónomo.

O planeamento de caminhos visa conseguir dotar um robô com a capa-cidade de calcular um percurso entre um ponto A e um ponto B da formamais eficiente possível e de maneira a não colidir com obstáculos. Normal-mente, é requerido ao planeador encontrar o caminho mais curto entre dois

1

CAPÍTULO 1. INTRODUÇÃO 2

(a) (b) (c)

Figura 1.1: Alguns exemplos de robôs de serviço. Em 1.1a está representadoum aspirador autónomo [2], em 1.1b um robô corta-relvas [3] e em 1.1c umrobô assistente em hospitais [4].

pontos, no entanto, outros critérios podem ser considerados, tais como, otempo necessário para percorrer o caminho ou o nível de segurança do robôem cada ponto do percurso.

Algumas aplicações práticas deste tipo de algoritmos têm surgido nosúltimos anos, tal como o carro autónomo da Google [5], sondas para ex-ploração espacial [6] e outros veículos inteligentes não tripulados [7] [8]. Noentanto, o planeamento de caminhos é também uma componente fundamen-tal noutros ambientes, como por exemplo em desenho CAD [9], em biologiamolecular [10], e até em ambientes virtuais, como jogos de computador (in-teligência artificial) [11], para mover as personagens dentro do ambiente dejogo. Os GPS’s são outros dos exemplos mais comuns da utilização destetipo de algoritmos. Estes sistemas de navegação são capazes de determinar asua posição, mas também de indicar o caminho que deve ser percorrido parachegar ao local desejado, a partir da análise dos seus mapas topológicos.Todas estas aplicações requerem um planeador suficientemente rápido paraque vários caminhos possam ser construídos num curto espaço de tempo.

Figura 1.2: Os GPS’s permitem encontrar o melhor caminho entre 2 pontos,a partir dos seus mapas topológicos integrados e um sistema de localizaçãopara estimar a posição atual1.

Este tema de dissertação surgiu a partir de uma proposta de criaçãode um carrinho de compras autónomo e inteligente para uso em superfícies

1Imagem retirada de: http://www.shutterstock.com/de/pic-94560832/stock-photo-smart-phone-navigation-mobile-gps-d-concept.html


comerciais. Este carrinho deveria não só ser capaz de seguir o ”dono” nassuas compras, mas também de o guiar, localizando um produto e decidindoo melhor caminho para alcançar esse produto.

1.2 Objetivos da dissertação

Nesta dissertação será feito um estudo genérico em relação ao planeamentode caminhos em ambientes conhecidos, mas também um estudo sobre o casoparticular do carrinho de compras autónomo e inteligente, tendo em atençãoque poderão existir vários carrinhos numa superfície comercial. Os robôsdevem ser capazes de operar cooperativamente de modo a serem evitadascolisões, ou seja, além dos obstáculos, devem ser capazes de planear o seucaminho de acordo com o caminho planeado pelos outros robôs.

O primeiro objetivo desta dissertação é estudar os diferentes métodosde planeamento de caminhos, implementar os algoritmos para os diferentesmétodos e simular o comportamento dos robôs com os diferentes algorit-mos, alterando-os, se for necessário, para se adaptarem da melhor forma aoambiente em que serão utilizados.

O segundo objetivo é fazer um estudo mais específico em relação à utili-zação do robô como um carrinho de compras em supermercados. Nesta faseserá necessário perceber a melhor forma de fazer o mapeamento do super-mercado, tendo em atenção que será necessário detetar não só os obstáculosfixos (i.e. prateleiras), mas também, será necessário perceber o compor-tamento e localização dos clientes e outros tipos de obstáculos, como porexemplo, carrinhos de compras não autónomos (ver figura 1.3).

Figura 1.3: Carrinhos de compras autónomos numa superfície comercial.Conhecendo a localização do produto pretendido, cada carrinho deve sercapaz de decidir o melhor percurso para chegar ao seu destino


Uma vez que o objetivo principal é encontrar caminhos, dentro de umambiente conhecido, entre pontos iniciais e pontos finais a serem atingidospor um robô, ou por vários em simultâneo é necessário percorrer algumasetapas que vão desde a representação de um mapa até ao planeamento docaminho a ser percorrido por cada robô (ver figura 1.4).

Mapa do Ambiente

Representação de Todos os Caminhos Possíveis

Algoritmo de Busca

Caminho Final

Figura 1.4: Passos necessários para encontrar um caminho a partir de umarepresentação de um mapa.

O primeiro problema a ser resolvido é o de encontrar a melhor forma derepresentar o ambiente através de um mapa, pois os robôs devem ser capazesde conhecer:

1. a sua localização

2. a localização, forma e tamanho dos obstáculos (fixos e móveis) e deoutros robôs

3. a localização do ponto final

Depois de se dotar cada robô com ummapa do ambiente, serão analisadosalguns métodos que permitem obter uma representação de todos os caminhospossíveis entre a posição atual de cada robô e o ponto que se deseja atingir.Existem vários métodos para resolver este tipo de problemas [12], sendoque, normalmente, mais do que um pode ser utilizado para encontrar amesma solução. É, portanto, necessário fazer um estudo sobre os diferentesmétodos, de forma a conhecer os prós e contras de cada um deles. Depoisde estudados os diferentes métodos será necessário proceder a simulaçõesque testem a capacidade dos métodos reagirem a situações idênticas às que


vão ser encontradas pelos robôs no mundo real. No fim, serão comparadosos diferentes resultados obtidos, e escolhida a melhor forma de resolver oproblema.

Como a partir dos resultados obtidos será necessário encontrar o caminhoentre o ponto inicial e o ponto final que melhor satisfaça o problema pro-posto, serão também estudados e simulados diferentes algoritmos de busca.Terá de se ter em atenção o facto de poderem existir vários robôs a operar emsimultâneo, sendo que os robôs têm de encontrar caminhos que se adaptemtambém aos caminhos descritos por outros robôs. Além disso podem existiralguns obstáculos dinâmicos durante o percurso dos robôs, o que poderá le-var a um replaneamento do caminho a ser percorrido. De forma análoga aocaso anterior, serão comparados os resultados obtidos, e escolhida a melhorforma de resolver o problema.

1.3 Descrição do problema

O planeamento de caminhos visa encontrar uma sequência contínua de po-sições válidas, entre uma localização inicial e uma localização final, quepermitam a um robô mover-se em direção ao alvo final ao mesmo tempoque o contacto com os obstáculos é evitado. O caminho gerado é uma curvarepresentada por uma expressão matemática ou por um conjunto de pontos.A escolha da sequência de posições é feita de forma a minimizar um custoque se ajuste ao problema em questão, tal como obter um caminho com amenor distância possível até localização final, planear um caminho no menorperíodo de tempo, minimizar o consumo de energia do robô ou aumentar oespaço de manobra. Em ambientes interiores, por exemplo, o caminho idealé normalmente aquele que permite ao robô navegar com a máxima segurançae com a maior distância possível em relação aos obstáculos.

O planeamento de um caminho pode ser feito global ou localmente. Noprimeiro caso, o robô possui um modelo do ambiente a priori através deum mapa inicial ou através da perceção obtida pela análise da informaçãosensorial recolhida em instantes anteriores. Por outro lado, o planeamentolocal é utilizado em ambientes desconhecidos, nos quais o robô tem que usaras leituras dos seus sensores para adotar estratégias reativas para evitarobstáculos ao mesmo tempo que se dirige para um alvo. Muitas vezes umplaneador global é utilizado em conjunto com um planeador local, para criarum planeador híbrido mais robusto [13] [14].

Em ambientes dinâmicos, as mudanças (obstáculos móveis ou outrosrobôs) também devem ser tidas em conta e oferecem um desafio mais com-plexo. Os obstáculos dinâmicos são normalmente tratados como objetosestáticos no instante em que se dá o planeamento.

Em situações em que existem vários robôs no mesmo ambiente, um pla-neador centralizado ou descentralizado, deve ser capaz de obter caminhos


para cada robô que permitam a cada um atingir a sua localização final, eevitar ao mesmo tempo colisões com outros robôs e obstáculos. Além disso,devem ser otimizados alguns critérios, tal como a distância percorrida porcada robô ou o tempo necessário para atingir a localização final.

1.4 Estrutura da dissertaçãoOs próximos capítulos desta dissertação estão organizados da seguinte forma.No capítulo 2 é feita uma revisão bibliográfica sobre diferentes metodologiase algoritmos usados no planeamento de caminhos. Essa revisão é feita tantopara um robô como para vários robôs em simultâneo no mesmo ambiente.Para cada uma dessas metodologias é feita uma análise às suas vantagense desvantagens. No capítulo 3 são apresentadas as ferramentas usadas paraefetuar as simulações, bem como a forma como alguns métodos foram usadospara controlar e coordenar os robôs. No capítulo 4, alguns algoritmos sãocomparados em situações em que existe apenas um robô a operar num dadoambiente. No capítulo 5, por sua vez, são comparados alguns métodos emsituações em que existem vários robôs a operar em simultâneo no mesmoespaço. Por último, são feitas algumas conclusões no capítulo 6, bem comosugestões para o trabalho futuro.

Capítulo 2

Fundamentos e Estado deArte

Este capítulo inicia-se com uma análise ao espaço de trabalho no qual osrobôs navegam. Depois, são abordados alguns dos algoritmos de planea-mento de caminhos mais utilizados. São estudados não só métodos globaisde planeamento de caminhos, como métodos roadmap, de decomposição porcélulas e campos potenciais, mas também, métodos locais, como algoritmosBug e o método dos atratores dinâmicos. Além disso também são analisadosalguns métodos probabilísticos. Também serão estudados alguns algoritmosde busca que permitem encontrar um caminho entre o ponto inicial e o pontofinal a partir das representações do ambiente criadas por alguns desses méto-dos. Por último, serão estudadas algumas metodologias usadas em situaçõesque envolvem vários robôs a operar em simultâneo no mesmo ambiente.

2.1 Espaço de trabalho

O espaço de trabalho é o ambiente no qual o robô está inserido. Dentrodeste espaço de trabalho, existem locais já ocupados (obstáculos) e locais nãoocupados (espaço livre). Para ser possível planear um caminho dentro desseespaço de trabalho, tanto o robô como a ambiente devem ser modelados.

Em primeiro lugar, o planeamento de caminhos envolve a existência deum espaço de estados que representa todas as configurações possíveis dorobô. A definição de um espaço de estados é muito importante para aformulação do problema a ser resolvido, bem como para o design e análisedos algoritmos que o podem resolver. Este espaço de estados deve ser capazde descrever o estado do robô dentro do ambiente, mas também de tornaro problema o mais simples possível, de modo a aumentar a exequibilidadedos algoritmos.

O espaço de estados é representado por um vetor de dimensão N, queindica o número de graus de liberdade do robô. No trabalho desenvolvido

7

CAPÍTULO 2. FUNDAMENTOS E ESTADO DE ARTE 8

nesta dissertação, é apenas necessário considerar que o robô se move numambiente a duas dimensões (ver figura 2.1) e, como tal, apenas são consi-derados três informações: as coordenadas relativas à posição do robô (x ey) e a direção em que o robô se move. A direção em que o robô se movetambém é na maior parte das vezes ignorada durante o planeamento. Pos-teriormente são aplicadas algumas estratégias que permitam ao robô alterara sua direção de navegação e seguir cada ponto do caminho planeado. Estasestratégias serão abordadas mais à frente neste capítulo. A representaçãodo robô tem, desta forma, apenas dois graus de liberdade durante o plane-amento: as coordenadas x e y.

No planeamento de caminhos normalmente assume-se:

1. uma representação do ambiente com dois graus de liberdade

2. que o robô é redondo e, portanto, a orientação não é importante

3. que o robô é holonómico (pode-se mover instantaneamente em qual-quer direção)

Figura 2.1: À esquerda está representado um objeto num ambiente a trêsdimensões e à direita o mesmo objeto num ambiente a duas dimensões.Assumir que o ambiente tem apenas duas dimensões em vez de três possi-bilita reduzir o número de graus de liberdade de seis (três coordenadas quedescrevem o movimento e três ângulos que descrevem a rotação) para três(duas coordenadas que descrevem o movimento e um ângulo que descreve arotação).

Para simplificar o planeamento de um caminho, o robô pode ser con-siderado como um ponto. Ao efetuar esta simplificação, é necessário fazeralguns ajustes de forma a ser possível encontrar um caminho final válido. Aforma mais usual de realizar esses ajustes é a de expandir os obstáculos ereduzir os limites do ambiente de acordo com o raio do robô. Se um ponto érepresentado como estando perto do limite de um obstáculo mas sem tocarneste, então o robô também não está a colidir com o obstáculo. No exemploda figura 2.2 está representado um ambiente com um robô circular e trêsobstáculos, e o mesmo ambiente com um ponto a representar o robô e comos três obstáculos expandidos. A figura 2.2a mostra que o robô é incapaz


de se mover entre os dois obstáculos da direita. A expansão dos obstáculosrepresentada na figura 2.2b também não permite que o robô representadopor um ponto passe entre esses dois obstáculos.

Este novo espaço criado após a expansão dos obstáculos é o espaçode configuração. O espaço total (Cspace) é dividido em espaço ocupado(Cobstacle) e espaço livre (Cfree). O espaço ocupado representa as configu-rações que o robô não pode tomar, enquanto que o espaço livre representatodas as configurações válidas em que o ponto se pode mover livrementedentro do espaço de configuração.

Cspace = Cfree + Cobstacle (2.1)

(a) (b)

Figura 2.2: Este exemplo demonstra a utilidade da expansão de obstáculosem ambientes que serão percorridos por robôs circulares (ou aproximada-mente circulares). No exemplo da figura 2.2a está representado um ambi-ente com um robô e alguns obstáculos. Na figura 2.2b está representado omesmo ambiente, mas com os obstáculos e os limites do mapa expandidosde forma a ser possível considerar o robô como um ponto.

2.2 Métodos roadmapOs métodos roadmap permitem obter a conectividade do espaço livre doambiente em que o robô está inserido, através de uma rede de retas e/oucurvas. Os grafos de visibilidade [15] e os diagramas de Voronoi [16] sãoexemplos deste tipo de métodos.

2.2.1 Grafos de visibilidade

O método dos grafos de visibilidade foi um dos primeiros métodos roadmapa ser desenvolvido. Um grafo de visibilidade é produzido a partir da criaçãode retas que passem por alguns pontos do mapa e não intersetem obstácu-los. Caso os obstáculos sejam poligonais ou circulares, os pontos do grafo devisibilidade são os seguintes: o ponto inicial, o ponto final e os vértices dos


A

B

(a)

A

B

(b)

Figura 2.3: Planeamento do caminho a ser percorrido por determinado robôentre um ponto A e um ponto B usando métodos roadmap [15] [16]. Noexemplo da figura 2.3a foi utilizado um grafo de visibilidade, enquanto queno exemplo da figura 2.3b foi utilizado um diagrama de Voronoi.

obstáculos poligonais (ver figura 2.3a) ou pontos tangentes aos obstáculoscirculares. Nos casos em que obstáculos têm outras formas, é aconselhávela utilização de outros métodos. Devido há forma como é construído, o per-curso em algumas zonas do mapa é feito demasiado próximo dos obstáculosem comparação com outros métodos roadmap.

2.2.2 Diagramas de Voronoi

Os diagramas de Voronoi consistem na criação de um conjunto de pontosequidistantes entre os obstáculos do ambiente de forma a serem desenhadasum conjunto de linhas curvas que maximizem o espaço livre entre os obstá-culos e esses pontos. Através dessas linhas, é possível encontrar um caminhoentre o ponto inicial e o ponto final (ver figura 2.3b). Os diagramas de Vo-ronoi permitem obter percursos o mais afastados possível dos obstáculos, oque é uma vantagem em relação aos grafos de visibilidade. No entanto, nãopermitem obter o caminho mais curto até ao ponto final, ao contrário destesúltimos.

2.3 Métodos de decomposição por célulasO método de decomposição por células, por sua vez, visa decompor o es-paço livre do ambiente em que o robô está inserido num conjunto de regiõesmais simples denominadas células. Cada célula é representada por um nóno espaço livre e um caminho é obtido encontrando um conjunto de nósadjacentes entre o ponto inicial e o ponto final [17]. Existem diversos mé-todos de decomposição por células, tais como: o método exato, o métodoaproximado e métodos que decompõe o ambiente recursivamente através de,por exemplo, quadtrees.


A

B

(a)

A

B

(b)

Figura 2.4: - Planeamento do caminho a ser percorrido por um determinadorobô entre um ponto A e um ponto B usando métodos de decomposição porcélulas [17]. No exemplo da figura 2.4a está representado um método exatode decomposição por células, enquanto que no exemplo da figura 2.4b estárepresentado um método aproximado de decomposição por células

2.3.1 Método exato de decomposição por células

O método exato divide o espaço livre em células através da utilização delinhas verticais que unem os vértices dos obstáculos com o limite externo doespaço de trabalho ou com outros obstáculos. Neste método, os obstáculossão poligonais e o espaço livre é decomposto em células triangulares e trape-zoidais. Cada uma dessas células é representada por um nó que indica o seuponto central. A união entre duas células adjacentes também é representadapor um nó que indica o ponto médio da reta que une as duas regiões. Umcaminho no espaço livre é encontrado percorrendo esses nós entre o pontoinicial e o ponto final (ver figura 2.4a).

2.3.2 Método aproximado de decomposição por células

O método aproximado visa decompor o espaço total do ambiente em que orobô está inserido num conjunto de células com uma resolução e uma formainiciais pré-definidas. Cada célula que interseta um obstáculo é definidacomo ”proibida”, enquanto que todas as outras são definidas como célulaslivres. O tamanho das células deve ser escolhido de acordo com o problemaa ser resolvido. Um tamanho de células pequeno permite obter uma grandeprecisão mas pode implicar a utilização de uma grande quantidade de me-mória e de um tempo de processamento demasiado elevado. Por outro lado,a utilização de um tamanho demasiado grande diminui a precisão e, conse-quentemente, pode impossibilitar que um caminho seja encontrado, mesmoquando este exista. Um maior tamanho de células diminui também o tempode processamento, devido ao menor número de células que têm que ser anali-


sadas. Após ser concluída a decomposição, um caminho pode ser encontradoatravés da análise de células adjacentes no espaço livre entre o ponto iniciale o ponto final (ver figura 2.4b).

2.3.3 Decomposição por células usando quadtrees

O método de decomposição por células usando quadtrees utiliza células detamanho variável para representar o ambiente [18]. As células são decom-postas sucessivamente de uma forma recursiva em quatro células-filhas atéque uma célula esteja situada numa zona totalmente preenchida ou livre,ou até que uma resolução limite seja atingida. Se as quatro células-filhasde uma célula estiverem totalmente livres ou ocupadas, então a célula-mãetambém pode ser considerada como estando livre/ocupada. Por este mo-tivo, as zonas próximas dos obstáculos têm um número de células bastantesuperior em relação às restantes regiões, tal como demonstra a figura 2.5.De igual modo aos métodos anteriores, um caminho é obtido encontrandoum conjunto de células adjacentes no espaço livre entre a localização iniciale final pretendidas. Como as células são sucessivamente decompostas atéestarem situadas numa zona totalmente preenchida ou livre, este métodopermite obter uma grande precisão nas zonas próximas dos obstáculos, in-dependentemente da resolução inicial escolhida. Por outro lado, nos casosem que existem obstáculos móveis, a decomposição tem que ser reiniciadasempre que surjam alterações no mapa, o que é uma desvantagem em termosde tempo de processamento.

B

A

Figura 2.5: Planeamento do caminho a ser percorrido por um determinadorobô entre um ponto A e um ponto B utilizando quadtrees para fazer umadecomposição recursiva do ambiente [18].

2.4 Campos potenciaisOs campos potenciais geram um caminho através da utilização de funçõesque criam um potencial atrativo em torno do alvo e um potencial repulsivo


em torno de cada obstáculo [19]. A soma destas forças controla o robôdurante o seu caminho entre o ponto inicial e o ponto final.

Figura 2.6: Caminho percorrido entre um ponto A um ponto B utilizandocampos potencias para orientar o robô [19]. As linhas curvas representama ação dos campos potenciais que afastam o robô dos obstáculos ao mesmotempo que o guiam até ao ponto final.

Para ser possível controlar o movimento do robô, é usada uma funçãopotencial total que é obtida através da soma das funções potenciais atrativase repulsivas. A função potencial total é então dada por:

U(p) =n∑

i=0Ui(p) (2.2)

em que p é um ponto do mapa, U0 é a função potencial para o alvo e Ui,para i = [1, n], são as funções potenciais para cada um dos n obstáculos.

Ao robô é aplicada uma força que é proporcional ao gradiente negativoda função potencial total. A direção que o robô deve tomar é então dadapor:

p = −U(p)(p) = −

n∑i=0

Ui(p)p

(2.3)

O método dos campos potenciais é bastante utilizado pela sua simplici-dade e pela velocidade com que apresenta uma solução, sendo consideradocomo um dos métodos mais rápidos no planeamento de caminhos [20]. Noentanto, existem alguns pontos negativos, tal como o problema dos mínimoslocais. Este problema surge em situações em que a força de atração e a forçade repulsão se anulam. Para resolver este problema, são normalmente utili-zadas funções de navegação que definem um único mínimo local possível: oponto final.


2.4.1 Fast Marching

Um dos métodos que gera campos potenciais e que permite que apenas ummínimo local seja definido, é o Fast Marching (FM) [21]. A construção decampos potenciais através do método FM, pode ser visto da mesma formaque a expansão de uma onda na água. Quando uma pedra é lançada eatinge a água, forma-se uma onda circular em torno do ponto onde a pedracaiu, sendo que a onda passa com a mesma velocidade em todos os pontosequidistantes em relação ao ponto inicial. No FM é construída uma ondaartificial da mesma forma, mas que não é circular devido à presença deobstáculos e outros fatores (i. e. tipo de terreno) que alteram a velocidadede expansão da onda em cada ponto. Este método permite gerar o caminhomais curto, criando uma trajetória que tem em atenção a velocidade comque a onda artificial percorreu cada ponto.

Os resultados produzidos pelo método original não são os ideais devido àproximidade da trajetória final com os obstáculos e ao facto de a velocidadeser muito baixa nos pontos próximos desses locais ocupados do mapa. Poreste motivo, algumas variantes baseadas no FM foram criadas, tal como a suautilização em conjunto com diagramas de Voronoi [22]. Tal como referido nocapítulo 2.2, os diagramas de Voronoi permitem criar um conjunto de pontosequidistantes em relação aos obstáculos. A partir dessa representação domapa, o método FM pode ser usado para criar campos potenciais até aoponto final. Esta variante reduz consideravelmente o tempo necessário paraencontrar uma trajetória.

Outra variante do método original é o Fast Marching Square (FM2) [23].Esta variante, em vez de criar uma onda artificial a partir do ponto inicial,cria um conjunto de ondas artificiais que têm como origem os obstáculos.O método FM2 permite obter uma trajetória o mais afastada possível dosobstáculos, sendo o resultado final idêntico ao obtido utilizando o FM comdiagramas de Voronoi.

Como muitas vezes não é necessário existir uma trajetória tão afastadados obstáculos, outra versão do mesmo método pode ser utilizada: o FM2com saturação [23]. Neste método, o mapa é alterado a partir da represen-tação obtida pelo FM2, de acordo com a distância máxima de segurançapermitida em relação aos obstáculos e com a velocidade máxima permitida.Todos os pontos que estão a uma distância superior à distância de segu-rança são pontos em que o robô pode viajar à velocidade máxima. A partirdessa distância, quanto mais perto um ponto esteja dos obstáculos, menora velocidade permitida nesse ponto.

Uma das variantes mais recentes deste método, e que utiliza custos heu-rísticos para orientar a procura de um caminho ao ponto final, é o FastMarching Square Star (FM2*) [23]. Ao contrário das variantes anterioresem que a onda artificial se expande em todas as direções da mesma forma,o FM2* reduz o número de pontos expandidos pois o ponto final é tido em


consideração e, desta forma, os pontos mais próximos do ponto final sãopercorridos em primeiro lugar (ver figura 2.7). De acordo com os autores,este método reduz até quatro vezes o tempo de computação de um caminhoem relação ao FM2, produzindo um caminho final semelhante.

(a) Trajetória obtida com o FM2. (b) Trajetória obtida com o FM2*.

Figura 2.7: Comparação entre os resultados obtidos utilizando o FM2 e oFM2* [23]. O FM2* permite obter a mesma trajetória analisando menoszonas do mapa.

2.5 Métodos probabilísticos

Ao contrário dos métodos anteriores, nos métodos probabilísticos um ca-minho é construído escolhendo e unindo pontos aleatórios do mapa até queuma solução seja encontrada ou até que o tempo de planeamento expire [24].Os sistemas Ant Colony [25], os algoritmos genéticos [26] [27], o método Par-ticle Swarm Optimization [28], os Probabilistic Roadmaps (PRM) [29] e oalgoritmo Rapidly Exploring Random Trees (RRT) são exemplos de méto-dos probabilísticos. Os dois últimos são os mais comuns e serão analisadosde seguida.

2.5.1 RRT - Rapidly Exploring Random Trees

Este tipo de métodos permitem uma solução rápida a partir da criação de ra-mos aleatórios a partir de um ponto inicial [30]. Os ramos que não colidemcom obstáculos são guardados, e novos ramos são criados aleatoriamenteaté ao ponto final ser atingido (ver figura 2.8). O algoritmo RRT começacom uma árvore vazia e no início é conhecido o ambiente, o ponto inicial,o ponto final e o número de amostras máximo. O algoritmo gera amostrasaleatoriamente até que o número máximo de amostras seja atingido ou atéque um caminho no espaço livre entre o ponto inicial e o ponto final sejaencontrado. Caso o número de amostras máximo seja atingido antes de umcaminho ser encontrado, o algoritmo volta a ser executado com um maior nú-mero de amostras, ou então assume-se que não existe solução. Outra formade utilizar o algoritmo RRT é, depois de uma solução inicial ser encontrada,


continuar a aumentar o número de amostras para procurar melhores solu-ções. Este algoritmo é muitas vezes utilizado em conjunto com diagramas deVoronoi, permitindo a este último método gerar ramos a partir das curvasiniciais e atingir mais locais do mapa.

A

B

Figura 2.8: Um caminho é planeado entre um ponto A e um ponto B utili-zando o algoritmo RRT [30]. Os círculos representam alguns pontos criadosaleatoriamente, enquanto quer as linhas retas representam os ramos criados.

O algoritmo RRT é um método simples, mas não permite encontraruma solução ótima. Para aproximar os resultados do ideal, foi propostarecentemente uma nova versão deste método: o algoritmo RRT* [31]. Estaversão reconecta os nós da árvore em zonas de menor custo de navegação,melhorando a solução ao longo do tempo. Esta variante apresenta melhoresresultados em ambientes estáticos e simples, mas em ambientes dinâmicos,o tempo de computação aumenta substancialmente, tendo um desempenhopior em relação ao RRT nessas situações.

2.5.2 PRM - Probabilistic Roadmap

Enquanto que o algoritmo RRT necessita normalmente de reconstruir a ár-vore para responder a necessidades de replaneamento, os PRMs podem serusados várias vezes para diferentes pontos inicial e final.

Os PRMs tentam ligar cada ponto a todos os pontos mais próximoscriados aleatoriamente (i.e. unindo cada ponto com todos os outros n pontosdentro de um raio r), ao contrário do que acontece no algoritmo RRT, emque cada ponto é unido apenas ao ponto mais próximo. Como existem várioscaminhos para unir os mesmos pontos, este algoritmo pode ser usado comsucesso para replanear um caminho diferente do original, a partir da mesmarepresentação do ambiente. Quanto maior o número de amostras, maior apossibilidade de um caminho ideal ser encontrado, devido à existência dediferentes soluções para navegar entre os mesmos pontos do mapa.


2.6 Algoritmos de busca

Em alguns dos métodos referidos anteriormente, como métodos que utilizamcampos potenciais e alguns métodos probabilísticos, um caminho é obtidodiretamente a partir do mapa original. Por outro lado, os métodos roadmap,os métodos de decomposição por células e os PRM, permitem criar umconjunto de caminhos possíveis através de pontos, curvas ou células querepresentam o espaço livre através de nós. A partir dessa representação doespaço livre, é necessário encontrar um conjunto de nós que unam o pontoinicial ao ponto final. Para que seja possível encontrar um conjunto de nósadjacentes que permita obter a melhor solução para diferentes situações, sãoutilizados algoritmos de busca.

Caso um grafo seja demasiado denso, o tempo de computação para en-contrar um caminho pode ser relativamente alto. Para atenuar este pro-blema, os nós percorridos são normalmente marcados como ”visitados”, oque permite que algoritmo se ”lembre” dos locais por onde passou, e, casoum nó seja revisitado, volte atrás e replaneie o seu caminho caso necessá-rio [32]. Alguns algoritmos utilizam também custos heurísticos. Estes custospermitem ao algoritmo ter em consideração a posição do nó inicial e/ou donó final durante o planeamento, possibilitando a obtenção de resultados maisotimizados.

Alguns dos algoritmos de busca mais conhecidos são o algoritmo de Dijsk-tra [33], o A* (A Star) [34] e o D* (D Star) [35]. Estes e outros algoritmos fo-ram criados com base em algoritmos mais antigos, como o Breadth-First [36],o Depth-First [36] ou o Best-First [36]. Estes métodos serão analisados nestecapítulo.

No algoritmo Breadth-First (BFS), a pesquisa começa no ponto iniciale os nós vizinhos são percorridos. Para cada um desses nós mais próxi-mos, os nós vizinhos que ainda não foram visitados são percorridos, e assimsucessivamente, até ser encontrado o nó final (ver figura 2.9).

No algoritmo Depth-First (DFS), à semelhança do que acontece no algo-ritmo Breadth-First, todos os nós do grafo são percorridos da mesma forma(sem custos heurísticos). A pesquisa começa num nó inicial e percorre tantoquanto possível cada um dos seus ramos. Caso o nó final não seja encon-trado no fim de um dos ramos, a pesquisa retrocede até um nó que tenhaum ramo que ainda não tenha sido percorrido (ver figura 2.10).

Estes algoritmos são simples de implementar e não precisam de muitasoperações matriciais, no entanto, têm algumas desvantagens: como o nófinal não é tido em consideração durante a pesquisa, existem muitos nóspercorridos desnecessariamente.

No algoritmo Best-First, por sua vez, são utilizados custos heurísticospara alcançar o nó final. Normalmente é estimada a distância entre os nósadjacentes ao nó atual e o nó final. O nó adjacente que estiver a uma menordistância em relação ao nó final será aquele a ser expandido. O processo


1

2 3

654

8 9 10 11

7

Figura 2.9: Busca Breadth-First. Os nós ocupados por obstáculos estão re-presentados a cinzento, enquanto os nós livres estão representados a branco.A busca inicia-se a partir do nó com o número 1. Os restantes númerosindicam a ordem segundo a qual os nós seriam percorridos usando este al-goritmo [36].

1

2 7

853

4 6 9 11

10

Figura 2.10: Busca Depth-First. Os nós ocupados por obstáculos estão re-presentados a cinzento, enquanto os nós livres estão representados a branco.A busca inicia-se a partir do nó com o número 1. Os restantes númerosindicam a ordem segundo a qual os nós seriam percorridos usando este al-goritmo [36].

repete-se até ser encontrado o nó final. À semelhança do Breadth-First, casoo nó final não seja encontrado no fim de um dos ramos, a pesquisa retrocedeaté um nó que tenha um ramo que ainda não tenha sido percorrido.

2.6.1 Algoritmo de Dijkstra

O algoritmo de Dijkstra é um tipo de algoritmo Breadth-First e é normal-mente utilizado em situações em que se pretende encontrar o caminho maiscurto entre o nó inicial e o nó final. Os custos neste algoritmo normalmentetêm em conta a distância entre nós adjacentes, no entanto, também podemser considerados outros aspetos. Nos casos em que se considera somente a


distância entre nós adjacentes, um nó que esteja perto do nó atual tem umcusto mais reduzido em relação a um nó que esteja mais afastado. Os nósque têm um custo inferior são percorridos em primeiro lugar. Depois sãopercorridos os nós com o segundo menor custo, e assim sucessivamente. Nofinal, é encontrado o caminho com menor custo até ao ponto final. Estealgoritmo é bastante eficiente em encontrar o caminho mais curto até aodestino, mas, tal como no algoritmo Breadth-First, o processo de planea-mento é pouco orientado ao nó final. Por este motivo, pode tornar-se umalgoritmo demasiado lento em ambientes de grandes dimensões.

O algoritmo de Dijkstra pode ser consultado no anexo A.1.

2.6.2 Algoritmo A*

O algoritmo A* é a escolha mais popular para o planeamento de caminhospois é bastante flexível, sendo conhecido pela sua performance e precisão deresultados [34]. Este algoritmo combina o melhor dos algoritmos de Dijkstrae Best-First sendo bastante fiável em diversas situações. Desde situaçõesem que se pretenda encontrar o caminho mais curto até situações em quese pretenda encontrar o caminho mais otimizado para determinado critérioestabelecido pelo utilizador (tempo, espaço de manobra, segurança, entreoutros).

Este algoritmo consegue obter bons resultados pois tem em conta duasinformações. A primeira baseia-se na distância entre o nó inicial e o nóatual, enquanto a segunda consiste no custo heurístico estimado entre o nóatual e o nó final. Este algoritmo é considerado como o mais eficiente emvárias situações, pois utiliza, simultaneamente, informação sobre a distânciaao nó inicial e ao nó final.

O algoritmo A* utiliza uma função de custo f(u) = g(u) + h(u), emque g(u) representa o custo exato do movimento entre um nó u e um nóadjacente a esse nó, e em que h(u) representa o custo heurístico estimadoentre um nó u e o nó que contém o ponto final. Se for definido que o valorde h(u) é sempre inferior ao custo do movimento entre o ponto atual e oponto final, o algoritmo vai sempre encontrar o caminho mais curto. Nolimite, quando h(u)=0, o algoritmo transforma-se no algoritmo de Dijkstraencontrando o caminho mais curto mas podendo expandir demasiados nós.Se for definido que o valor de h(u) pode ser superior ao custo do movimentoentre o ponto atual e o ponto final, não é garantido que o algoritmo encontreo caminho mais curto. No limite, quando o valor de h(u) é muito superiora g(u) o algoritmo transforma-se num algoritmo Best-First.

A capacidade deste algoritmo em alterar o seu comportamento de acordocom as funções heurísticas e de custo utilizadas pode ser bastante útil, poisintegra velocidade com precisão. Em várias situações não é obrigatório en-contrar o melhor caminho entre dois pontos, bastando encontrar um caminhoque se aproxime do ideal, enquanto que noutros casos, o caminho mais curto


é a solução procurada.Nos casos em que o ambiente está dividido em células do mesmo tama-

nho, para a função de custo g(u) são normalmente utilizados os valores 10e 14. Os valores usados estão relacionados com a distância entre célulasadjacentes (ver figura 2.11). Utilizando um custo de 10 para movimentoshorizontais ou verticais, e utilizando o teorema de Pitágoras, conclui-se queé adequado usar um custo de 14 para movimentos diagonais, pois a distânciareal para fazer um movimento na diagonal é 1,414 vezes superior à distân-cia para se fazer um movimento na vertical ou horizontal, de acordo com aseguinte equação:

d =√

102 + 102 = 14.14 ≈ 14 (2.4)

Figura 2.11: Custo normalmente associado ao deslocamento entre célulasadjacentes. Um movimento na diagonal implica um custo aproximadamente1.4 vezes superior a um movimento na horizontal ou vertical.

Para definir o valor a atribuir ao custo heurístico h(u), a distância entreo nó atual e o nó final pode ser estimada de diferentes formas. Para fazeressa estimativa utiliza-se normalmente uma de três funções: a distância deManhattan, a distância diagonal ou a distância euclidiana.

A distância de Manhattan é a forma mais usual de se obter o custoheurístico h(u) e é normalmente utilizada quando apenas é permitido haverum movimento em quatro direções. Esta distância consiste no número totalde células (independentemente da sua ocupação) que é necessário percor-rer para atingir a célula final, utilizando apenas movimentos horizontais everticais, de acordo com a seguinte equação:

h(u) = ∆x+ ∆y (2.5)

A distância diagonal (ou distância de Chebyshev) é, por sua vez, utilizadaquando o movimento pode ser feito em 8 direções, ou seja, quando sãopermitidos movimentos na diagonal:


h(u) = max(∆x+ ∆y) (2.6)

Por último, a distância euclidiana é utilizada quando o movimento podeser feito em qualquer direção. Trata-se da distância em linha reta entre oponto atual e o ponto final:

h(u) =√

(∆x)2 + (∆y)2 (2.7)

Durante a pesquisa, o algoritmo A* utiliza duas listas de nós: uma listaem aberto que contém os nós que ainda não foram verificados e uma listacom os nós que já foram visitados. O algoritmo expande consecutivamenteo nó da lista em aberto com o menor custo e adiciona os nós vizinhos à listaem aberto, inserindo depois o nó analisado na lista com os nós fechados. Oalgoritmo termina quando o nó final é encontrado.

A figura 2.12 mostra como uma busca A* se compara com uma buscarealizada com o algoritmo de Dijkstra. O algoritmo A* permite encontrarum caminho expandindo um número de nós bastante inferior ao algoritmode Dijkstra, desde que a distância à célula final seja bem estimada pelo custoheurístico utilizado.

(a) (b)

Figura 2.12: No exemplo da figura 2.12a estão representados os nós expan-didos e o caminho obtido para atingir o ponto final utilizando o algoritmode Dijkstra. No exemplo da figura 2.12b, por sua vez, estão representadosos nós expandidos e o caminho obtido para atingir o nó final utilizando oalgoritmo A*. Devido à utilização de custos heurísticos, o algoritmo A*consegue encontrar um caminho até ao nó final expandindo um número denós inferior em relação ao algoritmo de Dijkstra.

O algoritmo A* é utilizado pelo carro autónomo da Google para planearo seu percurso (ver figura 2.13). Além desse algoritmo de busca, é utilizadoum algoritmo de aprendizagem que aumenta a robustez do planeamento.Este carro autónomo obtém informação sobre o ambiente à sua volta atravésde mapas e de informação sensorial adquirida através de câmaras, sensores


laser e radares. Além disso, a sua localização atual no mapa é obtida atravésde GPS e encoders situados nas rodas [5].

Figura 2.13: Carro autónomo da Google. O planeamento do caminho a serpercorrido é feito usando o algoritmo A* em conjunto com um algoritmo deaprendizagem.

O algoritmo A* pode ser consultado no anexo A.2.

2.6.3 Algoritmos dinâmicos

Como muitas vezes existem alterações no ambiente (i.e. obstáculos móveis),o caminho para atingir o ponto final pode ter de ser alterado durante o mo-vimento do robô. Os algoritmos enunciados anteriormente nem sempre sãoos melhores para este tipo de casos, pois o tempo de processamento pode serdemasiado elevado, caso se tenha que replanear um caminho entre o pontoatual do robô e o ponto final sempre que uma alteração no ambiente é dete-tada. Além disso, o tempo que cada atualização do caminho demora a serrealizada, pode muitas vezes ser o suficiente para levar o robô a colidir comum obstáculo, quando utilizados alguns algoritmos de busca que necessitamde um tempo de processamento relativamente elevado. Caso necessário, osalgoritmos anteriormente referidos podem ser ligeiramente adaptados parareagir a obstáculos móveis com maior eficiência, ou então, podem ser utili-zados outros algoritmos de busca, como o D*.

O algoritmo D* foi implementado pela primeira vez em 1993 por AnthonyStentz, tendo o nome surgido a partir do termo ”Dynamic A*” [35]. Estealgoritmo é normalmente utilizado na exploração de terrenos desconhecidos,em situações que o robô encontra um obstáculo e tem de rapidamente re-planear o seu caminho. A utilização do D* é normalmente mais eficientedo que a utilização de várias pesquisas A* consecutivas, principalmente noscasos em que o ponto final não muda. A principal diferença em relação aoA* é o facto de a pesquisa começar a ser feita a partir do nó final em vezdo nó inicial. Além disso, quando ocorre um alteração no ambiente, apenasos nós situados na zona onde surgem as alterações são revisitados. Dessaforma, um caminho não é totalmente reconstruído de cada vez que existe


uma necessidade de replaneamento. Um dos pontos que o diferenciam doalgoritmo A*, é o facto de este não utilizar custos heurísticos.

O mesmo autor do algoritmo D* decidiu, alguns anos mais tarde, de-senvolver um algoritmo que apresentasse os mesmos resultados mas quereduzisse o tempo total para o replaneamento de um caminho e que utili-zasse custos heurísticos. Foi então criado o Focused D* [37]. Este algoritmocombina ideias do algoritmo A* e do algoritmo D* original.

Mais recentemente surgiu o D*Lite [38]. Este algoritmo caracteriza-sepor apresentar os mesmos resultados daqueles algoritmos que foram anteri-ormente propostos embora não seja baseado nos mesmos e, além de ser maisfácil de implementar, tem uma performance semelhante ou até melhor emrelação ao Focused D*. Este algoritmo tem sido usado nas mais diversasaplicações, sendo que a mais importante terá sido a sua inclusão no algo-ritmo Field D* que foi usado pelas sondas espaciais Opportunity e Spirit nassuas missões em Marte (ver figura 2.14). Este algoritmo permitiu às sondasserem mais autónomas e planearem caminhos em torno de obstáculos deuma forma mais rápida e eficiente [39].

Figura 2.14: Sonda ”Spirit” a navegar em solo marciano com a ajuda doalgoritmo Field D*.

Para explicar o funcionamento do algoritmo D* Lite é necessário em pri-meiro lugar analisar o algoritmo no qual foi baseado: o Lifelong PlanningA* (LPA*) [40]. O algoritmo LPA* comporta-se como o A* quando não hámudanças no ambiente. Quando ocorrem alterações no ambiente, o algo-ritmo encontra essas alterações detetando inconsistências entre nós. Estasinconsistências são detetadas utilizando, além dos valores g(s) e h(s), umnovo valor: o rhs(s) (”right hand side”). O rhs(s) é calculado somando ocusto do movimento entre um nó e o seu nó ”pai”, com o custo do movi-mento desde o nó inicial até esse nó ”pai”. Comparando o valor de g(s) como de rhs(s) é possível verificar se existem inconsistências. Na figura 2.15 estárepresentada uma situação normal em que existe caminho livre entre doisnós. Neste caso, os valores de g(s) e rhs(s) podem ser obtidos da seguinteforma:


g(s) = A+B (2.8)rhs(s) = g(s′) + c(s′, s) = A+B (2.9)

Como g(s) é igual a rhs(s) pode-se afirmar que os nós são localmenteconsistentes entre si.

g(s)=A+Bg(s')=A B

s' s

Figura 2.15: Custo do movimento entre nós adjacentes. Situação em queexiste caminho livre entre dois nós.

Na figura 2.16 está representada uma situação posterior em que um obs-táculo foi colocado entre os mesmos nós. Neste caso, os valores de g(s) erhs(s) podem ser obtidos da seguinte forma:

g(s) = A+B (2.10)rhs(s) = g(s′) + c(s′, s) = A+∞ =∞ (2.11)

Como g(s) é diferente de rhs(s) pode-se afirmar que os nós são localmenteinconsistentes entre si.

g(s)=A+Bg(s')=A ∞

s' s

obstáculo

Figura 2.16: Custo do movimento entre nós adjacentes. Situação em quedeixa de existir caminho livre entre dois nós.

Existem portanto dois tipos de inconsistências. Se g(s) < rhs(s), entãoo custo do movimento para o nó s aumentou devido à presença de um novoobstáculo. Por outro lado, caso se verifique que g(s) > rhs(s), então o custodo movimento para o nó s diminuiu devido, por exemplo, a um obstáculoque se moveu para uma nova posição.

Além dos valores g(s), h(s) e rhs(s), cada nó contém também o vetorkey(s). Esta ”chave” é usada para ordenar a lista com os nós em aberto e écalculada da seguinte forma:

key(s) = [α;β] = [min(g(s), rhs(s) + h(s));min(g(s), rhs(s))] (2.12)

A lista é ordenada de acordo com os valores de α. O nó com o valor deα mais baixo aparece em primeiro lugar na lista de nós em aberto. Quando


dois nós têm o mesmo valor α, a comparação entre as chaves desses dois nósé feita comparando os seus valores β da mesma forma.

A figura 2.17 mostra o conteúdo de cada nó quando usado o algoritmoLPA*. A lista ”Chidren[ ]” contém os nós que podem ser alcançados a partirdo nó s, enquanto que a lista ’Parents[ ]’ contém os nós a partir dos quais épossível avançar para o nó s.

g(s)

s

h(s)rhs(s)key(s)

Children[]Parents[]

Figura 2.17: Informação armazenada por cada nó quando usado o LPA*.

Este algoritmo é apenas eficaz em situações em que o nó inicial e o nófinal não mudam, não sendo por isso o ideal para lidar com mudanças noambiente ao mesmo tempo que um robô se desloca.

O algoritmo LPA* pode ser consultado no anexo A.3.Baseando-se no LPA*, o algoritmo D* Lite acrescenta a cada nó um novo

valor (km) para ter em consideração o caminho já percorrido. Este valor -que é alterado durante o movimento do robô - é também usado para calculara chave de cada nó. Essa chave passa a ser dada pela seguinte equação:

key(s) = [α;β] = [min(g(s), rhs(s) + h(sstart)) + km;min(g(s), rhs(s))](2.13)

Quando o robô se move, o valor km é aumentado de acordo com a dife-rença nos custos heurísticos entre a posição atual e anterior do robô. Comoo valor km está constantemente em mudança, sempre que um nó é analisado,a chave de um nó pode ser diferente daquela que o nó continha quando foiinserido na lista com os nós em aberto. Se a chave anterior for maior quea atual, o nó é inserido na lista, o que permite que os nós estejam semprecorretamente ordenados na lista em aberto.

O algoritmo D* Lite pode ser consultado no anexo A.4.Todas estas variantes de algoritmos dinâmicos têm sido usadas na ro-

bótica móvel, sendo que o algoritmo D* Lite é atualmente a variante maisusada devido à sua maior simplicidade de implementação em relação aosoutros algoritmos.

2.7 Métodos locaisOs métodos locais são métodos reativos, normalmente usados em ambientesdinâmicos e desconhecidos. Estes métodos não necessitam de um conheci-mento prévio do ambiente, utilizando a informação sensorial do robô para


detetar obstáculos e mudar a direção de navegação em tempo real. Por estemotivo, estes métodos podem ser bastante ineficientes em ambientes com-plexos. Os algoritmos Bug e o método dos atratores dinâmicos são dois tiposde métodos locais.

2.7.1 Algoritmos Bug

Os algoritmos Bug utilizam os sensores dos robôs para detetarem os obstácu-los mais próximos, enquanto o robô se desloca num ambiente desconhecido.Neste tipo de algoritmos existem apenas dois comportamentos básicos: an-dar em linha reta em direção ao alvo e contornar obstáculos. Os algoritmosBug são bastante usados na robótica móvel por serem simples e intuitivos,sendo que existem bastantes variantes. Os algoritmos Bug1 [41], Bug2 [41],e Tangent Bug [42] são as variantes mais comuns.

No algoritmo Bug1, o robô segue em direção ao alvo até que um obstá-culo seja detetado. Quando isto acontece, o obstáculo é contornado na suatotalidade e o ponto do obstáculo com uma menor distância ao ponto finalé memorizado. O algoritmo volta então a esse ponto e dirige-se novamenteao alvo, repetindo o mesmo processo caso outros obstáculo sejam detetados(ver figura 2.18a). No algoritmo Bug2, por sua vez, o robô segue uma linhareta que une o ponto inicial ao ponto final, normalmente denominada comom-line. Sempre que um obstáculo é encontrado, o robô contorna esse obstá-culo até encontrar um novo ponto da retam-line, seguindo depois novamenteessa reta até ao próximo obstáculo ou o ponto final serem encontrados (verfigura 2.18b). Se o robô encontra o mesmo ponto da reta depois de contornarum obstáculo, então não existe um caminho válido.

O algoritmo Bug1 faz uma busca mais exaustiva, procurando encontrara melhor solução antes de avançar. Por outro lado, o algoritmo Bug2 segueo caminho mais previsível sem procurar a existência de melhores soluções.

A

B

(a)

A

B

(b)

Figura 2.18: Um robô percorre um caminho entre um ponto A e um ponto Butilizando os algoritmos Bug1 e Bug2 [41]. Em 2.18a foi utilizado o algoritmoBug1, enquanto que em 2.18b foi utilizado o algoritmo Bug2.

O algoritmo Tangent Bug é baseado no Bug2 e é usado por robôs queutilizam os seus sensores para captar informação em todas as direções sobre


o ambiente à sua volta. Neste algoritmo, o robô deteta os vértices dos obstá-culos analisando descontinuidades nas leituras desses sensores. Por exemplo,um vértice é encontrado quando uma obstrução é detetada pelos sensoresnum instante e deixa de ser detetada no instante seguinte. O algoritmo ana-lisa a distância do robô ao ponto final e a distância de cada vértice detetadoao ponto final. Depois, analisa cada um desses vértices e calcula a distân-cia dmin. Esta distância representa a menor distância entre um vértice eo ponto final. Sempre que um novo vértice é detetado com uma distânciadmin inferior à distância entre o alvo e o ponto final, o robô segue em direçãoa esse vértice. Por outro lado, caso não existam vértices nessas condiçõeso robô segue em linha reta em direção ao ponto final. A figura 2.19 mos-tra um robô a navegar num ambiente usando o algoritmo Tangent Bug. Orobô inicialmente navega em direção ao ponto final, mas quando encontrao primeiro obstáculo segue na direção do vértice detetado mais próximo doalvo. Depois de contornar esse obstáculo navega novamente em direção aoalvo e o processo repete-se nos dois alvos seguintes. Este algoritmo consegueencontrar um caminho bastante mais próximo do ideal em comparação comos algoritmos Bug1 e Bug2.

A

B

Figura 2.19: Um robô percorre um caminho entre um ponto A e um pontoB utilizando o algoritmo Tangent Bug [42]. Os círculos representam o raioem torno do robô no qual é possível detetar obstáculos.

Apesar de bastante simples, estes algoritmos garantem que uma soluçãoseja encontrada sempre que um caminho válido entre o ponto inicial e oponto final realmente exista.

2.7.2 Atratores dinâmicos

Outro método que pode ser utilizado para um planeamento de caminhoslocal é o método dos atratores dinâmicos [43]. Neste método, o robô descreveo seu caminho com a ajuda da informação sensorial obtida ao longo dopercurso que lhe permite gerar um atrator na direção do alvo e repulsoresna direção dos obstáculos.


O controlo do movimento do robô é feito através da utilização de sistemasdinâmicos não lineares. O comportamento que este movimento representapode ser descrito e estruturado pela direção de navegação φ, em relação aum referencial externo, sendo essa direção uma variável comportamental. Nafigura 2.20, ψalvo representa a direção segundo a qual o alvo é visto a partirda posição atual do robô, enquanto que ψobs representa a direção segundoa qual o obstáculo está posicionado em relação ao robô. Dessa forma, ψalvo

especifica o valor desejado para a direção de navegação, enquanto que ψobs

especifica um valor que deve ser evitado.

alvo

x

obstáculo

robô

��

�

��

Figura 2.20: Exemplo de um robô que tenta mover-se para um alvo numambiente em que existe um obstáculo. O robô deve evitar a direção ψobs eprocurar a direção ψalvo, que são, respetivamente, a direção em que está oobstáculo e a direção em que está o alvo [43].

Ao longo do movimento do robô, são gerados continuamente valores paraa direção de navegação φ(t), através de um sistema dinâmico formuladocomo uma equação diferencial, em que a variável de estado é a direção denavegação do robô:

dφ

(dt) = f(φ) = falvo(φ) + fobs(φ) (2.14)

Um conjunto de forças aditivas constroem o campo vetorial do sistemadinâmico. Cada uma dessas forças especifica um valor desejado para a di-reção de navegação (ψalvo ou ψobs), a intensidade de atração e repulsão, etambém, a gama de valores da direção de navegação sobre os quais a forçaexerce o seu efeito.

Cada força constrói um atrator (estado assimptoticamente estável) ouum repulsor (estado instável) na dinâmica da direção de navegação. Umsistema dinâmico é obtido a partir da força atrativa que atrai o sistemapara o valor desejado (direção do alvo), e da força repulsiva que evita que osistema tome valores indesejados (direção dos obstáculos).

O sistema é sintonizado por forma a que a direção de navegação estejasempre num ou perto de um atrator da dinâmica resultante. Como as dire-


ções dos obstáculos e do alvo em relação ao robô variam à medida que estese move, o atrator resultante desloca-se arrastando a direção de navegaçãoφ.

O robô contém sensores em torno de si que permitem medir a distânciaem relação a obstáculos em várias direções. Cada sensor de distância apontanuma direção fixa θi, em relação à direção de navegação do robô. Dessaforma, cada sensor aponta numa direção ψi = φ+ θi em relação ao eixo dereferência externo.

Cada obstáculo detetado por um sensor é representado por uma forçarepulsiva centrada na direção em que o respetivo sensor aponta:

fobs,i(φ) = λi(φ− ψi) exp −(φ− ψi)2

2σ2i

(2.15)

Em que λi representa a magnitude da força de repulsão exercida peloobstáculo na direção ψi. Esta magnitude decresce com o aumento da dis-tância di medida pelo sensor i. A função para a magnitude da força derepulsão é então dada por:

λi = β1−di

β2(2.16)

Nesta equação, β1 controla a magnitude máxima da força de repulsãoe β2 representa a taxa de decaimento com o aumento da distância. Destaforma, é possível definir uma distância mínima em relação a um obstáculoa partir da qual a força repulsiva é nula.

A gama angular σi sobre a qual uma força repulsiva exerce o seu efeito,depende do ângulo de sensibilidade do sensor ∆θ e da distância medida di,de acordo com a seguinte equação:

σi = arctan(

tan(∆θ

2)

+ RrobôRrobô + di

)(2.17)

Para obter a dinâmica comportamental final para evitar dos obstáculos,as contribuições de todos os sensores são somadas:

dφ

dt= fobs(φ) =

n∑i=1

fobs,i(φ) (2.18)

Por outro lado, para dotar o robô com a capacidade de se mover nadireção do alvo, assume-se que as coordenadas do alvo (xalvo,yalvo) são co-nhecidas. A direção ψalvo em que o robô vê o alvo a partir da sua posição édada por:

ψalvo = arctan(yalvo − yrobôxalvo − xrobô

)(2.19)


Para orientar o robô na direção do alvo é construído um atrator nadireção ψalvo com uma intensidade λalvo. A equação que representa estaforça atrativa é a seguinte:

dφ

dt= falvo(φ) = −λalvo sin(φ− ψalvo) (2.20)

Para garantir que o robô não fica preso na direção de um repulsor duranteum tempo limite, é também usada uma força estocástica:

fstoch =√Qξn (2.21)

Essa força é calculada a partir de ruído branco Gaussiano, ξn, de vari-ância unitária, enquanto que Q é a variância efetiva da força estocástica.

Finalmente, para se obter o sistema dinâmico total, a força estocásticasoma-se às contribuições dos comportamentos de atração e repulsão:

dφ

dt= falvo(ψ) +

n∑i=1

fobs,i(ψ) + fstoch (2.22)

Além da velocidade angular, também a velocidade de translação, v, deveser ajustada de acordo com a informação sensorial obtida pelo robô. O sis-tema dinâmico da equação seguinte permite obter a velocidade mais indicadapara o robô:

dv

dt= −cobs(v − Vobs) exp

(−(v − Vobs)2

2σ2v

)

−calvo(v − Valvo) exp(−(v − Valvo)2

2σ2v

) (2.23)

Nessa equação, os dois termos do campo vetorial constroem duas forçasatrativas que atraem o robô para os valores Vobs e Valvo, com intensidadesde atração cobs e calvo, respetivamente.

A figura 2.21 apresenta um exemplo em que a direção de navegação deum robô é definida a partir da soma de uma força aditiva com uma forçarepulsiva. A força aditiva constrói um atrator na direção do alvo. Esteatrator é um zero de dφ/dt com declive negativo. Por sua vez, a forçarepulsiva constrói um repulsor na direção do obstáculo, sendo este repulsorum zero de dφ/dt com declive positivo. A sobreposição das duas forçasconstrói o atrator resultante que indica a direção que o robô deve tomarpara se dirigir ao alvo sem colidir com obstáculos.


��

d�/dt

�2ππ

(a) Força atrativa.

�obs

d�/dt

�2ππ

(b) Força repulsiva.

d�/dt

�2ππ

atrator

(c) Força resultante.

Figura 2.21: Em 2.21a está representada a força atrativa que gera um atratorna direção do alvo, ψalvo. Em 2.21b está representada a força repulsiva quegera um repulsor na direção do obstáculo, ψalvo. Finalmente, em 2.21c estárepresentada a força que resulta da sobreposição das duas forças anteriores.

2.8 Múltiplos robôs

O problema do planeamento de caminhos para múltiplos robôs é bastantemais complicado do que o planeamento de caminhos para um só robô, umavez que a complexidade do problema sobe com o aumento do número derobôs. Por este motivo, as soluções encontradas no planeamento para umúnico robô podem nem sempre ser aplicadas diretamente nalguns tipos deproblemas.

Neste tipo de problemas existem uma série de robôs com uma localizaçãoinicial e uma localização final definidas. O objetivo é determinar o caminhoque cada um deve escolher para atingir a sua localização final, enquanto


evita o contacto com os obstáculos e com outros robôs. Ao mesmo tempo,devem ser otimizados alguns critérios para cada robô, tais como a distânciatotal percorrida e o tempo para atingir a localização final.

Os métodos usados no planeamento de caminhos para múltiplos robôsenvolvem normalmente algum tipo de comunicação entre os vários robôs, demodo a permitir a cada um deles trocar informação sobre o seu estado esobre o ambiente à sua volta.

Nas últimas décadas têm sido propostos vários algoritmos para resolverproblemas relacionados com o planeamento de caminhos para vários robôsa operar no mesmo ambiente em simultâneo. Além de alguns métodos bási-cos, os algoritmos são normalmente divididos em duas categorias de acordocom a forma como os caminhos são gerados: planeamento descentralizadoe planeamento centralizado [44] [45]. Alguns destes métodos serão tratadosnos próximos subcapítulos.

2.8.1 Métodos básicos

Nos métodos mais simples, os robôs não tem qualquer tipo de conhecimentosobre as intenções dos outros robôs limitando-se a serem reativos ou a seguirregras predefinidas.

Cocktail party

Neste tipo de métodos não existe qualquer tipo de comunicação entre robôs[46]. Cada robô tem apenas a sua própria visão do ambiente e a localizaçãofinal que pretende atingir, enquanto que os outros robôs são vistos comoobstáculos desconhecidos. Como não há coordenação direta entre robôs,existem algumas situações onde os robôs podem não conseguir seguir umcaminho até ao seu ponto final (por exemplo quando dois robôs se movem emdireções opostas num corredor estreito). Este tipo de algoritmos é bastanteincompleto mas é muito popular devido à sua simplicidade, escalabilidade epela não necessidade de comunicação entre robôs.

Regras de trânsito

Tal como no método anterior, neste método os robôs não comunicam entresi. Neste caso, estes limitam-se a seguir regras semelhantes às que os au-tomobilistas têm que obedecer nas estradas [47]. Cada robô conhece a suaposição atual, a informação que adquire sobre o ambiente através dos seussensores e um mapa com a informação global sobre o ambiente. Os robôsdevem ser capazes de conhecer cada regra e de detetar todas as informaçõesnecessárias. Por exemplo, os robôs devem compreender que é necessário pa-rar quando existe um semáforo com a luz vermelha ligada e que devem darprioridade aos robôs que surgem à sua direita num cruzamento. As regrasdevem ser bastante simples e bem distribuídas pelo ambiente que se assume


como sendo relativamente estático e bem definido. A existência destas re-gras impede muitas vezes que um caminho ótimo seja gerado, na medida emque, por exemplo, um robô está impedido de se mover em sentido contrárionuma ”rua” de sentido único. O desafio neste tipo de métodos é criar regrasque se adequem da melhor forma ao ambiente em questão.

2.8.2 Planeamento descentralizado

Os algoritmos baseados num planeamento descentralizado são essenciais emambientes dinâmicos e com um elevado número de robôs. Neste tipo de pla-neamento, cada robô constrói um caminho no seu próprio espaço de configu-ração e adota algumas estratégias para adaptar o seu caminho ao dos outrosrobôs e evitar colisões [48] [49] [50]. Muitas estratégias têm sido desenvol-vidas para permitir a navegação de vários robôs em simultâneo utilizandoum planeamento descentralizado, sendo que essas estratégias são normal-mente divididas em duas categorias: planeamento priorizado e coordenaçãodo movimento.

Planeamento priorizado

No planeamento priorizado, o robô com maior prioridade planeia e percorreo seu caminho sem ter em consideração os outros robôs. Os robôs com menorprioridade, por sua vez, planeiam os seus caminhos podendo ou não trataros robôs com maior prioridade como obstáculos móveis. Esses caminhos sãoobtidos utilizando um, entre os vários métodos de planeamento de caminhosabordados anteriormente. Cada robô conhece o percurso dos robôs commaior prioridade e recebe informação constante sobre a posição atual dessesrobôs. Analisando essa informação, sempre que existe uma possibilidade decolisão com um robô com maior prioridade, o robô com menor prioridadefacilita a passagem a esse robô [51]. Os caminhos percorridos pelos robôscom maior prioridade podem ser ótimos (ou praticamente), enquanto que osrobôs com menor prioridade podem apresentar soluções longe do ideal.

A ordem de prioridades dos robôs podem ser atribuídas a priori ou jádurante o planeamento dos primeiros robôs. Essa ordem pode ser determi-nada de diversas formas, tais como: aleatoriamente, pela ordem de partidade cada robô ou de acordo com a tarefa que cada um vai realizar.

O planeamento priorizado apresenta muitas vezes soluções incompletas esub-ótimas. A ordem segundo a qual os caminhos são planeados tem grandeinfluência na maneira como pode ser resolvido um problema e no tamanhodas trajetórias. Isto pode levar à necessidade de encontrar um esquema deprioridades em que o planeamento não falhe e em que a ordem dos robôsleve aos caminhos mais curtos.

A figura 2.22 demonstra a importância da atribuição de prioridades acada robô. Nesse exemplo, o robô 1 precisa de ter uma prioridade maior


em relação ao robô 2, para cada um possa atingir a sua localização final.Uma solução poderia ser encontrada, caso a prioridade dos robôs fosse al-terada dinamicamente de acordo com a quantidade de obstáculos em tornode cada um deles, ou seja, o robô com uma maior quantidade de obstáculosà sua volta teria uma prioridade maior em relação a outro robô com menosobstáculos em torno de si.

robô1

robô2

Figura 2.22: Planeamento priorizado - Situação em que a ordem de priori-dades é muito importante. As setas representam o caminho que cada robôpretende percorrer.

Coordenação do movimento

No planeamento descentralizado baseado na coordenação do movimento, ocaminho de cada robô é gerado em primeiro lugar sem ter em consideraçãoo posicionamento ou comportamento dos outros robôs. Depois disso, é defi-nida a velocidade que cada robô deve ter ao longo da sua trajetória para seassegurar que não existam colisões, ou seja, o caminho originalmente obtidonão é alterado, mas sim a velocidade que o robô deve ter em cada pontodesse caminho. Este método é utilizado normalmente em robôs que têm umtrajeto fixo e que não necessitam de fazer desvios em relação a esse trajeto.Por isso mesmo, a coordenação de movimento perde eficiência em ambientesdinâmicos, uma vez que, nesses ambientes, os robô podem ser forçados arealizar uma série de desvios em relação à trajetória planeada. A coordena-ção de caminhos é muitas vezes considerada como sendo um método maiscompleto em relação ao Cocktail Party, regras de trânsito e planeamentopriorizado.

Apesar de normalmente não produzirem caminhos ótimos em termosde distância e tempo, ambas estas técnicas de planeamento descentralizadopermitem solucionar a maioria dos problemas. No entanto, existem algumassituações em que estas técnicas podem não encontrar uma solução. Na fi-gura 2.23 está representada uma dessas situações. Dois robôs num corredorestreito pretendem trocar de posição entre si. Como o corredor é demasi-ado estreito para possibilitar a passagem de dois robôs em simultâneo, oespaço livre à direita teria de ser utilizado para permitir a troca de posições.As técnicas de planeamento descentralizado dificilmente possibilitariam essatroca. Para uma solução ser possível neste caso, outros tipos de planeamento


teriam de ser utilizados nestas zonas especiais, ou então, para além do pla-neamento descentralizado, teriam de ser estabelecidas algumas regras pararesolver estes casos particulares. Por exemplo, nesta situação poder-se-iaproibir a entrada de um robô no corredor caso este já estivesse ocupado.

robô1

robô1

robô2

robô 2

(a) Configuração inicial.

robô2

robô robô1

robô 2

(b) Configuração final.

Figura 2.23: Dois robôs num corredor estreito pretendem trocar de posição.

2.8.3 Planeamento centralizado

Os algoritmos baseados num planeamento centralizado consideram o con-junto de robôs como uma equipa, sendo o planeamento do caminho de todosos robôs feito em simultâneo. Neste tipo de planeamento, os robôs são con-siderados como pedaços de um único robô e os caminhos são construídos apartir do espaço de configuração resultante [52]. Por este motivo, o tamanhodo espaço de estados sobe exponencialmente com o aumento do número derobôs e, como consequência, sobe também o tempo necessário para que umasolução seja encontrada. Os algoritmos baseados num planeamento centrali-zado garantem, normalmente, um caminho final otimizado caso o ambienteseja estático e simples, e o número de robôs seja relativamente pequeno.Em ambientes mais dinâmicos e/ou com um número relativamente alto derobôs, é aconselhável o uso de outras abordagens, tal como o planeamentodescentralizado abordado anteriormente.

2.9 Discussão do estado de arte

Os métodos que necessitam de um modelo do ambiente são normalmenteaqueles que permitem obter soluções mais próximas do ideal, uma vez quedividem o mapa original num conjunto de caminhos, e a partir desse con-junto, um caminho otimizado pode ser encontrado de acordo com os resul-tados pretendidos. Um exemplo disso é a utilização de algoritmos de buscaa partir de métodos roadmap ou de decomposição por células. Este tipo demétodos podem ser classificados como determinísticos, no sentido em queapresentam sempre os mesmos resultados a partir das mesmas condiçõesiniciais.


Os métodos de decomposição por células apresentam a vantagem de nãoterem restrições em relação à forma dos obstáculos, ao contrário do queacontece nos métodos roadmap. A utilização de um tamanho de células fixopara representar o ambiente é uma das metodologias mais usadas na robóticae em jogos de computador. Este método apresenta várias vantagens como asua simplicidade de implementação e a fácil atualização do mapa em caso dealterações no ambiente. A principal desvantagem é que a representação dosobstáculos é, normalmente, menos precisa em relação ao que acontece comoutros métodos. Existem vários algoritmos de busca para gerar caminhosa partir dessa ou de outras representações do ambiente. O algoritmo deDijkstra permite encontrar o caminho mais curto entre dois pontos, masnão é orientado à célula final e por isso necessita de um maior tempo deprocessamento em relação a outros algoritmos. O algoritmo A* utiliza custosheurísticos para estimar a distância à célula final e é um dos algoritmos debusca mais utilizados devido à sua simplicidade e eficiência. Os algoritmosdinâmicos, por sua vez, adaptam-se normalmente de uma melhor forma aambientes dinâmicos, sendo que o algoritmo D* Lite é um dos mais utilizadosdentro desta vertente.

Devido às vantagens enunciadas anteriormente, o método aproximadode decomposição por células foi o selecionado para representar o ambientenos testes realizados nesta dissertação. Para encontrar um caminho a partirdessa representação do ambiente, serão analisados com maior detalhe algunsalgoritmos de busca, de forma a selecionar o melhor para ser usado nosambientes em estudo nesta dissertação.

Ao contrário dos algoritmos de busca, os campos potenciais e os métodosprobabilísticos normalmente utilizam o mapa original como representação doambiente. No entanto, em alguns casos, estes dois métodos são usados a par-tir de diagramas de Voronoi. A principal desvantagem do primeiro métodoé a possibilidade de existirem mínimos locais onde o robô fique preso. Noentanto, novas variantes como o Fast Marching vieram reduzir ou até elimi-nar este problema. Os métodos probabilísticos, por sua vez, podem produzirdiferentes soluções a partir das mesmas condições iniciais. Estes métodospermitem obter resultados rápidos em situações complexas e são muito uti-lizados em situações em que é necessário obter soluções quase instantâneas.A principal desvantagem é que as soluções apresentadas normalmente nãosão as ideais, devido à aleatoriedade existente durante o planeamento.

Os métodos locais são normalmente usados quando o robô desconhecetotalmente o ambiente à sua volta. Os algoritmos Bug e o método dosatratores dinâmicos são exemplos de métodos locais, embora sejam muitodistintos entre si. Os primeiros baseiam-se em dois comportamentos base:seguir em frente e contornar os obstáculos. O método dos atratores dinâmi-cos, por sua vez, alteram a direção de navegação do robô em tempo real deacordo com uma força atrativa criada na direção do alvo e forças repulsivascriadas na direção dos obstáculos.


Estes tipo de métodos podem ser usados em conjunto com um planeadorglobal em ambientes inicialmente conhecidos, mas onde exista a possibilidadede surgirem novos obstáculos no caminho do robô, tal como acontece nosambientes em estudo nesta dissertação. Além disso, os métodos locais podemser utilizados para permitir ao robô navegar entre os pontos do caminhoplaneado. Por estes motivos, foi decidido utilizar o método dos atratoresdinâmicos em conjunto com o planeamento global selecionado nos testesrealizados.

Para que uma grande quantidade de robôs possa navegar em simultâneono mesmo ambiente, os robôs podem ou não utilizar comunicação entre si.Nos casos em que não existe comunicação, os métodos Cocktail Party e ométodo das regras de trânsito podem ser considerados. Nos casos em queexiste comunicação, pode ser utilizado um planeamento descentralizado ouum planeamento centralizado. O primeiro é indicado para lidar com vá-rios robôs em ambientes dinâmicos, enquanto que o segundo é normalmenteutilizado com um número de robôs relativamente pequeno em ambientessimples.

Como o ambiente em estudo nesta dissertação é composto por umagrande quantidade de robôs e obstáculos móveis, será testada a utilizaçãode um planeamento descentralizado, além de alguns métodos mais simples.


Capítulo 3

Implementação

Neste capítulo são abordadas as ferramentas de simulação utilizadas paratestar o comportamento dos robôs nas mais diversas situações. Além disso,também é referida a forma como foram implementadas algumas das meto-dologias analisadas e selecionadas no capítulo anterior.

3.1 Ferramenta de simulação

Depois de analisados os diferentes algoritmos, é necessário implementá-lose compará-los entre si. Isto pode ser feito recorrendo a robôs reais. Noentanto, o esforço despendido a preparar um robô e a construir diferentescenários experimentais pode ser bastante elevado. A dificuldade em conse-guir o número de robôs necessário para testes em alguns cenários multi-robôé também uma desvantagem. Por estes motivos, é muitas vezes recomendá-vel utilizar ferramentas de simulação para testar o comportamento de robôsmóveis com os diferentes algoritmos nas mais diversas situações.

As ferramentas de simulação possibilitam que os algoritmos sejam tes-tados várias vezes e nos mais diversos ambientes. Além disso, várias dessasferramentas permitem que o código usado nas simulações para controlar osrobôs seja bastante semelhante ao que seria usado em cenários reais.

Existem diversas ferramentas de simulação para robôs móveis autóno-mos, tais como o ARIA/MobileSim [53], o Webots [54] ou o Player/Stage[55]. De seguida será feita uma introdução à ferramenta utilizada nestadissertação: o Player/Stage.

O Player/Stage é um projeto open source, que está em constante desen-volvimento para se adaptar a diferentes plataformas robóticas e a diferentessensores e atuadores. Como se trata de uma ferramenta bastante versátil,podendo ser facilmente programada, é regularmente utilizada e modificadapor investigadores de todo o mundo.

Esta ferramenta é compatível com diversas linguagens de programação,como C/C++ ou JAVA, e disponibiliza algoritmos para navegação com des-

39

CAPÍTULO 3. IMPLEMENTAÇÃO 40

vio de obstáculos, planeamento de caminhos, localização, mapeamento, entreoutros.

O Player funciona como um servidor. Este servidor permite a interaçãocom os sensores e atuadores de robôs de uma maneira simples através deum rede IP. Um cliente ”fala” com o Player através de sockets TCP quepermitem a leitura de dados dos sensores, a escrita de comandos para osatuadores e a configuração de dispositivos em tempo real.

O Stage, por sua vez, permite a utilização de uma ambiente virtualpovoado por robôs móveis, e por vários objetos e sensores que os robôspodem utilizar e manipular. Este simulador permite criar e alterar ambientesa duas dimensões. O Stage foi desenvolvido para possibilitar o estudo dosmais diversos sistemas autónomos fornecendo modelos simples de um grandenúmero de dispositivos em vez de tentar imitar cada dispositivo na perfeição.Isto permite aos utilizadores alternarem entre um controlo de um robô reale de um robô virtual de uma forma realista e suficientemente rápida parasimular grandes populações. O Player acede aos dispositivos de hardwaredo Stage da mesma forma que acederia aos dispositivos de hardware de umrobô real. Devido à grande eficiência do Stage, podem ser simulados dezenasde robôs em simultâneo com um comportamento semelhante aos robôs reaisnos quais são baseados. Na figura 3.1 está representado um diagrama deblocos simples da estrutura Player/Stage. Cada dispositivo de hardware dorobô é subscrito como cliente através de proxies. O código desenvolvidopelo utilizador deve permitir a ligação ao servidor Player de modo a queeste possa aceder aos proxies que controlam o robô.

Simulação

Drivers

Código

ProxiesPlayer

Stage

Figura 3.1: Modelo cliente/servidor do Player/Stage quando usado comosimulador. Podem existir diversos proxies ligados simultaneamente ao ser-vidor.

Um dos robôs móveis que é possível controlar através do Player/Stage éo Pioneer 2DX (ver figura 3.2). Este robô é um dos mais populares e maisutilizados na robótica devido à sua versatilidade, fiabilidade e durabilidade.


O Pioneer 2DX tem 0.44m de comprimento, 0.38m de largura e 0.22m dealtura. Este robô consegue atingir velocidades até 1.6 m/s e transportarcargas até 23 kg. Nas simulações realizadas, este robô é capaz de obterinformações como a sua posição no espaço (x, y, θ) através do seu sistemade odometria, bem como obter informações sobre o ambiente à sua voltaatravés de sensores de distância e uma câmara de deteção de cores.

(a) (b)

Figura 3.2: À esquerda está representado o robô Pioneer 2DX e à direita oseu modelo equivalente no Player/Stage.

Para medir a distância em relação aos obstáculos à sua volta, o Pioneer2DX utiliza 16 sonares (8 na parte frontal e 8 na parte traseira). O ânguloentre dois sonares consecutivos é de 20◦, à exceção dos quatro sonares lateraiscujo ângulo entre si é de 40◦. Estes sonares são capazes de detetar objetosa uma distância superior a 10 cm e inferior a 5 m. A figura 3.3 mostra aforma como os sensores estão organizados na parte frontal do robô.

90º

50º

30º10º-10º

-30º

-50º

-90º

Figura 3.3: Sonares frontais do Pioneer 2DX.

Além dos sonares, este robô também é capaz de detetar a distância aosobstáculos utilizando um laser. Este laser deteta obstáculos num ângulo de180o com uma resolução angular de 0.5o e, nos testes realizados, foi utilizadauma distância máxima de deteção de 2m. A figura 3.4 demonstra a formacomo novos obstáculos são detetados pelo laser do robô.

As coordenadas x e y, medidas em relação à posição do robô, de cadaobstáculo detetado, calculam-se usando a distância d entre o sensor e oobstáculo, e o ângulo α, que representa a direção em que o obstáculo édetetado. Essas informações são fornecidas pelo laser a cada instante:


α

d y

xRobô

Obstáculo

Figura 3.4: Deteção da posição de um obstáculo através de um laser.

x = d ∗ cos(α) (3.1)

y = d ∗ sin(α) (3.2)

Para obter a posição exata do obstáculo no mapa, as coordenadas calcu-ladas anteriormente são somadas às coordenadas que representam a posiçãoatual do robô:

xobstáculo = x+ xrobô (3.3)

yobstáculo = y + yrobô (3.4)

Outra forma de detetar obstáculos, é utilizando a câmara de deteçãode cores. Esta câmara permite detetar um conjunto de cores especificadaspelo utilizador, sendo particularmente útil para distinguir obstáculos entresi. Quando um ou mais obstáculos com uma cor conhecida são detetados, acâmara fornece informações sobre o número de objetos detetados e a locali-zação de cada um. Essa localização permite perceber facilmente a distânciaa que o obstáculo se encontra do robô que o deteta, bem como o seu des-locamento horizontal (ver figura 3.5). Isto também é útil para determinarse um determinado objeto se está a aproximar ou a afastar, bem como paradeterminar o sentido em que se move em relação ao robô que o deteta. Paradeterminar se um determinado obstáculo se está a afastar ou a aproximar,é analisada a sua altura na visão fornecida pela câmara. Caso essa alturabaixe num instante em relação ao instante anterior, considera-se que existiuum afastamento do obstáculo. Por outro lado, caso essa altura aumente,considera-se que existiu um aproximação. Para determinar o sentido emque um obstáculo se move em relação ao robô que o deteta, é analisado oseu deslocamento horizontal na imagem. Dessa forma é possível determinarse o obstáculo se move da esquerda para a direita, da direita para a esquerdaou se mantém a mesma direção em relação ao robô que o deteta.

A figura 3.6 mostra um ambiente de simulação criado no Stage, em queo robô Pioneer 2DX navega entre obstáculos.


Distância

Posição

Figura 3.5: Deteção de um obstáculo através da câmara de deteção de cores.A distância a que o obstáculo se encontra pode ser obtida através da análiseda sua altura na imagem fornecida pela câmara, enquanto que a sua posiçãopode ser estimada analisando o seu desvio em relação ao centro da imagem.

Figura 3.6: Robô Pioneer 2DX e alguns obstáculos num ambiente produzidopelo Stage.

3.2 Detalhes da implementação

Na discussão feita em 2.9, foram selecionados alguns métodos para seremimplementados e analisados com maior detalhe. A figura 3.7 mostra a in-terligação que existe entre os métodos escolhidos. Ao longo deste capítulo,é analisada a forma como esses métodos foram implementados.

Para representar o ambiente, os robôs utilizam o método aproximado dedecomposição por células. Para isso, o mapa é dividido em células de igualtamanho. Esse tamanho varia de acordo com o tipo de ambiente e com osresultados pretendidos.

De modo a dividir o mapa num conjunto de células foi utilizada umamatriz binária (ver figura 3.8). Essa matriz representa as células intersetadas


Ambiente de Simulação

Robô

Representação do Ambiente

Decomposição por Células

Conjunto de Pontos-alvo

Algoritmo de Busca

A* D* Lite

Distância Diagonal

Distância de Manhattan

Atratores Dinâmicos

Custos Heurísticos

Distância Euclidiana

Figura 3.7: Interligação entre os diferentes métodos usados para controlar omovimento do robô.

por obstáculos com o valor ”1” e as restantes células com o valor ”0”.

Figura 3.8: Representação de um ambiente através de uma matriz biná-ria. As células que intersetam obstáculos são representadas com o valor”1” (células ocupadas), enquanto que as restantes células (células livres) sãorepresentadas com o valor ”0”.

Para encontrar um conjunto de células adjacentes entre o ponto inicial eo ponto final a partir dessa representação do ambiente, são utilizados algunsdos algoritmos de busca analisados no capítulo 2.6: Dijksra, A* e D* Lite.A escolha do algoritmo a ser utilizado depende do tipo de situações comque o robô se pode deparar. Se não existe a possibilidade de surgirem novosobstáculos durante o planeamento, então os algoritmos de Dijkstra ou A*são os mais indicados. Por outro lado, caso o robô precise de atuar numambiente mais dinâmico, o algoritmo D* Lite pode ser considerado. Osalgoritmos que utilizam uma estimativa da distância à célula final, utilizamum dos custos heurísticos referenciados nos capítulos anteriores (distânciade Manhattan, distância diagonal ou distância euclidiana).

A partir do caminho gerado pelos algoritmos de busca, o robô definealguns pontos desse percurso como uma sequência de alvos a atingir. Esses


pontos correspondem ao centro das células. Para permitir ao robô mover-seem direção a cada um desses alvos sequencialmente e ao mesmo tempo ter ematenção a presença de novos obstáculos foi utilizado o método dos atratoresdinâmicos. Caso a resolução seja suficientemente reduzida, todas os pontosobtidos no planeamento podem ser utilizados pois já se encontram a umadistância relativamente elevada entre si. Por outro lado, com resoluçõesmaiores os pontos podem estar demasiado próximos entre si. Como nãoé necessário existirem pontos demasiados próximos entre si em comparaçãocom o tamanho do robô, muitos dos pontos são ignorados. O próximo ponto-alvo definido pelo robô também não é necessariamente o mais próximo desi. Definir um dos pontos seguintes como ponto-alvo em vez do ponto maispróximo, permite ao robô percorrer caminhos mais suaves em relação aocaminho original planeado (ver figura 3.9).

Figura 3.9: Suavização do caminho percorrido pelo robô quando é utilizadoo método dos atratores dinâmicos para controlar a direção de navegação dorobô.

Caso um obstáculo esteja a obstruir o caminho do robô, este tentacontorná-lo usando o método dos atratores dinâmicos. Caso não seja pos-sível contornar o obstáculo dentro de um período de tempo máximo, a in-formação sobre a localização dos novos obstáculos é analisada e um novocaminho é planeado. Um mapa com a informação obtida sobre os obstácu-los é atualizado permanentemente. Tal como referido anteriormente, o robôé capaz de detetar novos obstáculos através dos seus sonares, câmara dedeteção de cores e laser. Este último sensor é usado para construir o mapa,pois permite obter uma representação mais precisa da localização dos novosobstáculos. Sempre que um novo obstáculo é detetado, a sua posição noambiente é calculada e definida como ocupada no mapa de obstáculos. Poroutro lado, as zonas onde o robô não deteta obstáculos são definidas comolivres no mapa de obstáculos. Sempre que é necessário replanear um cami-nho, o mapa de obstáculos é sobreposto ao mapa original de forma a criarum mapa global que inclua a informação sobre todos os obstáculos (fixos emóveis) conhecidos pelos robô.


A figura 3.10 mostra um caso em que um obstáculo foi contornado comsucesso usando o método dos atratores dinâmicos, sem necessidade de repla-neamento. Por sua vez, a figura 3.11 mostra um caso em que não é possívelcontornar um obstáculo e o caminho tem que ser replaneado.

(a) (b) (c)

Figura 3.10: Robô a contornar um obstáculo e a dirigir-se para o alvo finalutilizando o método dos atratores dinâmicos. As linhas desenhadas repre-sentam o caminho original e o caminho efetivamente percorrido pelo robô.

(a) (b) (c)

Figura 3.11: O robô segue normalmente o caminho planeado (figura 3.11a)até ao momento em que encontra um obstáculo desconhecido e tem quereplanear esse caminho (figura 3.11b). Depois, segue o novo percurso (fi-gura 3.11c) em direção à localização final.

O fluxograma da figura 3.12 mostra, de forma simplificada, como cadarobô utiliza os diferentes métodos para controlar o seu comportamento emdireção à localização final.

Para simplificar a recolha de informação relativamente aos resultadosobtidos, foi desenvolvida uma pequena aplicação gráfica (ver figura 3.13).Esta aplicação permite, de forma fácil e intuitiva, alterar vários parâmetrosrelativamente à representação do ambiente, ao algoritmo de busca utilizadoe às condições de replaneamento.


Início

Escolher resolução do mapaEscolher algoritmo de busca

Escolher ponto finalGerar caminho

Ponto final atingido?

NãoDefinir próximo

ponto-alvoSimFim

Não

Calcular força de atração na direção do ponto-alvo

Calcular forças de repulsão na direção dos obstáculos

Atualizar velocidade angular do robô de acordo com as duas forças

Ponto-alvo atingido?

Tempo limite para atingir o próximo ponto-

alvo ultrapassado?Sim

Gerar novo caminho

Sim

Não

Figura 3.12: Fluxograma da forma como o robô navega em direção ao ponto-alvo final.

Através desta aplicação é possível escolher o mapa do ambiente ou entãoiniciar o planeamento com um mapa vazio (em situações em que o ambienteé desconhecido). A aplicação também permite alterar facilmente a resoluçãodo mapa e o tamanho dos obstáculos. O algoritmo de busca a ser utilizadotambém pode ser alterado, bem como os custos heurísticos usados para esti-mar a distância à célula final. Após cada planeamento, é possível visualizaras células expandidas pelo algoritmo de busca e ter acesso direto ao númerode células expandidas, tempo de planeamento e distância total do caminhoobtido. Estes três critérios servirão de base para a comparação entre algo-ritmos ao longo do capítulo 4. Após o planeamento inicial, um mapa com os


Figura 3.13: Interface gráfica utilizada em conjunto com o Player/Stage.

novos obstáculos detetados pelo robô vai sendo construído (ver figura 3.16).Este novo mapa é usado para replanear um caminho, caso necessário. Casoexista uma obstrução no caminho original, o robô procura desviar-se dessaobstrução e voltar ao seu percurso usando o método dos atratores dinâmicos.Como muitas vezes não é possível regressar ao percurso original, torna-seútil definir um tempo máximo no qual o robô pode navegar fora do cami-nho original antes de usar o replaneamento. Através da aplicação é possívelalterar esse tempo máximo de replaneamento. Além disso, o planeamentopode ser feito permanentemente, ou seja, com o robô constantemente a atu-alizar o caminho com base na sua nova posição inicial e em possíveis novosobstáculos. O utilizador também tem a possibilidade de ordenar que umcaminho seja replaneado num dado instante, independentemente das outrasopções escolhidas para o replaneamento.

As figuras 3.15a e 3.15b exemplificam uma situação em que é comparadoo planeamento inicial de um caminho quando o robô pretende navegar entredois pontos opostos de um mapa. Neste exemplo foram comparadas as célu-las expandidas utilizando o algoritmo de Dijkstra e o algoritmo A*. Comoseria de prever nesta situação, o algoritmo A* encontra a célula final expan-


Figura 3.14: Deteção de obstáculos a partir das leituras do laser do robô. Abranco estão representados os obstáculos detetados pelos sensores do robô.

dindo um número bastante inferior de células em relação ao algoritmo deDijkstra, desde que usado um bom custo heurístico para estimar a distânciaaté à célula final. Esta situação em que o robô planeia um caminho entredois pontos opostos de um mapa é uma das usadas para comparar métodose algoritmos ao longo do capítulo 4.

(a) (b)

Figura 3.15: Células expandidas usando diferentes algoritmos. A preto estãorepresentados os obstáculos, enquanto que a cinzento estão representadas ascélulas que cada algoritmo necessitou de verificar. Em 3.15a foi utilizado oalgoritmo de Dijkstra e em 3.15b foi utilizado o algoritmo D* Lite.

Quando existem vários robôs a operar em simultâneo no mesmo ambi-ente é necessário recorrer a alguns dos métodos estudados no capítulo 2.8.Para situações básicas em que não há possibilidade de colisões entre robôs,o método Cocktail Party pode ser utilizado. Em algumas situações em queexiste um número de robôs relativamente pequeno e existe risco de colisões,


cada robô pode utilizar a sua câmara para diferenciar robôs de outros tiposde obstáculos (ver figura 3.16). Nesses casos, cada robô toma pequenas me-didas para evitar a colisão, tais como, mudar a direção de navegação até ooutro robô deixar de ser detetado no seu ângulo de visão, ou parar comple-tamente o seu movimento. Nos dois casos anteriores não existe comunicaçãoentre robôs. Nalguns casos, pode ser benéfico existir uma melhor coorde-nação entre robôs. Para isso ser possível, também foram realizados testesem situações em que estes podem comunicar entre si. O método selecio-nado para melhorar essa coordenação foi o planeamento priorizado. Nessemétodo, os robôs comunicam por mensagens que permitem a cada um de-les conhecer o caminho e o estado atual dos robôs com maior prioridade.Quando uma possível colisão é detetada, o robô com menor prioridade tomamedidas que permitam evitar a colisão com o robô com maior prioridade.

Figura 3.16: A câmara de deteção de cores permite distinguir robôs de outrotipo de obstáculos.

Todas estas metodologias serão analisadas mais profundamente nos pró-ximos capítulos.

3.3 Resumo

As simulações serão realizadas no Player/Stage usando o robô Pioneer 2DX.Este robô é capaz de obter informações sobre o ambiente à sua volta atra-vés de sensores de distância e uma câmara para deteção de cores. Cadarobô encontra caminhos usando algoritmos de busca a partir de um mapadecomposto em células de igual tamanho. Os robôs são também capazes dereplanear o seu caminho caso necessário, bem como desviar-se de pequenosobstáculos (neste último caso, usando o método dos atratores dinâmicos).Para se desviarem dos obstáculos em tempo real, os robôs utilizam os sona-res distribuídos em torno de si, enquanto que para construir um mapa comobstáculos, é utilizado o sensor laser que o robô possui. Para simplificara recolha de informação relativamente aos resultados obtidos, uma aplica-


ção gráfica foi desenvolvida para ser utilizada em conjunto com a janela doPlayer/Stage. De forma a existir coordenação num ambiente com váriosrobôs a operar em simultâneo, algumas estratégias serão testadas. Para ca-sos em que não existe comunicação serão usados os métodos Cocktail Party eo uso da câmara para diferenciação entre robôs e obstáculos. Para casos emque existe comunicação entre robôs será usado um planeamento priorizado.


Capítulo 4

Planeamento para um ÚnicoRobô

Depois de escolhidos alguns métodos é útil compará-los para perceber quaissão os mais indicados para as diferentes situações que cada robô pode en-contrar. Neste capítulo, são comparados os resultados obtidos com:

• diferentes tamanhos de células para representar o mapa;• a utilização de diferentes custos heurísticos para estimar a distância àcélula final;• a alteração do algoritmo de busca utilizado;• a utilização do método dos atratores dinâmicos para navegar para umalvo ao mesmo tempo que se evitam obstáculos;• a introdução de obstáculos móveis não conhecidos previamente queobrigam ao replaneamento do caminho.

Os mapas utilizados ao longo deste capítulo têm todos a dimensão de32x32 metros. Os resultados visam apenas as situações em que existe apenasum robô a operar num dado ambiente.

4.1 Resolução do mapaComo o método de decomposição por células foi o escolhido para represen-tar o ambiente, foi necessário analisar a importância do tamanho das célulaspara os resultados obtidos. No exemplo da figura 4.1 o ambiente foi repre-sentado com resoluções de 10x10 células, 20x20 células e 50x50 células. Otempo para encontrar um caminho é menor, quanto maior o tamanho dascélulas, pois há menos células para analisar. No entanto, nos primeiros doiscasos a resolução do ambiente não permite ao robô planear caminhos entretodos os locais possíveis do mapa, pois existem locais que são erradamenteconsiderados como estando obstruídos. Isto deve-se ao facto de bastar queuma pequena porção de um obstáculo seja intersetada por uma célula, para

53

CAPÍTULO 4. PLANEAMENTO PARA UM ÚNICO ROBÔ 54

toda a célula ser dada como ocupada. O último caso permite ao robô alcan-çar todas as zonas do mapa, embora um maior número de células tenha deser expandido para um caminho ser encontrado.

(a) (b) (c)

Figura 4.1: Decomposição do mapa em células de igual tamanho. Na fi-gura 4.1a o ambiente está representado por uma resolução de células de10x10, na figura 4.1b por uma resolução de 20x20 e na figura 4.1c por umaresolução de 50x50.

Os problemas que podem surgir quando se usa um ambiente dividido emcélulas estão ilustrados na figura 4.2. A figura 4.2a mostra um obstáculotriangular e o espaço extra que ocupa. A figura 4.2b, por sua vez, mostrauma situação em que uma zona do mapa é erradamente assumida comoocupada por obstáculos, e um caminho tem de ser replaneado por outrazona.

(a)

B

A(b)

Figura 4.2: Obstáculos num ambiente dividido em células. A preto estárepresentado o espaço extra ocupado pelos obstáculos. O tracejado na fi-gura 4.2b representa um caminho planeado entre dois pontos.

O tamanho de células escolhido deve ser o suficiente para maximizar arapidez dos algoritmos de busca, ao mesmo tempo que permita atingir todasas zonas do mapa.

A divisão de um mapa em células de diferentes tamanhos é uma dasformas de comparar diferentes algoritmos de busca. O tempo, o número de


células expandidas e a distância total do caminho produzido são alguns dosaspetos que podem ser comparados.

4.2 Custos heurísticos

Os custos heurísticos utilizados pelos algoritmos A* e D* Lite permitem queum caminho seja encontrado através de um menor número de células expan-didas em relação ao algoritmo de Dijkstra, desde que a distância à célula finalseja bem estimada (tal como analisado no capítulo 2.6.2). Como existemvários custos heurísticos, é necessário perceber qual o tipo de resultados quecada um pode obter e qual o que se adequa melhor às soluções pretendidas.Foram feitos testes com os três tipos de custos abordados anteriormente (dis-tância euclidiana, distância de Manhattan e distância diagonal), utilizandoo mesmo tamanho de células para representar o ambiente, e analisando onúmero de células expandidas, o tempo de planeamento e a distância totaldo caminho obtido. O algoritmo de busca utilizado para realizar as simu-lações foi o A*, embora o algoritmo D* Lite também pudesse ser utilizadopara comparar os custos heurísticos nas mesmas situações.

Os testes foram realizados em três mapas diferentes (ver figura 4.3) comuma resolução de células de 250x250. Estes três mapas foram escolhidospor representarem ambientes bem distintos entre si. O primeiro mapa écomposto por obstáculos simples e bem estruturados. O segundo mapa, porsua vez, representa um ambiente mais complexo, com obstáculos de formase tamanhos diferentes entre si. Nestes dois primeiros cenários em teste,o objetivo era encontrar um caminho entre dois pontos opostos do mapa.Por último, o terceiro mapa contém obstáculos simples e que ocupam umapercentagem relativamente pequena do ambiente. No entanto, a colocaçãodos obstáculos e o facto de a célula final se situar numa zona interior domapa, tornam a tarefa de encontrar um caminho entre os pontos inicial efinal mais complicada em relação aos dois primeiros cenários em teste.

(a) Mapa 1 (b) Mapa 2 (c) Mapa 3

Figura 4.3: Cenários utilizados para comparar custos heurísticos.


Tabela 4.1: Comparação entre diferentes custos heurísticos nos três cenáriosem teste.

Mapa Custo heurístico Tempo (ms) C. expandidas DistânciaD. euclidiana 193 (+522.6%) 2663 (+625.6%) 802 (-)

1 D. de Manhattan 31 (-) 367 (-) 808 (+0.7%)D. diagonal 210 (+577.4%) 3370 (+818.6%) 804 (+0.2%)

D. euclidiana 186 (+31%) 3092 (+10%) 804 (-)2 D. de Manhattan 142 (-) 2812 (-) 829 (+3.1%)

D. diagonal 218 (+53.5%) 3205 (+14%) 812 (+1%)

D. euclidiana 1704 (-) 33670 (+0.4%) 1826 (-)3 D. de Manhattan 1802 (+5.8%) 33550 (-) 1828 (+0.1%)

D. diagonal 1950 (+14.4%) 34010 (+1.4%) 1826 (-)

Através dos resultados obtidos, foi possível perceber que a utilizaçãoda distância euclidiana como custo heurístico permite geralmente obter ocaminho mais curto, enquanto que a distância de Manhattan, por sua vez,produz um caminho ligeiramente mais longo, mas com um número de nósexpandidos menor. A distância diagonal é aquela que necessita de um maiornúmero de células expandidas para alcançar a célula final, apresentandonormalmente a segunda menor distância total.

No cenário apresentado na figura 4.3a, a distância de Manhattan per-mitiu obter uma solução de uma forma bastante mais rápida em relaçãoaos outros custos heurísticos (ver tabela 4.1), pois necessitou de expandirum número de células bastante menor. No entanto, a distância total docaminho obtido foi ligeiramente superior em relação à utilização de outroscustos. Por sua vez, nos cenários representados nas figuras 4.3b e 4.3c,os resultados foram bastante mais equilibrados. No segundo cenário, a dis-tância de Manhattan foi novamente a que obteve melhores resultados emrelação ao tempo de execução e número de células expandidas, encontrandoum caminho final mais longo. No terceiro cenário, a distância euclidianaobteve os melhores resultados em termos de tempo e e distância, mas poruma pequena margem em relação aos outros custos.

A distância de Manhattan destacou-se, principalmente, no primeiro ce-nário. Esse mapa, semelhante ao de um supermercado, permite poucosmovimentos na diagonal em relação aos outros mapas. Como os ambientessemelhantes aos de um supermercados são o principal tipo de ambiente parao qual o planeamento de caminhos é orientado nesta dissertação, é possívelconcluir que a distância de Manhattan é o custo heurístico mais indicado.


4.3 Planeamento inicial

Depois de escolhida a distância de Manhattan como custo heurístico, foramcomparados os resultados obtidos para planear um caminho inicial usandoos algoritmos Dijkstra, A* e D* Lite.

Para comparar os algoritmos, o comportamento do robô foi testado emdiferentes situações (ver figura 4.4).

Inicio

Fim

(a) Caso 1.

Inicio

Fim

(b) Caso 2.

Figura 4.4: Cenários utilizados para comparar os resultados obtidos no pla-neamento inicial.

A primeira situação testada está representada na figura 4.4a. Nessa situ-ação o robô pretende navegar entre dois pontos opostos do mesmo corredor.

Os resultados obtidos podem ser consultados na tabela 4.2. Nesta situ-ação em que não existem obstáculos entre o robô e o alvo final, o algoritmoD* Lite é aquele que necessita de menos tempo para encontrar um cami-nho. Além disso, nesta situação, como não existem obstáculos entre o pontoinicial e final, tanto o algoritmo D* Lite como o A*, precisam apenas deexpandir os nós livres na direção do alvo. O algoritmo de Dijkstra, comonão utiliza informação sobre a distância à célula final, obtém claramente ospiores resultados nesses dois aspetos. Por último, os algoritmos encontramum caminho final praticamente igual nesta situação, sendo que o algoritmode Dijkstra encontra o caminho mais curto.

A segunda situação testada está representada na figura 4.4b. Nessasituação o robô pretendia navegar entre dois pontos opostos do mapa.

Os resultados obtidos podem ser consultados na tabela 4.3. O algo-ritmo A* mostrou-se como sendo o algoritmo mais rápido para planear umcaminho nestas condições, sendo que os algoritmos D* Lite e Dijkstra ne-cessitaram de um tempo bastante superior para encontrar um caminho. O


Tabela 4.2: Resultados obtidos para o planeamento inicial no cenário apre-sentado na figura 4.4a.

Resolução Algoritmo Tempo (ms) C. expandidas DistânciaDijkstra 28 (+460%) 264 (+942.9%) 264 (-)

50x50 A* 27 (+440%) 28 (-) 276 (+4.5%)D* Lite 5 (-) 30 (+7.1%) 275 (+4.2%)

Dijkstra 33 (+450%) 2026 (+3517%) 262 (-)100x100 A* 27 (+350%) 56 (-) 271 (+3.4%)

D* Lite 6 (-) 61 (+8.9%) 266 (+1.5%)

Dijkstra 711 (+8787%) 13675 (+9738%) 260 (-)250x250 A* 27 (+237.5%) 139 (-) 264 (+1.5%)

D* Lite 8 (-) 152 (+9.4%) 263 (+1.2%)

algoritmo A* foi também aquele que necessitou de um menor número decélulas expandidas nos testes efetuados, também com uma grande diferençade valores em relação aos outros dois algoritmos testados. O algoritmo deDijkstra precisa de expandir praticamente todas as células livres do mapapara atingir a célula final. Relativamente à distância do caminho final, osalgoritmos apresentam resultados bastante semelhantes, sendo que o algo-ritmo de Dijkstra é aquele que produz caminhos mais curtos. O algoritmoA* é aquele que produz caminhos mais longos.

Tabela 4.3: Resultados obtidos para o planeamento inicial no cenário apre-sentado na figura 4.4b.

Resolução Algoritmo Tempo (ms) C. expandidas DistânciaDijkstra 32 (+14.3%) 1032 (+829.7%) 816 (-)

50x50 A* 28 (-) 111 (-) 830 (+1.7%)D* Lite 58 (+107.1%) 824 (+642.3%) 822 (+0.7%)

Dijkstra 172 (+493.1%) 4057 (+2567%) 806 (-)100x100 A* 29 - 158 (-) 816 (+1.2%)

D* Lite 235 (+710.3%) 3108 (+1867%) 812 (+0.7%)

Dijkstra 1621 (+5129%) 32881 (+8859%) 802 (-)250x250 A* 31 (-) 367 (-) 813 (+1.4%)

D* Lite 1597 (+5052%) 24150 (+6480%) 810 (+1%)

Através da análise destes resultados, é possível perceber que o algoritmoA* apresenta um melhor desempenho em relação ao algoritmo D* Lite nostestes efetuados. Além disso, verificou-se que quanto maior a resolução domapa, menor a distância total do caminho produzido. No entanto, para reso-


luções elevadas, a diminuição da distância total com o aumento da resoluçãoé bastante menos acentuada em relação ao que acontece com baixas reso-luções. Por este motivo, é desnecessário utilizar uma resolução demasiadoalta, pois o tempo de planeamento não compensa as melhorias obtidas.

4.4 Atratores dinâmicos

Para que o robô se possa deslocar em direção ao próximo alvo e evitar co-lisões, é utilizado o métodos dos atratores dinâmicos. O robô conhece ascoordenadas da posição final que deve atingir, mas apenas consegue detetarnovos obstáculos com a ajuda de informação sensorial. A informação senso-rial para implementar a dinâmica de evitar obstáculos é obtida a partir dossonares que o robô possui. Como referido no capítulo 3.1, o robô utilizadonas simulações tem 16 sonares distribuídos em torno de si. Para implemen-tar a dinâmica de evitar obstáculos foi apenas necessário utilizar os oitosonares frontais. Cada um dos sensores permite criar forças repulsivas quecriam um repulsor na direção para a qual estão apontados. A força repulsivavaria de intensidade de acordo com a distância aos obstáculos. Ao mesmotempo é criada uma força atrativa, que varia de intensidade de acordo coma distância ao próximo alvo, e que permite criar um atrator na direção emque o alvo se encontra. A soma destas forças define a próxima direção queo robô deve tomar.

Nas figuras 4.5 e 4.6 são apresentadas duas situações em que o robô sedirige ao alvo final. Na primeira, não existem obstáculos e, sendo assim, adireção de navegação do robô é determinada apenas pela força atrativa. Estaforça gera um ponto fixo estável (atrator) na direção que o robô deve tomar(tal como referido em 2.7.2). Na segunda figura, um obstáculo foi colocadoentre a posição atual do robô e o alvo final. À força atrativa foi necessárioentão somar cada uma das forças repulsivas criadas pelos cinco sensores quedetetaram os obstáculos nessa situação. Cada uma dessas forças repulsivascria ponto fixo instável (repulsor) na direção em que obstáculo é detetadopelo sensor. A soma das forças atrativas e repulsivas permite obter umaforça resultante que, neste caso, cria um atrator resultante que indica aorobô que este deve mudar a sua direção de navegação.

Depois de planeado um caminho, o robô obtém um conjunto de pontosque unem a posição inicial à posição final. Como referido no capítulo 3.2,o robô pode adotar algumas estratégias para suavizar a sua trajetória aoseguir esses pontos:

• ignorar alguns pontos quando a resolução do mapa é alta, pois estãomuito próximos entre si;• não definir o ponto mais próximo de si como ponto-alvo, mas sim umdos pontos seguintes.


(a) (b)

Figura 4.5: Robô a dirigir-se para o próximo alvo. À esquerda está repre-sentado um robô que se desloca para o seu próximo alvo. À direita estárepresentada a força atrativa que exprime o comportamento ”orientação nadireção do alvo”. Esta força cria um atrator na direção em que esse alvoestá localizado (ψalvo).

(a) (b) fobs1 (c) fobs2 (d) fobs3

(e) fobs4 (f) fobs5 (g) falvo (h) ftotal

Figura 4.6: Em 4.6a está representada uma situação em que existe umobstáculo colocado entre o robô e o próximo alvo. Nos seis gráficos seguintesestão representadas as forças repulsivas produzidas por cada um dos cincosensores que estão a detetar o obstáculo, bem como a força que atrai o robôpara o alvo. Finalmente, em 4.6h está representada a resposta total e adireção atual do robô (indicada a vermelho).

O segundo ponto é bastante importante para permitir ao robô contornarobstáculos usando o método dos atratores dinâmicos, tal como demonstradona figura 4.7. Para definir o próximo ponto-alvo, o robô procura o pontomais próximo da posição final dentro de um raio r em torno de si. Dessaforma, quando um obstáculo é detetado e o robô o começa a contornar, opróximo ponto-alvo está num local ocupado pelo obstáculo, ou até do ladooposto. Esta colocação da próxima célula-alvo permite ao robô contornar o


obstáculo e reencontrar o seu percurso. Caso esta estratégia não fosse usada,o robô poderia ficar retido no mesmo lado do obstáculo junto à célula-alvoe um caminho teria de ser replaneado.

robô

ponto-alvo

(a)

robô

ponto-alvo

(b)

robô

ponto-alvo

(c)

robô

ponto-alvo

(d)

Figura 4.7: Robô segue o seu percurso ao mesmo tempo que evita a colisãocom obstáculos. As células representam o percurso do robô, enquanto quea circunferência em torno deste representa o raio no qual é procurada apróxima célula-alvo.

A figura 4.8, por sua vez, mostra uma situação em que um obstáculoobstrói na totalidade um corredor. Neste caso, o robô começa por tentarcontornar o obstáculo por um dos lados. Como isso não é possível, a forçade repulsão provocada pelos obstáculos ”empurra” o robô de volta à posiçãoanterior onde este verifica se o caminho continua bloqueado. Caso o tempode replaneamento máximo ainda não tenha sido atingido, a força resultanteconstruída pelos atratores dinâmicos leva o robô a manter a sua direçãode navegação e a verificar se é possível contornar o obstáculo pelo outrolado. Como o robô fica retido no mesmo local durante algum tempo, nãoconseguindo encontrar uma célula posterior à célula-alvo atual, o tempomáximo de replaneamento acaba por ser atingido e um novo caminho éreplaneado.

A figura 4.9 mostra a influência que o tempo de replaneamento podeter no caminho final percorrido pelo robô. Nesse exemplo foi utilizado ummapa com alguns obstáculos desconhecidos. Em 4.9a, está representado ocaminho original planeado pelo robô entre dois pontos opostos do mapa.Em 4.9b está representado o caminho final percorrido pelo robô ao utilizarum replaneamento contínuo do seu caminho, e, por último, em 4.9c estárepresentado o caminho final percorrido pelo robô quando foi definido um


robô

ponto-alvo

(a)

robô

ponto-alvo

(b)

robô

ponto-alvo

(c)

ponto-alvo

robô

(d)

Figura 4.8: Robô tenta contornar obstáculo, mas acaba por ter que replanearo seu caminho.

tempo limite para o robô atingir a próxima célula-alvo.

(a) Caminho original. (b) treplan = 0s. (c) treplan = 15s.

Figura 4.9: Influência do tempo de replaneamento no caminho final per-corrido. Em 4.9a está representado o caminho original planeado pelo robô.Em 4.9b está representado o caminho percorrido com um replaneamentoconstante. Por último, em 4.9c está representado o caminho percorrido pelorobô quando um caminho é replaneado sempre que o tempo máximo dereplaneamento é atingido.

Em algumas situações o uso dos atratores dinâmicos para o desvio deobstáculos é suficientemente eficiente, enquanto que noutros casos o robôpode ficar preso num corredor até ao tempo máximo expirar, como aconteceem duas situações assinaladas na figura 4.9c. Os atratores dinâmicos, noentanto, poderiam ser a melhor solução nessas duas situações, caso os obs-


táculos fossem móveis e deixassem de obstruir o corredor enquanto o robôse aproximava. Por outro lado, com um replaneamento constante, o robôreplaneia um caminho no momento em que um novo obstáculo é detetado.Mais uma vez, a eficiência dessa estratégia poderia mudar caso os obstáculosfossem móveis. Nesse caso, o robô poderia replanear um caminho por outrocorredor sem isso ser necessário.

4.5 Replaneamento

Como referido anteriormente, podem ser detetados novos obstáculos entrea posição atual do robô e o próximo ponto-alvo a ser atingido. Caso issoaconteça, o robô tenta contornar o obstáculo para atingir essa posição ouuma das posições seguintes. Caso não seja possível contornar o obstáculoe seguir o caminho previsto, é necessário encontrar um caminho alternativopara alcançar o mesmo destino, evitando a zona do mapa obstruída. Outraforma de lidar com estas situações, é replanear um caminho imediatamenteno momento em que um novo obstáculo é detetado.

Para comparar da melhor forma os algoritmos, nos próximos testes sãoutilizadas situações em que o robô replaneia constantemente o seu percurso.Em muitas dessas situações, no entanto, o método dos atratores dinâmicosera suficiente para evitar os obstáculos e seguir o caminho original, tal comoreferido no capítulo 4.4.

A primeira situação testada está representada na figura 4.10 e acontecequando existe um pequeno obstáculo no caminho do robô. Nesta situação,o robô é obrigado a fazer uma ligeira alteração ao caminho original.

(a) (b)

Figura 4.10: Robô segue normalmente o seu percurso até que um obstáculoé encontrado e o caminho tem de ser ligeiramente alterado.

Os resultados obtidos mostram que o algoritmo D* Lite é aquele que ne-cessita de verificar um menor número de células (ver gráfico da figura 4.11),sendo também aquele que obtém um caminho mais rapidamente nesta si-tuação (ver gráfico da figura 4.12). Estes resultados são os esperados, umavez que o algoritmo D* Lite apenas necessita de verificar as células que so-freram alterações, enquanto que o algoritmo A* reconstrói o caminho com-


pletamente independentemente do número de alterações no ambiente.

50 100 25050

100150200250

Resolução

Células

expa

ndidas

A*D* Lite

Figura 4.11: Número de células expandidas para replanear um caminhoquando existe um pequeno obstáculo a bloquear o caminho na situação dafigura 4.10.

50 100 2505

10

15

20

25

Resolução

Tempo

(ms) A*

D* Lite

Figura 4.12: Tempo necessário pelo algoritmo para encontrar um caminhoquando existe um pequeno obstáculo a bloquear o caminho original na situ-ação da figura 4.10.

A segunda situação testada está representada na figura 4.13 e acontecequando um corredor está completamente obstruído por um obstáculo. Nestasituação o robô é obrigado a replanear um caminho utilizando outro corre-dor.

Os resultados obtidos mostram que o algoritmo A* é, desta feita, aqueleque necessita de verificar um menor número de células (ver figura 4.14),sendo também aquele que apresenta melhores resultados em termos de tempode processamento nesta situação (ver figura 4.15). Essa diferença de tempotorna-se mais notória com o aumento da resolução do mapa. Nesta situação,o algoritmo D* Lite não é tão eficiente como no primeiro caso, pois é neces-sário fazer um grande desvio em relação ao trajeto original e o número decélulas alteradas que precisam de ser analisadas é suficientemente elevadopara que este algoritmo passe a ter uma performance inferior à do algoritmoA*.


(a) (b)

Figura 4.13: Robô segue normalmente o seu percurso até que encontra umobstáculo que bloqueia totalmente uma passagem e o obriga a replanear umcaminho utilizando outros corredores.

50 100 250

200

400

600

Resolução

Células

expa

ndidas

A*D* Lite

Figura 4.14: Número de células expandidas para replanear um caminhoquando um obstáculo bloqueia totalmente o caminho original na situaçãoda figura 4.13.

50 100 25020

40

60

80

Resolução

Tempo

(ms)

A*D* Lite

Figura 4.15: Tempo necessário pelo algoritmo para encontrar um caminhoquando um obstáculo bloqueia totalmente o caminho original na situaçãoda figura 4.13.


Além dos dois testes anteriores foram realizados testes em situações emque existem vários obstáculos no mesmo mapa. Na figura 4.16 está repre-sentada uma situação em que existem obstáculos de diferentes dimensõesque obrigam a pequenos e grandes desvios em relação à rota original. Aresolução utilizada para o mapa neste caso foi de 250x250.

Figura 4.16: Mapa com obstáculos inicialmente desconhecidos para o robô.Os novos obstáculos estão assinalados no mapa com números de 1 a 4.

A figura 4.17a mostra o caminho original planeado pelos algoritmos,enquanto que a figura 4.17b mostra o caminho final percorrido pelo robôentre as localizações inicial e final. A colocação dos obstáculos obriga orobô a sofrer dois pequenos desvios (obstáculos 1 e 3), e dois grandes desvios(obstáculos 2 e 4).

(a) Caminho planeado. (b) Caminho percorrido.

Figura 4.17: Caminho planeado e caminho percorrido no cenário com obs-táculos da figura 4.16.

A tabela 4.4 mostra os resultados obtidos pelos algoritmos em cada zona.Os resultados mostram que o tempo de processamento do algoritmo A*

para encontrar um caminho até à célula final é semelhante em todas as zonas


Tabela 4.4: Resultados obtidos para o replaneamento em diferentes zonasno cenário da figura 4.16.

Zona Algoritmo Tempo (ms) C. expandidasA* 25 (+212.5%) 380 (+80.9%)

1 D* Lite 8 (-) 210 (-)

A* 24 (-) 344 (-)2 D* Lite 104 (+333.3%) 2667 (+675.3%)

A* 24 (+700%) 305 (+522.4%)3 D* Lite 3 (-) 49 (-)

A* 23 (+475%) 215 (-)4 D* Lite 14 (-) 335 (+55.8%)

do mapa, aumentando muito ligeiramente com o aumento da distância àcélula final. De igual forma, o número de células expandidas aumenta como aumento da distância à célula final.

Relativamente ao algoritmo D* Lite, o tempo de processamento está di-retamente ligado ao número de novas células ocupadas com que o algoritmotem que lidar. Em três das quatro situações, o algoritmo D* Lite foi maisrápido a reagir em relação ao algoritmo A*. Na segunda zona, no entanto, oalgoritmo teve que lidar com uma grande percentagem de novos obstáculos asurgirem ao mesmo tempo nas leituras dos seus sensores e o tempo de proces-samento foi bastante superior em relação ao que o algoritmo A* necessitounuma situação idêntica. Na quarta zona, o tempo de processamento foi rela-tivamente baixo em relação ao previsto, pois o robô navegou paralelamenteaos obstáculos e as novas células foram sendo analisadas progressivamenteantes de ser necessário replanear o caminho por outro corredor.

O algoritmo D* Lite é aquele que se adapta melhor a pequenas alteraçõesno ambiente. No entanto, com o aumento do número de obstáculos, o de-sempenho deste algoritmo torna-se semelhante ou até inferior ao algoritmoA*, apesar deste último não reutilizar informação de caminhos anteriores,sendo a diferença mais notória com o aumento da resolução do mapa. Istodeve-se ao facto de, como explicado anteriormente, com o aumento do nú-mero de obstáculos, existirem mais alterações no ambiente em relação àsquais o algoritmo D* Lite tem que se adaptar.

4.6 Discussão dos resultados

O tamanho das células deve ser suficientemente baixo para permitir ao robôatingir todas as zonas do mapa. Ao mesmo tempo, quanto menor for o


tamanho das células, mais curto e suave é o caminho produzido duranteo planeamento. No entanto, como o caminho efetivamente percorrido pelorobô é realizado com a ajuda do método dos atratores dinâmicos, o robôacaba por percorrer um trajeto semelhante e suave com diferentes resoluçõesdo mapa. Por este motivo, conclui-se que é desnecessário utilizar resoluçõesdemasiado elevadas, pois a melhoria nos resultados obtidos não é suficientepara compensar o aumento dos custos computacionais.

O melhor custo heurístico para estimar a distância à célula final nassituações em estudo nesta dissertação é a distância de Manhattan, poisadapta-se melhor a mapas semelhantes aos de supermercados, em que sãorealizados mais movimentos na horizontal e vertical do que na diagonal.

O algoritmo A* permite obter geralmente um caminho inicial de umaforma bastante mais rápida em relação ao algoritmo D* Lite. Uma exceçãoà regra, é, por exemplo, uma situação em que não existam obstáculos entreo ponto inicial e final.

Em ambientes dinâmicos, o algoritmo D* Lite obtém os melhores re-sultados em várias situações. No entanto, em situações em que existe umgrande desvio em relação ao caminho original, o algoritmo A* é o mais indi-cado, especialmente se um corredor estiver totalmente obstruído e um novocaminho tiver que ser planeado utilizando outros corredores.

Pelos resultados obtidos, conclui-se que, tanto o algoritmo A*, como oD* Lite, são suficientemente fiáveis nas situações em estudo nesta disser-tação, mesmo em ambientes dinâmicos. O algoritmo D* Lite destaca-seprincipalmente em situações onde são realizados pequenos reajustamentosem relação ao caminho planeado. Como o método dos atratores dinâmicospode ser usado para reagir a grande parte desses pequenos desvios com efi-ciência, optou-se por utilizar o algoritmo A* em conjunto com esse métodolocal nas simulações realizadas no próximo capítulo.

Capítulo 5

Planeamento para VáriosRobôs

No capítulo anterior foram realizados testes para simular situações em queexiste apenas um robô a operar num dado ambiente. Algumas metodologiasforam escolhidas para permitir a cada robô planear e percorrer um cami-nho, e ao mesmo tempo reagir a obstáculos móveis. Para permitir a umconjunto de robôs navegar no mesmo ambiente em simultâneo, é necessárioque também exista algum tipo de coordenação entre eles.

A figura 5.1 exemplifica uma situação em que vários robôs navegam numambiente de simulação semelhante ao de um supermercado.

Figura 5.1: Robôs navegam num ambiente semelhante ao de um supermer-cado. Nele existem outros robôs a planear e percorrer os seus caminhos,além de clientes a fazer as suas compras.

Neste ambiente existem alguns robôs a planear e a percorrer os seus cami-nhos, além de alguns clientes a fazer as suas compras, que são os obstáculos

69

CAPÍTULO 5. PLANEAMENTO PARA VÁRIOS ROBÔS 70

móveis nesta situação. A partir das metodologias implementadas anterior-mente, cada robô é capaz de seguir o seu caminho e, ao mesmo tempo, evitaro contacto com essas pessoas e com outros obstáculos que possam surgir.Nos casos em que exista algum risco de colisão entre robôs, no entanto, estesainda não são capazes de tomar as melhores decisões para se coordenareme seguirem o seu percurso.

Neste capítulo são realizados testes para simular o comportamento devários robôs em simultâneo a operar no mesmo espaço, usando diferentesmetodologias. Foram realizadas simulações, tanto para casos em que nãoexiste comunicação entre robôs, como para casos em que existe comunicação.Ao longo do capítulo, são comparados os resultados obtidos com diferentesnúmeros de robôs e com os diferentes métodos utilizados.

5.1 Sem comunicação

Para testar o comportamento de vários robôs a operar em simultâneo numdado ambiente, começou-se por realizar simulações para casos em que nãoexiste qualquer tipo de comunicação entre robôs. As primeiras experiênciasrealizadas visaram, simplesmente, deixar cada robô seguir o seu caminho semqualquer tipo de consideração pelo trajeto dos outros robôs. Este método évulgarmente conhecido como Cocktail Party (ver capítulo 2.8.1).

Este método revelou-se pouco eficiente em muitas situações, tal comoesperado. Quando não existe nenhuma possibilidade de colisão entre robôs,cada robô navega normalmente até à sua localização final. Por outro lado,em situações em que existe possibilidade de colisão entre dois robôs, a efi-ciência deste método torna-se bastante mais reduzida. Os robôs conseguemmuitas vezes evitar a colisão da melhor forma, principalmente em situaçõesem que navegam na mesma direção. Noutras ocasiões no entanto, a direçãoescolhida para evitar a colisão não é a melhor e os robôs não conseguemcontinuar o seu trajeto imediatamente. A figura 5.2 mostra uma dessas si-tuações. Nela dois robôs navegam na perpendicular entre si, e acabam porse desviar para a mesma direção quando usam o método dos atratores dinâ-micos. Nas situações em que existem mais do que dois robôs a tentar evitara colisão, a taxa de eficiência deste método baixa consideravelmente (verfigura 5.3), e muitas vezes não é possível evitar situações de colisão nessaszonas onde que os robôs se aglomeram.

Além do método Cocktail Party, foi decidido implementar outro métodoque permitisse obter melhores resultados, também sem a utilização de co-municação. Para isso, dotou-se cada robô com a capacidade de diferenciaros robôs de outros tipos de obstáculos móveis. Para testar esse comporta-mento em simulação, optou-se por utilizar a câmara para deteção de coresdisponível em cada um deles. Como cada robô tem uma cor diferente entresi e em relação aos obstáculos, a câmara permite facilmente fazer a distinção


(a) (b)

Figura 5.2: Uma colisão é evitada entre dois robôs, que depois não con-seguem seguir o trajeto previsto, pois não alteram da melhor forma a suadireção de navegação. Esta situação pode acontecer quando não existe co-ordenação entre robôs.

Figura 5.3: Vários robôs aglomeram-se na mesma zona do mapa e não con-seguem seguir o trajeto planeado.

necessária entre robôs e obstáculos. Quando um robô deteta outro robô noseu ângulo de visão, tenta adotar algumas estratégias para evitar a colisão.Uma dessas estratégias é a de mudar a sua direção de navegação até o outrorobô deixar de ser detetado. Depois, tenta regressar ao percurso planeado.

Na figura 5.4, está representada uma situação semelhante à da figura 5.2,e em que dois robôs se cruzam. Neste caso, foi utilizada a câmara de deteçãode cores para permitir aos robôs seguirem o seu percurso da melhor forma.A imagem captada pela câmara permite a cada robô perceber a distância ea direção em que o outro robô está em relação a si. Quando essa distânciabaixa para um valor menor que a distância mínima de segurança, cada robôdeve ser capaz de adotar uma estratégia para evitar uma colisão. Neste caso,o robô vermelho verifica que o robô laranja se está a mover perpendicular-mente (da direita para a esquerda) em relação a si (figura 5.4b), detetandoao mesmo tempo uma diminuição da distância entre os dois. Através da aná-lise dessa informação obtida através da câmara, o robô decide que a melhorsolução neste caso é alterar a sua direção de navegação em sentido contrárioao do outro robô para evitar a colisão. Como os robôs alteram a sua dire-


ção de navegação em sentidos opostos, a colisão é facilmente evitada e cadarobô retoma o seu caminho quando o outro robô deixa de ser detetado noseu ângulo de visão.

(a) (b)

(c) (d)

Figura 5.4: Uma colisão é evitada com sucesso entre dois robôs.

A simples mudança da direção de navegação pode não ser a melhorsolução em algumas situações. Uma dessas situações está representada nafigura 5.5. Nessa situação, dois robôs navegam na diagonal e uma possívelcolisão acontece no local onde se cruzam. A mudança de direção neste caso,faz com que os robôs tomem a mesma direção e façam um grande desvioem relação ao caminho planeado. Se a estratégia fosse a de parar em vez demudar a direção, o robô que primeiro detetasse o outro poderia parar atéque a colisão fosse evitada.

Para responder da melhor forma às diferentes situações que podem sur-gir, foram definidas outras estratégias além da mudança de direção. Es-sas estratégias variam de acordo com a informação obtida através da câ-mara para deteção de cores. A partir dessas estratégias são definidos trêscomportamentos-base para os robôs:

• não fazer nada, deixando os atratores dinâmicos resolver a possibili-dade de colisão naturalmente;• mudar a direção de navegação;• parar.

A distância que separa os robôs tem implicações no comportamento quedeve ser adotado, sendo que por isso foram definidas três distâncias de se-gurança (ver figura 5.6).


(a) (b)

(c) (d)

Figura 5.5: Uma colisão é evitada entre dois robôs que se movem na diagonalentre si. No entanto, depois de efetuarem o desvio, os robôs seguem a mesmadireção de navegação e não conseguem seguir o trajeto planeado.

Figura 5.6: Distâncias de segurança em torno do robô. A distância a queoutro robô se encontra e o seu comportamento, definem a estratégia quedeve ser adotada.

Caso o robô detetado esteja a uma distância que não represente perigo decolisão (distância maior que a primeira distância de segurança), não é ado-tada qualquer estratégia e o robô continua normalmente o seu percurso. Estecomportamento também é adotado caso o robô detetado esteja a afastar-se,ou caso navegue na mesma direção, mesmo em situações em que a distânciaapresente algum perigo. Se a distância baixar para um valor menor que aprimeira distância de segurança e se o outro robô estiver a aproximar-se,é verificada a direção em que o outro robô se move. Caso ele se esteja amover da esquerda para a direita em relação ao robô que o deteta, é feitoum desvio da direção de navegação para a esquerda. Caso ele se esteja a


mover no sentido contrário, é feito um desvio da direção de navegação paraa direita. Além do desvio da direção de navegação, os robôs também tomama decisão de parar em situações mais perigosas. Caso um robô surja subi-tamente no ângulo de visão do robô que o deteta (i.e. caso não tenha sidodetetado pela câmara nos instantes anteriores) numa zona próxima (menorque a segunda distância de segurança), e caso não esteja a ser realizadonenhum desvio, o robô que o deteta para durante alguns segundos. Casoseja detetada uma distância muito baixa em relação ao outro robô (terceiradistância de segurança), é decidido parar durante alguns segundos, sem sernecessário analisar qualquer tipo de informação.

Na figura 5.7 está representada uma situação em que dois robôs navegamna diagonal, num cenário semelhante ao da figura 5.5. Neste caso, o robôlaranja deteta o outro robô subitamente no seu ângulo de visão e numazona próxima de si, tomando a decisão de parar durante alguns instantespara deixar o robô vermelho afastar-se da zona de perigo. Depois, segue oseu caminho normalmente.

(a) (b)

(c) (d)

Figura 5.7: Robô deteta outro robô através da sua câmara e toma a decisãode parar durante alguns instantes.

O fluxograma da figura 5.8 mostra como as diferentes estratégias sãoescolhidas a partir da informação obtida através da câmara.

Para que seja possível coordenar o movimento de mais do que dois robôsutilizando a câmara de deteção de cores, cada robô deve também pararsempre que mais do que um robô surja no seu ângulo de visão numa zonapróxima de si. Uma dessas situações está representada na figura 5.9. Nessasituação, quatro robôs navegam em direção à mesma zona. Os últimosrobôs a chegar ao cruzamento detetam os outros dois no seu ângulo de visãoe decidem parar até que esses robôs percorram os seus caminhos. Quandoexiste caminho livre, os dois robôs continuam o seu trajeto.


Verificar distância

d < dist. segurança 1


Não

Verificar proximidade

Robô a aproximar-se

Sim

Verificar direção

Esquerda para a direita

Não

Direita para a esquerda

Sim


Não

Verificar de onde surgiu o

robô

Robô surge subitamente no ângulo de visão

SimDesvio para a esquerda

SimDesvio para

a direita

Sim

Não

SimParar durante

alguns segundos

Parar durante alguns

segundosSim

NãoNão

Não

Robô detetado

Sim

Não

Início

Não

Figura 5.8: Fluxograma das estratégias adotadas quando outro robô é de-tetado pela câmara.

5.2 Com comunicação

Para resolver alguns problemas mais complexos, foi decidido implementarmétodos que utilizam comunicação entre robôs. Para ”imitar” essa comuni-cação em robôs virtuais foram usadas algumas técnicas para trocar mensa-gens, como a utilização de sockets ou memória partilhada. Como os métodosdescentralizados são os mais indicados para lidar com uma grande quanti-dade de robôs a operar em simultâneo no mesmo ambiente, optou-se porutilizar um tipo de planeamento priorizado para controlar o movimento dosrobôs.


(a) (b)

(c) (d)

Figura 5.9: Robôs num cruzamento utilizam a câmara de deteção de corespara utilizarem diferentes estratégias para evitar a colisão.

5.2.1 Planeamento priorizado

No planeamento priorizado implementado, cada robô determina o seu cami-nho individualmente. Quanto um deles se torna ativo, envia uma mensagempara todos os robôs que já se encontram operacionais, para indicar que estáprestes a iniciar o seu trajeto. Os outros robôs adicionam-no à lista de robôsativos e enviam-lhe informações sobre o seu caminho e o seu estado atual.Depois de receber informação sobre os caminhos de todos os robôs ativos, orobô inicia o seu trajeto. Cada robô percorre o seu caminho normalmente,recebendo informação constante sobre a posição atual dos robôs com maiorprioridade e parando caso haja perigo de colisão. Desta forma, depois detodos os robôs estarem ativos, cada um deles recebe informações sobre aposição atual dos robôs com maior prioridade e envia esse tipo de informa-ções aos robôs com menor prioridade. Isso significa que o robô com maiorprioridade percorre o seu caminho sem qualquer tipo de consideração pelaposição e caminho dos outros robôs, enquanto que o último robô tem de terem atenção todos os outros e parar sempre que necessário.

As mensagem trocadas entre robôs seguem o formato apresentado natabela 5.1.

A forma como essas mensagens são trocadas pelos robôs está ilustradano fluxograma da figura 5.10.

A figura 5.11 exemplifica uma situação simples em que o planeamentopriorizado pode ser utilizado. Nela estão representados dois robôs e os cami-


Tabela 5.1: Tipos de mensagens trocadas entre robôs.

Tipo Descrição”Ready” Robô está pronto para iniciar o seu trajeto e pretende

receber informações sobre os caminhos dos robôs commaior prioridade.

”Start” Robô recolheu todas as informações necessárias e jáiniciou o seu percurso.

”End” Robô atingiu o fim do seu percurso.”Path” Robô envia o seu caminho a um robô com menor

prioridade que pediu essa informação. Ou então, opercurso do robô teve de ser replaneado e o novocaminho é enviado a todos os robôs com menor

prioridade.”New Step” Robô comunica a sua posição atual aos robôs com uma

prioridade menor que a sua.

nhos que cada um planeia percorrer. Os números dos robôs representam asua prioridade, sendo que o robô 1 é aquele que tem uma maior prioridade.O robô 2, sendo aquele que tem uma menor prioridade neste caso, comparao seu trajeto com o do outro robô. Como existe uma zona próxima em queos caminhos dos dois robôs se cruzam e um conflito é muito provável, o robô2 toma a decisão de parar para permitir ao robô com maior prioridade seguiro seu caminho normalmente até que se afaste da zona de perigo.

Na figura 5.12 está exemplificada uma situação em que três robôs na-vegam coordenadamente dentro do mesmo mapa utilizando o planeamentopriorizado. Neste exemplo, os robôs 1 e 2 iniciam o seu percurso ao mesmotempo, sendo que os números indicam a sua prioridade (o robô 1 é o quetem maior prioridade). Cada um deles segue o seu trajeto normalmente atéà situação ilustrada em 5.12b. Nesse caso, o robô com menor prioridade(robô 2) compara o seu caminho com o primeiro robô e toma a decisãode parar pois deteta uma possível colisão. Essa possibilidade de colisão édetetada pois, comparando os caminhos que ambos planeavam fazer nos pró-ximos instantes, foi possível prever que a distância entre ambos seria menorem relação à distância máxima admitida num determinado instante futuro.Entretanto o robô 3 inicia o seu trajeto. Quando os dois primeiros robôsdeixam de estar a uma distância inferior ao limite máximo, o robô 2 conti-nua o seu trajeto. Ao mesmo tempo, o robô 3 deteta uma possível colisãocom o robô 2 e resolve parar. Quando os robôs 2 e 3 passam a estar a umadistância segura entre si, o robô 3 continua o seu caminho. Depois disto,todos continuam a percorrer normalmente os seus percursos até que novassituações de possível conflito surjam.

A figura 5.13 mostra um teste realizado em que quatro robôs se cru-


Início

Enviar mensagem “Ready” aos robôs

com maior prioridade

Já recebeu o caminho de todos os robôs com maior

prioridade?Sim

Enviar mensagem

“Start”a todos os robôs

Já terminou caminho?

Sim

Fim

Enviar mensagem

“End” a todos os robôs

Não

Enviar mensagem “New Step”

com a posição atual

Os outros robôs enviaram

mensagens?

Sim

Verificar mensagem

Mensagem “Ready”

Não

Mensagem “Start”

Não

Mensagem “New Step”

Mensagem “End”

Sim

Enviar mensagem

“Path” com o caminho total ao outro robô

Sim

Adicionar o outro robô à lista de robôs

ativos

Sim

Verificar se existe

possibilidade de colisão com o

outro robô

Remover o outro robô da lista de robôs

ativos

Não

Sim

Não

Não

Não

Figura 5.10: Fluxograma da comunicação entre robôs durante o planea-mento priorizado.

zam na mesma zona do mapa e pretendem seguir em frente. Os três robôscom menor prioridade detetam a possibilidade de colisão com um ou maisrobôs com menor prioridade e decidem parar. Depois, o robô com maiorprioridade (o da esquerda neste caso) segue o seu percurso fazendo um pe-queno desvio para evitar o robô da direita (ver figura 5.13b). Após isso, osdois robôs seguintes com maior prioridade continuam o seu percurso (verfigura 5.13c). Por último, quando existe caminho livre, o robô com menor


1

2

robô

1

robô

2

Figura 5.11: Robô com menor prioridade compara a sua trajetória com ado outro robô e toma a decisão de parar.

(a) (b)

(c) (d)

Figura 5.12: Trajetos percorridos por três robôs entre os seus pontos iniciale final utilizando o planeamento priorizado.

prioridade continua o seu trajeto.

O caminho percorrido pelos robôs é bastante semelhante ao planeado,tal como demonstra a tabela 5.2. O robô com menor prioridade é aqueleque precisa de fazer um menor desvio em relação ao caminho original, poisapenas avança depois de todos os outros robôs resolverem os seus conflitos.Por outro lado, o tempo que os robôs demoram a percorrer os seus caminhosvaria de acordo com a prioridade dos robôs. O robô com maior prioridadeé aquele que percorre mais rapidamente o percurso previsto, enquanto queo robô com menor prioridade é aquele que demora mais tempo a seguir ocaminho planeado.


(a) (b)

(c) (d)

Figura 5.13: Robôs cruzam-se na mesma zona e seguem o seu percursoutilizando o planeamento priorizado.

Tabela 5.2: Resultados obtidos quando usado o planeamento priorizado nasituação apresentada na figura 5.13.

Robô Distância planeada Distância percorrida Tempo (s)Vermelho 120 140 26Laranja 120 128 45Azul 120 140 45

Castanho 120 122 61

5.3 Discussão dos resultados

O método Cocktail Party é apenas indicado em situações em que não existequalquer risco de conflito entre robôs. A diferenciação entre robôs e ou-tros tipos de obstáculos, por outro lado, possibilita a adoção de pequenasestratégias que evitam com sucesso o conflito em várias situações. Essasestratégias devem ser tomadas de acordo com a situação em questão. Emalguns casos pode ser suficiente mudar a direção de navegação, enquanto quenoutros a melhor solução é parar. Os robôs devem ser capazes de analisar ainformação captada pela câmara e tomar a melhor decisão.


Com a adoção de um planeamento priorizado, são atribuídas prioridadesa cada um dos robôs. Sempre que existe possibilidade de colisão, o robôcom menor prioridade facilita a passagem ao robô com maior prioridade.Por este motivo, o caminho percorrido pelos robôs é bastante semelhanteao planeado, mas o tempo que esses caminhos demoram a ser percorridospode aumentar com a diminuição da prioridade e o aumento do número deconflitos.

A utilização de comunicação permite coordenar os robôs com uma maioreficiência em relação aos dois primeiros métodos, pois cada robô é capazde prever os locais que os outros robôs irão ocupar nos instantes futuros,tomando uma decisão para evitar o conflito caso necessário.


Capítulo 6

Conclusões e TrabalhoFuturo

Nesta dissertação analisaram-se e compararam-se algumas metodologias quepermitem a um conjunto de robôs planear caminhos em ambientes conheci-dos e com obstáculos dinâmicos, semelhantes aos encontrados em superfíciescomerciais.

Em primeiro lugar, descreveu-se a forma como o robô e os obstáculossão definidos no espaço de trabalho durante o planeamento de um caminho.Como é apenas necessário considerar que o robô se move num ambiente aduas dimensões e como se pode assumir que o robô é redondo e pode virarinstantaneamente em qualquer direção, consideraram-se apenas dois grausde liberdade: as coordenadas relativas à posição do robô (x e y). Uma vezque se assume que o robô é redondo, os obstáculos são aumentados de acordocom o seu tamanho, e o robô é tratado como um ponto que se pode moverinstantaneamente em qualquer direção.

De seguida, analisaram-se as vantagens e desvantagens da utilização dediferentes métodos de planeamento de caminhos. Foram analisados não sómétodos determinísticos, que apresentam sempre a mesma solução para asmesmas condições iniciais, mas também métodos probabilísticos, que sãonormalmente mais rápidos mas com uma maior aleatoriedade nas soluçõesencontradas. Um exemplo de método determinístico é a utilização de al-goritmos de busca a partir de um ambiente decomposto em células ou re-presentado por um método roadmap, enquanto que o algoritmo RRT e osPRMs são exemplos de métodos probabilísticos. Além disso foram estudadosmétodos locais, que utilizam informação sensorial para reagirem a obstácu-los desconhecidos. Os algoritmos Bug e o método dos atratores dinâmicossão exemplos desse tipo de métodos. Por último, foram também analisa-das formas de lidar com situações em que existem vários robôs a navegarem simultâneo no mesmo ambiente, através de métodos que não utilizamcomunicação entre robôs, mas também de métodos descentralizados e cen-

83

CAPÍTULO 6. CONCLUSÕES E TRABALHO FUTURO 84

tralizados.A partir desse estudo, foram selecionados e implementados alguns méto-

dos para simular o comportamento dos robôs. Para representar o ambienteselecionou-se o método aproximado de decomposição por células, devido àsua simplicidade de implementação e à fácil atualização do mapa em casode alterações no ambiente. Este método decompõe o ambiente em célulasde igual tamanho. Como a partir dessa representação do mapa, é necessárioencontrar um conjunto de células adjacentes entre os pontos inicial e final,foram também testados alguns algoritmos de busca, como o algoritmo deDikstra, o A* e o D* Lite. O algoritmo A*, juntamente com a distânciade Manhattan como custo heurístico para estimar a distância à célula final,foi o escolhido para gerar caminhos em ambientes semelhantes aos de umsupermercado, mesmo nos casos em que existem obstáculos dinâmicos. Apartir do caminho gerado pelos algoritmos de busca, o robô segue o caminhoplaneado através do uso do método dos atratores dinâmicos. A utilizaçãodeste método permite suavizar o caminho percorrido pelo robô. Por essemotivo, o trajeto percorrido é semelhante e suave com diferentes resoluçõesdo mapa, concluindo-se que é desnecessário utilizar resoluções do ambientedemasiado elevadas, pois a melhoria nos resultados obtidos não é sufici-ente para compensar o aumento dos custos computacionais. Por último,para permitir a cada robô seguir o seu caminho de forma coordenada como dos outros robôs, testou-se com maior detalhe o método Cocktail Party,a utilização da câmara para diferenciar os robôs de outros obstáculos, e umplaneamento priorizado. O primeiro apenas deve ser usado em situaçõesem que não há risco de conflitos entre robôs, enquanto que os dois últimospermitem resolver conflitos de uma forma bastante mais eficiente. Para umaimplementação final, optou-se por utilizar o planeamento priorizado.

Como trabalho futuro, pretende-se fazer algumas melhorias ao sistemaimplementado. Neste momento, cada robô tem uma representação do am-biente que inclui o mapa original e os obstáculos por si detetados. O idealseria ter um mapa geral, construído em simultâneo por todos os robôs. Ou-tra forma mais robusta de fazer o mapeamento, seria fazer a deteção dosobstáculos por um agente externo aos robôs, embora isso pudesse ser maiscomplicado de transportar para um sistema real. Por exemplo, um conjuntode câmaras poderia filmar o ambiente de uma perspetiva superior e atualizaro mapa permanentemente. Dessa forma, seria mais fácil estimar quais aszonas mais (ou menos) congestionadas do mapa.

No planeamento priorizado, a forma como a ordem de prioridades é atri-buída aos robôs pode ser melhorada. Neste momento, cada robô tem umaprioridade pré-definida. O objetivo no futuro é permitir que a ordem deprioridades seja alterada dinamicamente, de forma a melhorar as soluçõesencontradas, pois a ordem de prioridades é muito importante para que asmelhores soluções sejam encontradas.

O comportamento dos robôs foi testado através de simulações. Essas si-

CAPÍTULO 6. CONCLUSÕES E TRABALHO FUTURO 85

mulações foram realizadas com condições ideais (i.e. sem ruído nos sensorese outros fatores prejudicais). Como trabalho futuro, pretende-se fazer testesem robôs reais. Para isso, alguns métodos podem necessitar de sofrer ligeirasalterações para reagirem da melhor à maior imprevisibilidade dos ambien-tes reais em relação aos ambientes de simulação. Além disso, as simulaçõesforam realizadas robôs aproximadamente redondos e com dimensões relati-vamente reduzidas, enquanto que os ambientes-alvo irão exigir robôs commaiores dimensões capazes de transportar um grande volume de cargas.


Capítulo 7

Bibliografia

[1] I. F. of Robotics, “World robotics 2014 service robots.” http://www.ifr.org/service-robots/statistics/, 2014. [Online; accessed 16-October-2014].

[2] iRobot, “irobot roomba vacuum cleaning robot.” http://www.irobot.com/For-the-Home/Vacuum-Cleaning/Roomba.aspx, 2014. [Online;accessed 28-October-2014].

[3] Honda, “Say hello to miimo.” http://honda.co.uk/garden/miimo/,2014. [Online; accessed 28-October-2014].

[4] I. Spectrum, “Panasonic revives hospital delivery robot.” http://spectrum.ieee.org/automaton/robotics/medical-robots/panasonic-hospital-delivery-robot, 2014. [Online; accessed28-October-2014].

[5] E. Guizzo, “How googles self-driving car works,” IEEE Spectrum On-line, October, vol. 18, 2011.

[6] J. Leitner, “Multi-robot cooperation in space: A survey,” in Advan-ced Technologies for Enhanced Quality of Life, 2009. AT-EQUAL’09.,pp. 144–151, IEEE, 2009.

[7] S. Al-Hasan and G. Vachtsevanos, “Intelligent route planning for fastautonomous vehicles operating in a large natural terrain,” Robotics andautonomous systems, vol. 40, no. 1, pp. 1–24, 2002.

[8] S. Thrun, M. Montemerlo, H. Dahlkamp, D. Stavens, A. Aron, J. Die-bel, P. Fong, J. Gale, M. Halpenny, G. Hoffmann, et al., “Stanley: Therobot that won the darpa grand challenge,” Journal of field Robotics,vol. 23, no. 9, pp. 661–692, 2006.

[9] I. Ainsworth, M. Ristic, and D. Brujic, “CAD-based measurement pathplanning for free-form shapes using contact probes,” The International

87

CAPÍTULO 7. BIBLIOGRAFIA 88

Journal of Advanced Manufacturing Technology, vol. 16, no. 1, pp. 23–31, 2000.

[10] J. Cortés, T. Siméon, V. R. De Angulo, D. Guieysse, M. Remaud-Siméon, and V. Tran, “A path planning approach for computinglarge-amplitude motions of flexible molecules,” Bioinformatics, vol. 21,no. suppl 1, pp. i116–i125, 2005.

[11] J. Laird and M. VanLent, “Human-level AI’s killer application: Inte-ractive computer games,” AI magazine, vol. 22, no. 2, p. 15, 2001.

[12] J.-C. Latombe, Robot Motion Planning. Kluwer Academic Publishers,1991.

[13] M. Tarokh, “Hybrid intelligent path planning for articulated rovers inrough terrain,” Fuzzy Sets and Systems, vol. 159, no. 21, pp. 2927–2937,2008.

[14] L. C. Wang, S. Y. Lim, and V. Ang, “Hybrid of global path planning andlocal navigation implemented on a mobile robot in indoor environment,”in Intelligent Control, 2002. Proceedings of the 2002 IEEE InternationalSymposium on, pp. 821–826, IEEE, 2002.

[15] H.-P. Huang and S.-Y. Chung, “Dynamic visibility graph for path plan-ning,” in Intelligent Robots and Systems, 2004.(IROS 2004). Procee-dings. 2004 IEEE/RSJ International Conference on, vol. 3, pp. 2813–2818, IEEE, 2004.

[16] P. Bhattacharya and M. L. Gavrilova, “Roadmap-based path planning-Using the Voronoi diagram for a clearance-based shortest path,” Robo-tics & Automation Magazine, IEEE, vol. 15, no. 2, pp. 58–66, 2008.

[17] F. Lingelbach, “Path planning using probabilistic cell decomposition,”in Robotics and Automation, 2004. Proceedings. ICRA’04. 2004 IEEEInternational Conference on, vol. 1, pp. 467–472, IEEE, 2004.

[18] S. Kambhampati and L. S. Davis, “Multiresolution path planning formobile robots,” tech. rep., DTIC Document, 1985.

[19] J. Barraquand, B. Langlois, and J.-C. Latombe, “Numerical potentialfield techniques for robot path planning,” Systems, Man and Cyberne-tics, IEEE Transactions on, vol. 22, no. 2, pp. 224–241, 1992.

[20] P. Raja and S. Pugazhenthi, “Optimal path planning of mobile robots:A review,” International Journal of Physical Sciences, vol. 7, no. 9,pp. 1314–1320, 2012.


[21] J. A. Sethian, Level set methods and fast marching methods: evolvinginterfaces in computational geometry, fluid mechanics, computer vision,and materials science, vol. 3. Cambridge university press, 1999.

[22] S. Garrido, L. Moreno, and D. Blanco, “Voronoi diagram and fastmarching applied to path planning,” in Robotics and Automation,2006. ICRA 2006. Proceedings 2006 IEEE International Conferenceon, pp. 3049–3054, IEEE, 2006.

[23] A. Valero-Gomez, J. V. Gomez, S. Garrido, and L. Moreno, “Fast mar-ching methods in path planning,” IEEE Robotics and Automation Ma-gazine, no, 2013.

[24] R. Geraerts, Sampling-based motion planning: Analysis and path qua-lity. PhD thesis, Utrecht University, 2006.

[25] M. Brand, M. Masuda, N. Wehner, and X.-H. Yu, “Ant colony op-timization algorithm for robot path planning,” in Computer Designand Applications (ICCDA), 2010 International Conference on, vol. 3,pp. V3–436, IEEE, 2010.

[26] H. Burchardt and R. Salomon, “Implementation of path planning usinggenetic algorithms on mobile robots.,” in IEEE Congress on Evolutio-nary Computation, pp. 1831–1836, 2006.

[27] O. Castillo, L. Trujillo, and P. Melin, “Multiple objective genetic algo-rithms for path-planning optimization in autonomous mobile robots,”Soft Computing, vol. 11, no. 3, pp. 269–279, 2007.

[28] A. Z. Nasrollahy and H. Javadi, “Using particle swarm optimization forrobot path planning in dynamic environments with moving obstaclesand target,” in Computer Modeling and Simulation, 2009. EMS’09.Third UKSim European Symposium on, pp. 60–65, IEEE, 2009.

[29] L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Pro-babilistic roadmaps for path planning in high-dimensional configura-tion spaces,” Robotics and Automation, IEEE Transactions on, vol. 12,no. 4, pp. 566–580, 1996.

[30] S. M. LaValle, “Rapidly-exploring random trees: A new tool for pathplanning,” Tech. Rep. 98-11, Computer Science Dept., Iowa State Uni-versity, Oct. 1998.

[31] S. Karaman and E. Frazzoli, “Sampling-based algorithms for opti-mal motion planning,” The International Journal of Robotics Research,vol. 30, no. 7, pp. 846–894, 2011.

[32] S. M. LaValle, Planning algorithms. Cambridge university press, 2006.


[33] E. W. Dijkstra, “A note on two problems in connexion with graphs,”Numerische mathematik, vol. 1, no. 1, pp. 269–271, 1959.

[34] P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for theheuristic determination of minimum cost paths,” Systems Science andCybernetics, IEEE Transactions on, vol. 4, no. 2, pp. 100–107, 1968.

[35] A. Stentz, “Optimal and efficient path planning for partially-knownenvironments,” in Robotics and Automation, 1994. Proceedings., 1994IEEE International Conference on, pp. 3310–3317, IEEE, 1994.

[36] D. E. Knuth, Sorting and Searching (The Art of Computer Program-ming volume 3). Addison-Wesley, Reading, Mass, 1973.

[37] A. Stentz, “The focussed dˆ* algorithm for real-time replanning,” inIJCAI, vol. 95, pp. 1652–1659, 1995.

[38] S. Koenig and M. Likhachev, “D* lite.,” in AAAI/IAAI, pp. 476–483,2002.

[39] J. Carsten, A. Rankin, D. Ferguson, and A. Stentz, “Global path plan-ning on board the mars exploration rovers,” in Aerospace Conference,2007 IEEE, pp. 1–11, IEEE, 2007.

[40] S. Koenig and M. Likhachev, “Incremental a*.,” in NIPS, pp. 1539–1546, 2001.

[41] V. J. Lumelsky and A. A. Stepanov, “Path-planning strategies for apoint mobile automaton moving amidst unknown obstacles of arbitraryshape,” Algorithmica, vol. 2, no. 1-4, pp. 403–430, 1987.

[42] I. Kamon, E. Rivlin, and E. Rimon, “A new range-sensor based globallyconvergent navigation algorithm for mobile robots,” in Robotics andAutomation, 1996. Proceedings., 1996 IEEE International Conferenceon, vol. 1, pp. 429–435, IEEE, 1996.

[43] E. Bicho, Dynamic Approach to Behavior-Based Robotics: design, spe-cification, analysis, simulation and implementation. Shaker Verlag, Aa-chen, 2000.

[44] G. Sanchez and J.-C. Latombe, “Using a prm planner to comparecentralized and decoupled planning for multi-robot systems,” in Robo-tics and Automation, 2002. Proceedings. ICRA’02. IEEE InternationalConference on, vol. 2, pp. 2112–2119, IEEE, 2002.

[45] S. M. LaValle and S. A. Hutchinson, “Optimal motion planning formultiple robots having independent goals,” Robotics and Automation,IEEE Transactions on, vol. 14, no. 6, pp. 912–925, 1998.


[46] V. J. Lumelsky and K. Harinarayan, “Decentralized motion planning formultiple mobile robots: The cocktail party model,” in Robot colonies,pp. 121–135, Springer, 1997.

[47] S. Kato, S. Nishiyama, and J. Takeno, “Coordinating mobile robots byapplying traffic rules.,” in IROS, pp. 1535–1541, 1992.

[48] J. Peng and S. Akella, “Coordinating multiple robots with kinodyna-mic constraints along specified paths,” The International Journal ofRobotics Research, vol. 24, no. 4, pp. 295–310, 2005.

[49] T. Siméon, S. Leroy, and J.-P. Lauumond, “Path coordination for mul-tiple mobile robots: a resolution-complete algorithm,” Robotics andAutomation, IEEE Transactions on, vol. 18, no. 1, pp. 42–49, 2002.

[50] Y. Guo and L. E. Parker, “A distributed and optimal motion plan-ning approach for multiple mobile robots,” in Robotics and Automation,2002. Proceedings. ICRA’02. IEEE International Conference on, vol. 3,pp. 2612–2619, IEEE, 2002.

[51] M. Bennewitz, W. Burgard, and S. Thrun, “Optimizing schedules forprioritized path planning of multi-robot systems,” in Robotics and Auto-mation, 2001. Proceedings 2001 ICRA. IEEE International Conferenceon, vol. 1, pp. 271–276, IEEE, 2001.

[52] M. Bonert, L. Shu, and B. Benhabib, “Motion planning for multi-robotassembly systems,” International Journal of Computer Integrated Ma-nufacturing, vol. 13, no. 4, pp. 301–310, 2000.

[53] A. M. Community, “Mobilesim.” http://robots.mobilerobots.com/wiki/MobileSim/, 2014. [Online; accessed 10-July-2014].

[54] O. Michel, “Webots: Symbiosis between virtual and real mobile robots,”in Virtual Worlds, pp. 254–263, Springer, 1998.

[55] B. Gerkey, R. T. Vaughan, and A. Howard, “The player/stage project:Tools for multi-robot and distributed sensor systems,” in Proceedings ofthe 11th international conference on advanced robotics, vol. 1, pp. 317–323, 2003.


Anexo A

Algoritmos

A.1 Algoritmo de DijkstraO algoritmo de Dijkstra é um algoritmo de busca bastante utilizado paraencontrar o caminho mais curto entre dois pontos, tal como explicado nocapítulo 2.6.1.

O pseudocódigo apresentado utiliza uma lista inicialmente composta portodos os nós do mapa (Q). Esses nós são marcados como não visitados e adistância de cada nó ao nó inicial é desconhecida. Q.minimum() procura onó u no conjunto de nós Q que tem o menor valor dist[u], ou seja, o nó nãovisitado que tem a menor distância em relação ao nó inicial (na primeiraiteração, esse nó é o nó inicial). A variável alt armazena a distância docaminho entre o nó inicial e o nó u, somada à distância lenght(u, v), querepresenta a distância entre os nós vizinhos u e v. Se essa distância formenor em relação à distância mínima conhecida até ao nó v, então dist[v] éatualizado com esse valor. Ao mesmo tempo, no vetor previous vão sendoguardados o conjunto de nós que devem ser percorridos a partir do nó inicialpara atingir o caminho mais curto conhecido.

Algoritmo 1 Algoritmo de Dijkstra.1: procedure DijkstraSearch(Graph, source)2: dist[source]=03: for all (node v in Graph) do4: if (v 6= source) then5: dist[v] = ∞6: add [v] to queue Q7: while (Q is not empty) do8: u=Q.minimum()9: Remove u from Q

10: for all (neighbor v of u) do

93

ANEXO A. ALGORITMOS 94

11: alt=dist[u]+lenght(u, v)12: if (alt < dist[v]) then13: dist[v]=alt14: previous[v]=u15: return dist[], previous[]

A.2 Algoritmo A*O algoritmo A* é um algoritmo simples e eficaz para encontrar um caminhoentre dois pontos, sendo por isso um dos mais utilizados, tal como explicadono capítulo 2.6.2.

No pseudocódigo apresentado, é mostrado que este algoritmo utiliza duaslistas: a lista de prioridades open com os nós que ainda devem ser analisados,ordenados pela sua prioridade, e a lista closed com os nós que já foramanalisados. Inicialmente, as duas listas estão vazias. O algoritmo começapor adicionar o nó inicial s à lista open e calcula os seus valores g e h.Esses valores são a distância real em relação ao nó inicial e a distânciaestimada em relação ao nó final, respetivamente. Para esse primeiro nó, adistância g é 0, enquanto que a distância estimada ao nó final é dada porGoalDistEstimate(s). A soma desses dois valores permite obter o valorf , que representa a prioridade do nó (quando menor o valor f , maior aprioridade do nó). A cada iteração, o algoritmo remove o nó u com o menorvalor f da lista de nós em aberto (na primeira iteração, esse nó é o nó inicial)e analisa cada vizinho desse nó. A variável newg armazena a distância docaminho entre o nó inicial e o nó u, somada à distância cost(u, v), querepresenta a distância entre os nós vizinhos u e v. Se essa distância formenor em relação à distância mínima conhecida até ao nó v, então o valorg desse nó é atualizado, e um novo valor f é calculado. De seguida, o nó ué removido da lista open e o nó v é inserido nessa lista. O algoritmo repeteo processo até que o nó final seja encontrado, ou até que a lista open fiquevazia.

Algoritmo 2 Algoritmo A*.1: procedure AStarSearch2: s.g = 03: s.h = GoalDistEstimate(s)4: s.f = s.g + s.h5: s.parent = null6: push s on Open7: while Open is not empty do8: pop node u from Open9: if u is a goal node then


10: construct path11: return success12: else13: for all successor v of u do14: newg = u.g+cost(u, v)15: if (v is not in Open or Closed) OR (newg < v.g) then16: v.parent = u17: v.g = newg18: v.h = GoalDistEstimate(v)19: v.f = v.g + v.h20: if v is in Closed then21: remove if from Closed22: if v is not yet in Open then23: push v on Open24: push u onto Closed25: return failure // if no path found

A.3 Algoritmo LPA*O algoritmo LPA* baseia-se no algoritmo A*, adaptando-o para ser usadoem ambientes dinâmicos. Este algoritmo é analisado no capítulo 2.6.3.

No pseudocódigo apresentado, Succ(s) representa o conjunto de nós-filhodo nó atual s, enquanto que Pred(s) representa o conjunto de nós-pai do nóatual s. c(s, s′), por sua vez representa o custo do movimento entre os nósadjacentes s e s′. Este custo pode variar entre 0, quando existe caminho livreentre os dois nós, e∞, quando um obstáculo obstrói a passagem entre os dois.h(s, sgoal) permite estimar a distância de um nó s ao nó final. O algoritmoinicia-se com a lista de prioridades U vazia. O nó inicial é inicialmente oúnico nó localmente inconsistente e é inserido na lista de prioridades U . Naprimeira vez que é executado, ComputeShortestPath() gera um caminho deforma semelhante ao que acontece no algoritmo A*. Depois, quando existemalterações no custo de algum nó, a função UpdateV ertex() é chamada paraatualizar os valores rhs(s) e as keys dos nós alterados. Caso esses nós setenham tornado localmente consistentes ou inconsistentes (g(u) 6= rhs(u)),a sua posição na lista U é atualizada. ComputeShortestPath() expanderepetidamente nós localmente inconsistentes pela sua ordem de prioridades.Essa expansão é realizada até que sgoal seja localmente consistente e a chavedo próximo nó na lista U seja menor que a chave de sgoal. No final, umcaminho é encontrado a partir de sgoal, percorrendo os nós que minimizemg(s′) + c(s, s′) até que sstart seja atingido.


Algoritmo 3 Algoritmo LPA*.procedure CalculateKey(s)

return[min(g(s),rhs(s))+(h(s,sgoal)); min(g(s),rhs(s))]procedure Initialize()

U = ∅for all s ∈ S do

rhs(s) = g(s) =∞rhs(sstart) = 0;U.Insert(sstart, CalculateKey(sstart));

procedure UpdateVertex(u)if (u 6= sstart) then

rhs(u)=min(s′ ∈ Pred(u)(g(s′) + c(s′, u)))if (u ∈ U) then

U.Remove(u)if (g(u) 6= rhs(u)) then

U.Insert(u, CalculateKey(u))procedure ComputeShortestPath()

while ((U.TopKey()<CalculateKey(sgoal)) OR (rhs(sstart) 6= g(sgoal)))do

u= U.Pop()if (g(u) > rhs(u)) then

g(u) = rhs(u)for all (s ∈ Succ(u)) do

UpdateVertex(s)else

g(u) =∞for all ((s ∈ Succ(u)) OR {u} ) do

UpdateVertex(s)procedure Main()

Initialize()while (1) do

ComputeShortestPath();Wait for changes in edge costs;for all for all directed edges (u, v) with changed costs do

Update the edge cost c(u, v);UpdateVertex(v);


A.4 Algoritmo D* LiteO algoritmo D* Lite foi criado a partir do algoritmo LPA*, com o objetivode eliminar algumas fraquezas deste último, tal como analisado no capítulo2.6.3.

O pseudocódigo do algoritmo D* Lite é semelhante ao pseudocódigodo algoritmo LPA* apresentado em A.3. As alterações deste algoritmo emrelação ao algoritmo LPA* visam permitir uma melhor reação a mudançasno nó inicial. Por esse motivo, sstart representa a posição atual do robô e,por isso, está em constante mudança. Para se adaptar a essas mudanças, oalgoritmo utiliza um novo valor, km, que é alterado de acordo com o trajetojá percorrido pelo robô: km = km +h(slast, sstart), em que slast representa aúltima posição ocupada pelo robô.

Algoritmo 4 Algoritmo D* Lite.1: procedure CalculateKey(s)2: return[min(g(s),rhs(s))+(h(sstart,s))+km; min(g(s),rhs(s))]3: procedure Initialize()4: U = ∅5: km = 06: for all s ∈ S do7: rhs(s) = g(s) =∞8: rhs(sgoal) = 0;9: U.Insert(sgoal, [h(sstart, sgoal); 0]])

10: procedure UpdateVertex(u)11: if ((g(u) 6= rhs(u)) AND (u ∈ U)) then12: U.Update(u,CalculateKey(u))13: else14: if ((g(u) 6= rhs(u)) AND (u 6∈ U)) then15: U.Insert(u,CalculateKey(u))16: else17: if ((g(u) = rhs(u)) AND (u ∈ U)) then18: U.Remove(u)19: procedure ComputeShortestPath()20: while ((U.TopKey()<CalculateKeysstart) OR (rhs(sstart) > g(sstart)))

do21: u= U.Top;22: kold= U.TopKey();23: knew= CalculateKey(u);24: if (kold < knew) then25: U.Update(u, knew)


26: else27: if (g(u) > rhs(u)) then28: g(u) = rhs(u)29: U.Remove(u)30: for all (s ∈ Pred(u)) do31: if (s 6= sgoalrhs(s)) then32: min(rhs(s), c(s, u) + g(u))33: UpdateVertex(s)34: else35: gold = g(u)36: g(u) =∞37: for all ((s ∈ Pred(u)) OR {u}) do38: if (rhs(s) = c(s, u) + gold) then39: if (s 6= sgoal) then40: rhs(s)=mins′ ∈ Succ(s)(c(s, s′) + g(s′))41: UpdateVertex(s)42: procedure Main()43: slast = sstart

44: Initialize()45: ComputeShortestPath()46: while (sstart 6= sgoal) do47: sstart=argmin (s′ ∈ Succ(sstart)(c(sstart, s

′) + g(s′)))48: Move to sstart

49: Scan graph for changed edge costs50: if any edge cost changed then51: km = km + h(slast, sstart)52: slast = sstart

53: for all for all directed edges (u, v) with changed costs do54: cold = c(u, v)55: Update the edge cost c(u, v)56: if (cold > c(u, v)) then57: if (u 6= sgoal) then58: rhs(u) =min ((rhs(u), c(u, v) + g(v)))59: else60: if (rhs(u) = cold + g(v)) then61: if (u 6= sgoal) then62: rhs(u) =min s′ ∈ Succ(u)(c(u, s′) + g(s′))63: UpdateVertex(u)64: ComputeShortestPath()

Documents

Mauro Filipe Rodrigues Queirósintranet.dei.uminho.pt/gdmi/galeria/temas/pdf/40523.pdf · Mauro Filipe Rodrigues Queirós Planeamento de Caminhos para Robôs Móveis Autónomos em