Multi-Agent Path Finding

Detto anche: MAPF, multi-agent pathfinding, multi-robot path planning
Categoria: Learning & autonomy › Multi-robot
Tag: multi-robot, path-planning, warehouse-automation, coordination, graph-search

Il problema di calcolare percorsi privi di collisioni per molti agenti che si muovono contemporaneamente su un grafo condiviso, come i robot di magazzino su una griglia, in modo che ogni agente raggiunga il proprio obiettivo senza conflitti.

Definizione

Pianificazione di percorsi multi-agente (Multi-Agent Path Finding, MAPF) è il problema di pianificare i percorsi di un gruppo di agenti che condividono un ambiente, in modo che ogni agente vada dalla sua partenza al suo obiettivo senza che due agenti occupino lo stesso posto nello stesso istante o si scambino di posto lungo lo stesso arco. L'ambiente è di solito modellato come un grafo, spesso una griglia, e il tempo è diviso in passi discreti in cui ogni agente si sposta su un vertice vicino oppure attende.

Le soluzioni MAPF si valutano di solito con la somma dei costi, il tempo totale impiegato da tutti gli agenti per raggiungere i propri obiettivi, o con il makespan, il tempo fino all'arrivo dell'ultimo agente. Trovare una soluzione ottima rispetto a questi obiettivi è in generale NP-difficile, perciò il settore ha sviluppato algoritmi che barattano l'ottimalità con la velocità. Tra i metodi ottimi c'è Conflict-Based Search (CBS), che pianifica ogni agente in modo indipendente e poi risolve le collisioni aggiungendo vincoli in un albero di ricerca. I metodi subottimi, come la pianificazione con priorità, in cui gli agenti pianificano uno alla volta e trattano gli agenti precedenti come ostacoli in movimento, scalano a squadre molto più grandi.

Il lifelong MAPF è una variante in cui gli agenti ricevono nuovi obiettivi non appena raggiungono quelli vecchi, il che corrisponde al modo in cui lavorano davvero i robot di magazzino e di smistamento. La pianificazione viene allora eseguita di continuo, spesso su una finestra temporale limitata, e il throughput diventa la misura principale.

I robot reali violano anche le ipotesi da manuale: hanno dimensioni, limiti di accelerazione e ritardi di esecuzione, per cui i piani MAPF vengono di solito eseguiti con uno strato di coordinamento aggiuntivo che mantiene i robot in sicurezza quando alcuni restano indietro rispetto alla tabella di marcia. I metodi basati sull'apprendimento, compreso l'apprendimento per imitazione da pianificatori basati sulla ricerca, sono una direzione di ricerca attiva per scalare a flotte molto grandi.

Perché è importante

Magazzini, fabbriche e centri di smistamento gestiscono flotte crescenti di robot mobili su pavimenti condivisi, e il loro throughput dipende da quanto bene quei robot sono coordinati. Il MAPF fornisce gli algoritmi che mantengono i robot in movimento senza collisioni né deadlock man mano che le flotte crescono.

Applicazioni principali

Flotte di robot in magazzini e centri di evasione ordini
Sistemi di smistamento pacchi con molti robot mobili
Coordinamento di veicoli a guida automatica nelle fabbriche
Coordinamento di più droni e del traffico a terra negli aeroporti
Movimento dei personaggi nei videogiochi e simulazione di folle

In pratica

Un team che gestisce una flotta di magazzino di solito modella il pavimento come una griglia o un grafo di percorsi, con ogni cella dimensionata per contenere un robot. Un pianificatore centrale riceve gli obiettivi dal sistema degli ordini e calcola percorsi coordinati, spesso con una ricerca con priorità o a finestre che ripianifica ogni pochi secondi invece di risolvere l'intero problema in modo ottimo. I percorsi vengono convertiti in waypoint temporizzati e inviati ai robot, e uno strato di esecuzione, come un grafo delle dipendenze tra azioni, fa sì che un robot non entri in una cella finché il robot davanti non l'ha liberata. Gli ingegneri misurano throughput, tempi di attesa e frequenza dei deadlock in simulazione con la flotta al completo prima di cambiare il layout del pavimento o l'algoritmo sul sistema reale.

Idee sbagliate comuni

Ogni robot può pianificare il proprio percorso più breve in modo indipendente — percorsi indipendenti entrano in collisione, quindi i robot vanno coordinati nel tempo oltre che nello spazio
Il MAPF ottimo scala a flotte di qualsiasi dimensione — la risoluzione ottima è NP-difficile, quindi le flotte grandi si affidano a metodi subottimi o a finestre
Un piano MAPF può essere eseguito esattamente come è stato calcolato — i robot reali sono in anticipo o in ritardo, quindi l'esecuzione ha bisogno di un proprio strato di sicurezza e coordinamento

Chi dovrebbe saperlo

Ingegneri dell'automazione di magazzino e della gestione flotte
Ricercatori di pianificazione multi-robot
Integratori di sistemi AMR e AGV
Ricercatori operativi che lavorano nella logistica

Tecnologie correlate

Conflict-Based Search
Pianificazione con priorità (Prioritized Planning)
Ricerca A (A Search)
Sistemi di gestione flotte (Fleet Management Systems)
Apprendimento per imitazione (Imitation Learning)

Termini correlati

Progetti correlati

Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
Open X-Embodiment (OXE): Largest open robotics dataset: 1M+ episodes from 22 embodiments
IR-SIM: Lightweight pure-Python 2D robot simulator for navigation, control and RL research
Mesh Navigation: Robot navigation on 3D triangle meshes for rough outdoor terrain, from Nature Robots