Alberto Finzi » 17.Pianificazione ed esecuzione

Pianificazione gerarchica

I sistemi di pianificazione gerarchica lavorano a diversi livelli di astrazione e con diversa reattività.

Al livello più alto nella gerarchia il pianificatore ha una rappresentazione globale ed astratta del dominio e genera un piano con vincoli temporali rilassati (pianificazione deliberativa).

Al livello più basso il pianificatore ha una rappresentazione locale e dettagliata dello spazio di ricerca; è richesta la generazione del piano in tempo reale (pianificazione dinamica).

Ciclo SPA

Nelle architetture di controllo plan-based (deliberative) il ciclo di controllo è basato su tre passi:

1. sense (S), osserva;
2. plan (P) , pianifica;
3. act (A), esegui il piano.

Queste architetture sono spesso chiamate architetture SPA.

Pianificazione SPA vs. Sistemi BB

Sistemi Plan-based

• Basati su modelli.
• Integrano conoscenza del dominio.
• Lavorano con orizzonte lungo.
• Tempi di reazione non sempre rapidi.

Sistemi behavior-based

• Sistemi modulari.
• Comportamento robusto e tempi di reazione rapidi.
• Stretta interazione senso-motoria.
• Non modelli globali del domino e non sistemi di pianificazione.

Controllo Ibrido

Combinazione dei due paradigmi: controllo reattivo e controllo deliberativo.

Combinazione di rappresentazioni diverse e tempi di reazione differenti.

Le architetture ibride cercano di integrare le caratteristiche dei due paradigmi.

Architettura Ibrida

L’architettura si basa su due sistemi che interagiscono:

• un sistema di controllo top-down deliberativo;
• un sistema di controllo bottom-up reattivo.

L’interfaccia tra i due sistemi, chiamato sistema esecutivo, è una componente cruciale.

Riassumendo l’architettura è composta di 3 livelli:

• un sistema reattivo;
• un sistema di pianificazione model-based;
• uno strato esecutivo che combina i due sistemi.

=> Le architetture ibride sono anche dette architetture a tre livelli.

3T Architectures

Erann Gat (1998) ha introdotto le architetture 3T definendo una corrispondenza tra livelli, funzionalità e rappresentazione dello stato.

Deliberatore: lo stato riflette le predizioni sul futuro.
Esecutore: lo stato riflette il presente e la memoria del passato.
Controller: senza stato (algoritmi reattivi sensor-based).

La reattività e la scala temporale varia con le componenti.

Il livello di mezzo: controllo esecutivo

Il livello di mezzo ha un compito impegnativo:

1. compensa i limiti del pianificatore e del sistema reattivo;
2. integra differenti granularità temporali;
3. integra diverse rappresentazioni;
4. riconcilia conflitti tra i due strati.

Il livello di mezzo: controllo esecutivo

Il sistema di controllo esecutivo si occupa di:

• monitorare processi interni ed esterni;
• gestire fallimenti/eventi inattesi (fault detection, diagnosi, recovery);
• coordinare attività deliberative e reattive (Planning/Scheduling/Execution/Replanning);
• fornire un comportamento flessibile, coerente, e adattivo (Plan Monitoring, Plan Execution).

I servizi del livello esecutivo

Riusare piani

Alcuni piani possono essere riutilizzati per limitare la ripianificazione, questi possono contenere:

• azioni di livello intermedio
• macro operatori: piani generali precompilati per uso futuro.

Re-planning dinamico
Il livello reattivo influenza la pianificazione.
Cambiamenti di basso livello sono visibili al pianificatore che può ripianificare.
Il controllo reattivo deve coordinarsi con il pianificatore in attesa di istruzioni.

I servizi del livello esecutivo

Reazione basta sul Planner

• La pianificazione influenza la reazione.
• Ogni soluzione trovata dal planner viene passata al basso livello.

Tipi di interazione

• Reazione/Pianificazione.
• Selezione: pianificazione come configurazione.
• Suggerimento: pianificazione come suggerimento.
• Adattamento: pianificazione come sistema per l’adattamento.
• Ritardo: pianificazione per postporre (least commitment).

Piani Universali

Se per un determinato problema si possono generare e memorizzare tutti i possibili piani di azione, se per ogni situazione c’è un piano ottimale già generato e il sistema può agire in modo reattivo ed ottimale, allora è disponibile un piano universale.
Piani Universali
Un sistema con piano universale è reattivo; la pianificazione è a tempo di compilazione, non a run-time.
I piani universali spesso non sono disponibili:

• il mondo non è deterministico;
• il mondo non è statico;
• gli obiettivi variano;
• il mondo è complesso (spazio degli stati troppo largo);
• il mondo non è strutturato.

Problema di Planning

Newell e Simon 1956

Dato un insieme di azioni in un dominio, dato un problema specificato da:

• un insieme di stati del mondo;
• un insieme di obiettivi;

trova una soluzione al problema: un modo per trasformare lo stato iniziale in uno stato finale in cui tutti gli obiettivi sono soddisfatti.

Il problema è quindi definito da: un insieme di azioni, un insieme di stati, un modello per stati ed azioni (Action Model), un insieme di obiettivi.

Tipi di Planning

• Pianificazione Classica
• Temporal Planning
• Conditional Planning
• Decision Theoretic Planning
• Least-Commitment Planning
• HTN planning
• …

Pianificazione Classica

Modello per Azioni: completo, deterministico, corretto, dettagliato.

Stati: stato iniziale unico completamente noto.

Obiettivi: raggiungimento completo di tutti gli obiettivi.

Spazio degli Stati vs. Spazio dei Piani

Pianificazione nello spazio degli stati: sequenze di azioni, dallo stato iniziale allo stato goal.

Pianificazione nello spazio dei piani: sequenze di trasformazioni di piani, da un piano iniziale ad uno finale.

Spazio degli stati: Modello STRIPS

Spazio dei Piani

Ricerca nello spazio dei piani parziali

Un piano è una tupla <A, O, B>

• A è un insieme di azioni;
• O è un insieme di ordinamenti (a < b);
• B è un set di binding (v = c, v1 = v2, etc).

Piano iniziale:

• <{start, finish},{start > finish},{} >;
• start non ha precondizioni, il suo effetto è lo stato iniziale;
• finish non ha effetti, le sue precondizioni sono i goal.

Ricerca nello spazio dei piani

Operatori sui piani parziali

• Aggiungi un’azione e un link causale per chiudere una condizione aperta.
• Aggiungi un link causale da un’azione esistente per chiudere una condizione aperta.
• Aggiungi un ordinamento per ordinare un passo rispetto ad un altro.

Una condizione aperta è un’azione che non è causalmente linkata.

Un piano è completo se ogni precondizione è soddisfatta:

Una precondizione c di S_j è soddisfatta da Si se:

• S_i < S_j;
• c in effect(S_j);
• non c’è un S_k tale che S_i < S_k < S_j con not c in effect(Sk);
• altrimenti S_k si dice un threat.

Least Commitment

Idea: fai scelte con minimo impegno, che sono rilevanti solo per la risoluzione del sottoproblema corrente.

Scelte least commitment

• Ordinamento: lascia le azioni non ordinate se non devono essere sequenziali.
• Binding: lascia le variabili non istanziate se non ci sono condizioni che richiedono l’assegnazione.
• Azioni: non soggette a least commitment.

Raffinamento

• Aggiungi solo informazioni al piano corrente.
• La pianificazione può rimuovere delle scelte.

Algoritmo POP

Algoritmo POP (segue)

Ricerca non deterministica del piano, backtrack su scelte:

• scelta di S_add per supportare S_need;
• scelte di promotion o demotion dato un threat.

Corretto e completo.

Estensioni di vario tipo: disgiunzione, quantificazione universale, negazione, condizionale.

Efficiente con buone euristiche, ma molto sensibile all’ordinamento dei subgoal.

Buone prestazioni con subgoal poco vincolati.

Plan Monitoring

Monitoraggio dell’esecuzione del piano:

• fallimento: precondizioni del piano rimanente non soddisfatte.

Monitoraggio dell’esecuzione delle Azioni:

• fallimento: precondizioni della prossima azione non soddisfatta o azione fallita.

Conseguenza del fallimento:

• ripianificazione (totale o parziale: fino alla migliore continuazione).

Alcuni limiti della pianificazione classica

• Azioni istantane.
• Non durate.
• Non vincoli temporali.
• Non quantità continue.

Estensioni

• Tempi
• Durate
• Vincoli
• Risorse
• Incertezze
• Utilità

CBIP-Algorithm

Algoritmo del Constraint-based Interval Planning.

CBIP vs POP

CBIP è simile a POP: least commitment e partial order …
… ma in CBIP ci sono vincoli temporali.

Un piano contiene una rete di vincoli temporali (Contraints Temporal Network) che deve essere consistente.

Occorre la propagazione dei vincoli per verificare la consistenza della rete.

TCSP (Dechter, Meiri, Pearl, AIJ91)

• E’ consistente la TCSP?
• Quali sono i tempi possibili per ogni Xi?
• Quali le durate possibili tra Xi e Xj?
• Qual’è un insieme consistente di tempi?
• Quali sono gli earliest start time?
• Quali sono i latest start times?
• …

Controllabilità

Alcune attività non sono controllabili.
E.g. dopo start_turn quando si ha end_turn ?
La STN contiene punti controllabili e non controllabili.
Attività incontrollabili non possono essere schedulate, solo osservate.
Come avviene la propagazione dei vincoli?

Controllabilità (segue)

Weak Controllability: per ogni evento incontrollabile c’è uno scheduling che permette l’esecuzione.

Strong Controllability: esiste uno scheduling robusto rispetto a tutti gli eventi non controllabili.

Dynamic Controllability: per ogni evento incontrollabile del passato esiste uno scheduling che permette l’esecuzione.