Riepilogo Tecnico: Apprendimento di Modelli di Azioni Sollevati da Tracce con Informazioni Minime

Enunciato del Problema

Recenti lavori hanno dimostrato che i modelli STRIPS sollevati possono essere appresi in modo efficiente dalle sole tracce di azione (algoritmo SIFT), e che i modelli STRIPS+ (che consentono argomenti di azione impliciti) possono essere appresi da tracce stato-azione completamente osservabili (algoritmo SYNTH). Tuttavia, questi approcci presentano limitazioni pratiche:

1. SIFT richiede tracce di azione STRIPS complete in cui gli argomenti sono espliciti, il che spesso include parametri non necessari non richiesti per la selezione dell'azione (ad esempio, nei puzzle a tessere scorrevoli, la posizione corrente di una tessera deve essere passata esplicitamente anche se l'azione è "sposta a sinistra").
2. SYNTH assume la piena osservabilità di tutti i predicati dello stato, il che è irrealistico per agenti che operano in ambienti parzialmente osservabili.

Questo articolo affronta il problema dell'apprendimento di domini di azioni STRIPS+ da tracce in cui sia gli argomenti dell'azione che le informazioni sullo stato sono parzialmente osservabili. Nello specifico, gli autori indagano le condizioni sotto le quali è possibile apprendere un dominio equivalente quando le tracce trasportano informazioni minime: alcuni argomenti dell'azione sono omessi e i predicati dello stato sono completamente non osservabili, completamente osservabili o solo localmente osservabili (osservabili solo per gli oggetti rilevanti per lo stato corrente).

Metodologia

La soluzione proposta, SYNTH+, è un algoritmo unificato che estende e combina le capacità di SIFT e SYNTH. Opera su tracce estese (sequenze di azioni e osservazioni parziali dello stato) e si basa su due meccanismi fondamentali:

1. Caratteristiche Mutex (Estensione di SIFT)

Per gestire gli argomenti dell'azione mancanti senza osservabilità dello stato, gli autori introducono le caratteristiche mutex.

• Concetto: Una caratteristica mutex $f = \langle k, A, D \rangle$ rappresenta un predicato di arità $k$ in cui il $k$-esimo argomento è determinato implicitamente dai primi $k-1$ argomenti.
• Meccanismo: A differenza delle caratteristiche standard in cui i pattern di aggiunta e cancellazione hanno la stessa arità, le caratteristiche mutex permettono ai pattern di cancellazione di avere arità $k-1$. Questo cattura il vincolo secondo cui un'azione (ad esempio drop()) cancella un predicato (ad esempio holding(o)) in base all'oggetto attualmente tenuto, senza nominare esplicitamente quell'oggetto nella traccia dell'azione.
• Coerenza: Una caratteristica mutex è coerente se, attraverso il grafo delle tracce, ogni atomo ground $f(o)$ riceve un singolo valore di verità, e per qualsiasi coppia di atomi veri $f(o)$ e $f(o')$ nello stesso stato, se gli ultimi argomenti differiscono ($o_k \neq o'_k$), allora almeno un argomento precedente deve differire anch'esso ($o_i \neq o'_i$ per qualche $i < k$).

2. Sintesi delle Query e Integrazione (Estensione di SYNTH)

SYNTH+ integra l'"invenzione" dei predicati (tramite SIFT) con l'inferenza degli argomenti impliciti (tramite SYNTH) in un ciclo iterativo:

1. Input: Un grafo etichettato di tracce estese e un insieme di predicati completamente osservabili $P_\omega$.
2. Iterazione:
   • Passo SIFT+: Utilizza i pattern di azione sugli argomenti espliciti e sugli argomenti impliciti attualmente noti per inventare nuove caratteristiche mutex e caratteristiche semplici. Queste caratteristiche rappresentano nuovi predicati e i loro effetti.
   • Passo SYNTH: Utilizza i predicati appena inventati (e qualsiasi predicato osservabile) per definire query (sottoquery $Q_i$) che legano le variabili implicite ($z_i$) a oggetti unici nello stato.
   • Aggiornamento: Il grafo viene aggiornato con i nuovi argomenti impliciti e le loro query definitorie.
3. Terminazione: Il processo continua fino al raggiungimento di un punto fisso o al superamento di un limite di profondità massimo ($d_{max}$).

3. Osservabilità Locale

Il framework è esteso a LOCAL SYNTH+, che gestisce l'osservabilità locale. In questo contesto, un predicato è osservabile solo per oggetti "locali" (quelli che appaiono come argomenti nell'azione corrente). L'algoritmo modifica la procedura di test di coerenza (TEST*) assumendo che gli atomi non locali siano falsi quando si testano le precondizioni, garantendo che le parti non osservate dello stato non invalidino l'apprendimento degli argomenti impliciti.

Contributi Chiave

1. Algoritmo SYNTH+: Un algoritmo generale per l'apprendimento di domini STRIPS+ da tracce con osservabilità parziale sia delle azioni che degli stati. Unifica l'invenzione dei predicati di SIFT con la risoluzione degli argomenti impliciti di SYNTH.
2. Caratteristiche Mutex: Una nuova formalizzazione che permette l'apprendimento di predicati in cui l'ultimo argomento è funzionalmente dipendente dagli altri, consentendo il recupero degli argomenti dell'azione omessi senza piena osservazione dello stato.
3. Risultati di Completezza: Vengono stabilite condizioni teoriche per la completezza degli algoritmi:
   • SIFT+ (Nessuna osservabilità dello stato): Richiede che il dominio STRIPS+ nascosto sia ben formato, fortemente connesso e aciclico nel suo grafo di dipendenza (dove i nodi sono predicati e variabili implicite).
   • SYNTH+ (Osservabilità parziale dello stato): Richiede che il grafo di dipendenza limitato ai predicati non osservabili sia aciclico.
   • LOCAL SYNTH+: Dimostrato completo sotto osservabilità locale per i predicati chiave (predicati nelle precondizioni che coinvolgono solo argomenti impliciti) se sono completamente osservabili, e gli altri predicati sono localmente osservabili.
4. Generalizzazione: Il lavoro dimostra che SIFT e SYNTH sono casi particolari di SYNTH+ (dove rispettivamente $P_\omega = \emptyset$ e $P_\omega = P$).

Risultati Sperimentali

Gli autori hanno valutato SIFT+ e SYNTH+ su una serie di domini di pianificazione standard (ad esempio Blocchi, Consegna, Griglia, Sokoban, Logistica) utilizzando tracce estese generate da modelli STRIPS+ nascosti.

• Prestazioni di SIFT+: Ha appreso con successo domini corretti (tasso di verifica del 100%) dalle sole tracce di azione in tutti i domini testati, recuperando una media del 55% degli argomenti dell'azione che erano stati omessi dalle tracce.
• Prestazioni di SYNTH+: Ha appreso domini corretti utilizzando significativamente meno predicati osservabili rispetto a SYNTH.
  • In Consegna, SYNTH+ ha appreso il dominio osservando solo la posizione dell'agente (at(x)) e l'adiacenza statica, mentre SYNTH richiedeva tutti i predicati fluenti.
  • In Sokoban e Logistica*, SYNTH+ ha appreso domini con osservazione di soli predicati statici, uno scenario in cui né SYNTH né SIFT+ avrebbero potuto avere successo.
• Efficienza: Gli algoritmi sono stati eseguiti in modo efficiente (da secondi a minuti) su hardware standard, scalando fino a domini con migliaia di passaggi di traccia.

Significato e Affermazioni

L'articolo afferma che SYNTH+ fornisce un'alternativa pratica e sollevata all'apprendimento per rinforzo basato su modelli, consentendo l'apprendimento di modelli dinamici da tracce "naturali". Queste tracce richiedono informazioni minime:

• Non è necessario elencare ogni argomento richiesto da una codifica STRIPS formale (ad esempio, la posizione corrente di un blocco che viene sganciato).
• Non è richiesta la piena osservabilità dello stato; è sufficiente una osservabilità parziale o locale di specifici predicati.

Gli autori sottolineano che il loro approccio colma il divario tra l'apprendimento teorico dei modelli (che spesso assume piena osservabilità) e l'applicazione pratica (dove gli agenti hanno percezione limitata). Caratterizzando le condizioni esatte (aciclicità dei grafi di dipendenza) sotto le quali è possibile l'apprendimento, il lavoro stabilisce un ambito rigoroso per l'apprendimento di modelli di azioni sollevati in contesti parzialmente osservabili. I risultati suggeriscono che domini complessi possono essere ricostruiti da tracce che trasmettono solo le informazioni necessarie per selezionare le azioni, piuttosto che l'intera descrizione dello stato.