\section[Sol. navegação local]{Solução de navegação local}
\begin{frame}{Solução de navegação local}
	\begin{multicols}{2}
		\tableofcontents[currentsection, hideothersubsections]
	\end{multicols}
	\note[item]{Conteúdo da solução de navegação.}
\end{frame}

%--------------------------------------------%
% Solução implementada                       %
%--------------------------------------------%
\subsection{Solução implementada}
\begin{frame}{Algoritmo selecionado}
	\begin{itemize}
		\item RRT e suas variantes:
		\begin{itemize}
			\item[\checkmark] Consideração das restrições não holonómicas do veículo e rápida exploração do espaço de planeamento.
			\item[$\times$] Forte dependência da heurística de marcação aleatória dos pontos candidatos.
		\end{itemize}
		\item A* híbrido:
		\begin{itemize}
			\item[\checkmark] Trajetórias executáveis por veículos não holonómicos e natureza ótima da trajetória traçada.
			\item[$\times$] Planeamento em grelhas com forte dependência da discretização do espaço de planeamento.
		\end{itemize}
		\item Planeamento por múltiplas hipóteses:
		\begin{itemize}
			\item[$\times$] Não executa o planeamento completo da trajetória.
			\item[\checkmark] Capacidade de operação em tempo real.
		\end{itemize}
	\end{itemize}
	\note[item]{RRT e suas variantes têm a vantagem de considerar as restrições não holonómicas do veículo e da rápida exploração do espaço de planeamento. No entanto, a forte dependência da heurística de marcação aleatória dos pontos candidatos e da métrica para determinar o próximo estado condicionam a sua aplicação.}
	\note[item]{A* híbrido já considera trajetórias executáveis por veículos não holonómicos e estas trajetórias apresentam uma natureza ótima de acordo com a parametrização do algoritmo. No entanto, o planeamento em grelhas é muito demorado e com forte dependência da discretização do espaço de planeamento.}
	\note[item]{Planeamento por múltiplas hipóteses nem deve ser considerado para planeamento a baixas velocidades pois não executa o planeamento completo da trajetória. No entanto, a sua eficiência computacional permite a operação em tempo real.}
\end{frame}

%--------------------------------------------%
% Geração de trajetórias                     %
%--------------------------------------------%
\subsection{Geração de trajetórias}
\begin{frame}{Trajetórias}
	\begin{itemize}
		\item A geração das trajetórias hipotéticas, em arco, é realizada de acordo com a velocidade de veículo, que varia linearmente com a direção.
		\item O comprimento mínimo das trajetórias é de 4,5 m para garantir a ausência de colisões e permitir inversão de marcha.
	\end{itemize}
	\small
	\vspace{-5.0mm}
	\begin{minipage}[t]{0.59\linewidth}
		\begin{flushleft}
				\begin{equation*}
				\left[ \begin{array}{c} \prod_{x}^{} \\ \prod_{y}^{} \end{array} \right] = \left[ \begin{array}{c} \frac{D}{\tan(\alpha)} \cdot \sin \left( \frac{A \cdot \tan(\alpha)}{D} \right) \\ \frac{D}{\tan(\alpha)} \cdot \left( 1 - \cos \left( \frac{A \cdot \tan(\alpha)}{D} \right)\right) \end{array} \right]
				\end{equation*}
		\end{flushleft}
	\end{minipage}
	\begin{minipage}[t]{0.39\linewidth}
		\begin{flushright}
			\begin{equation*}
			D = \frac{v^2}{2 \cdot \mu \cdot g}  
			\end{equation*}
		\end{flushright}
	\end{minipage}
	\normalsize
	\begin{figure}[!h]
		\centering
		\subfloat
		{\includegraphics[width=0.26\textwidth]{figuras/traj_gif_0.png}}
		\subfloat
		{\includegraphics[width=0.26\textwidth]{figuras/traj_gif_1.png}}
		\subfloat
		{\includegraphics[width=0.26\textwidth]{figuras/traj_gif_2.png}}
		\subfloat
		{\includegraphics[width=0.26\textwidth]{figuras/traj_gif_3.png}}
	\end{figure}
	\note[item]{As trajetórias são arcos de circunferência com centro no meio do eixo traseiro do carro. A posição do carro é calculada de acordo com o comprimento do arco, D, o entre-eixo, A, e o ângulo da direção, alpha.}
	\note[item]{Os arcos são divididos em segmentos para facilitar o cálculo das colisões.}
	\note[item]{As trajetórias passaram de estáticas a dinâmicas com o comprimento a depender da velocidade de circulação. O coeficiente de atrito utilizado foi 0,4.}
	\note[item]{Numa fase mais avançada a velocidade do veículo foi alterada de acordo com o ângulo de direção escolhido. Esta relação é linear entre dois valores pré-definidos.}
	\note[item]{O comprimento mínimo das trajetórias teve que ser limitado para evitar situações de colisão quando surgem obstáculos repentinos. Foi limitado a 4,5 m para garantir a possibilidade de inversão de marcha.}
\end{frame}

%--------------------------------------------%
% Deteção de colisões                        %
%--------------------------------------------%
\subsection{Deteção de colisões}
\begin{frame}{Colisões}
	\begin{itemize}
		\item Inicialmente as colisões eram detetadas por interseções de linhas.
		\item De forma a eliminar o problema da criação de barreiras virtuais passaram a ser determinadas por inclusões poligonais, com recurso ao \textit{winding number}.
	\end{itemize}
	\vspace{-8.0mm}
	\begin{figure}[!h]
		\centering
		\subfloat
		{\includegraphics[width=0.43\textwidth]{figuras/colisoes3.png}}
		\hspace*{0.02\textwidth}
		\subfloat
		{\includegraphics[width=0.505\textwidth]{figuras/colisoes7.png}}
	\end{figure}
	\note[item]{As colisões eram inicialmente detetadas através da interseção das linhas do polígono de espaço livre com as linhas do retângulo representativo do carro.}
	\note[item]{Como o polígono contém todos os obstáculos sem distinção entre os obstáculos existe uma linha que criava uma barreira fictícia.}
	\note[item]{Para resolver este problema as colisões passaram a ser detetadas através de inclusões de pontos da nuvem dentro dos retângulos representativos do carro.}
	\note[item]{Para saber se um ponto está dentro do retângulo recorre-se ao winding number. Se o ponto estiver à esquerda do vetor (sentido anti-horário), que une um lado do retângulo soma 1 se estiver à direita soma -1. Se o winding number for 0 o ponto está fora.}
\end{frame}

%--------------------------------------------%
% Definição do ponto atrator                 %
%--------------------------------------------%
\subsection{Definição do ponto atrator}
\begin{frame}{Ponto atrator}
	\begin{itemize}
		\item O planeamento necessita de um objetivo, neste caso o ponto atrator.
	\end{itemize}
	\begin{minipage}[t]{0.49\linewidth}
		\begin{flushleft}
			\begin{itemize}
				\small
				\item Em simulação, o ponto atrator é definido pela posição de um marcador em Rviz.
				\normalsize
			\end{itemize}
		\end{flushleft}
	\end{minipage}
	\begin{minipage}[t]{0.49\linewidth}
		\begin{flushright}
			\begin{itemize}
				\small
				\item Em ambiente real, o ponto atrator depende dos \textit{way points} seguinte e anterior.
				\normalsize
			\end{itemize}
		\end{flushright}
	\end{minipage}
	\vspace{-3.0mm}
	\begin{figure}[!h]
		\centering
		\subfloat
		{\includegraphics[width=0.43\textwidth]{figuras/ponto1.png}}
		\hspace*{0.02\textwidth}
		\subfloat
		{\includegraphics[width=0.43\textwidth]{figuras/ponto2.png}}
	\end{figure}
	\note[item]{Para o bom funcionamento do algoritmo de planeamento tem que existir um ponto de convergência.}
	\note[item]{Durante as simulações foi utilizado um marcador visual em Rviz com 3 graus de liberdade e cuja posição determina a posição do ponto atrator.}
	\note[item]{Em navegação em ambiente real o ponto atrator é virtualmente colocado numa linha que une os dois way points mais próximos do carro. A distância do ponto atrator virtual é dada pelo raio da circunferência de centro no eixo traseiro que interceta a reta dos way points. isto permite que o ponto atrator esteja sempre dentro do intervalo de normalização da distância DAP.}
\end{frame}

%--------------------------------------------%
% Pontuação das trajetórias                  %
%--------------------------------------------%
\subsection{Pontuação das trajetórias}
\begin{frame}{Parâmetros da trajetória}
	\begin{itemize}
		\item Depois de detetadas as colisões e identificado o ponto atrator, cada trajetória é avaliada individualmente de acordo com os parâmetros:
		\begin{itemize}
			\item $FS$ --- espaço livre;
			\item $CL$ --- linha central;
			\item $DAP_{norm}$ --- distância normalizada ao ponto atrator;
			\item $ADAP_{norm}$ --- distância normalizada angular ao ponto atrator;
			\item $DLO_{norm}$ --- distância normalizada mínima aos obstáculos;
			\item  $m_{1,2,3}$--- pesos dos parâmetros de distância.
		\end{itemize}
	\end{itemize}
	\vspace{3.0mm}
	\begin{equation*}
	P_{traj} = (m_1 \cdot DAP_{norm} + m_2 \cdot ADAP_{norm} + m_3 \cdot DLO_{norm}) \cdot CL \cdot FS
	\end{equation*}
	\begin{itemize}
		\item É selecionada a trajetória que apresentar maior pontuação.
	\end{itemize}
	\note[item]{Para se escolher entre o leque de trajetórias geradas é preciso pontua-las de acordo com a equação.}
	\note[item]{O parâmetro FS representa o espaço livre, isto é, se a trajetória colide ou não.}
	\note[item]{O parâmetro CL representa a linha central em simulação, isto é, se a trajetória a interceta ou não.}
	\note[item]{O parâmetro DAP representa a distância linear normalizada do nodo da trajetória mais próximo do ponto atrator.}
	\note[item]{O parâmetro ADAP representa a distância angular normalizada do nodo da trajetória mais próximo do ponto atrator.}
	\note[item]{O parâmetro DLO representa a distância linear normalizada do obstáculo mais próximo a qualquer retângulo representativo do carro.}
	\note[item]{Os coeficientes $m_{1,2,3}$ são os pesos que se pretende atribuir às distâncias calculadas.}
	\note[item]{A trajetória que tiver maior pontuação é a escolhida.}
\end{frame}

%--------------------------------------------%
\begin{frame}{FS e CL}
	\begin{itemize}
		\item O parâmetro FS é um parâmetro exclusivo, ou seja, elimina as trajetórias que incluem pontos da nuvem de obstáculos.
		\begin{itemize}
			\item $FS = 1$ se não existe colisão ou $FS = 0$ se existe colisão.
		\end{itemize}
	\end{itemize}
	\begin{itemize}
		\item O parâmetro CL deve ser pesado consoante o tipo de linha que a trajetória hipotética interseta.
		\begin{itemize}
			\item $CL = 1$ quando não existe interseção ou $CL = \in [0;1[$ quando existe interseção.
		\end{itemize}
	\end{itemize}
	\begin{figure}[!h]
		\centering
		\includegraphics[width=0.55\textwidth]{figuras/linhas1.png}
	\end{figure}
	\note[item]{Os dois parâmetros FS e CL são parâmetros de afetação global.}
	\note[item]{O parâmetro FS é um parâmetro exclusivo. Ao ser igualado a 0 quando uma trajetória inclui um ponto da nuvem de obstáculos exclui automaticamente essa trajetória da lista de escolhas. Caso contrário o parâmetro é sempre 1.}
	\note[item]{O parâmetro CL representa a influência da linha central quando uma trajetória a interseta. O seu valor pode ser atribuído consoante o tipo de linha e o grau de perigosidade em a transporr. Apenas as trajetórias da esquerda podem ser afetadas de forma a permitir que o carro retorne à sua faixa.}
\end{frame}

%--------------------------------------------%
\begin{frame}{DAP, ADAP e DLO}
	\small
	\begin{itemize}
		\item DAP representa a distância linear do ponto mais próximo da trajetória ao ponto atrator.
		\item ADAP representa a distância angular entre ponto mais próximo da trajetória e o ponto atrator.
		\item DLO dá a distância linear do obstáculo mais próximo a qualquer ponto da trajetória.
	\end{itemize}
	\normalsize
	\vspace{-3.0mm}
	\begin{figure}[!h]
		\centering
		\includegraphics[width=0.6\textwidth]{figuras/linear1.png}
	\end{figure}
	\note[item]{DAP representa a distância linear do ponto mais próximo da trajetória ao ponto atrator. Este valor é normalizado com uma constante que corresponde à distância de influência do ponto atrator. O valor final varia sempre entre 0 e 1 pois o depois da divisão pelo parâmetro de normalização este valor é subtraído à unidade.}
	\note[item]{ADAP representa a distância angular entre ponto mais próximo da trajetória e o ponto atrator. A normalização é realizada pelo parâmetro $\pi$ que é divide o valor nominal. O valor também é subtraído à unidade.}
	\note[item]{DLO dá a distância linear do obstáculo mais próximo a qualquer ponto da trajetória. A normalização é realizada com o valor esperado a que os obstáculos se encontram. Este valor pode ser superior a 1 dependendo da distância mínima dos obstáculos.}
\end{frame}