Planejamento de movimento - Motion planning

O planejamento de movimento , também planejamento de caminho (também conhecido como o problema de navegação ou o problema do movedor de piano ) é um problema computacional para encontrar uma sequência de configurações válidas que move o objeto da origem ao destino. O termo é usado em geometria computacional , animação por computador , robótica e jogos de computador .

Por exemplo, considere navegar um robô móvel dentro de um edifício para um ponto de passagem distante. Deve executar esta tarefa evitando paredes e não caindo de escadas. Um algoritmo de planejamento de movimento pegaria uma descrição dessas tarefas como entrada e produziria os comandos de velocidade e giro enviados para as rodas do robô. Algoritmos de planejamento de movimento podem abordar robôs com um grande número de juntas (por exemplo, manipuladores industriais), tarefas mais complexas (por exemplo, manipulação de objetos), diferentes restrições (por exemplo, um carro que só pode dirigir para frente) e incerteza (por exemplo, modelos imperfeitos de ambiente ou robô).

O planejamento de movimento possui diversas aplicações de robótica, como autonomia , automação e design de robôs em softwares CAD , bem como aplicações em outras áreas, como animação de personagens digitais , videogame , projeto arquitetônico , cirurgia robótica e estudo de moléculas biológicas .

Conceitos

Exemplo de um espaço de trabalho.
Espaço de configuração de um robô do tamanho de um ponto. Branco = C livre , cinza = C obs .
Espaço de configuração para um robô de tradução retangular (foto em vermelho). Branco = C livre , cinza = C obs , onde cinza escuro = os objetos, cinza claro = configurações onde o robô tocaria um objeto ou deixaria a área de trabalho.
Exemplo de um caminho válido.
Exemplo de um caminho inválido.
Exemplo de um roteiro.

Um problema básico de planejamento de movimento é calcular um caminho contínuo que conecta uma configuração de início S e uma configuração de objetivo G, evitando a colisão com obstáculos conhecidos. A geometria do robô e do obstáculo é descrita em um espaço de trabalho 2D ou 3D , enquanto o movimento é representado como um caminho em um espaço de configuração (possivelmente de dimensão superior) .

Espaço de configuração

Uma configuração descreve a pose do robô, e o espaço de configuração C é o conjunto de todas as configurações possíveis. Por exemplo:

  • Se o robô é um único ponto (tamanho zero) transladando em um plano bidimensional (a área de trabalho), C é um plano e uma configuração pode ser representada usando dois parâmetros (x, y).
  • Se o robô tem uma forma 2D que pode ser transladada e girada, a área de trabalho ainda é bidimensional. No entanto, C é o grupo euclidiano especial SE (2) = R 2 SO (2) (onde SO (2) é o grupo ortogonal especial de rotações 2D), e uma configuração pode ser representada usando 3 parâmetros (x, y, θ )
  • Se o robô é uma forma 3D sólida que pode transladar e girar, o espaço de trabalho é tridimensional, mas C é o grupo euclidiano especial SE (3) = R 3 SO (3), e uma configuração requer 6 parâmetros: (x, y, z) para translação e ângulos de Euler (α, β, γ).
  • Se o robô é um manipulador de base fixa com N juntas de revolução (e sem loops fechados), C é N-dimensional.

Espaço livre

O conjunto de configurações que evita a colisão com obstáculos é denominado espaço livre C livre . O complemento de C livre em C é chamado de obstáculo ou região proibida.

Freqüentemente, é proibitivamente difícil computar explicitamente a forma de C free . No entanto, testar se uma determinada configuração está em C livre é eficiente. Primeiro, a cinemática direta determina a posição da geometria do robô e os testes de detecção de colisão se a geometria do robô colide com a geometria do ambiente.

Espaço alvo

O espaço alvo é um subespaço de espaço livre que indica para onde queremos que o robô se mova. No planejamento de movimento global, o espaço alvo é observável pelos sensores do robô. No entanto, no planejamento de movimento local, o robô não pode observar o espaço alvo em alguns estados. Para resolver este problema, o robô passa por vários espaços virtuais de destino, cada um deles localizado dentro da área observável (ao redor do robô). Um espaço de destino virtual é chamado de meta secundária.

Espaço de obstáculo

O espaço de obstáculo é um espaço para o qual o robô não pode se mover. O espaço de obstáculo não é oposto ao espaço livre.

Algoritmos

Problemas de baixa dimensão podem ser resolvidos com algoritmos baseados em grade que se sobrepõem a uma grade no topo do espaço de configuração ou algoritmos geométricos que calculam a forma e a conectividade de C gratuitamente .

O planejamento de movimento exato para sistemas de alta dimensão sob restrições complexas é computacionalmente intratável . Os algoritmos de campo potencial são eficientes, mas são vítimas de mínimos locais (uma exceção são os campos de potencial harmônico). Algoritmos baseados em amostragem evitam o problema de mínimos locais e resolvem muitos problemas rapidamente. Eles são incapazes de determinar que não existe nenhum caminho, mas têm uma probabilidade de falha que diminui para zero à medida que mais tempo é gasto.

Algoritmos baseados em amostragem são atualmente considerados estado da arte para planejamento de movimento em espaços de alta dimensão e têm sido aplicados a problemas que têm dezenas ou mesmo centenas de dimensões (manipuladores robóticos, moléculas biológicas, personagens digitais animados e com pernas robôs ).

Existe o algoritmo paralelo de planejamento de movimento (A1-A2) para manipulação de objetos (para pegar o objeto voador).

Pesquisa baseada em grade

Abordagens baseadas em grade sobrepõem uma grade no espaço de configuração e assumem que cada configuração é identificada com um ponto de grade. Em cada ponto da grade, o robô pode se mover para pontos adjacentes da grade, desde que a linha entre eles esteja completamente contida em C livre (isso é testado com detecção de colisão). Isso discretiza o conjunto de ações e algoritmos de pesquisa (como A * ) são usados ​​para encontrar um caminho do início ao objetivo.

Essas abordagens requerem a definição de uma resolução de grade. A pesquisa é mais rápida com grades mais grosseiras, mas o algoritmo não conseguirá encontrar caminhos através de porções estreitas de C livre . Além disso, o número de pontos na grade cresce exponencialmente na dimensão do espaço de configuração, o que os torna inadequados para problemas de alta dimensão.

As abordagens tradicionais baseadas em grade produzem caminhos cujas mudanças de direção são restritas a múltiplos de um determinado ângulo de base, geralmente resultando em caminhos abaixo do ideal. As abordagens de planejamento de caminhos de qualquer ângulo encontram caminhos mais curtos propagando informações ao longo das bordas da grade (para pesquisar rapidamente) sem restringir seus caminhos às bordas da grade (para encontrar caminhos curtos).

As abordagens baseadas em grade geralmente precisam pesquisar repetidamente, por exemplo, quando o conhecimento do robô sobre o espaço de configuração muda ou o próprio espaço de configuração muda durante o seguimento do caminho. Algoritmos de pesquisa heurística incremental replanejam rapidamente usando a experiência com os problemas de planejamento de caminho semelhantes anteriores para acelerar sua pesquisa para o atual.

Pesquisa baseada em intervalo

Essas abordagens são semelhantes às abordagens de pesquisa baseadas em grade, exceto que geram uma pavimentação que cobre inteiramente o espaço de configuração em vez de uma grade. O pavimento é decomposto em duas sub-pavimentação X - , X + feitas com caixas tais que X - ⊂ C livre ⊂ X + . Caracterizar valores livres de C para resolver um problema de inversão de conjuntos . A análise de intervalo pode, portanto, ser usada quando C livre não pode ser descrito por desigualdades lineares para ter um invólucro garantido.

O robô pode, portanto, mover-se livremente em X - e não pode sair de X + . Para ambos os subpavings, um gráfico vizinho é construído e os caminhos podem ser encontrados usando algoritmos como Dijkstra ou A * . Quando um caminho é viável em X - , também é viável em C grátis . Quando não existe nenhum caminho no X + de uma configuração inicial para o objetivo, temos a garantia de que nenhum caminho viável existe no C livre . Já para a abordagem baseada em grade, a abordagem de intervalo é inadequada para problemas de alta dimensão, devido ao fato de que o número de caixas a serem geradas cresce exponencialmente em relação à dimensão do espaço de configuração.

Uma ilustração é fornecida pelas três figuras à direita, onde um gancho com dois graus de liberdade deve se mover da esquerda para a direita, evitando dois pequenos segmentos horizontais.

Movimento desde a configuração inicial (azul) até a configuração final do gancho, evitando os dois obstáculos (segmentos vermelhos). O canto inferior esquerdo do anzol deve ficar na linha horizontal, o que torna o anzol dois graus de liberdade.
Decomposição com caixas cobrindo o espaço de configuração: O subpaving X - é a união de todas as caixas vermelhas e o subpaving X + é a união das caixas vermelhas e verdes. O caminho corresponde ao movimento representado acima.
Esta figura corresponde ao mesmo caminho acima, mas obtido com muito menos caixas. O algoritmo evita a divisão de caixas em partes do espaço de configuração que não influenciam o resultado final.

A decomposição com subpavings usando análise de intervalo também torna possível caracterizar a topologia de C livre , como contar seu número de componentes conectados.

Algoritmos geométricos

Aponte robôs entre obstáculos poligonais

Traduzindo objetos entre obstáculos

Encontrando a saída de um edifício

  • traço de raio mais distante

Dado um feixe de raios em torno da posição atual atribuída com seu comprimento atingindo uma parede, o robô se move na direção do raio mais longo, a menos que uma porta seja identificada. Esse algoritmo foi usado para modelar a saída de emergência de edifícios.

Campos potenciais artificiais

Uma abordagem é tratar a configuração do robô como um ponto em um campo potencial que combina atração ao objetivo e repulsão de obstáculos. A trajetória resultante é produzida como o caminho. Esta abordagem tem vantagens porque a trajetória é produzida com poucos cálculos. No entanto, eles podem ficar presos nos mínimos locais do campo potencial e não conseguir encontrar um caminho ou podem encontrar um caminho não ideal. Os campos de potencial artificial podem ser tratados como equações contínuas semelhantes aos campos de potencial eletrostático (tratando o robô como uma carga pontual), ou o movimento através do campo pode ser discretizado usando um conjunto de regras linguísticas. Uma função de navegação ou uma função de navegação probabilística são tipos de funções potenciais artificiais que têm a qualidade de não ter pontos mínimos, exceto o ponto alvo.

Algoritmos baseados em amostragem

Algoritmos baseados em amostragem representam o espaço de configuração com um roteiro de configurações amostradas. Um algoritmo básico faz a amostragem de configurações N em C e as mantém em C gratuitamente para serem usadas como marcos . Um roteiro é então construído que conecta dois marcos P e Q se o segmento de linha PQ estiver completamente em C livre . Novamente, a detecção de colisão é usada para testar a inclusão no C free . Para encontrar um caminho que conecte S e G, eles são adicionados ao roteiro. Se um caminho no roteiro liga S e G, o planejador é bem-sucedido e retorna esse caminho. Caso contrário, o motivo não é definitivo: ou não há caminho em C livre ou o planejador não coletou marcos suficientes.

Esses algoritmos funcionam bem para espaços de configuração de alta dimensão, porque, ao contrário dos algoritmos combinatórios, seu tempo de execução não é (explicitamente) exponencialmente dependente da dimensão de C. Eles também são (geralmente) substancialmente mais fáceis de implementar. Eles são probabilisticamente completos, o que significa que a probabilidade de produzirem uma solução se aproxima de 1 à medida que mais tempo é gasto. No entanto, eles não podem determinar se não existe solução.

Dadas as condições básicas de visibilidade em C livre , foi provado que conforme o número de configurações N aumenta, a probabilidade de que o algoritmo acima encontre uma solução se aproxima de 1 exponencialmente. A visibilidade não depende explicitamente da dimensão de C; é possível ter um espaço de grande dimensão com "boa" visibilidade ou um espaço de baixa dimensão com "má" visibilidade. O sucesso experimental dos métodos baseados em amostras sugere que os espaços mais comumente vistos têm boa visibilidade.

Existem muitas variantes deste esquema básico:

  • Normalmente é muito mais rápido testar apenas os segmentos entre pares próximos de marcos, em vez de todos os pares.
  • As distribuições de amostragem não uniformes tentam colocar mais marcos em áreas que melhoram a conectividade do roteiro.
  • Amostras quase aleatórias normalmente produzem uma cobertura melhor do espaço de configuração do que as pseudo - aleatórias , embora alguns trabalhos recentes argumentem que o efeito da fonte de aleatoriedade é mínimo em comparação com o efeito da distribuição de amostragem.
  • Emprega amostragem local executando um passeio aleatório Monte Carlo de cadeia de Markov direcional com alguma distribuição de proposta local.
  • É possível reduzir substancialmente o número de marcos necessários para resolver um determinado problema, permitindo a visão de olhos curvos (por exemplo, rastejando nos obstáculos que bloqueiam o caminho entre dois marcos).
  • Se apenas uma ou algumas consultas de planejamento são necessárias, nem sempre é necessário construir um roteiro de todo o espaço. Variantes de crescimento de árvore são normalmente mais rápidas para este caso (planejamento de consulta única). Os roteiros ainda são úteis se muitas consultas devem ser feitas no mesmo espaço (planejamento de várias consultas)

Lista de algoritmos notáveis

Completude e desempenho

Um planejador de movimento é considerado completo se o planejador em tempo finito produzir uma solução ou relatar corretamente que não há nenhuma. A maioria dos algoritmos completos é baseada em geometria. O desempenho de um planejador completo é avaliado por sua complexidade computacional . Ao provar esta propriedade matematicamente, deve-se ter certeza de que ela ocorre em tempo finito e não apenas no limite assintótico. Isso é especialmente problemático, se ocorrerem sequências infinitas (que convergem apenas no caso limite) durante uma técnica de prova específica, pois então, teoricamente, o algoritmo nunca irá parar. Os "truques" intuitivos (muitas vezes baseados na indução) são tipicamente erroneamente considerados como convergentes, o que eles fazem apenas para o limite infinito. Em outras palavras, a solução existe, mas o planejador nunca a relatará. Esta propriedade, portanto, está relacionada à Completude de Turing e serve na maioria dos casos como um suporte / orientação teórica. Os planejadores baseados em uma abordagem de força bruta são sempre completos, mas só são realizáveis ​​para configurações finitas e discretas.

Na prática, o término do algoritmo sempre pode ser garantido pelo uso de um contador, que permite apenas um número máximo de iterações e então sempre para com ou sem solução. Para sistemas de tempo real, isso normalmente é obtido usando um cronômetro de watchdog , que simplesmente interrompe o processo. O watchdog deve ser independente de todos os processos (normalmente realizado por rotinas de interrupção de baixo nível). O caso assintótico descrito no parágrafo anterior, entretanto, não será alcançado dessa forma. Ele relatará o melhor que encontrou até agora (o que é melhor do que nada) ou nenhum, mas não pode relatar corretamente que não há nenhum. Todas as realizações, incluindo um watchdog, estão sempre incompletas (exceto todos os casos que podem ser avaliados em tempo finito).

A integridade só pode ser fornecida por uma prova de correção matemática muito rigorosa (muitas vezes auxiliada por ferramentas e métodos baseados em gráficos) e só deve ser feita por especialistas especializados se a aplicação incluir conteúdo de segurança. Por outro lado, refutar a completude é fácil, uma vez que basta encontrar um loop infinito ou um resultado errado retornado. A verificação formal / correção de algoritmos é um campo de pesquisa por si só. A configuração correta desses casos de teste é uma tarefa altamente sofisticada.

A integridade da resolução é a propriedade de que o planejador tem a garantia de encontrar um caminho se a resolução de uma grade subjacente for boa o suficiente. A maioria dos planejadores completos de resolução são baseados em grade ou em intervalos. A complexidade computacional dos planejadores completos de resolução depende do número de pontos na grade subjacente, que é O (1 / h d ), onde h é a resolução (o comprimento de um lado de uma célula da grade) e d é a configuração dimensão do espaço.

Completude probabilística é a propriedade de que quanto mais "trabalho" é executado, a probabilidade de que o planejador falhe em encontrar um caminho, se houver, assintoticamente se aproxima de zero. Vários métodos baseados em amostra são probabilisticamente completos. O desempenho de um planejador probabilisticamente completo é medido pela taxa de convergência. Para aplicações práticas, costuma-se utilizar esta propriedade, pois permite configurar o time-out do watchdog com base em um tempo médio de convergência.

Os planejadores incompletos nem sempre produzem um caminho viável quando existe (ver primeiro parágrafo). Às vezes, planejadores incompletos funcionam bem na prática, uma vez que sempre param após um tempo garantido e permitem que outras rotinas assumam o controle.

Variantes do problema

Muitos algoritmos foram desenvolvidos para lidar com variantes desse problema básico.

Restrições diferenciais

Holonômico

  • Braços manipuladores (com dinâmica)

Não holonômico

  • Drones
  • Carros
  • Monociclos
  • Aviões
  • Sistemas limitados de aceleração
  • Obstáculos móveis (o tempo não pode retroceder)
  • Agulha orientável de ponta chanfrada
  • Robôs de direção diferencial

Restrições de otimização

Sistemas híbridos

Sistemas híbridos são aqueles que misturam comportamento discreto e contínuo. Exemplos de tais sistemas são:

Incerteza

  • Incerteza de movimento
  • Faltando informação
  • Detecção ativa
  • Planejamento sem sensor

Formulários

Veja também

Referências

Leitura adicional

links externos