Dual-Informed Vertical Expansion for Multi-Objective Node Selection in Anytime Conflict-Based Search

Sintesi Tecnica: Espansione Verticale a Informazione Duale per la Selezione di Nodi Multi-Obiettivo in un Conflict-Based Search Anytime

Definizione del Problema
Il Conflict-Based Search (CBS) è un algoritmo esatto di primo piano per il Multi-Agent Path Finding (MAPF). Il CBS standard impiega una strategia di ricerca best-first (BFS) ad alto livello, selezionando i nodi con il valore minimo della chiave del limite inferiore (lower-bound key) per l'espansione. Sebbene questo approccio sia efficiente nel minimizzare il numero di nodi espansi e nel far avanzare rapidamente il limite duale (il certificato di ottimalità), presenta tre significativi svantaggi nell'impiego pratico:

1. Intensità di Memoria: Mantiene una vasta frontiera aperta, che può eccedere i limiti di memoria integrata.
2. Scarsa Continuità Genitore-Figlio: Salta frequentemente tra rami non correlati dell'albero dei vincoli, fallendo nel capitalizzare i guadagni di efficienza derivanti dal processare immediatamente un nodo figlio dopo il suo genitore (dove cambia un solo vincolo).
3. Mancanza di Comportamento Anytime: Tipicamente non fornisce alcuna soluzione fattibile (incumbent) finché l'algoritmo non termina e l'ottimalità è certificata, rendendolo inadatto a sistemi che richiedono piani fattibili intermedi sotto vincoli di tempo o risorse.

Le alternative esistenti, come l'Iterative Deepening CBS (IDCBS), affrontano la memoria utilizzando passaggi depth-first ma introducono lavoro ripetuto e non riescono comunque a fornire incumbent intermedi. Questo articolo sostiene che la selezione dei nodi debba essere trattata come una scelta di design modulare piuttosto che come un dettaglio di implementazione fisso, permettendo un compromesso multi-obiettivo tra nodi espansi, uso della memoria, continuità genitore-figlio e scoperta di l'incumbent.

Metodologia
Gli autori formalizzano la selezione dei nodi ad alto livello in CBS come una politica modulare $\pi$ che determina l'ordine di espansione dei nodi senza alterare la ricerca a basso livello, le regole di branching o gli euristiche ammissibili. Dimostrano che il cambiamento di questa politica preserva l'esattezza del CBS, a patto che vengano mantenute le standard condizioni di pruning del branch-and-bound.

Il documento introduce la Dual-Informed Vertical Expansion (DIVE), una nuova politica di selezione dei nodi progettata per occupare un "punto medio mancante" nello spazio di design. DIVE opera attraverso due meccanismi distinti:

1. Fase di Dive (Orientata alla Profondità): Quando un nodo viene espanso, DIVE tenta di continuare un "dive" espandendo immediatamente il suo miglior figlio (il lower-bound più basso) se il bound di tale figlio è strettamente inferiore al costo dell'incumbent corrente ($z_P$). Ciò sfrutta la località genitore-figlio e cerca soluzioni fattibili precocemente.
2. Fase di Reanchoring (Best-Bound): Se un dive termina (perché il miglior figlio non può migliorare l'incumbent o non esistono figli), la politica ritorna alla frontiera globale best-bound per selezionare la radice del successivo dive. Ciò garantisce un progresso regolare verso il certificato di ottimalità.

DIVE incorpora anche il pruning dell'incumbent: qualsiasi nodo con un lower bound maggiore o uguale al costo della migliore soluzione fattibile corrente viene scartato (pruned). Ciò consente a DIVE di esplorare in sicurezza la "zona primale" (nodi con costi superiori all'ottimo) per trovare buone soluzioni fattibili senza compromettere la prova finale di ottimalità.

Il documento propone inoltre la Memory-Constrained DIVE (MC-DIVE), una variante reattiva che passa a una ricerca puramente depth-first se la coda aperta eccede una specifica soglia di memoria, dimostrando come la selezione dei nodi possa adattarsi ai vincoli di runtime.

Contributi Chiave

1. Separazione Formale tra Politica e Correttezza: Il documento dimostra che la selezione dei nodi è indipendente dall'esattezza del CBS. Sotto le standard condizioni di branch-and-bound, qualsiasi politica che selezioni i nodi dall'insieme aperto preserva l'ottimalità, consentendo la progettazione di politiche che ottimizzano metriche diverse dal solo conteggio dei nodi.
2. La Politica DIVE: L'introduzione di DIVE, che combina il reanchoring best-bound con il diving orientato alla profondità. Si dimostra che essa è un punto di Pareto distinto nello spazio multi-obiettivo, minimizzando i dive breaks (transizioni tra catene genitore-figlio) pur mantenendo il progresso best-bound.
3. Framework Multi-Obiettivo: Gli autori definiscono un framework per valutare le politiche basandosi su cinque obiettivi concorrenti: nodi espansi, dive breaks, dimensione massima della coda, progresso del primal-bound (qualità dell'incumbent) e progresso del dual-bound (velocità del certificato).
4. Analisi Teorica: Il documento fornisce limiti teorici sulle prestazioni di BFS, DFS, ID e DIVE su alberi di ricerca perfetti, prevedendo che BFS minimizzi i nodi, ID minimizzi la dimensione della coda e DIVE minimizzi i dive breaks.

Risultati Sperimentali
Esperimenti su benchmark MAPF standard (mappe empty, random, room e warehouse) con diverse densità di robot supportano la mappa dei compromessi teorici:

• Nodi Espansi: BFS rimane la più efficiente in termini di numero di nodi espansi. DIVE espande leggermente più nodi (dal 18% al 57% in più in alcuni benchmark) a causa dell'esplorazione controllata della zona primale, ma significativamente meno di ID (che può espandere dal 13% al 134% in più a causa dei restart ripetuti).
• Dive Breaks: DIVE riduce costantemente il numero di dive breaks dal 6% al 51% rispetto a BFS, migliorando significativamente la continuità genitore-figlio.
• Uso della Memoria: DIVE riduce la dimensione massima della coda dal 44% all'86% rispetto a BFS, sebbene ID rimanga la politica più efficiente in termini di memoria (riducendo la dimensione della coda dell'89-97%).
• Comportamento Anytime: DIVE è l'unica politica che fornisce costantemente early feasible incumbents con gap primal-dual certificati prima del completamento della ricerca. In molti casi, DIVE trova una soluzione ottimale prima che il dual bound raggiunga l'ottimo, mentre BFS e ID non forniscono alcuna soluzione fino al termine.
• Warm Starts: Nei regimi densi dove trovare un incumbent iniziale è difficile, DIVE beneficia significativamente dei warm start (ad esempio, da PIBT), permettendole di risolvere istanze che altrimenti andrebbero in timeout.
• Ablation: Rimuovendo la componente di "ricerca diversificata" (restarts best-bound) da DIVE, si ottiene una politica che si comporta come una DFS con pruning, richiedendo sostanzialmente più nodi e dive breaks, confermando che il meccanismo di reanchoring è critico per l'efficienza di DIVE.

Significatività e Assertions
Il documento afferma che DIVE non domina universalmente le altre politiche, ma offre piuttosto un punto operativo distinto nello spazio di design dell'esatto CBS. La sua significatività risiede nel trasformare l'esatto CBS in un algoritmo anytime che può:

• Fornire soluzioni fattibili di alta qualità con gap certificati sotto vincoli di tempo o memoria.
• Ridurre la pressione sulla memoria e migliorare il tempo di esecuzione dell'implementazione attraverso una migliore continuità genitore-figlio.
• Adattarsi ai contesti di deployment (ad esempio, robot con memoria limitata) attraverso varianti reattive come MC-DIVE.

Gli autori sottolineano che, sebbene BFS sia ottimale per minimizzare il conteggio dei nodi e ID sia ottimale per minimizzare la memoria esplicita, DIVE è la scelta preferibile quando il sistema richiede un equilibrio tra questi fattori, specificamente quando la disponibilità di soluzioni fattibili precoci e la riduzione dei dive breaks sono critiche per le applicazioni robotiche reali. Il lavoro motiva un passaggio dalla visione della selezione dei nodi come un'euristica fissa a un parametro di design multi-obiettivo e regolabile.