Qual é a melhor maneira de navegar e evitar obstáculos para um robô de serviço?
Os robôs são sistemas mecânicos e de software que interagem com o mundo real. Para um robô de serviço, é extremamente importante entender sua posição atual no espaço, a posição do alvo e a capacidade de construir uma rota para o alvo, evitando possíveis obstáculos. Estamos desenvolvendo um
robô para coletar bolas de golfe no driving range . Consideramos opções diferentes para a construção de uma rota, a fim de encontrar a melhor para nós mesmos, talvez essa informação seja interessante para alguém.
A maneira mais fácil de fazer com que o robô direcione para seu objetivo final no espaço bidimensional. O veículo espacial aqui é um pequeno ponto em frente ao qual não há obstáculos. Portanto, o robô nessa situação se move em linha reta e, quando atinge a meta, para.
Este método é adequado se houver apenas um robô no mundo e o objetivo que ele deve alcançar. O Direct permitirá que você alcance a configuração final o mais rápido possível.
Mas esse algoritmo não pode ser aplicado se um obstáculo surgir repentinamente na frente do robô. Movendo-se em linha reta, o veículo espacial não poderá contorná-lo ou passar por ele. Nesse contexto, ele simplesmente para na frente de um obstáculo e não segue em frente.
Como contornar um obstáculo? A maneira mais fácil de resolver o problema é a opção de comportamento chamada "Prevenção de Obstáculos". Na prática, é representado por vários algoritmos.
Walk To Algorithm
Se o objetivo não for alcançado:
- Avance para o objetivo.
- Caso contrário: pare.
Este método é adequado se houver apenas um robô no mundo e o objetivo que ele deve alcançar. O Direct permitirá que você alcance a configuração final o mais rápido possível. Mas qual algoritmo deve ser aplicado se surgir um obstáculo na frente do alvo na frente do robô?
Um obstáculo não permite que o robô chegue ao seu destino em uma linha reta, o rover nesta situação apenas para na frente dele. Nesse caso, você também pode usar o algoritmo “Walk To”, mas ele precisa ser complementado.
Algoritmo de Bug
Na vida cotidiana, uma pessoa, quando vai de um ponto a outro ao objetivo e se depara com um obstáculo, simplesmente o ignora. Esse comportamento é chamado de "evitar obstáculos". Ele será aplicado para atingir a meta do robô. A maneira mais fácil de aplicar o algoritmo de besouro.
O algoritmo Bug é chamado por especialistas dessa maneira porque o comportamento do besouro é tomado como base - se ele vê um obstáculo, ele o ignora.
Os passos que o robô dá ao se mover em direção ao alvo (inclusive ao andar em torno de um obstáculo) são chamados de trajetória.
O algoritmo de bug serviu de base para os conceitos usados na construção de rotas de um tipo mais complexo. Estes incluem:
Conceito de trajectória. Esta é uma sequência simples de movimentos do robô, que ele realiza para atingir o objetivo final. O algoritmo do besouro também é um "Planejador de trajetória". Tendo recebido as coordenadas dos pontos em que o robô e seu alvo estão localizados, o algoritmo desenvolve uma trajetória de movimento apropriada.
Conceito de política . Se usar o algoritmo de besouro, certas instruções de movimento são transmitidas ao robô, então essa maneira de construir a rota é chamada de “Política de Gerenciamento”.
Conceito heurístico. Este é o nome da regra usada para informar o robô sobre o próximo estágio do algoritmo. Nessa situação, a heurística é a linha pela qual o objeto se move. Ao criar um caminho, você precisa determinar corretamente a heurística. Se isso for feito incorretamente, a rota construída ficará inoperante.
No entanto, esse algoritmo limita o desenvolvedor, porque com sua ajuda será possível construir uma rota com tamanho limitado. Ao usar esse algoritmo para construir um caminho, é necessário que todos os obstáculos tenham a forma de um polígono convexo.
O algoritmo Bug também tem limitações:
- os obstáculos devem estar a uma certa distância um do outro, é impossível que eles tenham um terreno comum;
- os limites dos obstáculos são curvas fechadas, embora devam ser tais que a linha reta ao longo da qual o robô se move intercepte cada um deles por um número limitado de vezes;
- um robô é um ponto desproporcionalmente pequeno, para que possa se mover entre obstáculos, independentemente da passagem entre eles.
Algumas dessas limitações podem ser superadas usando o algoritmo avançado DH-Bug. Sua característica é que, com sua ajuda, o robô será capaz de lidar com obstáculos em movimento. Além disso, esse algoritmo consiste em duas camadas. O primeiro é consultivo. Ele permite que você pré-avalie a rota sem usar informações adicionais. A segunda camada é adaptável. Graças a ele, o robô responde oportunamente aos obstáculos que não foram estabelecidos no programa inicialmente.
Algoritmo CBUG
O algoritmo CBUG é uma versão da construção de rotas de maneira a levar em consideração todos os detalhes. Durante o seu desenvolvimento, os especialistas levaram em conta o tamanho do robô e também resolveram problemas relacionados à otimização do caminho criado. Uma característica distintiva de um algoritmo aprimorado é que, para gerar uma rota, é necessário que o ponto de partida permaneça sempre na memória do objeto. Invariavelmente para o algoritmo CBUG, apenas que para sua aplicação é necessário ter uma quantidade fixa de memória.
Algoritmo de Dijkstra
O algoritmo usado nos gráficos foi criado por E. Dijkstroy na segunda metade do século passado. Com sua ajuda, será possível determinar o caminho mais curto de um dos vértices do gráfico para outros. Esse algoritmo termina quando o robô visita todos os picos. Se aqueles que ele ainda não visitou montam, um pico com uma marca mínima é selecionado.
As vantagens do algoritmo Deister incluem:- prestando atenção ao comprimento do caminho e seu custo;
- nós são atualizados se um mais ideal for encontrado.
A desvantagem desse método de construção de uma rota é que ela é adequada apenas para gráficos em que não há arestas de peso negativo. É inconveniente que ele esteja mal orientado ao pesquisar em largura.
Algoritmo de Bellman-Ford
Mas muitas vezes surgem situações em que é necessário construir uma rota em que haja costelas com peso negativo. O algoritmo Bellman-Ford ajudará a resolver esse problema. Se, como resultado, a soma dos pesos das arestas do caminho final tiver um valor negativo, será chamado de ciclo negativo.
Algoritmo de Johnson
Este algoritmo foi introduzido pelo DB Johnson, a fim de identificar todas as rotas mais curtas de um pico para outro. Nesse caso, o método pode ser usado para arestas com pesos positivos e negativos. A única desvantagem do algoritmo é que não há ciclos negativos.
Algoritmo A *
Para encontrar a melhor maneira de usar gráficos, você precisa aplicar o algoritmo A *. Ele permite que você determine a melhor rota do robô para o alvo pela primeira partida no gráfico. A base desse algoritmo é a fórmula heurística, que é a seguinte:
f(n)=g(n)+h(n).
f(n) - , n.
g(n) - n .
h(n) - .Esse algoritmo permite encontrar o caminho mais curto para a meta até que h (n) obtenha o valor máximo permitido. Uma característica do algoritmo A * é a sua flexibilidade. Na maioria das vezes, o estado é a célula ou a localização do robô. Mas também pode ser velocidade ou orientação.
Ao mesmo tempo, os estados vizinhos variam de acordo com o caso específico.
A flexibilidade do algoritmo também se manifesta no fato de que o objetivo que o robô precisa alcançar pode consistir em várias posições ao mesmo tempo. Em tal situação, a aproximação heurística h (n) deve ser válida imediatamente para todos os propósitos disponíveis.
A eficácia do algoritmo A * depende do expoente h (n). Quanto melhor a qualidade da aproximação heurística, maior a eficiência. Além disso, a quantidade de memória livre e o tempo do processador afetam a operação do algoritmo.
Algoritmo de rastreamento de ondas
Além disso, um algoritmo de onda é frequentemente usado para desenhar uma rota em um gráfico. Ao construir um caminho dessa maneira, é utilizado o método de pesquisa da primeira largura.
O próprio algoritmo inclui as seguintes etapas:- inicialização
- construção de ondas;
- recuperação de rota.
No estágio inicial, a imagem de muitas células é criada, cada uma das quais se torna aceitável ou intransitável para o robô.
O robô, movendo-se de uma célula para outra, determina sequencialmente se é possível passá-lo e se ele não o marcou antes.
Depois disso, o caminho mais curto da célula inicial até a final é criado pela força bruta, cuja realização é o objetivo do rover.
Algoritmo de espaço discreto
- O espaço de configuração tem um tamanho constante em todas as dimensões.
- Discrete todas as medições para que elas tenham um número constante de células.
- Todas as células localizadas no espaço de configuração dentro do obstáculo devem ser marcadas como intransitáveis.
- Como resultado, todas as células passáveis se transformaram em nós.
- Cada nó se conecta a todos os vizinhos no gráfico.
Localizador de Caminho Aleatório
Os aspectos mais difíceis ao planejar uma rota são calcular o espaço de configuração e determinar o caminho mais conveniente ao passar por esse espaço. Graças aos roteiros, será possível resolver esses problemas. A essência do método é dividir o espaço em quadrados idênticos, conectando todos os vértices mais próximos. Iterar sobre todos os caminhos. Classifique todos os caminhos para encontrar o caminho com o menor valor.
Algoritmo probabilístico de mapas de estradas
- 1. Crie um gráfico vazio G.
- 2. Adicione ao gráfico G os nós do robô e seu objetivo final.
- 3. Para o enésimo número de integrações:
- Encontre uma amostra aleatória uniforme do espaço de configuração e dê o nome R.
- Se o robô estiver em conflito com a configuração R, você poderá continuar.
- Caso contrário: adicione R à coluna G.
- 4. Identifique todos os nós no gráfico que estão localizados nos pontos d e R.
- 5. Para todos os N nós que se encaixam neste parâmetro:
Explorando Rapidamente o Algoritmo de Árvores Aleatórias
Às vezes, você precisa criar um caminho sem aplicar consultas de planejamento anteriores. Em tais situações, você deve usar o seguinte método:
- Crie uma árvore T. vazia
- Adicione à T a configuração inicial do robô.
- Até que a meta seja alcançada:
- Busca para o nó R.
- Defina em T o nó localizado mais próximo de R. Dê a ele o nome K.
- Mova o robô de K para R até que a seguinte condição seja atendida:
- No caso de uma colisão, prossiga para a definição de uma amostra aleatória.
- Caso contrário: adicione um novo nó a T nesta configuração.
- Se a distância máxima entre d e K for alcançada, comece a trabalhar na amostragem aleatória novamente.
- A solução é obtida se o nó da cadeia estiver localizado dentro da distância d de qualquer nó T.
Conclusão
Para nós, é ideal separar a questão da construção de rotas em global e local. Uma rota global é uma lista de pontos de destino para ignorar o campo ou o objetivo de retornar à base. Uma rota local começa quando sensores ultrassônicos ou um para-choque detectam um obstáculo.
Como em nossas especificidades todos os obstáculos são convexos, usamos o algoritmo BUG mais simples e ainda mais simples. Um certo método de navegação "infantil". Quando um ultrassom detecta um obstáculo, o veículo espacial gira no sentido horário 90 graus, passa 1m e gira 90 no sentido anti-horário. Se um obstáculo for detectado pelo pára-choques, antes de virar o robô 0,5 metros para trás.
Planos
Durante o início do projeto, no verão de 2018. Um grande número de eventos aconteceu. Estamos preparando um post sobre o desenvolvimento do nosso projeto. Obrigado pela atenção!
Referências