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).
Nelle architetture di controllo plan-based (deliberative) il ciclo di controllo è basato su tre passi:
Queste architetture sono spesso chiamate architetture SPA.
Sistemi Plan-based
Sistemi behavior-based
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.
L’architettura si basa su due sistemi che interagiscono:
L’interfaccia tra i due sistemi, chiamato sistema esecutivo, è una componente cruciale.
Riassumendo l’architettura è composta di 3 livelli:
=> Le architetture ibride sono anche dette architetture a tre livelli.
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 ha un compito impegnativo:
Il sistema di controllo esecutivo si occupa di:
Riusare piani
Alcuni piani possono essere riutilizzati per limitare la ripianificazione, questi possono contenere:
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.
Reazione basta sul Planner
Tipi di interazione
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:
Newell e Simon 1956
Dato un insieme di azioni in un dominio, dato un problema specificato da:
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.
Modello per Azioni: completo, deterministico, corretto, dettagliato.
Stati: stato iniziale unico completamente noto.
Obiettivi: raggiungimento completo di tutti gli obiettivi.
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.
Ricerca nello spazio dei piani parziali
Un piano è una tupla <A, O, B>
Piano iniziale:
Operatori sui piani parziali
Una condizione aperta è un’azione che non è causalmente linkata.
Un piano è completo se ogni precondizione è soddisfatta:
Una precondizione c di Sj è soddisfatta da Si se:
Idea: fai scelte con minimo impegno, che sono rilevanti solo per la risoluzione del sottoproblema corrente.
Scelte least commitment
Raffinamento
Ricerca non deterministica del piano, backtrack su scelte:
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.
Monitoraggio dell’esecuzione del piano:
Monitoraggio dell’esecuzione delle Azioni:
Conseguenza del fallimento:
Estensioni
Pianificazione temporale
Nella pianificazione temporale, oltre alle precondizioni e agli effetti si possono considerare altri vincoli temporali.
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.
I vincoli temporali di un piano temporale definiscono una rete di vincoli:
Occorre verificare se questa rete è soddisfatta.
Se non c’è disgiunzione di vincoli allora si ha una Simple Temporal Network (STP).
Variabili: punti temporali per eventi.
Dominio: insieme di reali (istanti di tempo).
Vincoli: arco tra punti temporali ([5, 10] ↔ 5≤Pb-Pa≤10).
Algoritmo: Floyd-Warshall, tempo polinomiale.
Vincoli non visibili a tempo di esecuzione.
In una rete dispatchable si introducono vincoli impliciti (e.g. D before B).
Compila la rete in forma dispatchable:
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?
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.
2. Robotica mobile - parte prima
3. Robotica mobile - parte seconda
4. Robotica Probabilistica - Filtri Bayesiani (parte prima)
5. Robotica Probabilistica - Filtri Bayesiani (parte seconda)
7. Modello Probabilistico dei Sensori
8. Robotica Probabilistica - Filtri Gaussiani
10. SLAM
11. Filtri Discreti
12. FastSLAM
13. SLAM grid-based
14. Esplorazione basata su guadagno di informazione