%pdflatex -synctex=1 -interaction=nonstopmode %.tex
% uaThesis example (for a thesis written in Portuguese)
%
% the complete list of options and commands can be found in uaThesis.sty 
%

\documentclass[11pt,twoside,a4paper]{report}
\usepackage[DEM,newLogo]{uaThesis}
%encoding
%--------------------------------------
\usepackage[latin1]{inputenc} 
%%%%\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%--------------------------------------
 
%Portuguese-specific commands
%--------------------------------------
\usepackage[portuguese]{babel}
%--------------------------------------

%Hyphenation rules
%--------------------------------------
\usepackage{hyphenat}
\hyphenation{mate-mática recu-perar}
%--------------

%Sections Numbering rule
%--------------------------------------
%\setcounter{secnumdepth}{4}
%--------------------------------------

%Svg Stuff
%--------------------------------------
\usepackage{svg}                   %to include directly svg graphics.
\setsvg{inkscape=inkscape -z -D}   %Options to invoke inkscape (assuming inkspace is in the PATH)
\setsvg{svgpath=Imagens/}           %Or any other path where SVG images are
%--------------------------------------

%\usepackage[backend=bibtex]{biblatex}
  \usepackage[
    backend=bibtex,
    style=ieee,
  ]{biblatex}

\addbibresource{bibliografie.bib}
%--------------------------------------



\def\ThesisYear{2015}




% custom macros
\def\I{\mathtt{i}}
\def\Exp#1{e^{2\pi\I #1}} % argument inside braces, i.e., "{}"
\def\EXP#1.{e^{2\pi\I #1}} % argument finishes when a full stop is encountered, i.e., "."

% optional: visual delimiters for floats (figures and tables)
\def\topfigrule{\kern 7.8pt \hrule width\textwidth\kern -8.2pt\relax}
\def\dblfigrule{\kern 7.8pt \hrule width\textwidth\kern -8.2pt\relax}
\def\botfigrule{\kern -7.8pt \hrule width\textwidth\kern 8.2pt\relax}


\begin{document}

%
% Cover page (use only one of the first two \TitlePage)
%

% First alternative, with a figure
\TitlePage
  %\GRID  % for debugging ONLY
  \HEADER{\BAR\FIG{\includegraphics[height=60mm]{uaLogoNew}}} % the \FIG{} is optional
         {\ThesisYear}
  \TITLE{Miguel \newline da Mota Rodrigues}
        {Mapas de navegabilidade para condução autónoma no Campus UA}
\EndTitlePage
\titlepage\ \endtitlepage % empty page

%
% First thesis pages
%

\TitlePage
  \HEADER{}{\ThesisYear}
  \TITLE{Miguel \newline da Mota Rodrigues}
        {Mapas de navegabilidade para condução autónoma no Campus UA}
  \vspace*{15mm}
  \TEXT{}
       {Dissertação apresentada à Universidade de Aveiro para cumprimento dos
requisitos necessários à obtenção do grau de Mestrado em Engenharia Mecânica, realizada sob a orientação científica de Vitor Manuel Ferreira dos
Santos, Professor Associado do Departamento de Engenharia Mecânica da Universidade de Aveiro.}
\EndTitlePage
\titlepage\ \endtitlepage % empty page

\TitlePage
  \vspace*{55mm}
  \TEXT{\textbf{o j\'uri~/~the jury\newline}}
       {}
  \TEXT{presidente~/~president}
       {\textbf{Professor Doutor Jorge Augusto Fernandes Ferreira}\newline {\small
        Professor Auxiliar da Universidade de Aveiro - Departamento de Engenharia \\Mecânica}}
  \vspace*{5mm}
  \TEXT{vogais~/~examiners committee}
       {\textbf{Professor Doutor Vitor Manuel Ferreira dos Santos}\newline {\small
        Professor Associado da Universidade de Aveiro - Departamento de Engenharia \\Mecânica (orientador)}}
  \vspace*{5mm}
  \TEXT{}
       {\textbf{Professor Doutor Carlos Baptista Cardeira}\newline {\small
        Professor Auxiliar da Universidade de Lisboa - Instituto Superior Técnico }}
\EndTitlePage
\titlepage\ \endtitlepage % empty page

\TitlePage
  \vspace*{55mm}
  \TEXT{\textbf{agradecimentos~/\newline acknowledgements}}
       {\\Gostava de deixar aqui os meus mais sinceros agradecimentos ao Professor Doutor Vitor Santos e ao Doutor Ricardo Pascoal, pela orientação, o entusiasmo e motivação que sempre me transmitiram ao longo desta dissertação.
       Um especial agradecimento a Jorge Almeida e a João Torrão pelo apoio e troca de opiniões essenciais ao desenvolvimento deste projecto.  
       Agradeço ainda à minha namorada Bárbara Pereira, por todo o apoio, compreensão e paciência que teve para comigo.  
       Aos meus colegas que partilharam o Laboratório de Automação e Robótica ao longo destes meses, pela boa disposição e pelos momentos de descontração proporcionados. 
       Finalmente, quero deixar um agradecimento a toda a minha família.}
\EndTitlePage
\titlepage\ \endtitlepage % empty page

\TitlePage
\vspace*{55mm}
\TEXT{\textbf{Palavras-Chave}}
{Grupo Atlas; GPS; ROS; Nuvem de Pontos; Varrimento Laser; Navegabilidade; Reconstrução 3D.}
  \TEXT{\textbf{Resumo}}
       {Este trabalho propõe um sistema para levantamento e avaliação da navegabilidade de uma zona de interesse. Numa primeira fase, usando o robô Atlas2000 pertencente ao grupo Atlas, do Laboratório de Automação e Robótica (LAR) do Departamento de Engenharia Mecânica (DEM) da Universidade de Aveiro, é realizado o levantamento da nuvem de pontos com o auxílio de dois lasers 2D. Um dos lasers realiza um varrimento horizontal para obter uma nuvem de pontos de obstáculos positivos, nomeadamente postes, bancos, entre outros. O segundo laser, com um varrimento num plano inclinado, realiza uma reconstrução 3D da área de passagem, com a acumulação de nuvens de pontos. Posteriormente, será possível realizar uma avaliação do local de passagem para verificar a possibilidade de navegabilidade do veículo. Finalmente, estando a fase anterior concluída, é criada uma representação da navegabilidade num formato possível de visualizar como uma camada no GoogleMaps.}
\EndTitlePage
\titlepage\ \endtitlepage % empty page

\TitlePage
  \vspace*{55mm}
  \TEXT{\textbf{Keywords}}
{Atlas Group; GPS; ROS; Pointcloud; Laser scan; ; 3D Reconstruction.}
  \TEXT{\textbf{Abstract}}
       {This work proposes a system that will be surveying and evaluating an area
of interest.
In a first phase, using the robot Atlas 2000 that belongs to the research
and development team Atlas, of the Automation and Robotics Laboratory
from the Mechanical Engineering Department at Aveiro University, a survey
is obtained using two 2D lasers. One of the lasers by doing an horizontal scan
obtains a pointcloud in which if is possible to detect the positive obstacles, like
benchs, poles and others. The second laser, with an inclined scan, makes
a 3D reconstruction that is obtained by the accumulation of several lasers
scans.
In the second stage if is possible to evaluate the area of interest that the
Atlas2000 will be passing through and determine if the area is
navigable or not.
Finally a file will be created with the final representation that can be
visualized in GoogleMaps.}
\EndTitlePage
\titlepage\ \endtitlepage % empty page


%
% Tables of contents, of figures, ...
%

\pagenumbering{roman}
\tableofcontents

\cleardoublepage
\listoffigures

\cleardoublepage
\listoftables


% The chapters (usually written using the isolatin font encoding ...)

\cleardoublepage
\pagenumbering{arabic}

\chapter{Introdu\c c\~ao}

\section{Enquadramento e Descrição do Problema}
\label{sec:EnquadramentoDescricao}
Esta dissertação enquadra-se na \'area de condu\c c\~ao aut\'onoma do Laborat\'orio de Automa\c c\~ao e Rob\'otica, do Departamento de Engenharia Mec\^anica da Universidade de Aveiro.

A existência de condu\c c\~ao aut\'onoma pressupõe, entre outras coisas, saber-se onde \'e poss\'ivel um veículo navegar. Para condu\c c\~ao em estradas públicas destinadas ao tráfego automóvel, os mapas proporcionados pela Google são adequados como base de trabalho, mas para condu\c c\~ao em outras \'areas, e.g., em campus universit\'arios ou em zonas privadas de empresas, isso n\~ao \'e poss\'ivel.

Tornou-se necessária a existência de uma ferramenta que possibilita a cria\c c\~ao de mapas onde conste informação sobre certas \'areas, fora das estradas públicas destinadas ao tráfego automóvel, que permita inferir se são compatíveis com a realização de rotas para a navega\c c\~ao aut\'onoma de veículos. Com isto torna-se poss\'ivel o planeamento de visitas guiadas sem condutores e transporte automático em áreas privadas.
Neste projeto é necessário fazer-se o levantamento tridimensional de um espaço e para tal há que efetuar a aquisição e análise de dados provenientes de vários equipamentos. A plataforma para recolha de dados consiste no veículo robótico Atlas 2000 em modo de teleoperação. Já existem muitos desenvolvimentos nesta área, mas um sistema que engloba todas as partes necessárias para a construção de mapas de navegabilidade ainda não está disponível. Como referido anteriormente, é necessário recolher, avaliar e representar dados vindos de vários sensores para:
\begin{itemize}
\item Deteção de obstáculos positivos como, por exemplo, postes e bancos de jardim;
\item Deteção de obstáculos negativos como, por exemplo, ravinas e desníveis de pavimento;
\end{itemize}

\section{Projeto ATLAS}

\subsection{Introdução ao Projecto}
O robô utilizado nesta dissertação, nomeadamente o Atlas 2000, foi desenvolvido no contexto do projeto ATLAS. Este projeto foi criado com o objetivo de participar em competições nacionais de condução autónoma, no qual, por várias vezes, alcançou o primeiro e segundo lugar. Os dois robôs que participavam nestas competições denominam-se de Atlas 2000 e Atlas MV apresentados na figura \ref{fig:figura1.1} e \ref{fig:figura1.2}, respetivamente.
\begin{figure} [H]
\center
\subfloat[Atlas 2000]{\label{fig:figura1.1}\includegraphics[height=5cm]{Figura1}}
\qquad
\centering
\subfloat[Atlas MV]{\label{fig:figura1.2}\includegraphics[height=5cm]{Figura2}}
\caption{Robôs para competição de condução autónoma do projeto ATLAS}
\label{fig:figura1} 

\end{figure}

\subsection{Atlas 2000}
O Atlas 2000 sofreu, ao longo do tempo, várias alterações. Inicialmente a sua estrutura estava preparada para as competições de navegação \textit{indoors}, mas devido a uma intervenção anteriormente executada por Eugénio Costa~\autocite{dacostanavegacao}, este passou a poder navegar em ambientes exteriores. As intervenções ocorreram nas seguintes frentes:
\begin{itemize}
\item \textbf{Rodas} - Troca das rodas para pista de velocidade de escala 1:4 para umas rodas com pneu pneumático regulável de 8 polegadas de diâmetro, representadas na figura \ref{fig:figura2.1} e \ref{fig:figura2.2} respetivamente.
\begin{figure} [H]
\center
\subfloat[Rodas para pista de velocidade]{\label{fig:figura2.1}\includegraphics[height=5cm]{Figura3v3}}
\qquad
\centering
\subfloat[Rodas com pneu pneumático]{\label{fig:figura2.2}\includegraphics[height=5cm]{Figura4}}
\caption{Troca de rodas para uso do Atlas 2000 em \textit{outdoors}}
\label{fig:figura2} 

\end{figure}


\item \textbf{Receptor GPS} - Para determinar a posição geográfica aproximada em que o veículo se encontra, foi adicionado um módulo receptor GPS e criada a placa de controlo e alimentação do mesmo. A figura \ref{fig:figura3} mostra o receptor GPS na estrutura de suporte fixa ao veículo e apresenta também a placa de controlo e alimentação.
\begin{figure} [H]
\center
\subfloat[Recetor GPS e sua posição no carro]{\label{fig:figura3.1}\includegraphics[height=5cm]{Figura5}}
\qquad
\centering
\subfloat[Placa de monitorização e alimentação do recetor GPS]{\label{fig:figura3.2}\includegraphics[height=5cm]{Figura6v2}}
\caption{Recetor GPS e sistema auxiliar do Atlas 2000}
\label{fig:figura3}

\end{figure}

\item \textbf{Estrutura} - Foi realizado um reforço à estrutura existente bem como feita a troca de peças danificadas.

\end{itemize}

\section{Plataforma de Desenvolvimento de Software}
\label{sec:PlataformaDeDesenvolvimento}
Optou-se por utilizar como plataforma de desenvolvimento o ecossistema \textit{Robot Operating System} (ROS), mostrado no trabalho de ~\textcite{288}. Esta plataforma encontra-se estabelecida como preferencial nos desenvolvimentos executados no Laboratório de Automação e Robótica, e tem como características principais a facilidade de reutilização do código desenvolvido, de integração do software compatível com o \textit{hardware}, entre outras.

Esta plataforma tem um caráter bastante flexível para a criação de \textit{software} diretamente relacionado com a área da robótica. Neste momento, o sistema proporciona, de forma gratuíta e com código aberto, um número considerável de ferramentas, \textit{drivers} e bibliotecas padrão. Encontra-se ainda em expansão, sendo a comunidade de investigadores da área os principais responsáveis por tal crescimento.

O ROS aplica uma estrutura modular constituída por \textit{packages}, em que usa o método de publicação/subscrição para comunicação. De uma forma resumida, um módulo publicador gera informação que é encapsulada numa mensagem de um certo tipo e publicada num tópico. Todos os módulos interessados, que estejam subscritos ao referido tópico, terão acesso aos dados.

\section{Objetivos Principais}
Esta dissertação tem como objetivo principal a criação de um sistema, estrutura e software que permita a reconstrução e avaliação da navegabilidade de ambientes exteriores. Isto será possível com a utilização de dois distanciómetros \textit{laser}, um 2D Hokuyo UTM-30LX e um 2D URG-04LX-UG01, mas também com a criação de novos módulos em conjugação com a utilização de módulos já existentes em ROS.

Os módulos usados terão de ser capazes de obter nuvens de pontos 3D, fazer o processamento dessa informação para determinar o que é navegável ou não em função da existência de obstáculos, e por fim, representar a informação relevante num formato standard denominado de KML para ser utilizado como camada no GoogleMaps.
\section{Estrutura da Dissertação}
Esta dissertação está dividida, e organizada, da seguinte forma:
\begin{itemize}

\item Capítulo 2 - Estado da Arte \\Apresentação das soluções já existentes na área da localização e mapeamento, bem como na criação de mapas para navegação.

\item Capítulo 3 - Localização do Atlas 2000 \\Descrição de possíveis métodos de localização para o Atlas 2000

\item Capítulo 4 - Alterações Realizadas ao Atlas 2000 \\Alterações realizadas à estrutura do Atlas 2000, bem como ao seu software.

\item Capítulo 5 - Mapeamento e Representação \\Explicação do processo usado desde a utilização da informação proveniente dos sensores usados até à sua representação num mapa da Google.

\item Capítulo 6 - Resultados \\Apresentação e comentário dos resultados obtidos 

\item Capítulo 7 - Conclusões e Trabalho Futuro \\Neste capítulo são explicadas as conclusões e possíveis trabalhos futuros.

\end{itemize}

\chapter{Estado da Arte}

De maneira a suportar o desenvolvimento da ferramenta geradora de mapas de navegabilidade, fez-se uma pesquisa inicial sobre sistemas de localização e mapeamento existentes para criar mapas locais, métodos de tratamento e sua representação.

\section{Localização e Mapeamento}
Desde há uns anos até à atualidade, a área da robótica dedicada à localização e mapeamento tem ganho bastante atenção. Tem havido grandes avanços, mas as limitações ainda são consideráveis, nomeadamente em zonas extensas e com uma dinâmica elevada, e é ainda um problema a resolver para obter um veículo verdadeiramente autónomo~\cite{Thrun:2003:RMS:779343.779345}.

É de uma importância elevada um veículo autónomo saber a sua própria localização para poder realizar planeamento de caminhos ou evitar obstáculos. Sem este tipo de informação, um veículo estará limitado ao facto de reagir ao que lhe poderá aparecer, e não planear para o futuro~\cite{THESIS:PHD:BAILEY:2002}.

Serão mencionadas várias formas de adquirir a localização de um veículo:
\begin{itemize}

\item \textbf{Navegação estimada} - Esta forma de localização, mais conhecida por \textit{Dead reckoning}, tem como objetivo estimar a posição atual tendo a informação da posição e direção numa iteração anterior, bem como dados de sensores relativos à propriocepção. O veículo está equipado com vários sensores, entre eles um codificador para as rotações do motor e um potenciómetro no sistema de direção dianteiro. Sabendo o diâmetro das rodas é possível determinar o espaço percorrido pelo veículo.
Um problema grave com este método é que a cada iteração o erro associado é acumulado, não havendo limite para o erro total (\textit{boundless}) por ausência de referência externa conhecida.

\item \textbf{\textit{A priori map localization}} - Tendo o robô sensores para obter informação sobre o ambiente que o rodeia, poderá ser obtida uma posição absoluta no mundo, recorrendo a um mapa previamente conhecido, e então, ser feita a localização por comparação com pontos de interesse (\textit{distinct landmarks}). Para a criação de um \textit{a priori map}  tem de se efetuar um levantamento da área em questão. Zonas novas implicam a geração de novos mapas, o que em espaços exteriores dinâmicos pode resultar em mapas de pouca qualidade.

\item \textbf{Localização e Mapeamento Simultâneos (SLAM)} - Nestes métodos é necessário armazenar a informação recolhida enquanto um robô se move. Nesta abordagem deixa de ser necessário um \textit{a priori map}, o que, por consequência, permite a construção de mapas de elevada complexidade. À medida que os pontos de referência vão acumulando, a posição estimada do robô é melhorada, bem como o mapeamento. É de mencionar que à medida que os pontos de referência são revistos mais vezes, o mapa começa a ganhar mais o aspeto de um "\textit{a priori map}".

SLAM é uma opção ideal para navegação em ambientes completamente desconhecidos, porque o robô pode ser deixado sem qualquer tipo de intervenção humana para realizar o levantamento do espaço.

Na tabela \ref{tab:tabela1}, de forma resumida, são descritos alguns dos métodos SLAM existentes~\autocite{Nuchter:2007:SMO:1291068.1291071}.

\begin{table}[h]
\center
\begin{tabular}{c|c|c|}
\cline{2-3}
                                 & \multicolumn{2}{c|}{Dimensionalidade da Representação da Posição e Orientação}                                                                                                                                                                                                                                                                                            \\ \hline
\multicolumn{1}{|c|}{Tipo de Laser} & 2D                                                                                                                                                           & 6D                                                                                                                                                                     \\ \hline
\multicolumn{1}{|c|}{2D}            & \begin{tabular}[c]{@{}c@{}}\textbf{Mapeamento 2D Planar}\\ com um sonar ou laser 2D\\~\autocite{Thrun:2003:RMS:779343.779345}\end{tabular}                                                           & \begin{tabular}[c]{@{}c@{}}\textbf{Slice-wise 6D SLAM}\\ Mapeamento 3D com a \\localização a considerar x, y, z , \\roll, yaw e pitch\\~\autocite{Bosse:2009:CSS:1703775.1704130}\end{tabular}                                  \\ \hline
\multicolumn{1}{|c|}{3D}            & \begin{tabular}[c]{@{}c@{}}\textbf{Mapeamento 3D Planar}\\ usando método de \\localização planar com \\laser scan com varrimento vertical \\ou um 3D scanner\end{tabular} & \begin{tabular}[c]{@{}c@{}}\textbf{Verdadeiro 6D SLAM }\\ Mapeamento 3D com laser 3D \\ou um sistema stereo\\ em que a posição é estimada \\com a informação do sensor\\~\autocite{Nuchter:2007:SMO:1291068.1291071}\end{tabular} \\ \hline
\end{tabular}

\caption{Resumo dos possíveis métodos SLAM (\textit{\textbf{S}imultaneous \textbf{L}ocalization \textbf{A}nd \textbf{M}apping})}
\label{tab:tabela1} 

\end{table}
\end{itemize}

É ainda de mencionar que para realizar apenas uma reconstrução 3D parcial de um mapa local, pode ser usado o método descrito na dissertação de Pedro Salvado~\autocite{salvadoreconstrucao}. Este trabalho usa um distanciómetro laser suportado por uma plataforma rígida com uma ligeira inclinação, de forma a que este se encontre apontado para superfície do solo à frente do veículo. Neste trabalho foi desenvolvido um módulo em ROS que estava responsável pela acumulação de várias nuvens de pontos, com o auxílio de uma biblioteca denominada de \textit{Point Cloud Library}~\autocite{1184}. Este módulo poderia subscrever a informação proveniente de câmaras \textit{Bumblebee XB3} e \textit{Kinect} e de distanciómetros \textit{laser}. 

A figura \ref{fig:figura23} ilustra o resultado de uma reconstrução com a utilização da câmara \textit{Kinect} desenvolvido pelo trabalho de Joel Pereira~\autocite{joel}.
\clearpage
\begin{figure} [H]
\center
\subfloat{\includegraphics[height=5cm]{Figura23}}
\caption{Exemplo de reconstrução com uma \textit{Kinect}~\autocite{joel}}
\label{fig:figura23} 
\end{figure}

Para o caso do uso de um distanciómetro \textit{laser} planar, a informação disponibilizada encontra-se em coordenadas polares, i.e., fornece a distância e o ângulo a que um obstáculo (ponto) se encontra relativamente ao sensor.
Para a criação de uma nuvem tridimensional, representada em coordenadas cartesianas, é necessário que os dados em unidades polares sejam primeiro convertidos com o auxílio do sistema \ref{eq:ConvCoord}.
\begin{equation}
\left\{
  \begin{array}{lr}
    x_i=r_i\cos(\theta_i)\\
    y_i=r_i\sin(\theta_i)\\
    z_i=0
  \end{array} 
\right.
\label{eq:ConvCoord}
\end{equation}
onde $r_i$ é a distância medida pelo sensor e $\theta_i$ o ângulo de varrimento de cada ponto. Depois são rodados e transacionados de acordo com as estimativas dos movimentos da plataforma para acumulação em nuvem de pontos. Isto é possível com a concatenação (operação += da \textit{Point Cloud Library}) entre nuvens de pontos.

Após esta fase, é necessário transformar os valores obtidos, que se encontravam no referencial do sensor para o referencial de origem. Que, neste caso, foi considerado como referencial de origem o centro do para-choques frontal, sendo mostrado na equação \ref{eq:cbs} a transformação mencionada.

\begin{equation}
f(x)=\begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix}_{center\_bumper} = \begin{bmatrix}
r_{11}&r_{12}&r_{13}&d_{x}\\
r_{21}&r_{22}&r_{23}&d_{y}\\
r_{31}&r_{32}&r_{33}&d_{z}\\
0&0&0&1\\
\end{bmatrix} \times \begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix}_{sensor}
\label{eq:cbs}
\end{equation} 



\section{Mapas para Navegação} 
Mesmo depois de obter informação proveniente de \textit{lasers} ou câmaras e realizar o mapeamento, momento em que estes mapas poderão servir de base ao planeamento de rotas, verifica-se que este processo apresenta um grau elevado de dificuldade e, consequentemente, esta área tem recebido bastante atenção e o assunto tem sido bastante investigado.
Neste contexto, a representação geométrica destes mapas (mapas de elevação) têm sido populares, sejam os modelos 3D~\autocite{Wurm10octomap:a} ou os 2.5D ~\autocite{Triebel06multi-levelsurface}, sendo necessário um nível elevado de processamento para processar e construir estes modelos 3D.
\subsection{Modelo 2.5D}
\label{subsec:Modelo_2.5D}
Os mapas de elevação consistem em grelhas de ocupação~\autocite{Moravec19851840}~\autocite{Elfes:1989:UOG:68491.68495} em que cada célula inclui o valor de altura. É de notar que a caraterização discreta do ambiente em zonas como túneis ou passagens sob pontes seriam representadas erradamente como obstáculos, conforme apresentado na figura \ref{fig:figura5}.

\begin{figure} [H]
\center
\subfloat[Nuvem de pontos de uma ponte]{\label{fig:figura5.1}\includegraphics[height=2.8cm]{Figura9}}
\centering
\subfloat[Mapa de elevação da ponte]{\label{fig:figura5.2}\includegraphics[height=2.8cm]{Figura10}}
\caption{Mapas de elevação e limitações inerentes.}
\label{fig:figura5} 
\end{figure}

No trabalho de~\textcite{Triebel06multi-levelsurface}, foi apresentada uma extensão aos mapas de elevação que é denominada por \textit{MLS Maps} (\textit{Multi Level Surface Maps}). Estes mapas consistem numa grelha 2D de tamanho variável em que cada célula representa cada uma das superfícies com a média e a variação da altura registada. Estes parâmetros, ao serem processados, determinam o facto de a célula em questão ser acessível àquela altura, e é representada pela média $\mu_{ij}^{k}$, e a incerteza representada pela variação $\sigma_{ij}^{k}$. Na figura \ref{fig:figura6.1} podem ser visualizados alguns exemplos de representações de células num MLS.

Um mapa do tipo MLS pode ser criado por dois processos, por uma nuvem de pontos ou juntando dois mapas MLS já existentes. Conclui-se que, se um mapa $m_1$ for criado de uma nuvem de pontos $C_1$ e um mapa $m_2$ de uma nuvem de pontos $C_2$, então um mapa $m_3$ resultante de juntar $m_1$ e $m_2$ é idêntico de um criado de uma nuvem de pontos $C_3=C_1+C_2$.  
A criação de um MLS dada uma nuvem de pontos $C$ segue os seguintes pontos:
\begin{itemize}
\item Cada célula do mapa com índices $(i,j)$ armazena todos os pontos $P=(x,y,z)$ a ela correspondentes, isto é:
\begin{equation}
s(i) \le x \le s(i+1) 
\label{eq:si}
\end{equation}
\begin{equation}
s(j)  \le y \le s(j+1)
\label{eq:sj}
\end{equation}
em que $s$ é a largura da célula.
\item Para cada célula é calculado um intervalo de alturas com base nas alturas dos pontos da mesma. Se o espaçamento entre dois intervalos consecutivos forem menores que um valor inicialmente estabelecido, $\gamma$, isto significa que os mesmos pertencem de facto ao mesmo intervalo. Este espaçamento deve ser escolhido de forma que o robô que pretenda navegar consiga passar nesse espaço.
\item Os intervalos são classificados de horizontais ou verticais se, respetivamente, a altura dos mesmo for inferior ou superior a um certo valor limite.
\item Para cada intervalo classificado como vertical, é armazenado o valor da média e a maior variação, pois estabeleceu-se que eram os parâmetros importantes para determinar se seria navegável. É memorizado também o comprimento do intervalo, denominado de profundidade de uma célula ($d$), pois este é importante para o caso de juntar dois mapas MLS.
\item Para cada intervalo classificado como horizontal, é calculada a média, $\mu$, e o desvio padrão, $\sigma$, para todas as medições no mesmo. De mencionar que é atribuído um valor nulo à profundidade das células horizontais.
\end{itemize}

\begin{figure} [H]
\center
\subfloat[]{\label{fig:figura6.1}\includegraphics[height=4cm]{Figura11}}
\centering
\subfloat[]{\label{fig:figura6.2}\includegraphics[height=3.8cm]{Figura12}}
\caption{a) Exemplo de várias células num mapa MLS. A célula \textit{A} mostra que podem existir mais que um grupo de valores de media e variação. A célula \textit{B} mostra que todas elas podem ter profundidade. A célula \textit{C} representa uma que não tem profundidade; b) Mapa MLS que representa correctamente as elevações}
\label{fig:figura6} 
\end{figure}

Por fim, após a classificação das células em horizontais ou verticais, é verificado para cada uma se tem entre 5 a 8 células vizinhas e se a diferença de altura entre a célula em questão e as células vizinhas é inferior a 10 cm. Se estas condições forem verificadas, uma célula é classificada como navegável.
Na figura \ref{fig:figura7} pode-se ver o resultado após classificação e representação.

\begin{figure} [H]
\center
\subfloat{\includegraphics[height=4cm]{Figura13}}
\caption{Mapa MLS. A amarelo são as zonas navegáveis, a azul as zonas não navegáveis e a vermelho as superfícies verticais}
\label{fig:figura7} 
\end{figure}

Uma variação deste método foi usado na dissertação realizada por Diogo Matos~\autocite{matos_detecao}. Após a recolha de uma nuvem de pontos, é-lhe aplicado um pré-processamento que consistiu em usar um filtro que descartava pontos acima dos 2 metros e a uma distância superior a 25 metros (figura \ref{fig:figura24}). Além deste filtro, foram estimadas as normais da nuvem de pontos, aplicando o produto externo aos vetores definidos entre um ponto e os seus vizinhos. Isto é possível com o auxilio da biblioteca da \textit{PointCloud}. Nesta biblioteca existem duas formas de determinar as normais, em que o método usado considerava os vizinhos num determinado raio do ponto a processar.

\begin{figure} [H]
\center
\includegraphics[height=5cm]{Figura24}
\caption{Nuvem de pontos após a aplicação do filtro que limita altura e comprimento}
\label{fig:figura24} 
\end{figure}

Para evitar variações muito grandes induzidas pela discretização da superfície, foi usado um raio com valor suficiente para que a normal determinada seja coerente em relação ao que a rodeia. O problema de determinar as normais com o raio da vizinhança, é que este raio tem de ser suficientemente grande para que as normais em cada ponto não sejam influenciadas por erros de medição aos pontos vizinhos mais próximos, mas também que a sua dimensão oculte variações reais com interesse. Este problema pode ser visualizado na figura \ref{fig:figura26}.

\begin{figure} [H]
\center
\subfloat[Cálculo das normais utilizando R=0.1 m]{\label{fig:figura26.1}\includegraphics[height=5cm]{Figura25}}
\qquad
\centering
\subfloat[Cálculo das normais utilizando R=0.4 m]{\label{fig:figura26.2}\includegraphics[height=5cm]{Figura26}}
\caption{Determinação das normais de uma nuvem de pontos}
\label{fig:figura26} 
\end{figure}

Após esta fase é inicializada uma grelha de ocupação, são processados os pontos da nuvem e é armazenada a informação para cada célula que lhes corresponde. A equação \ref{eq:Celula} mostra como é calculada a célula $C(i,j)$ onde o ponto $\overrightarrow{p}_n$, pertence.

\begin{equation}
\overrightarrow{p}_n=(p_x,p_y)\hookrightarrow C(i,j):\left\{
  \begin{array}{lr}
    i=round\left(\frac{p_x}{S_x}\right)\\
    j=CARaxis\_col+round\left(\frac{p_y}{S_y}+k\right)
  \end{array} 
\right.
\label{eq:Celula}
\end{equation}

onde $p_x$ e $p_y$ representam as coordenadas $x$ e $y$ do ponto $\overrightarrow{p}_n$. 

Para ser determinada a coluna à qual um ponto pertence é levado em conta a posição central da grelha de ocupação, para que esta fique definida em torno da origem do referencial da nuvem de pontos. Logo, $k$ na equação \ref{eq:Celula}, toma os valores de +0.5 ou -0.5 para o caso de $p_y$ ser positivo ou negativo.

Na fase seguinte são calculadas as médias aritméticas da coordenada $z$ e os ângulos associados às normais nos pontos de uma célula, $\mu_{z}$, $\mu_{\alpha}$, $\mu_{\beta}$ e $\mu_{\psi}$, respetivamente. Com as equações \ref{eq:nuz}, \ref{eq:nua}, \ref{eq:nub} e \ref{eq:nup} são determinados valores de confiança $\nu$ associados a cada célula para os valores de cada média, que representam o grau de representatividade dos valores contidos na célula, para posteriormente ser usado no cálculo da acessibilidade.
\begin{multicols}{2}
  \begin{equation}
    \nu_z=1-\frac{\sigma_z}{\sigma_{0z}}
    \label{eq:nuz}
  \end{equation}
  \begin{equation}
    \nu_{\alpha}=1-\frac{\sigma_{\alpha}}{\sigma_{0\alpha}}
    \label{eq:nua}
  \end{equation}
\end{multicols}
\begin{multicols}{2}
  \begin{equation}
    \nu_{\beta}=1-\frac{\sigma_{\beta}}{\sigma_{0\beta}}
    \label{eq:nub}
  \end{equation}
  \begin{equation}
    \nu_{\psi}=1-\frac{\sigma_{\psi}}{\sigma_{0\psi}}
    \label{eq:nup}	
  \end{equation}
\end{multicols}

A confiança $\nu$, que é calculada com base no desvio padrão corrigido, $\sigma$, e de uma constante $\sigma_0$ para normalizar os valores da confiança entre 0 e 1. É de mencionar que estes cálculos só são válidos para células com mais do que um ponto, em que, para o caso de existir apenas um ponto numa célula, é-lhe atribuído uma confiança de 0.5.

Nesta fase, cada célula é classificada com 8 variáveis, $\nu_z$, $\nu_{\alpha}$, $\nu_{\beta}$, $\nu_{\psi}$, $\mu_{z}$, $\mu_{\alpha}$, $\mu_{\beta}$ e $\mu_{\psi}$ , em que 4 delas são as médias geométricas das confianças e as outras quatro são os valores de confiança. Com as equações \ref{eq:vartz}, \ref{eq:varta}, \ref{eq:vartb} e \ref{eq:vartp} são calculados os valores de disparidade para cada uma das propriedades que significam o quanto uma célula se difere das suas células vizinhas, em que $k$ representa o número de vizinhos de uma célula.
\begin{multicols}{2}
  \begin{equation}
    \vartheta_{z}^n = \frac{\displaystyle\sum_{i=1}^{k} {\frac{|\mu_{z}^i - \mu_{z}^n|}{\sqrt{\nu_z^i \cdot \nu_z^n}}}}{k}	
    \label{eq:vartz}
  \end{equation}
  \begin{equation}
    \vartheta_{\alpha}^n = \frac{\displaystyle\sum_{i=1}^{k} {\frac{|\mu_{\alpha}^i - \mu_{\alpha}^n|}{\sqrt{\nu_{\alpha}^i \cdot \nu_{\alpha}^n}}}}{k}
    \label{eq:varta}
  \end{equation}
\end{multicols}
\begin{multicols}{2}
  \begin{equation}
    \vartheta_{\beta}^n = \frac{\displaystyle\sum_{i=1}^{k} {\frac{|\mu_{\beta}^i - \mu_{\beta}^n|}{\sqrt{\nu_{\beta}^i \cdot \nu_{\beta}^n}}}}{k}
    \label{eq:vartb}
  \end{equation}
  \begin{equation}
    \vartheta_{\psi}^n = \frac{\displaystyle\sum_{i=1}^{k} {\frac{|\mu_{\psi}^i - \mu_{\psi}^n|}{\sqrt{\nu_{\psi}^i \cdot \nu_{\psi}^n}}}}{k}
    \label{eq:vartp}	
  \end{equation}
\end{multicols}

Por fim usando as equações \ref{eq:varpz}, \ref{eq:varpa}, \ref{eq:varpb} e \ref{eq:varpp} é calculado a acessibilidade das células, $\varpi$, comparando a disparidade com um valor limite, $Th$. Na figura \ref{fig:figura27} pode ser visualizado o resultado do produto das acessibilidades, usando um $Th_z$ de 10 cm, $Th_{\alpha}=Th_{\beta}=Th_{\psi}$ de 0.2 radianos e para o cálculo da confiança foi usado $\sigma_0=2 \cdot Th$. De mencionar que nesta figura a cor azul corresponde a uma acessibilidade de 1 e a cor vermelha a uma de valor igual a 0

\begin{multicols}{2}
  \begin{equation}
    \varpi_z^n=1-\frac{\vartheta_z^n}{Th_z}
    \label{eq:varpz}
  \end{equation}
  \begin{equation}
    \varpi_{\alpha}^n=1-\frac{\vartheta_{\alpha}^n}{Th_{\alpha}}
    \label{eq:varpa}
  \end{equation}
\end{multicols}
\begin{multicols}{2}
  \begin{equation}
  	\varpi_{\beta}^n=1-\frac{\vartheta_{\beta}^n}{Th_{\beta}}
    \label{eq:varpb}
  \end{equation}
  \begin{equation}
   	\varpi_{\psi}^n=1-\frac{\vartheta_{\psi}^n}{Th_{\psi}}
    \label{eq:varpp}	
  \end{equation}
\end{multicols}

\begin{figure} [H]
\center
\includegraphics[height=6cm]{Figura27}
\caption{Mapa resultante dos produtos das acessibilidades}
\label{fig:figura27} 
\end{figure}

\subsection{Modelo 3D}
Na investigação apresentada por~\textcite{Wurm10octomap:a} foi criada uma representação 3D de um ambiente que considera não só as zonas ocupadas mas também as zonas livres ou desconhecidas. Este modelo usa a filosofia das \textit{Octrees} que, na base, é uma estrutura de árvore em que cada célula da octree representa um cubo em espaço físico (\ref{fig:figura8}).  

\begin{figure} [H]
\center
\subfloat[Exemplo de armazenamento de espaço livre, a branco, e espaço ocupado, a preto, de uma octree]{\label{fig:figura8.1}\includegraphics[height=5cm]{Figura15}}
\centering
\subfloat[Representação em árvore de uma octree]{\label{fig:figura8.2}\includegraphics[height=5cm]{Figura16}}
\caption{Representação generalizada de uma octree}
\label{fig:figura8} 
\end{figure}

Este modelo de octree tem como características principais os seguintes pontos: 
\begin{itemize}
\item \textbf{Modelo \textit{Full 3D}} - O mapa modela o ambiente sem qualquer tipo de simplificações, em que, também tem de representar o espaço livre e desconhecido. De notar que o espaço livre e ocupado é importante para planeamento, e o desconhecido para a exploração.

\item \textbf{Atualizável} - Este modelo permite a adição de novas informações às já existentes. As atualizações e modelações levam em consideração os erros dos sensores usados e mudanças no ambiente para levar em conta a dinâmica do espaço. Existe também a possibilidade de usar vários robôs a atualizar um mesmo mapa.

\item \textbf{Flexível} - Não necessita de conhecimento \textit{a priori} do tamanho do mapa resultante, pois este permite uma expansão dinâmica. Ele também permite a representação em várias resoluções para o tratamento de informação ser otimizável.

\item \textbf{Compacto} - O mapa é armazenado de forma compacta para ser possível a sua troca entre robôs e para minimizar o espaço utilizado em disco. Variando a resolução da octree, ilustrado na figura \ref{fig:figura9}, a quantidade de dados poderá variar.
\end{itemize}

\begin{figure} [hbtp]
\center
\includegraphics[height=3cm]{Figura18}
\caption{Resultado da limitação de profundidade das células nas octree. Diferentes resoluções, da esquerda para a direita, para profundidade de 0.08m, 0.64m e 1.28m, respetivamente.}
\label{fig:figura9} 
\end{figure}

Comparando o resultado do modelo 3D mostrado na figura \ref{fig:figura10.4}, com os resultados de outros métodos tipicamente usados, concluí-se que de uma nuvem de pontos 3D, sem qualquer processamento prévio (\ref{fig:figura10.1}), pode ser obtido também um mapa de elevação para os pontos em questão (\ref{fig:figura10.2})~\autocite{Hebert_1989_2435} e um mapa MLS (\ref{fig:figura10.3}), referido no sub-capítulo~\ref{subsec:Modelo_2.5D}.
\begin{figure} [hbtp]
%\center
\subfloat[Nuvem de pontos de um laser sem qualquer tipo de tratamento]{\label{fig:figura10.1}\includegraphics[height=3.5cm]{Figura19}}
\quad
%\centering
\subfloat[Mapa de elevação dessa mesma nuvem de pontos]{\label{fig:figura10.2}\includegraphics[height=3.5cm]{Figura20}}
%\center
\quad
\subfloat[Mapa MLS (Multi-level surface map)]{\label{fig:figura10.3}\includegraphics[height=3.5cm]{Figura21}}
\quad
%\centering
\subfloat[Mapa resultante usando a filosofia de Octrees falada]{\label{fig:figura10.4}\includegraphics[height=3.5cm]{Figura22}}
\caption{Possíveis resultados do processamento de nuvens de pontos 3D de dados laser}
\label{fig:figura10} 
\end{figure}

\clearpage
\section{Considerações Adicionais}
Após realizado o levantamento do estado da arte, conclui-se que para criar mapas que representassem os obstáculos, num sistema global, poderiam ser usados como base o mapas da Google. Teriam de ser recolhidos dados da área proposta nesta dissertação (Universidade de Aveiro) e para existir uma passagem desses dados de nível local para um global, serão usados recetores GPS.

O sistema de posicionamento global (GPS) oferece, com precisão e em qualquer parte do globo, uma posição a três dimensões e a velocidade a um utilizador que tenha um recetor apropriado. Este posicionamento é realizado com o auxílio de uma constelação de 24 satélites organizados em 6 órbitas com 4 satélites por órbita (figura \ref{fig:ConstSat}), utilizando um tempo universal sincronizado entre eles (UTC). Pode-se ainda referir que o protocolo para comunicar com o recetor é o NMEA 0183~\autocite{national1995nmea}. %em que as especificações de comunicação são ilustradas na tabela \ref{tab:tabela2}.

\begin{figure} [hbtp]
\centering
\subfloat{\includegraphics[height=5.5cm]{Figura48}}
\caption{GPS - Constelação de satélites~\autocite{citsci}}
\label{fig:ConstSat} 
\end{figure}

%\begin{table}[H]
%\center
%\begin{tabular}{|c|c|}
%\hline
%{\bf Velocidade de Transmissão} & 4800 \\ \hline
%{\bf Nº de Bits}                & 8    \\ \hline
%{\bf Paridade}                  & Nulo \\ \hline
%{\bf Stop Bits}                 & 1    \\ \hline
%{\bf Handshake}                 & Nulo \\ \hline
%\end{tabular}
%\caption{Especificações de comunicação do protocolo NMEA}
%\label{tab:tabela2} 
%\end{table}

Determinou-se que para representação nos mapas da Google era possível a utilização de camadas para o efeito. O KML ou \textit{Keyhole Markup Language}~\autocite{KML} é um formato de ficheiros usado para representar dados geográficos em aplicações que usem mapas, logo com a ajuda da biblioteca KML será possível a criação de polígonos representativos dos obstáculos. É ainda de mencionar que este é um formato standard gerido pela Open Geospatial Consortium, Inc.

Um possível resultado com este processo de representação está ilustrado na figura \ref{fig:figura49}.

\begin{figure} [hbtp]
\centering
\subfloat{\includegraphics[height=4.8cm]{Figura49}}
\caption{Mapa Google resultante da aplicação de uma camada em KML}
\label{fig:figura49} 
\end{figure}

\chapter{Localização do Atlas 2000}
Para o desenvolvimento dos mapas para navegação de veículos será necessário conhecer a posição e orientação do veículo que executa o levantamento, os quais seriam obtidos a partir dos vários sensores que existem no Atlas 2000, nomeadamente lasers, codificadores e recetores GPS.

Serão apresentadas as duas metodologias consideradas para obtenção da informação necessária, proveniente do Atlas 2000 e dos seus sensores, para ser determinada a posição e orientação do mesmo.

\section{Sistema de Coordenadas do Atlas 2000}
Além da instalação de sensores, é necessário relacioná-los entre si e transmitir essa informação de posicionamento relativo para um sistema responsável pela recolha e tratamento desses dados. Esta informação é disponibilizada por um tipo de ficheiro com extensão URDF (Unified Robot Description Format), que permite descrever a posição e orientação dos sensores relativamente a um referencial à escolha~\autocite{288}. De notar que nem todos os referenciais estão relacionados com um sensor, como por exemplo \textbackslash base\_link (que diz respeito ao referencial de movimento do veículo) e o \textbackslash world (referencial mundo com origem onde se deu o início da recolha de informação). Esta relação é necessária  para possibilitar a realização de transformações e cálculos em relação ao robô. É importante a utilização destes referenciais para que a informação proveniente de equipamentos diferentes esteja sobre o mesmo referencial final.

A figura \ref{fig:FramesCarro} mostra um esquema onde estão representados os referenciais associados a cada sensor.
\clearpage
\begin{figure} [H]
\centering
\subfloat{\includegraphics[height=7cm]{Figura47v2}}
\caption{Sistema de referenciais adotados para o Atlas 2000}
\label{fig:FramesCarro} 
\end{figure}


\section{Recurso ao modelo mecânico do Atlas 2000}

O modelo de movimento do Atlas 2000 segue uma simplificação do modelo mecânico do veículo de Ackerman, denominado de Modelo Bicicleta. Este modelo, com o objetivo de apenas monitorizar o caminho percorrido, simplifica um veículo de quatro rodas num de duas, combinados as duas rodas dianteiras e as duas rodas traseiras, usando assim um veículo de duas rodas~\autocite{Latombe:1991:RMP:532147}. A figura \ref{fig:figura11.2} ilustra a simplificação do modelo mecânico usado no Atlas 2000.

O cálculo da hodometria do robô necessita de vários parâmetros, nomeadamente a distância entre eixos, a relação de transmissão, a velocidade e o ângulo da direção do veículo. Com o auxílio do algoritmo de egomotion pertencente ao \textit{software} do Atlas 2000, pode ser determinada a orientação ($\psi$) e posição (coordenadas $x$ e $y$) do carro. Na figura \ref{fig:figura11.1} é apresentado um diagrama com os parâmetros de entrada necessários para serem determinados a orientação e posição anteriormente referidas.   
\begin{figure} [H]
\center
\subfloat[Diagrama do modelo mecânico simplificado de Ackerman]{\label{fig:figura11.1}\includegraphics[height=4.5cm]{AkermannFigure}}
\qquad
\centering
\subfloat[Representação do modelo bicicleta do Atlas 2000]{\label{fig:figura11.2}\includegraphics[height=4.5cm]{Figura8v4}}
\label{fig:figura11} 
\caption{Modelo de movimento utilizado para o Atlas 2000}
\end{figure}

Foi necessário definir o vetor de estado a utilizar, que é constituído pelas coordenadas do veículo no plano $xy$ e a sua orientação $\psi$, o valor da velocidade atual $v$ e a orientação das rodas $\phi$.
\begin{equation}
f(x)=\begin{bmatrix} x \\ y \\ \psi \\ v \\ \phi \end{bmatrix}
\end{equation} 

Para se determinar a posição e orientação do veículo, têm de ser obtidas as variações das coordenadas no plano $x$ e $y$ do carro, identificadas como $\Delta x$ e $\Delta y$ respetivamente, mas também a variação da orientação do carro em torno do eixo $z$, denominada de $\Delta \psi$.
Com o apoio de fórmulas descritas no trabalho de~\textcite{Latombe:1991:RMP:532147}, e apresentadas nas equações \ref{eq:deltapsi}, \ref{eq:deltax} e \ref{eq:deltay}, é possível determinar estas variações.
\begin{equation}
\Delta \psi = \sin{(\phi)} \frac{v}{l} \Delta t
\label{eq:deltapsi}
\end{equation} 
\begin{equation}
\Delta x=\cos{(\phi)}\cos{(\phi)}v\Delta t
\label{eq:deltax}
\end{equation} 
\begin{equation}
\Delta y = \sin{(\phi)} \cos{(\phi)} v \Delta t
\label{eq:deltay}
\end{equation} 

Após determinadas as variações das coordenadas no plano local ao veículo e a variação da orientação, com o auxílio das equações \ref{eq:psi}, \ref{eq:x} e \ref{eq:y}, é calculada a posição e orientação real do Atlas 2000.
\begin{equation}
\psi_i = \psi_{i-1} + \Delta \psi
\label{eq:psi}
\end{equation} 
\begin{equation}
x_i = x_{i-1} + \Delta x
\label{eq:x}
\end{equation} 
\begin{equation}
y_i = y_{i-1} + \Delta y
\label{eq:y}
\end{equation} 

Nesta fase do trabalho, as informações provenientes dos sensores não se encontram relacionadas entre si, logo, utiliza-se o pacote em ROS (\textit{atlas2000\_egomotion}) que tem como função publicar as transformações entre referenciais (\textit{frames}), e caraterizar o carro em relação ao ambiente que o rodeia, relacionando, assim, todos os referenciais a um principal, nomeadamente o \textit{frame} \textbackslash world.

A figura \ref{fig:EsquemaTransv2} ilustra a árvore de transformações do referencial do laser horizontal para o referencial mundo e a árvore de transformações do referencial do laser inclinado até ao referencial mundo.

\begin{figure} [H]
\centering
\subfloat{\includegraphics[height=6cm]{EsquemaTransv2}}
\caption{Árvore de transformações do laser horizontal (laser1) e do laser inclinado (laser2)}
\label{fig:EsquemaTransv2} 
\end{figure}

\section{Hector SLAM}
Para realizar a localização do Atlas 2000, poderá ser usado o pacote ROS denominado de \textit{hector\_slam}. No âmbito desta dissertação será utilizado o \textit{hector\_mapping} que permite a localização e mapeamento simultâneo (SLAM). Este método é denominado por um \textit{SLAM frontend} uma vez que estima o movimento do robô em tempo real. O algoritmo depende apenas da existência de um distanciómetro planar de alta frequência para poder realizar o alinhamento entre varrimentos.\autocite{Kohlbrecher11aflexible}~\autocite{2013:RoboCup}

Este pacote subscreve o tópico de um laser e publica, principalmente, uma grelha de ocupação do espaço que o rodeia e as transformações necessárias para saber a posição e orientação em que o laser se encontra em qualquer momento e onde foi iniciado o pacote.

Para a criação de um mapa e por consequência a sua grelha de ocupação, usando o \\\textit{hector\_mapping}, é necessário realizar um passo denominado de alinhamento. É de mencionar que este alinhamento é baseado numa aproximação Gauss-Newton inicialmente apresentada no estudo de~\textcite{Lucas:1981:IIR:1623264.1623280}. Para este alinhamento, entre varrimentos diferentes ou de varrimentos novos com um mapa existente, é necessário determinar a transformação representada por $\xi=(p_x,p_y,\psi)^T$ que minimiza a equação \ref{eq:MinOcup}.
\begin{equation}
\xi^*=\operatorname*{\text{argmin}}_{\xi} \displaystyle\sum_{i=1}^{n} [ 1-M( \text{S}_{i} ( \xi ) ) ]^2
\label{eq:MinOcup}
\end{equation} 

em que $S_{i}(\xi)$ são as coordenadas no mundo dos pontos recolhidos por um varrimento laser e $M(S_{i}(\xi))$ determina a ocupação nesse ponto. Nesta fase, é relevante mencionar que dada a natureza discreta da grelha de ocupação resultante do \textit{hector\_mapping}, existe um limite à precisão que pode ser obtida, mas também não permite o processamento direto dos valores interpolados ou suas derivadas parciais. Logo, é necessário a utilização de uma sub-grelha para aplicar uma interpolação	bilinear (figura \ref{fig:figura29.1}) para estimar a probabilidade de ocupação e suas derivadas (gradiente de ocupação) mostrado na figura \ref{fig:figura29.2}.
\begin{figure} [H]
\center
\subfloat[Esquema para a interpolação bilinear da grelha de ocupação sendo o ponto $P_m$ a ser interpolado]{\label{fig:figura29.1}\includegraphics[height=5cm]{Figura28}}
\qquad
\centering
\subfloat[Grelha de Ocupação e suas derivadas]{\label{fig:figura29.2}\includegraphics[height=5cm]{Figura29}}
\label{fig:figura29} 
\caption{Esquema de funcionamento das grelhas de ocupação do pacote do Hector SLAM}
\end{figure}

De notar que a resolução considerada nesta grelha é igual a 1.





Dado um mapa contínuo de coordenadas $P_m$, o valor de ocupação $M(P_m)$ e o seu gradiente $\nabla M(P_m)=(\frac{\delta M}{\delta x}(P_m),\frac{\delta M}{\delta y}(P_m)$, podem ser aproximados usando as equações \ref{eq:MP}, \ref{eq:deltaMx} e \ref{eq:deltaMy} respetivamente.
\begin{align}
\label{eq:MP}
M(P_m) \approx \frac{y-y_0}{y_1-y_0}\left(\frac{x-x_0}{x_1-x_0}M(P_{11})+\frac{x_1-x}{x_1-x_0}M(P_{01})\right)+ \nonumber \\
+\frac{y_1-y}{y_1-y_0}\left(\frac{x-x_0}{x_1-x_0}M(P_{10})+\frac{x_1-x}{x_1-x_0}M(P_{00})\right)
\end{align}

\begin{equation}
\frac{\delta M}{\delta x}(P_m) \approx \frac{y-y_0}{y_1-y_0}(M(P_{11})-M(P_{01}))+\frac{y_1-y}{y_1-y_0}(M(P_{10}-M(P_{00}))
\label{eq:deltaMx}
\end{equation} 

\begin{equation}
\frac{\delta M}{\delta y}(P_m) \approx \frac{x-x_0}{x_1-x_0}(M(P_{11})-M(P_{01}))+\frac{x_1-x}{x_1-x_0}(M(P_{10}-M(P_{00}))
\label{eq:deltaMy}
\end{equation} 
em que $P_{00}$, $P_{01}$, $P_{10}$ e $P_{11}$ são os valores inteiros, das coordenadas no mapa, e $P_m$ a coordenada do ponto interior à célula.
 
Dada uma estimação inicial da transformação, é necessário determinar $\Delta \xi$ que otimiza  o erro medido com base na equação \ref{eq:OptError} e, por consequência, devido à primeira ordem da expansão de Taylor de $M (S_{i}(\xi + \Delta{\xi}))$ é deduzida a equação \ref{eq:OptErrorExp}.
\begin{equation}
\displaystyle\sum_{i=1}^{n} [1 - M (S_{i}(\xi + \Delta{\xi}))]^2 \rightarrow 0
\label{eq:OptError}
\end{equation}

\begin{equation}
\displaystyle\sum_{i=1}^{n} \left[1 - M (S_{i}(\xi)) - \nabla M (S_{i}(\xi))\frac{\delta S_{i}\xi}{\delta (\xi)}\Delta \xi)) \right]^2 \rightarrow 0
\label{eq:OptErrorExp}
\end{equation}


Na figura \ref{fig:EsquemaTransHector} é mostrada a árvore de transformações usada e que relaciona o referencial do laser horizontal para o mundo e o referencial do laser inclinado para o mundo.
\begin{figure} [H]
\centering
\subfloat{\includegraphics[height=7.5cm]{EsquemaTransHector}}
\caption{Árvore de transformações do laser horizontal (laser1) e do laser inclinado (laser2)}
\label{fig:EsquemaTransHector} 
\end{figure}


\chapter{Alterações Realizadas no Atlas 2000}
Para preparar o robô Atlas 2000 para os trabalhos de levantamente e criação dos mapas de navegabilidade, houve necessidade de realizar algumas intervenções no sistema mecânico, no sistema elétrico e ao nível do \textit{software} base. Todas as alterações serão descritas com mais detalhe ao longo deste capítulo.
\section{Software}
No início desta dissertação o veículo encontrava-se a operar com uma coleção de \textit{software open-source} denominado CARMEN (\textit{Carnegie Mellon Robot Navigation Toolkit})~\autocite{CarmenWWW} que entretanto foi substituída pela plataforma ROS já apresentada na secção~\ref{sec:PlataformaDeDesenvolvimento}. Explicando um pouco a filosofia da CARMEN, trata-se de uma coleção modular, expansível, programada principalmente na linguagem  C, com módulos básicos de navegação. localização e outros do interesse da robótica móvel. A comunicação entre processos escolhida para a coleção trata-se de um pacote denominado de IPC (\textit{Inter-process Comunication})~\autocite{LamportInterProcess} que é estabelecida com sockets TCP/IP e sockets Unix.

\section{Intervenção Elétrica}
Ao longo de vários trabalhos anteriores foram realizadas alterações pontuais ao sistema elétrico que não respeitaram uma estrutura de ligações elétricas organizada e segura, nomeadamente:
\begin{itemize}

\item Condutores sob tensão com pontas soltas;

\item Circuitos constituídos por troços condutores concatenados sem consistência entre cores do isolamento;

\item Ausência total de etiquetagem, e.g., que tornasse mais evidente a forma correta de ligação dos condutores às baterias;

\item Interruptor geral com ligações incorretas interrompia apenas metade do circuito.

\end{itemize}
  
\begin{figure} [H]
\centering
\subfloat{\includegraphics[height=8cm]{Figura30}}
\caption{Aspeto inicial dos cabos nas placas de controlo do veículo.}
\label{fig:figura31} 
\end{figure}
O aspecto do circuito, antes intervenção nas placas de controlo e na zona das baterias, pode ser visto na figura \ref{fig:figura31}. Para melhor oranizar as cablegem utiliza-se a zona inferior da placa acrílica de cobertura da zona traseira do veículo para realizar uma grande parte do suporte para o circuito apresentado na figura \ref{fig:figura33.1}. É de mencionar também que o esquema de cores foi decidido de tal forma que apenas os condutores ligados ao terminal de referência da alimentação possuem isolamento preto, isto é, o terminal indicado como negativo da primeira bateria, o zero do servo-amplificador e o zero do regulador de tensão. Todos os restantes, que apresentam diferença de potencial (12 Volt, 24 Volt e 48 Volt) ficaram com isolamento vermelho e encontram-se etiquetados com a tensão correspondente  das ligações das baterias, como pode ser visto na figura \ref{fig:figura33.2}.

\begin{figure} [H]
\center
\subfloat[Organização do circuito elétrico após intervenção.]{\label{fig:figura33.1}\includegraphics[height=5cm]{Figura33}}
\centering
\qquad
\subfloat[Etiquetação dos cabos terra e com tensão.]{\label{fig:figura33.2}\includegraphics[height=5cm]{Figura32}}
\caption{Aspeto do circuito elétrico após alterações.}
\label{fig:figura33} 
\end{figure}

\section{Mudanças da Plataforma Física}
Para realizar a recolha de informação do ambiente onde o veículo irá percorrer, foram escolhidos dois lasers Hokuyo, modelos URG-04LX-UG01 e UTM-30LX, mostrados respetivamente nas figuras \ref{fig:figura35.1} e \ref{fig:figura35.2}. A razão da escolha da utilização destes dois modelos foi a limitação de material disponível e adequabilidade para o trabalho.
\begin{figure} [H]
\center
\subfloat[Hokuyo URG-04LX-UG01]{\label{fig:figura35.1}\includegraphics[height=5cm]{Figura34v2}}
\centering
\qquad
\subfloat[Hokuyo UTM-30LX]{\label{fig:figura35.2}\includegraphics[height=5cm]{Figura35v2}}
\caption{Lasers usados no trabalho relatado na dissertação}
\label{fig:figura35} 
\end{figure}

É ainda de mencionar que o modelo URG-04LX-UG01 tem um campo de visão de 240º, um alcance máximo de 5.6 metros, uma precisão de $\pm$ 30 milímetros e funciona a uma frequência de amostragem de 10 hertz de um varrimento completo. Relativamente ao modelo UTM-30LX este tem como caraterísticas principais o facto de ter um campo de visão de 270º, um alcance máximo de 30 metros, uma precisão de $\pm$ 30 milímetros e funciona a uma frequência de amostragem de 40 hertz para o varrimento completo .

Para fazer a reconstrução 3D, os lasers tiverem de ser colocados num suporte que permitisse fixar um deles com um plano de varrimento aproximadamente horizontal e o outro com um plano de varrimento com uma certa inclinação. Esta inclinação foi decidida tomando em atenção o facto da radiação solar na gama do infravermelho perturbar o sistema de deteção, podendo mesmo saturá-lo, mas que mesmo assim permitisse a visualização do estado do espaço à frente do veículo. Na figura \ref{fig:figura37.1} ilustra-se a primeira versão do suporte para os dois sensores, que permitia uma maior liberdade de posicionamento dos lasers mas, por consequência, sofria de algumas instabilidades, o que inviabilizava uma calibração permanente das transformações extrínsecas. Numa segunda versão (figura \ref{fig:figura37.2}), foi levado em atenção esse problema, e optou-se pela criação de um suporte mais rígido composto por chapa de alumínio e um perfil bosch.
\clearpage
\begin{figure} [H]
\center
\subfloat[Suporte para os \textit{lasers} em acrilico]{\label{fig:figura37.1}\includegraphics[height=5cm]{Figura36v2}}
\centering
\qquad
\subfloat[Suporte para os \textit{lasers} em alumínio]{\label{fig:figura37.2}\includegraphics[height=5cm]{Figura37}}
\caption{Lasers usados no trabalho relatado na dissertação}
\label{fig:figura37} 
\end{figure}

Também foi realizado um reforço ao suporte do computador de bordo para evitar danos de choque ou queda, que se tornaram mais prováveis devido aos movimentos que o veículo irá executar em piso irregular. Na figura \ref{fig:figura38} é apresentado o estado final da zona em questão.
\begin{figure} [H]
\centering
\subfloat{\includegraphics[height=8cm]{Figura38v2}}
\caption{Reforço de apoios para a zona de acomodação do computador de bordo}
\label{fig:figura38} 
\end{figure}

\chapter{Mapeamento e Representação Global}
\label{ch:MapRep}
Neste capítulo será demonstrada a sequência de algoritmos usados para o rpocessamento da nuvem 3D inicial até à sua representação num mapa da Google maps. Esta sequência de algoritmos é ilustrada na figura \ref{fig:cap5Esquema} e cada um será explicado de uma forma breve .

\begin{figure} [H]
\centering
\subfloat{\includegraphics[scale=0.55]{Cap5Esquemav2}}
\caption{Esquema de processamento de uma nuvem de pontos 3D para a sua representação no referencial global}
\label{fig:cap5Esquema} 
\end{figure}

Os algoritmos usados pertencentes à biblioteca da pointcloud:
\begin{itemize}

\item \textit{RANSAC}(\textit{\textbf{RAN}dom \textbf{SA}mple \textbf{C}onsensus)} - Baseia-se num método iterativo para estimar parâmetros de um modelo matemático de informação previamente recolhida. Inicialmente esta técnica foi apresentada por~\textcite{AICPub836:1981}. Neste caso o modelo oferecido é o plano e os dados são uma nuvem de pontos.

\item \textit{PassThrough} - Filtro que processa pontos de uma nuvem e aplica limites numéricos, p.e., numa dada coordenada.

\item \textit{ProjectInlier} - Usando um \textit{sample consensus model} e com base nos coeficientes determinados pelo \textit{RANSAC}, é possível projetar pontos de uma nuvem num plano.

\item \textit{EuclideanClusterExtration} - Sendo fornecido uma nuvem de pontos e com base na distância euclidiana, torna-se possível decompor o espaço em conjuntos separados de pontos (\textit{clusters}).

\item \textit{ConcaveHull} e \textit{ConvexHull} - Algoritmos para determinar conjuntos de pontos num espaço em que o ``fecho'' dos mesmos poderá ser, respetivamente, côncavo ou convexo. Na figura \ref{fig:figura46.1} é ilustrado com linhas vermelhas um invólucro côncavo de um conjunto de pontos e na figura \ref{fig:figura46.2} é demonstrado com linhas verdes um invólucro convexo .

\begin{figure} [hbtp]
\center
\subfloat[]{\label{fig:figura46.1}\includegraphics[height=5cm]{Figura46Part1v2}}
\centering
\qquad
\subfloat[]{\label{fig:figura46.2}\includegraphics[height=5cm]{Figura46Part2v2}}
\caption{Resultados da aplicação de algoritmos \textit{ConcaveHull} e \textit{ConvexHull}. a)As linhas vermelhas representam o resultado da utilização do algoritmo \textit{ConcaveHull} a um conjunto de pontos; b)As linhas verdes representam o resultado da utilização do algoritmo \textit{ConvexHull} a um conjunto de pontos~\autocite{journalsjiseParkO12}}
\label{fig:figura46} 
\end{figure}
\end{itemize}


\textit{Keyhole Markup Language} (KML) utiliza uma estrutura de tags com elementos e atributos, que se assemelha à estrutura usada pelo XML. No~\nameref{sec:anexoA} é demonstrada uma estrutura exemplo resultante da criação de um polígono, com as coordenadas definidas na \textit{tag} <coordinates>, com um estilo personalizado, nomeadamente, as linhas a vermelho definidas pela \textit{tag} <color> da <LineStyle> e um preenchimento a vermelho definido nas \textit{tags} <color> e <fill> da <PolyStyle>.  A figura \ref{fig:KMLFigure} ilustra o resultado da aplicação deste código a um mapa Google.

\begin{figure} [H]
\centering
\subfloat{\includegraphics[scale=0.25]{KMLFigurev2}}
\caption{Exemplo da aplicação da estrutura KML no ~\nameref{sec:anexoA} num mapa da Google.}
\label{fig:KMLFigure} 
\end{figure}

\subsubsection{Aquisição e Processamento}
Para criar um mapa local utilizaram-se os dados do laser horizontal (\ref{fig:figura35.2}) para a utilização do pacote \textit{hector\_mapping}, usando-o como hodometria na reconstrução da nuvem de pontos. Usaram-se também os dados do laser inclinado, apresentado na figura \ref{fig:figura35.1} para determinar a distância ao solo e em especial, os obstáculos positivos e negativos.
Para realmente realizar a reconstrução 3D do ambiente recorreu-se a um pacote em ROS, denominado de \textit{pc\_accumulation} desenvolvido por Pedro Salvado~\autocite{salvadoreconstrucao}. Este módulo é responsável pela acumulação de nuvens de pontos. A figura \ref{fig:figura39} ilustra uma nuvem de pontos 3D (do ambiente exterior mostrado na figura \ref{fig:figura39.2}) que representa uma acumulação de varrimentos consecutivos obtida com o pacote referido.
\begin{figure} [hbtp]
\centering
\subfloat{\includegraphics[height=8.7cm]{Figura39_2v2}}
\caption{Ambiente exterior usado para realizar os testes iniciais de utilização do método proposto}
\label{fig:figura39.2} 
\end{figure}

\clearpage

\begin{figure} [hbtp]
\centering
\subfloat{\fcolorbox{black}{white}{\includegraphics[height=5.5cm,width=13cm]{Figura39v2}}}
\caption{Reconstrução 3D do ambiente exterior apresentado na figura \ref{fig:figura39.2}}
\label{fig:figura39} 
\end{figure}

Após recolhida a nuvem de pontos, é necessário processá-la para realizar a extração e representação dos obstáculos positivos e negativos com diferença de cota fora do limiar permitido (zonas que são de impossível navegação). Para este efeito foi criado um pacote em ROS, denominado de \textit{obstacle\_extraction}, que usa funções da biblioteca \textit{pointcloud} para processamento do mapa 3D, e da biblioteca KML, para representação de polígonos num mapa da Google, respetivamente.

Numa primeira fase de processamento, e como o uso do veículo será apenas em pisos praticamente planos, será usado o algoritmo de \textit{RANSAC} presente na biblioteca da \textit{pointcloud} para determinar o plano do chão e determinar os coeficientes desse plano.

Após esta fase, é usado o filtro de \textit{PassThrough} para separar todos os pontos cuja cota diste mais do que \mbox{15 cm} do plano, assim obtém-se uma nuvem resultante apenas com as zonas onde a passagem é impossibilitada por algum obstáculo, positivo ou negativo (figura \ref{fig:figura40}). Foi escolhido este valor devido a ser a limitação de altura que o carro consegue subir ou descer em segurança.

Os coeficientes do plano do chão, anteriormente determinados, tornam possível projetar a nuvem 3D (figura \ref{fig:figura41}) no referido plano. 
\begin{figure} [H]
\center
\subfloat{\fcolorbox{black}{white}{\includegraphics[height=6cm,width=13cm]{Figura40v2}}}
\caption{Nuvem de pontos 3D com as zonas onde se encontram os obstáculos}
\label{fig:figura40} 
\end{figure}
\begin{figure} [H]
\center
\subfloat{\fcolorbox{black}{white}{\includegraphics[height=6cm,width=13cm]{Figura41v2}}}
\caption{Nuvem de pontos projetada das zonas onde se encontram os obstáculos}
\label{fig:figura41} 
\end{figure}

Por fim, ao aplicar o algoritmo de \textit{concave hull} é possível delimitar de uma forma côncava todos os obstáculos. Na figura \ref{fig:figura43} pode ser visualizado a diferença de situações entre o antes e o depois de aplicar o algoritmo mencionado a um dos obstáculos.

\begin{figure} [H]
\center
\subfloat[Obstáculo projetado]{\label{fig:figura43.1}\fcolorbox{black}{white}{\includegraphics[height=5cm]{Figura42v2}}}
\qquad
\centering
\subfloat[Resultado do algoritmo de \textit{concave hull} aplicado a obstáculo projectado aplicado]{\label{fig:figura43.2}\fcolorbox{black}{white}{\includegraphics[height=5cm]{Figura43v2}}}
\caption{Estado inicial e final da aplicação do algoritmo \textit{concave hull} a um obstáculo}
\label{fig:figura43} 
\end{figure}

Por fim, foi tomada a decisão de realizar os polígonos dos obstáculos de uma forma conservadora, logo foi usado o algoritmo de \textit{ConvexHull} em cada um deles para delimitar as suas extremidades. Para isso acontecer a cada obstáculo, o \textit{ConvexHull} não poderá ser aplicado à nuvem de pontos como ela se encontra, logo foi usado o algoritmo de \textit{EuclideanClusterExtraction} para extrair cada obstáculo para a sua nuvem individual e então suceder à aplicação do \textit{ConvexHull}. A parte da nuvem de pontos resultante deste processo pode ser visualizada na figura \ref{fig:figura44}.

\begin{figure} [H]
\centering
\subfloat{\fcolorbox{black}{white}{\includegraphics[scale=0.33]{Figura44v3}}}
\caption{Obstáculos delimitados pelas extremidades com a aplicação do algoritmo \textit{ConvexHull} que são os pilares da figura \ref{fig:figura39.2}}
\label{fig:figura44} 
\end{figure}


\subsubsection{Transformação do Mapa Local para Global}
Após esta fase, e com o registo geográfico do local onde foi iniciada a reconstrução do ambiente, obtido via recetor GPS, é possível transformar as coordenadas cartesianas do mapa $x$ e $y$ para latitude e longitude. De mencionar que, numa área pequena é válida a utilização de uma transformação com elemento de arco esférico num plano. Com o auxílio da função \ref{eq:CGI} é possível determinar as coordenadas globais iniciais x ($Y\_Global\_Init$) e y ($Y\_Global\_Init$).
\begin{equation}
\begin{cases}
    Y\_Global\_Init = LatInit \times EarthR\\
    X\_Global\_Init = LongInit \times EarthR \times cos(LatInit)\\
\end{cases}
\label{eq:CGI}
\end{equation} 
onde a $LatInit$ é a latitude inicial, a $LongInit$ é a longitude inicial e $EarthR$ é o raio médio terrestre em quilómetros. A latitude e longitude inicial provenientes do módulo recetor GPS estão em graus, sendo necessário realizar a conversão para radianos.

Para cada obstáculo é conhecida a coordenada local na nuvem de pontos, assim, com o auxílio do sistema \ref{eq:VarGlob}, é possível determinar a variação em x e y das coordenadas globais. Note-se no entanto que os eixos do referencial do mapa local e do global não estão coincidentes.
\begin{equation}
\begin{bmatrix} \Delta X \\ \Delta Y\end{bmatrix} = \begin{bmatrix}
\cos(\gamma)&\sin(\gamma)\\
-\sin(\gamma)&\cos(\gamma)\end{bmatrix} \times \begin{bmatrix} \Delta x \\ \Delta y\end{bmatrix}
\label{eq:VarGlob}
\end{equation} 

onde $\Delta X$ e $\Delta Y$ são as variações das coordenadas $X$ e $Y$ do referencial global, $\Delta x$ e $\Delta y$ são as variações das coordenadas $x$ e $y$ do referencial local e $\gamma$ é o ângulo necessário para o mapa global fique alinhado com mapa mundo. O ângulo foi determinado de forma heurística.

Após determinadas as variações das coordenadas globais dos pontos de cada obstáculo, é necessário aplicar o sistema \ref{eq:LLP} para serem determinadas as latitudes e longitudes respetivas a cada ponto. De notar que estes resultados estarão em radianos e será necessário realizar a conversão para graus.
\begin{equation}
\begin{cases}
    Lat\_Point = (Y\_Global\_Init + \Delta Y )/EarthR\\
    Long\_Point = (X\_Global\_Init + \Delta X) /(EarthR \times cos(Lat\_Point))
\end{cases}
\label{eq:LLP}
\end{equation} 

Nesta fase, e com o auxílio da biblioteca KML, é possível criar um algoritmo que realiza estes cálculos e cria os polígonos em KML. O resultado deste processo pode ser visualizado na figura \ref{fig:figura44}
\begin{figure} [H]
\centering
\subfloat{\fcolorbox{black}{white}{\includegraphics[height=7cm]{Figura45v2}}}
\caption{Representação da nuvem de pontos 2D num mapa da Google}
\label{fig:figura45} 
\end{figure}

\cleardoublepage
\chapter{Resultados}
Neste capítulo serão apresentados os resultados obtidos, para três zonas do campus da Universidade de Aveiro. 
Serão apresentadas numa primeira fase as nuvens de pontos recolhidas em três zonas distintas, e numa segunda fase o resultado do pós-processamento que culmina num ficheiro KML. Este pós-processamento encontra-se descrito no capítulo \ref{ch:MapRep}. Nas figuras seguintes estão ilustradas a verde as zonas navegáveis e a vermelho as zonas não navegáveis.

\section{Dados do Sistema Laser}

A figura \ref{fig:figura50} mostra a primeira zona de testes que foi escolhida, devido à existência de bastantes obstáculos, de modo a que o pacote de localização usado tivesse referencias suficientes e acumulasse o mínimo de erros.
A figura \ref{fig:figura53} mostra a segunda zona de testes que foi escolhida devido ao facto de estar presente um plano inclinado. Por fim, a figura \ref{fig:figura56} demonstra a terceira zona de testes que foi escolhida por proporcionar um ambiente intermédio entre conter obstáculos que poderão servir de referencia, para a localização, e zonas sem referencias.
As figuras \ref{fig:figura51} e \ref{fig:figura52}, \ref{fig:figura54} e \ref{fig:figura55}, \ref{fig:figura57}  ilustram respetivamente a primeira, a segunda e a terceira zona de testes com o pós-processamento referenciado.
\clearpage

Na figura \ref{fig:figura50} é possível visualizar um extenso plano do chão, pilares de seção circular e retangular, palmeiras e parte de um edifício. 
Nas nuvens de pontos processadas, figuras \ref{fig:figura51} e \ref{fig:figura52}, é possível verificar que o os pilares, troncos e parede do edifício, encontram-se a vermelho e o plano do chão e todas os pontos que distam menos de 15 cm dele, encontra-se a verde. É de notar que parte da parede encontra-se a verde devido a esta se intercetar com o plano do chão. Estas duas reconstruções de pontos foram efetuadas quando, respetivamente, se encontravam pessoas a circular e sem pessoas. 
\begin{figure} [H]
\centering
\subfloat{\includegraphics[height=7cm]{Figura50v2}}
\caption{Primeira zona de testes para realizar reconstrução 3D}
\label{fig:figura50} 
\end{figure}

\begin{figure} [H]
\centering
\subfloat{\fcolorbox{black}{white}{\includegraphics[height=8cm, width=15cm]{Figura51}}}
\caption{Resultado do pós-processamento realizado à primeira zona com pessoas a passar. A cor verde representa as zonas navegáveis e a vermelho as zonas não navegáveis.}
\label{fig:figura51} 
\end{figure}

\begin{figure} [H]
\centering
\subfloat{\fcolorbox{black}{white}{\includegraphics[height=8cm, width=15cm]{Figura52}}}
\caption{Resultado do pós-processamento realizado à sem movimentação de pessoas. A cor verde representa as zonas navegáveis e a vermelho as zonas não navegáveis.}
\label{fig:figura52} 
\end{figure}




Na figura \ref{fig:figura53} é possível visualizar um curto plano do chão inclinado e parte de um edifício. 
Nas nuvens de pontos processadas, figuras \ref{fig:figura54} e \ref{fig:figura55}, é possível verificar que o plano do chão percorrido encontra-se a verde e o plano do relvado e da zona superior do lado esquerdo encontram-se a vermelho. Estas duas reconstruções de pontos foram efetuadas quando, respetivamente, se encontravam pessoas a circular e sem pessoas. 


\begin{figure} [H]
\centering
\subfloat{\includegraphics[height=8cm]{Figura53v2}}
\caption{Segunda zona de testes para realizar reconstrução 3D}
\label{fig:figura53} 
\end{figure}
\begin{figure} [H]
\centering
\subfloat{\fcolorbox{black}{white}{\includegraphics[height=8cm, width=15cm]{Figura54}}}
\caption{Resultado do pós-processamento realizado à segunda zona com a influencia da passagem de pessoas. A cor verde representa as zonas navegáveis e a vermelho as zonas não navegáveis.}
\label{fig:figura54} 
\end{figure}
\begin{figure} [H]
\centering
\subfloat{\fcolorbox{black}{white}{\includegraphics[height=8cm, width=15cm]{Figura55}}}
\caption{Resultado do pós-processamento realizado à segunda zona sem movimentação de pessoas. A cor verde representa as zonas navegáveis e a vermelho as zonas não navegáveis.}
\label{fig:figura55} 
\end{figure}


Na figura \ref{fig:figura56} é possível visualizar o plano do chão, postes de iluminação, parte de um edifício e grandes obstáculos no meio do espaço. 
Na nuvem de pontos processada, figura \ref{fig:figura57}, é possível verificar que o plano do chão percorrido encontra-se a verde e, os grandes obstáculos no meio do espaço, parte do edifício e a escadaria, encontram-se a vermelho. 




\begin{figure} [H]
\centering
\subfloat{\includegraphics[height=8cm]{Figura56v2}}
\caption{Terceira zona de testes para realizar reconstrução 3D}
\label{fig:figura56} 
\end{figure}
\begin{figure} [H]
\centering
\subfloat{\fcolorbox{black}{white}{\includegraphics[height=8cm, width=15cm]{Figura57}}}
\caption{Resultado do pós-processamento realizado à terceira zona. A cor verde representa as zonas navegáveis e a vermelho as zonas não navegáveis.}
\label{fig:figura57} 
\end{figure}
\clearpage

\section{Mapas de Navegabilidade}
Após a fase inicial de pós-processamento das nuvens de pontos e usando dados recolhidos pelo recetor GPS, poderá ser concluída a análise das nuvens de pontos para realizar os mapas de navegabilidade. Os resultados deste processo final podem ser visualizados nas figuras \ref{fig:figura58} e \ref{fig:figura59} para o primeira zona, nas figuras \ref{fig:figura60} e \ref{fig:figura61} para o segunda zona e a figura \ref{fig:figura62} para o terceira zona.
As zonas navegáveis são a interceção do alcance do laser e das zonas definidas como não navegáveis.
\begin{figure} [H]
\centering
\subfloat{\includegraphics[height=10cm, width=15cm]{Figura58}}
\caption{Mapa de navegabilidade para a primeira zona com pessoas a passar. A cor verde representa as zonas navegáveis e a vermelho as zonas não navegáveis}
\label{fig:figura58} 
\end{figure}
\clearpage
\begin{figure} [H]
\centering
\subfloat{\includegraphics[height=10cm, width=15cm]{Figura59}}
\caption{Mapa de navegabilidade para a primeira zona sem movimentação de pessoas. A cor verde representa as zonas navegáveis e a vermelho as zonas não navegáveis}
\label{fig:figura59} 
\end{figure}

\begin{figure} [H]
\centering
\subfloat{\includegraphics[height=8cm, width=15cm]{Figura60}}
\caption{Mapa de navegabilidade para a segunda zona com a influencia da passagem de pessoas. A cor verde representa as zonas navegáveis e a vermelho as zonas não navegáveis}
\label{fig:figura60} 
\end{figure}

\begin{figure} [H]
\centering
\subfloat{\includegraphics[height=8cm, width=15cm]{Figura61}}
\caption{Mapa de navegabilidade para a segunda zona. A cor verde representa as zonas navegáveis e a vermelho as zonas não navegáveis}
\label{fig:figura61} 
\end{figure}

\begin{figure} [H]
\centering
\subfloat{\includegraphics[height=8cm, width=15cm]{Figura62v2}}
\caption{Mapa de navegabilidade para a terceira zona. A cor verde representa as zonas navegáveis e a vermelho as zonas não navegáveis}
\label{fig:figura62} 
\end{figure}

\cleardoublepage

\chapter{Conclusões e Trabalhos Futuros}
Este trabalho teve como objetivo criar um sistema de dois \textit{lasers} 2D e um GPS, em que fosse possível realizar uma recolha de dados de ambientes exteriores, nomeadamente do campus da Universidade de Aveiro e criar mapas de navegabilidade. Neste capítulo será feita uma análise sobre o trabalho desenvolvido e os objetivos cumpridos. Por fim, serão enumeradas algumas propostas para trabalhos futuros.

\subsubsection{Conclusões}

A migração do software para ROS foi realizada com sucesso, resultando num programa que, de forma precisa, lida com o fluxo de informação para o controlo do Atlas 2000. O sistema baseado em ROS combina as vantagens já existentes de ser modular, com o facto de ser possível alterar código que controla tarefas específicas sem que estas influenciem outras funções, mas também com a filosofia de tornar o sistema mais organizado, simplificando, a inserção de novas funções.

A criação do suporte final para o hardware foi realizada com sucesso, sendo composto por peças em alumínio e aço. Tornando-se assim mais vantajoso pelo facto de permitir manter a calibração inicial válida, i.e., sem que vibrações provocadas pelo movimento do veículo em pisos não regulares, alterem a calibração inicial.

O sistema desenvolvido para a recolha de dados, e que usa o pacote \textit{Hector Mapping} como auxílio na localização do veículo, foi realizado com sucesso. Este sistema não tem a capacidade de mapear todos os casos impostos por um ambiente exterior mas, de uma forma genérica, para as zonas apresentadas, foram obtidos resultados visualmente aceitáveis. Isto pode ser verificado na comparação entre os mapas da google com os mapas de navegabilidade resultantes.
O facto do sistema desenvolvido não resolver todos os casos é devido à forma simplificada como se obteve a localização do veículo. Foi usado o \textit{Hector\_Mapping} sem terem sido usados mais sensores para auxiliar esta localização, nomeadamente para determinar a pose do veículo.

Com os resultados obtidos pode-se concluir que, para a primeira zona de testes em que a localização se realizou com um maior sucesso, a passagem de pessoas influencia de forma negativa e progressiva na acumulação de erros da nuvem de pontos, algo que se visualiza no canto superior direito da figura \ref{fig:figura52}, com a curvatura existente na nuvem de pontos. Mesmo assim, verificou-se que para este caso, num espaço de 100 metros percorridos, a precisão do mapa realizado é visualmente aceitável, isto comparando com o mapa da Google respetivo.

Para o segundo e terceiro caso, devido à falta de obstáculos positivos, o pacote \\\textit{Hector\_Mapping} não conseguiu, em alguns casos, efetuar o alinhamento correto dos varrimentos laser, sendo que as novas localizações publicadas fiquem incorretas. 
Neste caso foram obtidos melhores resultados no teste em que existia passagem de pessoas. Mesmo que normalmente a movimentação de pessoas influencie negativamente no pacote usado para a localização, quando existem poucos ou nenhuns obstáculos que sejam usados como referencia para a mesma, a presença de pessoas tem o efeito contrario.

Isto pode ser verificado com o facto de, no segundo caso, as nuvens de pontos resultarem com tamanhos diferentes. O problema é visualizado com maior facilidade nos mapas de navegabilidade destes dois testes, mostrados nas figuras \ref{fig:figura60} e \ref{fig:figura61}. 
Para o terceiro caso, este problema deve-se ao facto de existir uma falha de pontos no centro da imagem, em que no mapa de navegabilidade para este teste (figura \ref{fig:figura62}) isto pode ser visualizado com o facto de existirem pontos dispersos no mapa.

Foram encontrados valores com baixa precisão para os dados provenientes do recetor GPS. Este problema pode ser visualizado nas figuras onde os polígonos que representam os obstáculos não estarem corretamente alinhados com a sua posição real no mapa da Google(figura \ref{fig:figura62}).

Com isto, pode ser concluído que os objetivos inicias de criar um sistema que possibilitasse a recolha de informação do ambiente exterior do campus da Universidade de Aveiro, com respetiva avaliação da informação para criar mapas de navegabilidade, foram alcançados. É ainda de mencionar que o sistema aplicado em ambientes com obstáculos tem um funcionamento bastante bom, o mesmo já não se pode dizer para espaços amplos desobstruídos. Este trabalho foi concluído com potencial para ser continuado em trabalhos futuros.

\subsubsection{Trabalhos Futuros}
Com o objetivo de resolver os problemas encontrados ao longo desta dissertação, ou serem adicionadas novas funcionalidades, são apresentadas algumas propostas de trabalhos futuros.:
\begin{itemize}

\item	Substituição do servo da direção e da sua placa de controlo;

\item   Melhorar o sistema de tração do carro para este realizar subidas de maior inclinação;

\item   Melhorar o sistema de localização usado para realizar as reconstruções de pontos 3D;

\item   Melhorar o pós processamento das nuvens de pontos para que se realize uma identificação mais refinada de obstáculos positivos e negativos; 

\item 	Implementar um sistema de calibração automática para o posicionamento dos lasers;
\end{itemize}



%
% The bibliography
%
\cleardoublepage
\renewcommand\bibname{Referências}
 %\bibliography{bibliografie}% replace by the name of name of your .bib file
 \printbibliography
  %\bibliographystyle{apalike}% use any style you like (I recommend the harvard package)
	

\cleardoublepage

\chapter{Anexos}
\section{Anexo A}
\label{sec:anexoA}
Código exemplo de uma estrutura KML

\begin{figure} [H]
\centering
\subfloat{\includegraphics[scale=0.6]{KMLExemple}}
\end{figure}






































\end{document}
