Landscape-Aware Bandit Hyper-Heuristics for Online Operator Selection in UAV Inspection Routing

Riepilogo Tecnico: Ipereuristiche Bandit Consapevoli del Paesaggio per la Selezione Online degli Operatori nella Pianificazione di Ispezione con UAV

1. Definizione del Problema

Il documento affronta il problema di pianificazione di ispezione multi-sito con UAV, astratto come un Problema del Commesso Viaggiatore Euclideo (TSP). In questo contesto, un UAV deve visitare un insieme di siti assegnati e tornare a una base entro una finestra temporale di volo limitata. La variabile decisionale fondamentale è l'ordine di visita di questi siti, assumendo che le preoccupazioni di livello inferiore (ad esempio, controllo dell'altitudine, evitamento delle collisioni, tempi di servizio) siano gestite separatamente da altri pianificatori.

La sfida risiede nel fatto che diversi paesaggi di pianificazione (ad esempio, uniformi, raggruppati, a corridoio, a griglia, a densità mista) e diverse fasi del processo di ricerca richiedono strategie di ottimizzazione differenti. Le euristiche classiche spesso si basano su programmi fissi o sulla selezione casuale degli operatori, il che può portare a inefficienze come l'uso eccessivo di un operatore che ha cessato di fornire miglioramenti o lo spreco di valutazioni su movimenti inadatti allo stato di ricerca corrente.

2. Metodologia: LA-BHH

Gli autori propongono LA-BHH (Ipereuristica Bandit Consapevole del Paesaggio), un controller online compatto progettato per apprendere una politica di selezione degli operatori durante una singola esecuzione di ottimizzazione senza addestramento offline.

• Quadro Ipereristico: LA-BHH opera a un livello elevato, selezionando da un portafoglio di quattro operatori di basso livello (braccia):
  1. 2-opt: Inverte un segmento del tour per rimuovere gli incroci degli spigoli.
  2. Swap: Scambia due siti di ispezione.
  3. Relocate: Sposta un sito in una posizione diversa.
  4. Or-opt-2: Sposta un blocco di due siti.
• Controller Bandit Contestuale: Il meccanismo di selezione utilizza un algoritmo LinUCB (Upper Confidence Bound Lineare).
  • Vettore di Contesto ($z_t$): Il controller condiziona le sue decisioni su un vettore di caratteristiche comprendente:
    • Descrittori Statici del Paesaggio: Dimensione normalizzata del problema, distanza media del vicino più prossimo, dispersione, anisotropia delle coordinate, dispersione radiale e peso dell'MST per nodo.
    • Caratteristiche Dinamiche dello Stato di Ricerca: Progresso del budget, lunghezza attuale/migliore del tour rispetto all'iniziale, miglioramento recente, tasso di accettazione e indicatori di stallo.
  • Segnale di Apprendimento: La ricompensa ($r_t$) è il miglioramento relativo troncato nella lunghezza del tour prodotto dall'operatore selezionato. Questa ricompensa aggiorna le statistiche di regressione ridge ($A_a, b_a$) per la braccia scelta, consentendo al controller di adattare la sua assegnazione del credito in tempo reale.
• Riparazione Consapevole dello Stallo: Una caratteristica specifica di progettazione sbilancia la selezione verso movimenti 2-opt quando la ricerca rileva uno stallo (mancanza di miglioramento in una breve finestra). Questo sfrutta l'efficacia nota del 2-opt per la riparazione euclidea senza introdurre nuovi tipi di movimento.
• Strategia di Accettazione: Il metodo impiega una regola greedy di miglioramento migliore. Sebbene sia stata testata un'accettazione di stile ricottura come ablazione, si è scoperto che degradava le prestazioni su queste specifiche istanze euclidee interrompendo forti strutture di vicini più prossimi.

3. Contributi Chiave

• Apprendimento Online per la Pianificazione: Il documento dimostra che un controller online compatto può apprendere efficacemente a selezionare operatori basandosi sia sulle caratteristiche statiche dell'istanza che sul progresso dinamico della ricerca, eliminando la necessità di grandi dataset offline o architetture neurali complesse.
• Assegnazione del Credito Contestuale: Combina esplicitamente descrittori statici del paesaggio con caratteristiche dello stato di ricerca online per guidare la selezione degli operatori, mostrando che questo contesto è superiore alla selezione bandit non contestuale (UCB-HH) o alla selezione casuale.
• Gestione dello Stallo: L'integrazione di un gate consapevole dello stallo che sbilancia dinamicamente il controller verso movimenti di riparazione 2-opt è identificata come un componente critico per mantenere il progresso della ricerca.
• Analisi di Ablazione: Lo studio isola sistematicamente i contributi di componenti specifici (contesto, caratteristiche statiche, caratteristiche dinamiche, operatori specifici), chiarificando che i guadagni di prestazioni derivano dall'interazione tra riparazione 2-opt, assegnazione del credito contestuale e uso dello stato consapevole dello stallo.

4. Risultati Sperimentali

Il metodo è stato valutato su 45 istanze TSP euclidee generate attraverso cinque famiglie di paesaggi (uniforme, raggruppato, corridoio, griglia con jitter, densità mista) e tre dimensioni di istanza (50, 100, 200 siti).

• Metriche di Prestazione: LA-BHH ha raggiunto il miglior gap medio finale (0,0223) e AUC di convergenza (0,0389) tra tutti i metodi confrontati.
• Miglioramenti Comparativi:
  • Riduzione del gap finale del 17,6% rispetto a UCB-HH non contestuale.
  • Riduzione del gap finale del 22,6% rispetto a Random-HH.
  • Riduzione del gap finale del 68,2% rispetto alla costruzione Nearest-Neighbor (NN).
• Robustezza: LA-BHH ha costantemente superato i baselines classici (inclusi Ricottura Simulata, Algoritmi Genetici e Ricerca Locale Iterata) su tutte le famiglie di paesaggi, dimostrando stabilità in scenari di dispiegamento diversificati.
• Utilizzo degli Operatori: L'analisi ha mostrato che, sebbene il 2-opt fosse l'operatore dominante (specialmente durante lo stallo), il controller appreso ha utilizzato efficacemente swap, relocate e Or-opt-2 per correggere errori di ordinamento locale che il solo 2-opt non poteva affrontare.

5. Significato e Affermazioni

Il documento posiziona LA-BHH come un caso di studio pratico per la Progettazione di Algoritmi Assistita dall'Apprendimento (LEAD) nel dominio della pianificazione. Il suo significato è inquadrato attorno a diverse affermazioni modeste ma pratiche:

• Interpretabilità ed Efficienza: A differenza di grandi modelli offline, LA-BHH è un controller leggero e ispezionabile che apprende durante una singola esecuzione, rendendolo adatto a scenari in cui è disponibile solo un piccolo numero di istanze correlate.
• Ruolo Complementare: Gli autori affermano esplicitamente che LA-BHH non intende sostituire i risolutori TSP all'avanguardia (come LKH). Invece, funge da livello di ordinamento della pianificazione che decide quale operatore di ricerca riutilizzabile applicare sotto un budget fisso.
• Scalabilità: Il metodo è computazionalmente efficiente (solo CPU, complessità $O(Tn)$) e scala bene da 50 a 200 siti, mantenendo la competitività dove i baselines classici di ricerca locale diventano meno affidabili.
• Applicabilità Futura: Gli autori suggeriscono che il quadro può essere esteso all'ispezione UAV nel mondo reale sostituendo le distanze euclidee con le distanze del percorso più breve su grafi di percorribilità e gestendo gli ostacoli tramite pianificatori di livello inferiore, sebbene notino che gli esperimenti attuali si basano su istanze generate controllate piuttosto che su dati raccolti sul campo.