Kinodynamic Planning

Também chamado: kinodynamic motion planning
Categoria: Planning & manipulation › Motion planning
Tags: motion-planning, dynamics, sampling-based-planning, trajectory-optimization, state-space

Planejamento de movimento que respeita tanto restrições geométricas, como colisões, quanto a dinâmica do sistema, encontrando entradas de controle ao longo do tempo em vez de apenas um caminho livre de colisões.

Definição

Planejamento cinodinâmico (kinodynamic planning) é o planejamento de movimento em que a solução precisa satisfazer ao mesmo tempo restrições cinemáticas, como evitar obstáculos e limites das juntas, e restrições dinâmicas, como acelerações, forças ou torques limitados. O termo foi introduzido por Donald, Xavier, Canny e Reif em 1993. Em vez de buscar um caminho geométrico no espaço de configurações e definir os tempos depois, um planejador cinodinâmico busca uma duração e uma função de controle cuja trajetória resultante, obtida integrando a dinâmica do sistema, comece no estado inicial, permaneça no espaço livre e termine em uma região objetivo.

A busca acontece, portanto, no espaço de estados, que inclui velocidades além de posições e muitas vezes tem o dobro da dimensão do espaço de configurações. A principal dificuldade é que dois estados próximos em geral não podem ser ligados por uma linha reta: conectá-los exige resolver um problema de valor de contorno de dois pontos sob a dinâmica, o que é fácil para sistemas simples como integradores duplos ou carros de Dubins, mas difícil em geral. Planejadores baseados em amostragem, como o RRT cinodinâmico introduzido por LaValle e Kuffner, evitam isso fazendo uma árvore crescer para a frente: escolhem um nó, aplicam controles amostrados ou escolhidos por um tempo curto e mantêm os estados resultantes. Métodos posteriores como o SST acrescentam quase otimalidade assintótica sem precisar de uma função de direcionamento (steering function).

Outras famílias tratam o mesmo problema de forma diferente. Planejadores baseados em busca usam um reticulado de primitivas de movimento pré-calculadas, cada uma delas dinamicamente factível. Métodos de otimização de trajetória, incluindo a colocação direta e o tiro (shooting), tratam os controles e os estados como variáveis de decisão e resolvem um programa não linear com restrições, que converge rapidamente em nível local, mas pode ficar preso em mínimos locais. Sistemas práticos muitas vezes combinam os dois: uma etapa de amostragem ou de busca encontra uma trajetória factível, e a otimização então a refina. Quando a dinâmica é incerta, como ao empurrar objetos, os planejadores podem usar modelos aprendidos ou residuais do sistema e planejar com controles em malha aberta que depois são corrigidos por realimentação.

Por que importa

Robôs rápidos ou pesados, carros, drones e objetos empurrados não conseguem seguir caminhos geométricos arbitrários: um caminho que ignora a quantidade de movimento ou os limites dos atuadores pode ser impossível de executar. O planejamento cinodinâmico produz trajetórias que o sistema consegue de fato seguir, o que importa mais quando o robô se move rápido ou tem autoridade de controle limitada.

Principais aplicações

Planejamento de trajetória para carros e outros veículos não holonômicos
Planejamento de voo agressivo para drones e aeronaves de asa fixa
Manipulação não preênsil, como o planejamento de sequências de empurrões
Movimentos rápidos de braços perto dos limites de torque e velocidade
Planejamento de movimento de robôs com pernas e humanoides com dinâmica de contato
Manobras de espaçonaves e veículos subaquáticos

Na prática

Um braço robótico precisa empurrar uma caixa sobre uma mesa até uma região objetivo, evitando um obstáculo, sem agarrá-la. A equipe modela o movimento da caixa em função de parâmetros do empurrão, como ponto de contato, direção e duração, usando um modelo analítico de empurrão corrigido por um residual aprendido. Um RRT cinodinâmico amostra ações de empurrão a partir do estado atual da caixa, propaga cada uma pelo modelo e acrescenta à árvore as poses resultantes da caixa, descartando empurrões que colidiriam com o obstáculo. Quando um ramo alcança a região objetivo, a sequência de empurrões é executada, e a pose da caixa é observada de novo após cada empurrão para que o planejador possa replanejar a partir do estado real se o modelo estiver errado.

Equívocos comuns

Planejamento cinodinâmico é planejamento geométrico seguido de parametrização temporal — pipelines desacoplados podem produzir caminhos que nenhuma trajetória dinamicamente factível consegue seguir, enquanto planejadores cinodinâmicos consideram a dinâmica durante a busca
Qualquer planejador baseado em amostragem pode virar cinodinâmico trocando a métrica de distância — conectar dois estados em geral exige resolver um problema de valor de contorno ou propagar controles para a frente, não traçar uma linha reta
Um plano cinodinâmico pode ser executado em malha aberta — erros de modelo e perturbações se acumulam, então o plano normalmente é seguido com um controlador por realimentação ou replanejado

Quem deve saber

Engenheiros de planejamento de movimento para veículos, drones e braços
Pesquisadores de manipulação que trabalham com empurrões e outras tarefas dinâmicas
Engenheiros de planejamento para direção autônoma
Estudantes de robótica que estudam planejamento além do espaço de configurações

Tecnologias relacionadas

RRT cinodinâmico (Kinodynamic RRT)
Stable Sparse RRT (SST)
Planejadores de reticulado de estados (State Lattice Planners)
Open Motion Planning Library (OMPL)
Otimização de trajetória (Trajectory Optimization)

Termos relacionados

Projetos relacionados

Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
mink: Python inverse kinematics library built on MuJoCo supporting 20+ robot platforms
Ruckig: Real-time jerk-constrained time-optimal trajectory generation for robots and machines

Vídeos

6.8210 Spring 2024 Lecture 18: Sampling-based (kinodynamic) motion planning: underactuated