Probabilistic Roadmap

• Também chamado: PRM, probabilistic roadmap method
• Categoria: Planning & manipulation › Motion planning
• Tags: motion-planning, sampling-based-planning, path-planning, graph-search, manipulation

Um planejador de movimento baseado em amostragem que constrói um grafo reutilizável de configurações aleatórias livres de colisão e dos caminhos viáveis entre elas, e depois responde a consultas de planejamento por busca em grafo.

Definição

Mapa de rotas probabilístico (Probabilistic Roadmap, PRM) é um método de planejamento de movimento baseado em amostragem apresentado por Kavraki, Švestka, Latombe e Overmars em 1996. Em vez de buscar no espaço de configurações do zero a cada solicitação, o PRM primeiro constrói um grafo, o mapa de rotas, que captura a conectividade do espaço livre do robô, e depois usa esse grafo para responder a qualquer número de consultas de início a objetivo.

O planejamento tem duas fases. Na fase de construção, o planejador amostra configurações aleatórias do robô, mantém como nós as que estão livres de colisão e tenta conectar cada nó aos nós próximos com um planejador local simples, geralmente uma linha reta no espaço de configurações verificada quanto a colisões em intervalos finos. As conexões bem-sucedidas se tornam arestas. Na fase de consulta, as configurações de início e de objetivo são conectadas ao mapa de rotas, e uma busca em grafo, como o algoritmo de Dijkstra ou o A*, encontra um caminho através dele.

O PRM é adequado a problemas de múltiplas consultas, em que o ambiente é estático e o robô precisa planejar muitos movimentos no mesmo espaço, porque a custosa construção do mapa de rotas é feita uma única vez. Ele é probabilisticamente completo: se existe um caminho, a probabilidade de o mapa de rotas conter um se aproxima de 1 à medida que o número de amostras cresce.

Sua principal fraqueza são as passagens estreitas. Amostras aleatórias uniformes raramente caem em regiões finas do espaço livre, então o mapa de rotas pode deixar de conectar áreas que na verdade estão ligadas. Estratégias de amostragem enviesada, como amostrar perto das fronteiras dos obstáculos, foram desenvolvidas para resolver isso. O PRM* é uma variante que escolhe os raios de conexão de modo que o mapa de rotas se torna assintoticamente ótimo.

Por que importa

O PRM mostrou que a amostragem aleatória podia tornar o planejamento de movimento prático para robôs com muitos graus de liberdade, em que os métodos exatos são intratáveis. Sua ideia de mapa de rotas continua útil sempre que um robô trabalha repetidamente no mesmo ambiente, como uma célula industrial fixa.

Principais aplicações

• Planejamento de movimento com múltiplas consultas para braços robóticos em células de trabalho fixas
• Planejamento de caminhos para robôs móveis em mapas estáticos
• Planejamento para sistemas com muitos graus de liberdade, como humanoides e robôs de dois braços
• Ensino e benchmarking de planejamento baseado em amostragem

Na prática

As equipes geralmente usam o PRM por meio do OMPL, muitas vezes via MoveIt para planejamento de braços, onde PRM e PRM* ficam ao lado de planejadores baseados em árvores como o RRT-Connect. Como um mapa de rotas pode ser armazenado e reutilizado, o PRM se encaixa em células de trabalho fixas em que um braço se move entre muitas poses em torno dos mesmos dispositivos de fixação: o mapa de rotas é construído offline e consultado em tempo de execução, com verificações de colisão repetidas apenas onde objetos podem ter se movido. Os engenheiros ajustam o número de amostras e o raio de conexão e observam componentes desconectados no mapa de rotas, que geralmente indicam uma passagem estreita que precisa de mais amostras ou de amostras mais bem direcionadas.

Equívocos comuns

• O PRM sempre encontra um caminho se ele existir — ele é probabilisticamente completo, então a garantia só vale no limite de infinitas amostras
• O PRM serve principalmente para mapas 2D — seu uso principal é em espaços de configurações de alta dimensão, como o espaço das juntas de um braço
• Um mapa de rotas continua válido para sempre — se os obstáculos se movem, as arestas afetadas precisam ser verificadas de novo ou o mapa de rotas reconstruído

Quem deve saber

• Engenheiros de planejamento de movimento
• Integradores de células de robôs industriais
• Pesquisadores de manipulação
• Estudantes de robótica que aprendem planejamento baseado em amostragem

Tecnologias relacionadas

• OMPL
• MoveIt
• RRT
• PRM*
• Busca A (A Search)
• Espaço de configurações (Configuration Space)

Termos relacionados

• Motion Planning
• RRT*
• Configuration Space

Projetos relacionados

• LeRobot: HuggingFace ML library for real-world robotics in PyTorch
• Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim
• NVIDIA Isaac GR00T: NVIDIA open foundation model for humanoid robot reasoning and skills
• OpenVLA: 7B-parameter Vision-Language-Action model for robotic manipulation
• Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
• Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design

Vídeos

• Modern Robotics, Chapter 10.5: Sampling Methods for Motion Planning (Part 1 of 2): Northwestern Robotics