Navegar é preciso: como drones autônomos encontram os caminhos certos

Udacity Brasil
7 de mai de 2018

Estudar aviação envolve diversas disciplinas e quem quer ser piloto precisa estudar – muito. Pilotos aprofundam-se em diversas matérias, como meteorologia, regulamentos de tráfego, aerodinâmica e navegação, o foco deste post.

Imagine um avião que decola do ponto A e segue direto para o ponto B em linha reta. Simples, certo? Na verdade, a navegação é mais ou menos assim: em um voo de 50 minutos, um avião costuma passar por no mínimo 5 waypoints, ou pontos de notificação.

Isso quer dizer que, quando o avião decola, ele sai de A e vai para B, que normalmente é um ponto logo depois da pista. Daí ele muda sua proa para C e, chegando lá, muda para D e em seguida segue para E, que é um ponto alinhado com a pista de pouso no destino.

Ou seja, para encontrar a linha reta até a chegada, já trocou de rumo algumas vezes. Não se trata de uma linha reta assim.

Na figura abaixo, podemos visualizar como é uma carta aeronáutica de verdade, usada no planejamento e execução da navegação. Os pilotos e computadores de bordo usam essas cartas antes e durante a navegação. Lá podemos ver a quantidade de waypoints virtuais que existem para a navegação aeronáutica.

Para facilitar a programação dos voos, cada waypoint recebe um nome e referência, e alguns emitem sinais de rádio, que podem ser usados pelos sistemas de navegação das aeronaves.

Assim, o avião navega por uma lista de waypoints e referências. Mas isso quando nossa máquina voadora não precisa desviar de formações meteorológicas, tais como as famosas Cumulonimbus, ou lidar com outros imprevistos. Todas essas possibilidades de variáveis fazem com que o planejamento do voo seja uma das etapas mais importantes do voo em si.

Com o entendimento dos waypoints, é fácil pensar que fazer um drone voar de A para B, num voo curtinho, é moleza. Mais ou menos.

Leia: A inteligência artificial como artista: músicas, filmes e quadros criados por AI

Embora ninguém espere que nosso querido quadrocopter substitua as aeronaves para voos de longo alcance – seu objetivo maior será voos de curtas distâncias –, é preciso navegar aproveitando os espaços apertados entre os edifícios.

Isso quer dizer que o quadrocopter vai voar entre os prédios? Essa é a ideia – e o desafio do projeto proposto pelo Nanodegree Voo Autônomo. É neste ponto em que os métodos de navegação do drone autônomo se aproximam dos métodos usados pelos carros autônomos e se distanciam das aeronaves maiores.

Os drones autônomos precisar ter a capacidade de atuar como carros voadores, o que significa buscar as pessoas em algum lugar e deixá-las em outro lugar. E será nos centros urbanos que de fato provarão sua eficiência, como mostram estes 8 modelos que estão prestes a chegar ao mercado.

Agora que você já entendeu que carros voadores não são uma lenda futurista, imagine um que decola de um jardim, sobe e navega até o topo de edifício. No caminho, ele deve evitar áreas restritas ao voo de grandes aeronaves, manter uma distância segura dos edifícios e seguir uma rota que seja confortável para passageiros.

Como planejar voos autônomos em termos de navegação?

A primeira etapa para criar um modelo eficiente é transformar o mapa atual daquele terreno em um grid. Tendo um grid em mãos, é possível definir quais células são factíveis para um drone voar e quais não são, como No Fly Zones.

Agora temos uma rota em uma dimensão, como evidencia a figura acima. Mas lembre-se que nosso drone autônomo precisa de regras matemáticas bem claras para achar o melhor caminho do “start” até o “goal”.

É aí que aproveitamos os aprendizados de inteligência artificial e aplicamos um algoritmo muito “inteligente”. O mais usado atualmente, ensinado no Nanodegree Voo Autônomo, é o chamado A* , ou A-Star.

O A-Star usa o conceito de grid e mais uma heurística aplicada (mais sobre este fator adiante) para definir pesos para cada uma das células. Na prática, para robótica, a heurística é uma fórmula matemática que define um parâmetro capaz de indicar claramente que você está mais próximo do objetivo.

Confuso? Pense numa folha de papel quadriculado. Este é o grid. Agora escolha dois quadrados: origem e destino. Pinte alguns quadrados de preto e estes serão os obstáculos, tornando-se espaços inutilizáveis em sua rota.

Em seguida, nos quadrados ao redor do seu destino, escreva o número 1. Ao redor destes números, faça outra volta e escreva 2. Continue assim até completar a folha inteira. Isso mesmo, você acabou de fazer sua primeira heurística para um algoritmo de path planning!

O A-Star, que é o nosso algoritmo de procura, funciona da seguinte maneira: a partir do ponto de origem, o algoritmo testa todos os possíveis pontos ao redor do ponto inicial e para cada uma das possibilidades é atribuída uma pontuação, chamada de custo.

Em seguida, é adicionado o valor do custo de acordo com o peso da heurística (que foi o número que você escreveu nas células). A célula que tiver a menor soma é escolhida como próxima célula, e você move sua posição atual para esta célula. A partir daí, o algoritmo repete a pesquisa sucessivamente até chegar no destino.

A regra da heurística é o que torna o algoritmo mais eficiente em espaços abertos e é muito usada em robótica, carros autônomos e drones autônomos. No campo de inteligência artificial, admite-se que uma boa heurística tem que ser consistente e admissível:

  • Consistente: a heurística é consistente se o valor total do custo de chegar na próxima célula sempre for menor ou igual ao custo total para chegar no objetivo.

  • Admissível: nunca superestima o custo de alcançar o objetivo

Para interessados, dois bons exemplos de heurística são os cálculos de distância Manhattan e Euclidianas.

Quer ver na prática? Assista ao tutorial de A* acima

Como mapear o mundo com um drone

Já sabemos ir de A para B. Ótimo! Então só falta pegar um mapa por aí, fazer as contas e soltar o drone para voar, certo? Não exatamente. Os mapas precisam ser extremamente precisos e incluir todos os prédios, as alturas exatas de cada construção, as distâncias de segurança e outras restrições. Ou seja, escolher que mapa usar é essencial.

Além disso, não se esqueça que nosso drone vai parar em cada ponto em que houver mudança de direção, apontar para a próxima parada e voar mais um pouquinho, o que não seria nada confortável. Vamos precisar resolver este fluxo também.

Primeiro, vamos solucionar a questão dos mapas. Mapas de alta precisão são um requisito fundamental para um voo seguro. E justamente por sua alta definição, os mapas são limitados, o que quer dizer que, para ter uma referência global holística, será preciso usar mais de um para montar o percurso.

Para tanto, usamos pelo menos duas referências: local (ou ECEF) e global (ou geodética).

Representações de mapas ECEF e geodético, respectivamente

E há mais uma referência: a chamada Body Frame, que diz respeito ao corpo do drone e considera a distância dos motores e dos sensores entre si, tais como GPS.

Este aspecto é importante por dois motivos: para saber considerar o tamanho do drone e o posicionamento dos sensores e para mapear mais facilmente as forças que atuam sobre o drone e entender como compensá-las.

Naturalmente, aí entramos na física e matemática, de maneira profunda e divertida – mas isso fica para o próximo post, onde vamos detalhar a dinâmica do veículo em vôo.

Leia: O que acontece em campeonatos de corrida de drone

Ao todo, esses requisitos todos querem dizer que incluímos ao menos mais duas dimensões às dimensões de controle do nosso quadcopter (e vem mais por aí!):

  • Espaço tridimensional com três eixos de rotação (roll, pitch, yaw)
  • Deslocamentos em três dimensões
  • Coordenadas geográficas locais
  • Coordenadas geográficas globais

Considerando estas três representações espaciais, podemos enfim criar uma representação única: a Configuration Space.

É essa representação, considerando todas as dimensões aplicadas e os obstáculos (uau…), que é usada no planejamento da navegação. A Configuration Space é a representação digital do local onde o nosso quadrocopter vai voar.

Dá para entender a configuration space no desenho abaixo:

Uma navegação inteligente

Resolvemos o problema do mapa. E como fazer o drone seguir para o próximo waypoint que realmente requer uma mudança de atitude ao invés de parar para recalcular em cada célula?

Neste ponto, juntamos três algoritmos muito interessantes:

  • Pontos colineares
  • Ray-tracing
  • Bresenham

O primeiro faz um triângulo dos três waypoints (atual, próximo e o que vem depois). Se a área deste triângulo for zero, voilá: temos três pontos colineares.

Se quisermos que o nosso drone seja realmente inteligente – que, ao invés de voar em caminhos quadrados, ele pense em como calcular diagonais e “novos pontos” –, aplicamos os algoritmos chamados ray-tracing e bresenham.

Esses três algoritmos podem ser embarcados ou não, dependendo da capacidade de memória e processamento do drone. Nos casos em que o drone não possui memória suficiente, estes algoritmos são executados em um sistema de controle, e os waypoints já processados são carregados no drone.

Bom, não é exatamente o que queremos em um drone que tome certas decisões sozinho, ou seja, autônomo. No nosso caso, vamos considerar que todas as decisões estão embarcadas no software do drone autônomo.

Assim, nosso drone calcula uma nova rota (o ray-tracing em si) com um ponto ao invés de dois, e usa arredondamentos para reduzir a complexidade das operações (bresenham).

Pronto! Nossa navegação ficou mais inteligente:

Agora fazemos uma nova representação do nosso mapa usando todas as técnicas acima e nosso drone estará pronto para voar. Para incluir as margens de segurança, normalmente é usada uma representação chamada de Voronoi que facilita muito a navegação, e inclui um fator de segurança na distância com os obstáculos.

Esta representação nos ajuda a recalcular os possíveis waypoints – aqueles pontos que criam a trajetória de qualquer veículo voador –, padronizando as rotas e consecutivamente as distâncias das rotas em relação aos obstáculos, criando uma representação como a seguir:

Representação de Voronoy com waypoints desenhados

Se sua cabeça está girando, você não está sozinho. É muita coisa mesmo. Mas a aplicação de todas estas técnicas no segundo projeto do Nanodegree de Voo Autônomo ficou muito divertida (sério!).

Neste projeto, chamado 3D Motion Planning, é possível aplicar todas as técnicas descritas acima e testar sua criação em um simulador de voo que tem ruas, edifícios e obstáculos. É sensacional.

Com todos aprendizados sobre navegação, aliados aos aprendizados anteriores que já descrevi em outros artigos, fortaleceu-se minha vontade de ter um drone programável de verdade: eu já comecei a montar o meu.

Ao completar esta parte do curso e aplicar meus conhecimentos no mundo real, consolidei minha impressão de que o voo autônomo e é completamente factível – e é uma questão de tempo até termos drones autônomos zunindo pelas cidades.

Leia também:

Alexandre Nogueira é engenheiro de computadores e trabalha com desenvolvimento de novos negócios na Ericsson, em São Paulo. Interessado em tecnologias emergentes e novas oportunidades, retomou os estudos na Udacity com o Nanodegree Engenheiro de Carro Autônomo e hoje é aluno do Nanodegree Voo Autônomo.