Probabilistic Roadmap

• Detto anche: PRM, probabilistic roadmap method
• Categoria: Planning & manipulation › Motion planning
• Tag: motion-planning, sampling-based-planning, path-planning, graph-search, manipulation

Un pianificatore del movimento basato sul campionamento che costruisce un grafo riutilizzabile di configurazioni casuali prive di collisioni e dei percorsi ammissibili tra di esse, e poi risponde alle interrogazioni di pianificazione con una ricerca su grafo.

Definizione

Roadmap probabilistica (Probabilistic Roadmap, PRM) è un metodo di pianificazione del movimento basato sul campionamento introdotto da Kavraki, Švestka, Latombe e Overmars nel 1996. Invece di esplorare da capo lo spazio delle configurazioni per ogni richiesta, PRM costruisce prima un grafo, la roadmap, che rappresenta la connettività dello spazio libero del robot, e poi usa quel grafo per rispondere a un numero qualsiasi di interrogazioni da partenza a obiettivo.

La pianificazione ha due fasi. Nella fase di costruzione, il pianificatore campiona configurazioni casuali del robot, tiene come nodi quelle prive di collisioni e cerca di collegare ogni nodo ai nodi vicini con un semplice pianificatore locale, di solito un segmento rettilineo nello spazio delle configurazioni verificato contro le collisioni a intervalli fitti. I collegamenti riusciti diventano archi. Nella fase di interrogazione, le configurazioni di partenza e di obiettivo vengono collegate alla roadmap, e una ricerca su grafo come l'algoritmo di Dijkstra o A* trova un percorso al suo interno.

PRM è adatto ai problemi a interrogazioni multiple, in cui l'ambiente è statico e il robot deve pianificare molti movimenti nello stesso spazio, perché la costosa costruzione della roadmap si fa una sola volta. È probabilisticamente completo: se esiste un percorso, la probabilità che la roadmap ne contenga uno tende a 1 al crescere del numero di campioni.

Il suo punto debole principale sono i passaggi stretti. I campioni casuali uniformi cadono raramente nelle regioni sottili dello spazio libero, quindi la roadmap può non riuscire a collegare zone che in realtà sono connesse. Per affrontare il problema sono state sviluppate strategie di campionamento polarizzato, come campionare vicino ai bordi degli ostacoli. PRM* è una variante che sceglie i raggi di connessione in modo che la roadmap diventi asintoticamente ottima.

Perché è importante

PRM ha dimostrato che il campionamento casuale poteva rendere praticabile la pianificazione del movimento per robot con molti gradi di libertà, per i quali i metodi esatti sono intrattabili. La sua idea di roadmap resta utile ogni volta che un robot lavora ripetutamente nello stesso ambiente, come una cella industriale fissa.

Applicazioni principali

• Pianificazione del movimento a interrogazioni multiple per bracci robotici in celle di lavoro fisse
• Pianificazione del percorso per robot mobili in mappe statiche
• Pianificazione per sistemi con molti gradi di libertà, come umanoidi e robot a due bracci
• Didattica e benchmarking della pianificazione basata sul campionamento

In pratica

I team di solito usano PRM tramite OMPL, spesso attraverso MoveIt per la pianificazione dei bracci, dove PRM e PRM* stanno accanto a pianificatori basati su alberi come RRT-Connect. Poiché una roadmap si può salvare e riutilizzare, PRM si adatta alle celle di lavoro fisse in cui un braccio si sposta tra molte pose attorno alle stesse attrezzature: la roadmap viene costruita offline e interrogata durante l'esecuzione, ripetendo i controlli di collisione solo dove gli oggetti possono essersi spostati. Gli ingegneri regolano il numero di campioni e il raggio di connessione, e controllano se nella roadmap compaiono componenti scollegate, che di solito indicano un passaggio stretto che richiede più campioni o campioni meglio mirati.

Idee sbagliate comuni

• PRM trova sempre un percorso se ne esiste uno — è probabilisticamente completo, quindi la garanzia vale solo al limite di infiniti campioni
• PRM serve soprattutto per mappe 2D — il suo uso principale è negli spazi delle configurazioni ad alta dimensione, come lo spazio dei giunti di un braccio
• Una roadmap resta valida per sempre — se gli ostacoli si spostano, gli archi interessati vanno ricontrollati oppure la roadmap va ricostruita

Chi dovrebbe saperlo

• Ingegneri di pianificazione del movimento
• Integratori di celle robotiche industriali
• Ricercatori di manipolazione
• Studenti di robotica che studiano la pianificazione basata sul campionamento

Tecnologie correlate

• OMPL
• MoveIt
• RRT
• PRM*
• Ricerca A (A Search)
• Spazio delle configurazioni (Configuration Space)

Termini correlati

• Motion Planning
• RRT*
• Configuration Space

Progetti correlati

• 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

Video

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