Planejamento de movimento

problemas de baixa dimensão podem ser resolvidos com algoritmos baseados em grade que sobrepõem uma grade em cima do espaço de configuração, ou algoritmos geométricos que computam a forma e conectividade de Cfree.

o planejamento exato de movimento para sistemas de alta dimensão sob restrições complexas é computacionalmente intratável. 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 dos mínimos locais, e resolvem muitos problemas muito rapidamente.Eles são incapazes de determinar que nenhum caminho existe, mas eles têm uma probabilidade de falha que diminui para zero à medida que mais tempo é gasto.Algoritmos baseados em amostragem são atualmente considerados de última geração 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 robôs legged).

There is the motion planning parallel algorithm (A1-A2) for objects manipulation (for catching the flying object).

Searchedit baseado 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 grelha, o robô pode mover-se para pontos adjacentes da grelha, desde que a linha entre eles esteja completamente contida dentro do Cfree (isto é testado com detecção de colisão). Isto discreta o conjunto de ações, e algoritmos de busca (como um*) são usados para encontrar um caminho desde o início até o objetivo.

estas abordagens requerem a definição de uma resolução da grelha. Search is faster with coarser grids, but the algorithm will fail to find paths through narrow portions of Cfree. 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 grid produzem caminhos cujas mudanças de rumo são limitadas a múltiplos de um dado ângulo de base, muitas vezes resultando em caminhos subóptimos. Abordagens de planejamento de trajetos de any-angle encontram caminhos mais curtos, propagando informações ao longo das bordas da grade (para pesquisar rapidamente) sem restringir seus caminhos para as bordas da grade (para encontrar caminhos curtos).

abordagens baseadas em grade Muitas vezes precisam procurar 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 caminho seguinte. Algoritmos de busca heurística incrementais replan rápido, usando a experiência com os problemas anteriores de planejamento de caminho similares para acelerar a sua busca pela atual.

Searchedit baseado em intervalo

estas abordagens são semelhantes às abordagens de busca baseadas em grade, exceto que geram uma pavimentação cobrindo inteiramente o espaço de configuração em vez de uma grade. A pavimentação é decomposta em duas subpavagens X−,X+ feitas com caixas tais que X− ⊂ Cfree ⊂ X+. Caracterizar Cfree equivale a resolver um problema de inversão. A análise do intervalo poderia, assim, ser utilizada quando o Cfree não pode ser descrito por desigualdades lineares a fim de ter um compartimento garantido.

o robô pode assim mover− se livremente em X -, e não pode sair de X+. Para ambos os subpavings, um grafo vizinho é construído e caminhos podem ser encontrados usando algoritmos como Dijkstra ou a*. Quando um caminho é viável em X -, ele também é viável em Cfree. Quando não existe nenhum caminho em X+ de uma configuração inicial para o objetivo, temos a garantia de que não existe nenhum caminho viável no Cfree. Quanto à 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 com 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 tem de se mover da esquerda para a direita, evitando dois pequenos segmentos horizontais.

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

Geométricas algorithmsEdit

Ponto de robôs entre poligonal obstáculos

• Visibilidade gráfico de
• Célula decomposição

Tradução objetos entre obstáculos

• Minkowski soma

Encontrar a maneira de sair de um edifício

• mais distante ray trace

Dado um feixe de raios em torno da posição atual atribuído com seu comprimento de bater em uma parede, o robô move-se para a direção de maior raio, a menos que uma porta é identificada. Tal algoritmo foi usado para modelagem de saída de emergência de edifícios.Uma abordagem é tratar a configuração do robô como um ponto em um campo potencial que combina atração para o objetivo, e repulsão de obstáculos. A trajetória resultante é saída como o caminho. Esta abordagem tem vantagens em que a trajetória é produzida com pouca computação. No entanto, eles podem ficar presos em mínimos locais do campo potencial e não conseguem encontrar um caminho, ou podem encontrar um caminho não-ideal. Os campos potenciais artificiais podem ser tratados como equações contínuas semelhantes aos campos potenciais eletrostáticos (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.

algorithmsEdit por amostragem

algoritmos baseados em amostragem representam o espaço de configuração com um roteiro de Configurações amostradas.A basic algorithm samples N configurations in C, and retains those in Cfree to use as milestones. Um roteiro é então construído que conecta dois marcos P E Q Se o segmento de linha Pq é completamente em Cfree. Novamente, detecção de colisão é usada para testar a inclusão no Cfree. Para encontrar um caminho que conecte S E G, eles são adicionados ao roteiro. Se um caminho no roteiro links S E G, O planejador tem sucesso, e retorna esse caminho. Caso contrário, a razão não é definitiva: ou não há caminho no Cfree, ou o planejador não provou Marcos suficientes.

estes algoritmos funcionam bem para espaços de configuração de alta dimensão, porque ao contrário de 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 a probabilidade de que eles irão produzir uma solução aproxima-se 1 como mais tempo é gasto. No entanto, não podem determinar se não existe uma solução.

dadas as condições básicas de visibilidade no Cfree, tem sido provado que, à medida que o número de Configurações N cresce mais alto, a probabilidade de que o algoritmo acima encontra uma solução aproxima-se 1 exponencialmente. A visibilidade não depende explicitamente da dimensão de C; é possível ter um espaço de alta dimensão com “boa” visibilidade ou um espaço de baixa dimensão com “má” visibilidade. O sucesso experimental de métodos baseados em amostras sugere que os espaços mais comumente vistos têm boa visibilidade.

existem muitas variantes deste regime básico:

• é tipicamente muito mais rápido testar apenas segmentos entre pares próximos de Marcos, em vez de todos os pares.
• distribuições de amostragem não-uniforme tentam colocar mais Marcos em áreas que melhoram a conectividade do roteiro.
• Quasirandom amostras, normalmente, produzir uma melhor cobertura do espaço de configuração de pseudo-queridos, embora alguns trabalhos recentes argumenta que o efeito da fonte de aleatoriedade é mínimo quando comparado com o efeito da distribuição de amostragem.
• emprega amostragem local através da realização de uma cadeia direcional de Markov Monte Carlo random walk com alguma distribuição de proposta local.
• é possível reduzir substancialmente o número de Marcos necessários para resolver um dado problema, permitindo vistas curvas (por exemplo, rastejando sobre os obstáculos que bloqueiam o caminho entre dois marcos).Se forem necessárias apenas uma ou algumas consultas de planeamento, nem sempre é necessário construir um roteiro de todo o espaço. Variantes de crescimento de árvores são tipicamente mais rápidas para este caso (planejamento de consulta única). Roteiros ainda são úteis se muitas consultas estão a ser feitas no mesmo espaço (multi-consulta de planeamento)

Lista de notáveis algorithmsEdit

• A*
• D*
• Rapidamente-explorar aleatório árvore
• Probabilística roteiro