Planejamento de Movimento

O que “Planejamento de Movimento” Significa

Planejamento de movimento (motion planning) é o processo de computar uma forma viável e, muitas vezes, ótima para um robô se mover de um estado inicial até um estado objetivo, satisfazendo restrições. Na prática, o planejamento de movimento normalmente inclui três componentes fortemente acoplados:

  1. Verificação de colisão (collision checking): garantir que o robô não interseccione obstáculos (e, muitas vezes, mantenha uma margem de segurança).
  2. Geração de caminho ou trajetória (path or trajectory generation): produzir um caminho geométrico (posições/configurações) e/ou uma trajetória parametrizada no tempo (posições, velocidades e acelerações ao longo do tempo).
  3. Pilhas de planejamento (planning stacks): a arquitetura de software que conecta percepção, mapeamento, planejamento e controle em um sistema confiável.

O planejamento de movimento se encaixa no pipeline clássico de Percepção → Planejamento → Controle (Perception → Planning → Control), interagindo de perto com Controle em malha fechada (feedback), com localização e mapeamento como Localização e Mapeamento Simultâneos (SLAM), e com camadas de segurança como Segurança em Robótica (Robotics Safety).

Formulação Central do Problema

Espaço de estados e espaço de configurações (C-space)

O “estado” de um robô depende da tarefa:

  • Robô móvel (navegação 2D): frequentemente ((x, y, \theta)).
  • Braço manipulador: ângulos das juntas (\mathbf{q} \in \mathbb{R}^n) (por exemplo, 7 graus de liberdade).
  • Estado cinodinâmico completo (full kinodynamic state): inclui velocidades (\dot{\mathbf{q}}) (e, às vezes, acelerações).

Um conceito-chave é o espaço de configurações (configuration space, C-space): o espaço de todas as configurações possíveis do robô. Obstáculos no espaço de trabalho induzem obstáculos no espaço de configurações (C-space obstacles) — regiões de configurações que causam colisões.

Planejar passa a ser: encontrar uma curva contínua (\mathbf{q}(s)) (caminho) ou (\mathbf{q}(t)) (trajetória) do início ao objetivo que permaneça no espaço livre e respeite as restrições.

Restrições comumente modeladas

  • Restrições geométricas de colisão (geometric collision constraints): a geometria do robô não pode interseccionar obstáculos.
  • Restrições cinemáticas (kinematic constraints):
    • Limites de junta: (q_i \in [q_i^{min}, q_i^{max}])
    • Restrições não holonômicas (nonholonomic constraints) (por exemplo, robôs tipo carro não conseguem se mover lateralmente).
  • Restrições dinâmicas (dynamic constraints):
    • Limites de velocidade/aceleração/tranco (jerk)
    • Limites de torque
    • Atrasos de atuação / dinâmica do atuador
  • Restrições de tarefa (task constraints):
    • Restrições de pose do efetuador final (end-effector) (manter um copo na vertical)
    • Restrições de contato (posicionamento dos pés para robôs com pernas)

Verificação de Colisão: O Cavalo de Batalha do Planejamento de Movimento

Para muitos planejadores, a verificação de colisão domina o tempo de execução. Um planejador pode testar milhares a milhões de estados ou arestas candidatos, e cada um precisa ser verificado.

O que a verificação de colisão responde

Dado:

  • Modelo do robô (elos, juntas, aproximações geométricas)
  • Modelo do ambiente (malhas, primitivos, grades de ocupação, nuvens de pontos)
  • Uma configuração (\mathbf{q}) (e, às vezes, o movimento entre (\mathbf{q}_1 \to \mathbf{q}_2))

Retorna:

  • Livre de colisão?
  • Opcional: distância até o obstáculo mais próximo, pontos de contato, profundidade de penetração, quais elos colidem

Detecção de colisão discreta vs contínua

  • Verificação de colisão discreta (discrete collision checking) testa um conjunto finito de configurações ao longo de um caminho. Ela pode deixar passar colisões por “tunelamento” (tunneling) se os passos forem grandes demais.
  • Detecção contínua de colisão (continuous collision detection, CCD) verifica se o volume varrido ao longo de uma aresta intersecciona obstáculos. A detecção contínua de colisão é mais cara, mas crucial para movimentos rápidos ou obstáculos finos.

Fase ampla e fase estreita

A verificação de colisão frequentemente é feita em etapas:

  1. Fase ampla (broad-phase): elimina rapidamente colisões improváveis usando volumes envolventes (bounding volumes) (AABB, OBB, esferas) e estruturas de aceleração espacial (spatial acceleration structures) (BVH, árvores k-d).
  2. Fase estreita (narrow-phase): verificações precisas entre pares candidatos:
    • Interseção de malhas triangulares (triangle mesh)
    • Algoritmos de colisão convexa (convex collision algorithms) como GJK (Gilbert–Johnson–Keerthi) com EPA para penetração
    • Campos de distância assinada (signed distance fields) para consultas de distância e gradientes

Exemplo prático: verificar colisão em uma aresta interpolada

Muitos planejadores baseados em amostragem (sampling-based planners) (por exemplo, RRT) verificam uma aresta interpolando entre duas configurações e testando cada amostra:

def edge_is_collision_free(q1, q2, step_size, is_state_valid):
    dist = norm(q2 - q1)
    steps = max(1, int(dist / step_size))
    for i in range(steps + 1):
        alpha = i / steps
        q = (1 - alpha) * q1 + alpha * q2
        if not is_state_valid(q):   # includes collision + joint limits, etc.
            return False
    return True

Isso é simples, mas pode ser lento e pode não detectar colisões se step_size for grande demais; a detecção contínua de colisão ou subdivisão adaptativa pode melhorar a robustez.

Saídas do Planejamento: Caminho vs Trajetória

Planejamento de caminho (geométrico)

Um caminho (path) é uma curva no espaço de configurações (\mathbf{q}(s)) sem temporização explícita. Ele garante:

  • conectividade do início ao objetivo,
  • estados livres de colisão ao longo da curva.

Exemplos:

  • A* em uma grade 2D para um robô com tração diferencial (frequentemente ignorando a dinâmica).
  • RRT em um espaço articular de 7 graus de liberdade para um braço.

Planejamento de trajetória (parametrizado no tempo)

Uma trajetória (trajectory) inclui tempo: (\mathbf{q}(t)), (\dot{\mathbf{q}}(t)), (\ddot{\mathbf{q}}(t)). Isso é necessário quando dinâmica ou temporização importam.

Etapas comuns em pilhas de robótica:

  1. Computar um caminho livre de colisão (geométrico).
  2. Parametrizar no tempo sob restrições de velocidade/aceleração/tranco.
  3. Rastrear com um controlador (controlador PID (PID), regulador linear quadrático (Linear Quadratic Regulator, LQR), controle preditivo por modelo (Model Predictive Control, MPC) etc.; veja Controle).

Técnicas de parametrização temporal (comuns na prática)

  • Ajuste de splines (spline fitting): splines cúbicas/quínticas passando por pontos de passagem (waypoints) para suavidade.
  • Trajetórias de mínimo tranco / mínimo snap (minimum-jerk / minimum-snap) (populares em quadricópteros).
  • Parametrização Temporal de Caminho com Tempo Ótimo (Time-Optimal Path Parameterization, TOPP): dado um caminho, computar a temporização mais rápida viável sob limites dinâmicos (por exemplo, métodos no estilo TOPP-RA).

Um detalhe de engenharia importante: um caminho livre de colisão não é necessariamente viável dinamicamente, especialmente perto de obstáculos ou com curvatura acentuada.

Famílias de Algoritmos de Planejamento de Movimento

Métodos de planejamento de movimento fazem trade-offs entre otimalidade, tempo de execução, robustez e requisitos de modelagem.

Busca em grafo (planejamento discreto)

Quando o mundo ou o espaço de estados é discretizado, o planejamento vira busca em grafo:

  • Algoritmo de Dijkstra: ótimo, mas pode ser lento.
  • A*: usa uma heurística (h(n)) para guiar a busca.
  • D* / D*-Lite: variantes de replanejamento para mapas que mudam.

Navegação móvel prática frequentemente usa A* ou variantes em:

  • grades de ocupação (occupancy grids),
  • mapas de custo (costmaps) (obstáculos inflados, custos de terreno).

Exemplo: A* para navegação em grade 2D (simplificado)

import heapq

def astar(start, goal, neighbors, cost, heuristic):
    open_heap = [(heuristic(start), 0.0, start)]
    came_from = {start: None}
    g = {start: 0.0}

    while open_heap:
        _, g_cur, cur = heapq.heappop(open_heap)
        if cur == goal:
            break

        for nxt in neighbors(cur):
            g_new = g_cur + cost(cur, nxt)
            if nxt not in g or g_new < g[nxt]:
                g[nxt] = g_new
                f = g_new + heuristic(nxt)
                heapq.heappush(open_heap, (f, g_new, nxt))
                came_from[nxt] = cur

    # reconstruct
    if goal not in came_from:
        return None
    path = []
    cur = goal
    while cur is not None:
        path.append(cur)
        cur = came_from[cur]
    return list(reversed(path))

Isso funciona bem para problemas de baixa dimensionalidade, mas escala mal para manipuladores com muitos graus de liberdade, a menos que seja combinado com discretização inteligente ou heurísticas.

Planejamento baseado em amostragem (planejamento em alta dimensionalidade)

Planejadores baseados em amostragem evitam discretização explícita de espaços de alta dimensionalidade:

  • PRM (Probabilistic Roadmap): constrói um roteiro (roadmap) por amostragem e depois faz consultas nele.
  • RRT (Rapidly-exploring Random Tree): cresce uma árvore a partir do início em direção a amostras aleatórias.
  • RRT*: variante assintoticamente ótima do RRT.
  • BIT*, FMT*: combinam amostragem com ordenação tipo busca em grafo para melhores trade-offs de otimalidade/tempo.

Por que são populares:

  • Escalam melhor com a dimensão do que métodos baseados em grade.
  • Podem lidar com cinemática complexa de robôs e obstáculos apenas com um verificador de colisão.

Propriedade teórica chave:

  • Muitos são probabilisticamente completos (probabilistically complete): se um caminho existe, a probabilidade de encontrá-lo vai a 1 quando o número de amostras → ∞ (assumindo condições suaves).

Loop simplificado do RRT (conceitual)

def rrt(start, sample, nearest, steer, collision_free, goal_test, max_iters):
    tree = {start: None}
    for _ in range(max_iters):
        x_rand = sample()
        x_near = nearest(tree, x_rand)
        x_new  = steer(x_near, x_rand)  # move a step toward x_rand
        if collision_free(x_near, x_new):
            tree[x_new] = x_near
            if goal_test(x_new):
                return extract_path(tree, x_new)
    return None

Na prática, o desempenho depende de:

  • verificação de colisão rápida,
  • boa amostragem (viés para o objetivo, amostragem informada),
  • boas métricas de distância e funções de direcionamento (steering functions).

Planejamento baseado em otimização (otimização de trajetória)

A otimização de trajetória formula o planejamento como a minimização de um custo sujeito a restrições:

  • CHOMP, STOMP, TrajOpt (populares em manipulação)
  • Colocação direta (direct collocation) e programação não linear (nonlinear programming) (comuns em robótica com pernas e drones)
  • Controle preditivo por modelo (MPC) quando planejamento e controle são fortemente integrados

Uma formulação típica:

[ \min_{\mathbf{q}(t)} \int_0^T \underbrace{\ell(\mathbf{q}(t), \dot{\mathbf{q}}(t))}{suavidade/esforço} + \underbrace{c{obs}(\mathbf{q}(t))}_{custo\ de\ obstáculo}, dt ] sujeito a:

  • dinâmica (opcional),
  • condições de contorno (início/objetivo),
  • limites de junta e restrições de colisão.

Prós:

  • Produz trajetórias suaves e pode incorporar custos ricos (suavidade, energia, afastamento de obstáculos).
  • Funciona bem quando existe uma estimativa inicial razoável.

Contras:

  • Pode ficar preso em mínimos locais.
  • O tratamento de restrições e a robustez exigem cuidado (especialmente em passagens estreitas).

Um padrão híbrido comum: usar RRT/PRM para encontrar um caminho viável e depois otimizar/suavizar esse caminho.

Pilhas de Planejamento de Movimento em Sistemas Reais

Robôs reais raramente dependem de um único planejador. Eles usam uma pilha que combina planejamento global, planejamento local, suavização e controle, com monitoramento de segurança.

Pilha típica para robôs móveis

  1. Mapeamento / localização (frequentemente via Localização e Mapeamento Simultâneos (SLAM))
  2. Planejador global: rota grosseira em uma grade (A*, D*)
  3. Planejador local: desvio de obstáculos e rastreamento de curto horizonte (DWA, TEB, MPC)
  4. Controlador: converte o plano local em comandos de velocidade
  5. Camada de segurança: parada de emergência, limitação de velocidade, zonas de exclusão (“keepout”) (Segurança em Robótica)

Ideia-chave: o plano global lida com a intenção de longo alcance, enquanto o planejador local lida com obstáculos dinâmicos e rastreamento.

Pilha típica para manipuladores (braços)

Um pipeline comum de manipulação:

  1. Percepção: estimar pose do objeto, obstáculos
  2. Cinemática inversa (inverse kinematics, IK): encontrar configuração(ões) de junta objetivo
  3. Planejador: planejador no espaço articular (RRTConnect, PRM etc.)
  4. Processamento de trajetória:
    • suavização / atalhamento (shortcutting),
    • parametrização temporal (respeitando limites de velocidade/aceleração),
    • retemporização (retiming) opcional para sincronização
  5. Execução e monitoramento:
    • rastrear com um controlador,
    • parar/replanejar se o ambiente mudar

Frameworks no ecossistema incluem MoveIt (ROS), OMPL (biblioteca de planejamento) e toolchains modernas como Drake e Tesseract (frequentemente usadas para planejamento com forte ênfase em otimização e tarefas ricas em contato).

Exemplos Práticos

Exemplo 1: Navegação ao redor de obstáculos (robô de armazém)

Problema:

  • Um robô deve se mover do corredor A para o corredor D.
  • Obstáculos estáticos: prateleiras; obstáculos dinâmicos: humanos e outros robôs.

Abordagem típica:

  • Manter uma grade de ocupação + mapa de custo inflado.
  • Executar A* global para obter uma rota em forma de “corredor”.
  • Executar um planejador local a ~10–50 Hz que:
    • prevê obstáculos no futuro próximo,
    • seleciona um comando de velocidade seguro,
    • respeita restrições não holonômicas.

Modos de falha comuns:

  • Mínimos locais (o robô oscila em espaços apertados).
  • Mapas desatualizados (deriva ou latência do SLAM).
  • Inflação excessiva (o planejador “acha” que passagens estão bloqueadas).

Mitigações:

  • Melhor previsão e rastreamento de obstáculos.
  • Gatilhos de replanejamento e histerese.
  • Limites de velocidade conservadores perto de incerteza.

Exemplo 2: Manipulador alcançando dentro de uma caixa (pick-and-place)

Problema:

  • Um braço de 7 graus de liberdade deve alcançar uma pose de preensão dentro de uma caixa desorganizada.

Uma receita prática de planejamento:

  1. Amostrar múltiplas soluções de cinemática inversa para a pose de preensão (braços frequentemente têm várias).
  2. Para cada candidato de cinemática inversa:
    • planejar um caminho livre de colisão (por exemplo, RRTConnect),
    • validar com configurações de colisão mais rígidas (autocolisão, geometria do objeto acoplado).
  3. Escolher o melhor candidato por:
    • caminho mais curto / menor tempo,
    • maior afastamento de obstáculos,
    • menos quase-violação de limites de junta.
  4. Suavizar + parametrizar no tempo e executar.
  5. Se contato/desordem mudar e invalidar o plano, replanejar a partir do estado atual.

É aqui que os detalhes de verificação de colisão importam: autocolisões, geometria de carga acoplada e margens de segurança conservadoras podem dominar as taxas de sucesso.

Ideias Teóricas-Chave (e Por Que Elas Importam)

Completude e otimalidade

  • Completo (complete): garantido encontrar um caminho se existir (raro em planejamento contínuo de alta dimensionalidade sem hipóteses de discretização).
  • Completo em resolução (resolution complete): completo até uma resolução de discretização (comum em planejadores baseados em grade).
  • Probabilisticamente completo (probabilistically complete): a probabilidade de sucesso se aproxima de 1 à medida que a computação aumenta (comum em PRM/RRT).
  • Ótimo (optimal): retorna o caminho de menor custo; métodos assintoticamente ótimos (asymptotically optimal) (RRT*, PRM*) convergem ao ótimo com amostras infinitas.

Em engenharia, frequentemente você escolhe completude probabilística + rapidez em vez de otimalidade garantida, e então adiciona suavização e checagens de segurança.

Métricas de distância e direcionamento

Planejadores baseados em amostragem dependem de uma noção de “mais próximo” e “mover em direção a”:

  • No espaço articular, distância euclidiana pode ser suficiente, mas a ponderação de juntas pode importar.
  • Para robôs não holonômicos, direcionamento em linha reta simples em ((x,y,\theta)) pode ser inválido; você precisa de primitivas de movimento (motion primitives) ou uma função de direcionamento cinodinâmica.

Planejamento cinodinâmico

Quando a dinâmica importa, o planejamento precisa considerar ((x, \dot{x})) e entradas de controle:

  • Mais difícil porque “conectar dois estados” não é trivial.
  • Métodos comuns:
    • amostragem no espaço de controle (control space) (simular à frente),
    • planejadores em lattice com primitivas de movimento,
    • otimização local no estilo MPC.

Onde o Aprendizado de Máquina Entra (e Onde Não Entra)

O planejamento de movimento é tradicionalmente baseado em modelos, mas o aprendizado de máquina (machine learning) cada vez mais o complementa:

  • Heurísticas aprendidas (learned heuristics) para A* ou busca em grafo (planejamento mais rápido).
  • Distribuições de amostragem aprendidas (learned sampling distributions) para RRT/PRM (amostrar onde soluções são prováveis).
  • Proxies neurais de colisão (neural collision proxies) ou aproximadores de distância assinada (signed distance approximators) (acelerações, mas devem ser validados com cuidado).
  • Políticas locais aprendidas (learned local policies) (navegação reativa) treinadas via Aprendizado por Imitação (Imitation Learning) ou aprendizado por reforço (reinforcement learning); frequentemente combinadas com filtros clássicos de segurança.

Alerta prático importante:

  • Planejadores puramente aprendidos podem falhar sob mudança de distribuição (distribution shift); combinar aprendizado com verificações clássicas e restrições de segurança é comum, especialmente ao implantar além da simulação (Da Simulação para o Real (Sim2Real)).

Considerações de Engenharia e Armadilhas Comuns

Qualidade do mapa e da geometria

  • Nuvens de pontos ruidosas, latência e calibração incorreta podem causar obstáculos fantasmas ou colisões não detectadas.
  • Use filtragem, integração temporal e margens conservadoras.

Margens de segurança e inflação

  • Inflar obstáculos melhora a segurança, mas pode tornar passagens estreitas inviáveis.
  • Considere margens adaptativas com base na velocidade e na incerteza de localização.

Passagens estreitas

Planejadores baseados em amostragem têm dificuldade com corredores estreitos no espaço de configurações. Técnicas incluem:

  • amostragem enviesada (teste da ponte, amostragem baseada em obstáculos),
  • usar um plano global grosseiro para guiar a amostragem,
  • otimização de trajetória inicializada a partir de um caminho viável.

Replanejamento e monitoramento de execução

O mundo muda. Sistemas robustos:

  • replanejam continuamente ou por gatilhos,
  • validam online segmentos futuros da trajetória,
  • recorrem a comportamentos seguros de parada (Segurança em Robótica).

Benchmarking

Meça:

  • taxa de sucesso,
  • distribuição do tempo de planejamento (não apenas a média),
  • qualidade do caminho/trajetória (comprimento, suavidade, afastamento de obstáculos),
  • falhas em tempo de execução (colisões, erros de rastreamento).

Resumo

O planejamento de movimento transforma objetivos de alto nível (“vá até lá”, “pegue aquilo”) em movimento seguro do robô ao combinar:

  • Verificação de colisão (raciocínio geométrico rápido e robusto),
  • Geração de caminho/trajetória (da viabilidade a trajetórias suaves e dinamicamente válidas),
  • Pilhas de planejamento que integram planejamento global, reação local, controle e segurança.

Na robótica moderna, uma implantação bem-sucedida normalmente depende de sistemas híbridos: planejadores clássicos para confiabilidade e garantias (completude probabilística, tratamento de restrições), otimização para suavidade e viabilidade sob dinâmica, e componentes de aprendizado de máquina para melhorar velocidade, robustez ou percepção — ancorados por verificação de colisão rigorosa e monitoramento de segurança dentro do pipeline mais amplo de Percepção → Planejamento → Controle.