Um algoritmo de busca nada mais é do que um algoritmo que recebe um problema de busca como entrada e retorna uma solução dentro de um conjunto de possibilidades. O algoritmo de busca A* é utilizado em vários campos da ciência da computação, podendo também ser aplicado em problemas de busca relacionados a robótica móvel. O A* foi criado como parte de um projeto de robô móvel de propósito geral chamado Shakey (1972), um dos resultados mais notáveis do Shakey foi a utilização desse algoritmo de busca.

drawing200

Shakey o robô

Não mais importante que o Shakey, porém relevante, o TurtleBot3 colheu os frutos da evolução dos algoritmos de busca após mais da 30 anos da criação do Shakey! Sim, é possível utilizar o A* no TurtleBot3.

O algoritmo A*

O algoritmo A* utiliza grafos como base do sistema de busca. O vértice inicial representa o ponto inicial em que se pretende realizar a busca e o ponto final é o objetivo final, o algoritmo é formulado em termos de gráficos ponderados visando encontrar um caminho para o objetivo dado com o menor custo (menor distância percorrida, etc.). O algoritmo faz isso mantendo uma quantidade de caminhos originados do ponto inicial e expandindo esses caminhos um ponto de cada vez até que seu critério de busca seja satisfeito.

drawing400

TurtleBot 3

Para realizar a navegação com A* foi utilizado o modelo Burger do Turtlebot3, ele é um robô móvel pequeno, acessível, programável e baseado em ROS para uso em educação, pesquisa, hobby e prototipagem de produto.

drawing200

TurtleBot3 Burger

Algumas conceitos foram importantes para o desenvolvimento da navegação, a utilização de algumas funcionalidades e pacotes específicos do ROS (Robot Operating System) foram utilizados, a seguir esse conceitos serão detalhados.


Move base

O move base é um pacote do ROS que, dado um objetivo no mundo, tentará alcançá-lo, sendo que o robô parte de um ponto de referência inicial para o objetivo final. O nó move base vincula um planejador global e local para realizar sua tarefa de navegação global, para esse desenvolvimento foi utilizado o planejador global GlobalPlanner que irá utilizar o algoritmo A*, a seguir um esquema que explica a estrutura do move base no ambiente ROS:

drawing450

Utilizando o Move base com o A*

O burger foi capaz de cumprir o objetivo selecionado pelo move base fazendo um planejamento de rota utilizando o A*! A região colorida representa o potencial desenvolvido pelo algoritmo, a linha verde representa a rota considerada ideal para alcançar o objetivo selecionado.

drawing400

AMCL

Amcl é um sistema de localização probabilística para um robô se movendo em 2D. Ele implementa a abordagem de localização adaptativa (ou amostragem KLD) de Monte Carlo (conforme descrito por Dieter Fox), que usa um filtro de partículas para rastrear a pose de um robô em relação a um mapa conhecido, a seguir um exemplo:

drawing400

Utilizando o Move base com o AMCL e o A*

O Amcl consegue criar uma navegação mais precisa, já que a utilização de um mapa previamente criado acrescenta mais precisão na navegação.

drawing400

Conclusão

A implementação do algoritmo de busca A* aplicado a navegação do turtlebot permitiu aprofundar o conhecimento sobre conceitos como algoritmos de busca, ROS (Robot Operating System) e navegação em robótica.



Autor


amarco
Anderson Lima
Pesquisador em Robótica no Centro de Competências em Robótica e Sistemas Autônomos do Senai Cimatec. Anderson é formado em engenharia civil. Exerce atualmente a função de pai 24 horas.