Anytime Motion Planning

• Também chamado: anytime planning, anytime planner
• Categoria: Planning & manipulation › Motion planning
• Tags: motion-planning, sampling-based-planning, optimal-planning, real-time, bounded-computation

Planejamento de movimento que devolve rapidamente um caminho válido e depois continua a melhorá-lo enquanto houver tempo, de modo que há uma resposta utilizável sempre que o planejador for parado.

Definição

Um planejador de movimento anytime (anytime motion planner) produz uma primeira solução viável e livre de colisões o mais cedo que consegue e depois usa o tempo restante para melhorá-la, normalmente reduzindo o comprimento do caminho, o tempo de execução ou outro custo. Em cada momento após a primeira solução, ele mantém a melhor resposta até então, que pode ser devolvida se ele for interrompido. A ideia vem da noção mais ampla de algoritmos anytime em inteligência artificial, introduzida por Dean e Boddy no fim da década de 1980, em que a qualidade da solução é trocada por tempo de computação e a relação entre as duas é descrita por um perfil de desempenho.

Na busca em grafos, o comportamento anytime costuma ser obtido executando primeiro uma heurística ponderada e inflada e depois apertando o peso enquanto se reaproveita o esforço de busca anterior, como no Anytime Repairing A (ARA). No planejamento baseado em amostragem, planejadores assintoticamente ótimos como o RRT e a variante PRM dos mapas de rotas probabilísticos são anytime por natureza: continuam amostrando e religando após a primeira solução, e o custo do melhor caminho tende ao ótimo à medida que o número de amostras cresce. Informed RRT e Batch Informed Trees (BIT) aceleram a fase de melhoria restringindo as amostras à região que ainda poderia conter um caminho melhor. Uma árvore aleatória de exploração rápida** simples não é anytime nesse sentido, porque para assim que conecta o objetivo, embora reinícios ou pós-processamento possam ser acrescentados em torno dela.

A melhoria ao longo do tempo raramente é suave. O custo costuma cair em degraus, sobretudo quando o planejador encontra uma rota por uma abertura diferente entre obstáculos, isto é, um caminho em uma nova classe de homotopia, e longos trechos podem trazer quase nenhum ganho. Isso faz da decisão de parar um problema por si só: parar cedo demais desperdiça qualidade, parar tarde demais desperdiça tempo que o robô poderia passar se movendo. Orçamentos de tempo fixos são a prática usual, enquanto métodos de metarraciocínio aprendem ou estimam quando mais computação já não vale a pena.

Por que importa

Robôs raramente têm uma quantidade de tempo fixa e conhecida para planejar. Um planejador anytime oferece quase de imediato uma alternativa segura e transforma qualquer tempo de sobra em um movimento melhor, o que convém a sistemas que precisam agir dentro de um prazo mas ainda se importam com a qualidade do caminho, a energia ou o tempo de ciclo.

Principais aplicações

• Planejamento de movimento de braços com orçamentos de tempo por consulta em pipelines de manipulação
• Replanejamento para robôs móveis e veículos que precisam agir em um ciclo de controle fixo
• Planejamento de caminhos para robôs aéreos, em que caminhos mais curtos economizam bateria
• Busca heurística em grafos sobre grades e reticulados com redução de peso no estilo do ARA*
• Pesquisa em metarraciocínio sobre quando parar de planejar e começar a agir

Na prática

Um manipulador móvel planeja os movimentos do braço com um planejador baseado em amostragem assintoticamente ótimo de uma biblioteca como o OMPL. Cada consulta recebe um orçamento de tempo: o planejador costuma encontrar um primeiro caminho no início desse orçamento e depois continua a encurtá-lo. A equipe registra o melhor custo em função do tempo decorrido em muitas consultas gravadas e vê que a maior parte do ganho chega cedo, com quedas grandes ocasionais quando uma rota mais curta em torno de um obstáculo é encontrada tarde. Em vez de sempre gastar o orçamento inteiro, eles param quando o custo não melhora por um intervalo definido, ou usam uma regra de parada aprendida, e então aplicam atalhos e parametrização temporal ao resultado antes de enviá-lo ao controlador.

Equívocos comuns

• Anytime significa que a primeira solução é quase ótima — a primeira solução costuma estar longe do ótimo, e a qualidade depende de quanto tempo o planejador roda
• O custo melhora de forma constante com o tempo — ele normalmente cai em degraus irregulares, com longos platôs entre eles
• A otimalidade assintótica garante um bom caminho dentro do orçamento de tempo — ela só descreve o limite quando a computação cresce sem limite e não diz nada sobre um prazo finito
• Usar todo o orçamento de tempo é sempre o melhor — tempo gasto planejando é tempo não gasto se movendo, então parar cedo costuma ser a melhor troca

Quem deve saber

• Engenheiros de planejamento de movimento que configuram planejadores baseados em amostragem ou em busca
• Desenvolvedores de manipulação móvel e navegação que trabalham com limites de tempo real
• Pesquisadores de robótica que estudam planejamento com computação limitada
• Estudantes aprendendo planejamento de movimento ótimo

Tecnologias relacionadas

• ARA (Anytime Repairing A)
• RRT*
• Informed RRT*
• BIT* (Batch Informed Trees)
• OMPL

Termos relacionados

• RRT*
• Rapidly-exploring random tree
• Probabilistic Roadmap
• Homotopy Class
• Warm Start
• Motion Planning

Projetos relacionados

• GENESIS: World's fastest physics engine: 43M FPS for embodied AI learning
• Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
• FAST-LIVO2: Fast, direct LiDAR-inertial-visual odometry from HKU-MARS, published in IEEE T-RO
• Dora AI: Dataflow middleware for AI robotics applications, built in Rust
• OpenMind OM1: AI-native operating system for robots with modular perception, cognition, and action
• Fast DDS: eProsima's high-performance DDS middleware — the default transport under ROS 2