Problemi di Planning
Ingegneria della Conoscenza e Sistemi
Esperti
Ettore Colombo
Problem-Solving Types
Classification
Construction
Configuration
 Assignment
 Planning

Simulation
PLANNING
Robotica:
ricerca di algoritmi per dire
automaticamente ad un
robot come muoversi
Trajectory
Motion
Planning Planning
Control Theory (approccio
analitico)
Storicamente: Modellazione attraverso
equazioni differenziali e sistemi di
equazioni differenziali; svilupppo di
feedback policies per una risposta
adattiva durante l’esecuzione, mirata
alla stabilità del sistema
Nuovi orizzonti: modellazione
incertezza e ricerca dell’ottimizzazione
Intelligenza
Artificiale
Discrete Planning
• Knowledge Based Planning
• Expet Systems for Planning
Descrizione del Problema
Dati:
uno stato iniziale
 un insieme di azioni
 un obiettivo da raggiungere (Goal)

Risultato:

determinazione di un piano, ossia un
insieme (parzialmente o totalmente
ordinato) di azioni necessarie per
raggiungere il goal
Esempio
 Descrizione del problema:
supponiamo di avere come obiettivo
quello di raggiungere l’università per
seguire le lezioni e di essere a casa e
di avere un automobile a disposizione
 Stato iniziale: sono a casa e ho
un’auto a disposizione
 Obiettivo: raggiungere l’università
Esempio: soluzione
 Una possibile soluzione:
1.
2.
3.
4.
5.
6.
7.
prendere il materiale per le lezioni;
prendere le chiavi dell’auto;
uscire di casa;
prendere l’auto;
raggiungere l’università;
entrare in aula;
...
 Pianificare ci permette di scegliere le azioni giuste da
eseguire nella giusta sequenza: invertendo 2 e 3
arriveremmo ad una soluzione impraticabile
Esempio: soluzioni equivalenti
Un’ altra possibile soluzione (equivalente alla
precedente, ottenuta invertendo 1 e 2):

1.
2.
3.
4.
5.
6.
7.

prendere le chiavi dell’auto;
prendere il materiale per le lezioni;
uscire di casa;
prendere l’auto;
raggiungere l’università;
entrare in aula;
...
Non sempre è necessario definire l’ordine delle
azioni (il piano può avere un ordinamento parziale)
Esempio: estensione della
rappresentazione
 Estendendo la descrizione del problema all’esistenza
dei “mezzi pubblici” si possono ottenere delle
soluzioni diverse
 Consideriamo quindi anche la possibile azione di
“prendere l’autobus” un’altra possibile soluzione
sarebbe:
1.
2.
3.
4.
5.
6.
7.
8.
prendere il materiale per le lezioni;
prendere i biglietti dell’autobus;
uscire di casa;
raggiungere la fermata dell’autobus;
prendere l’autobus;
raggiungere l’università;
entrare in aula;
...
Definizioni a confronto
PLANNING = PROBLEMA
“The task of coming up with a sequnce of action
that will achieve a goal is called planning”
[S.M. LaValle]
PLANNING = PROBLEM SOLVING METHOD
“Problem solving agents decide what to do by
finding sequnces of actions that lead to desirable
states”
[S.M. LaValle]
Caratteristiche delle Attività
Pianificazione  ricerca del Piano
Esecuzione  applicazione del Piano
Problema




Non decomponibile: ci può essere interazione tra
sottoproblemi
Reversibile: le scelte fatte durante la generazione
del piano sono revocabili (backtracking)
Irreversibile: l’esecuzione delle azioni porta ad un
cambiamento di stato irreversibile
Non deterministica: il piano può avere un effetto
diverso quando applicato al mondo reale che
spesso è impredicibile. In questo caso è possibile
rifare il piano solo parzialmente oppure invelidarlo
a seconda del problema
Alcuni Concetti Base
Pianificatore Automatico

Decision maker, Intelligent Agent, Planner
Rappresentazione Stato
Rappresentazione Goal
Rappresentazione Azioni
Rappresentazione Piano
Pianificatore Automatico
Un pianificatore automatico è un agente
intelligente che, date:
una rappresentazione dello stato iniziale
 una rappresentazione del goal
 una descrizione formale delle azioni
eseguibili

definisce il piano di azioni necessario per
raggiungere il goal
Rappresentazione dello stato
Occorre fornire al Planner un modello
del dominio del problema
Scelta di un adeguato linguaggio di
rappresentazione
Limiti nella rappresentazione
dello stato
Lo stato di un sistema spesso può essere osservato
solo in modo parziale, per diversi motivi:
 Limiti sensoriali:


alcuni aspetti non sono osservabili
il dominio è troppo dinamico per consentire un
aggiornamento continuo della rappresentazione
 Frame Problem: il dominio è troppo vasto per essere
rappresentato nella sua interezza
 Incertezza: le osservazioni sono soggette a rumore e
quindi si hanno delle osservazioni parziali o
imperfette
Rappresentazione del goal
Per rappresentare il Goal si utilizza lo
stesso linguaggio usato per la
rappresentazione dello stato iniziale.
Il Goal è spesso rappresentato con una
descrizione parziale dello stato finale:
descrive le condizioni che devono
essere verificate affinché il goal sia
soddisfatto
Rappresentazioni delle azioni
 Il planner deve essere costruito secondo una Teoria
del Dominio in cui sono descritte in modo formale le
azioni eseguibili
 Una generica azione sarà descritta da:



Nome: identificativo
Precondizione: condizioni che devono essere verificate
affinché l’azione possa essere eseguita
Postcondizione: gli effetti che l’azione porta sul mondo
 Si possono avere:


Azioni atomiche
Necessità di rappresentare del tempo
Rappresentazione del Piano
Azioni atomiche:

Successione di azioni
Rappresentazione del tempo

Successione di coppie [Azione, Intervallo
di tempo]
Rappresentazione di condizioni
Tecniche Intelligenza Artificiale
 Pianificazione Classica


Tipo di pianificazione off-line che produce l’intero piano prima di eseguirlo
lavorando su una rappresentazione istantanea dello stato corrente
Assunzioni:
•
•
•
•
Tempo Atomico
Determinismo degli effetti
Stato iniziale completamente noto
Non esistono altri eventi oltre alle azioni consentite che modificano lo stato
 Pianificazione Reattiva




Metodo on-line
Ambiente deterministico e dinamico
Osservazioni del mondo durante pianificazione e esecuzione
Spesso si alterna la pianificazione con l’esecuzione “reagendo” ai
cambiamenti di stato
 Pianificazione Condizionale

Piano costituito da:
• azioni
• verifica di condizioni
• comportamento condizionale a seconda dei risultati delle verifiche
Pianificazione Classica
 Planning Deduttivo


Uso di linguaggi logic based
Situation Calculus (fine anni 60)
 Planning Mediante Ricerca



Uso di linguaggi specializzati
Planning Lineare  STRIPS (primi anni 70)
Planning Non Lineare  Partial Order Planning (POP)
 Planning Gerarchico



definire operatori a diversi livelli di astrazione
pianificare ad livello alto
sostitituire macro azioni con loro espansione (magari già
precompilata)
Problem-Solving Types
Classification
Construction
Configuration
 Assignment
 Planning

Simulation
Expert Systems for Configuration
 Oggetti Elementari: oggetti base con attributi e
relazioni tra essi
 Problema: Selezione, parametrizzazione e
aggregazione di oggetti base in oggetti soluzione
 Soluzione: unione di oggetti base che costituiscono
una soluzione (ottima) che soddisfa le richieste
 Spazio Soluzioni: le configurazioni diverse sono m^n
dove n=#medio di attributi dell’oggetto richiesti
ognuno con m valori
 Esempi: Configurazione di ascensori, di computer
Expert Systems for Assignment
 Oggetti Elementari: almeno due insiemi disgiunti di
oggetti
 Problema: fornire un piano di ordinamento che
considera previsioni, risorse e altre restrizioni
 Soluzione: piano di assegnamento (ottimo) che
mappa un oggetto ad un altro
 Spazio Soluzioni: con due insiemi di n elementi ci
sono n! possibili soluzioni
 Esempi: generazione di orari/calendari, utilizzo di
macchine
Expert Systems for Planning
 Oggetti Elementari: oggetti con attributi e operatori
(generici) con precondizioni e azioni
 Problema: trasformazione di uno stato iniziale dato in
uno stato finale desiderato
 Soluzione: sequenza (ottima) di operatori applicabili
che trasformano stati iniziali in stati finali
 Spazio Soluzioni: i piani differenti sono m^n dove
m=#medio di operatori applicabili in ogni stato
intermedio e n=#medio di operatori per soluzione
Planning 1 - Esperimenti in
genetica molecolare
 Problema: sostanze disponibili, organismi,
azioni e scopo dell’esperimento
 Soluzione: sequenza di azioni per
raggiungere lo scopo dell’esperimento e
l’indicazione delle sostanze e degli organismi
necessari all’esperimento
 Spazio Soluzioni: tutti i piani disponibili
 Sistema: MOLGEN [Friedland 79, 85]
Planning 2 – Produzione di
semilavorati
 Problema: “blank”, forma, proprietà e le
possibili azioni di lavoro (bucare, macinare,
dipingere, etc...)
 Soluzione: sequenza, processo manifatturiero
per trasformare lo stato “blank” nello stato
finale
 Spazio Soluzione: tutti i possibili piani di
lavoro
 Sistema: ExAP [Dyckhoff 89]
Planning: Altri Esempi di sistemi
Uso efficace delle capacità di una
macchina  ISIS [Fox 83, Smith 86]
Mondo dei Blocchi, composizione di
blocchi  [Sacerdoti 77]
Individuazione di terapie per il
trattamento del cancro:
ONCOCIN/OPAL [Hickman 85, Musen
87]
PSM adottati per il problema di
Planning
Planning è un particolare problema di
Costruzione
PSM adottati sono PSM tipici dei
problemi di Costruzione
(configurazione, planning,
assegnamento)
Construction: Problem Solving
Methods
Heuristic construction
Skeletal construction
 Propose-revise strategy
 Propose-exchange strategy
 Least-commitment strategy

Model based construction
Case based construction
P Truck Compounding
Dominio
Divisione Materiali della Business Unit
Truck di Pirelli Pneumatici
Esperti con una profonda conoscenza
della materia
Istruzione personale (chimici)
 Scuola Pirelli (esperienza secolare)

Terminologia (1)
Mescola: composto chimico ottenuto
principalmente utilizzando gomma
Descrizione:
Caratteristiche Mescola CM
 Ricetta  elenco di coppie [ingrediente,
quantità]

Terminologia (2)
 Famiglie di ingredienti

Attributi descrittivi degli ingredienti di una famiglia
 Combinazioni: aggregati omogenei (per famiglia)
 Sistemi: aggregati eterogenei
 Interventi di modifica della ricetta




Aumento/Diminuzione
Sostituzione
Shift
Due livelli di descrizione (livello ingredienti, livello delle
famiglie e dei sistemi)
Gli ingredienti
Ingredienti a disposizione per la produzione delle mescole
CB CRX 1345
CB CRX 1380
Carbon Black
CB N115
CB N121
CB N220
CB N326
Cariche Chiare SILICA
Oli
AROMATIC OIL
Resine Styrene-Indene Resin
Silano
TESPT50%
Derivati di Acidi
Fatty Acid Zinc Salt
Grassi
Stearic Acid
Acidi
ZnO
ZnO
???
TBBS
???
CBS
???
CTP
SULFUR
Vulcanizzanti
SMR 20
STR 20 NR - Gomme Naturali
RSS 3
BR Ni
BR - Gomme Polibutadieniche
BR Co
BR Li
BR Ti
SBR 1500
SBR - Gomme Stirene Butadiene
SBR 1502
SBR 1712
???
6PPD
???
TMQ
DTPD ???
Cera
Wax
Ogni ingrediente appartiene ad una famiglia di ingredienti
Le ricette
SMR 20
SBR 1502
CB CRX 1345
CB N115
SILICA
TESPT50%
Styrene-Indene Resin
AROMATIC OIL
Fatty Acid Zinc Salt
Stearic Acid
ZnO
6PPD
TMQ
DTPD
Wax
TBBS
CTP
SULFUR
q1
q2
q3
q4
q5
q6
q7
q8
q9
q10
q11
q12
q13
q14
q15
q16
q17
q18
STR 20
BR Ni
CB CRX 1345
SILICA
Styrene-Indene Resin
TESPT50%
Fatty Acid Zinc Salt
Stearic Acid
ZnO
6PPD
TMQ
DTPD
Wax
TBBS
CTP
SULFUR
q1
q2
q3
q4
q5
q6
q7
q8
q9
q10
q11
q12
q13
q14
q15
q16
Le combinazioni
SMR 20
SBR 1502
CB CRX 1345
CB N115
SILICA
TESPT50%
Styrene-Indene Resin
AROMATIC OIL
Fatty Acid Zinc Salt
Stearic Acid
ZnO
6PPD
TMQ
DTPD
Wax
TBBS
CTP
SULFUR
q1
q2
q3
q4
q5
q6
q7
q8
q9
q10
q11
q12
q13
q14
q15
q16
q17
q18
NR
SBR
Carbon Black
Silici
Silani
Resine
Oli
Der. Acidi Grassi
Acidi
ZnO
???
???
???
Cere
???
???
Zolfo
I sistemi
SMR 20
SBR 1502
CB CRX 1345
CB N115
SILICA
TESPT50%
Styrene-Indene Resin
AROMATIC OIL
Fatty Acid Zinc Salt
Stearic Acid
ZnO
6PPD
TMQ
DTPD
Wax
TBBS
CTP
SULFUR
q1
q2
q3
q4
q5
q6
q7
q8
q9
q10
q11
q12
q13
q14
q15
q16
q17
q18
NR
Sistema Matrice Polimerica
SBR
Carbon Black
Silici
Silani
Resine
Oli
Der. Acidi Grassi
Acidi
ZnO
???
???
???
Cere
???
???
Zolfo
Sistema Rinforzante
Sistema Plastificante
Sistema Ausiliari di
Processo
Sistema Attivanti della
Vulcanizzazione
Sistema Protettivo
Sistema Acceleranti della
Vulcanizzazione
Sistema Agenti Vulcanizzanti
Il problema della formulazione
 IN:


Mescola
Richieste di modifica delle CM
 OUT:

Sequenza di IR (interventi di modifica della ricetta)
Dov’è la conoscenza?
Regole di Formulazione

Relazioni esistenti tra CM e IR
Vincoli di Formulazione
Sulle quantità di ingredienti
 Sui valori degli attributi

T-Matrix
 Strumento di rappresentazione
 Strumento di supporto alla KA
 Regole di formulazione:

(IR, CM, corr, prop)
No Correlation (NC)
P-Truck Compounding
 IN:


Ricetta associata ad una mescola
Richieste di modifica delle CM
 Dati:


IR Possibili
Conoscenza: T-Matrix e Vincoli di Formulazione
 OUT:

Sequnza di IR (interventi di modifica della ricetta)
PTruck Compounding
Stato Iniziale: Ricetta
Goal: Raggiungere la variazione delle
Caratteristiche desiderata
Azioni: Interventi sulla Ricetta
Conoscenza a disposizione: il
Knowledge Artifact (T-Matrix) e vincoli
Quale PSM abbiamo scelto?
Perchè non è un problema di
configurazione?
Mondo dei blocchi
 Problema: data una configurazione di quattro blocchi (ad es [2])
si desidera trovare l’insieme di operazioni per ottenere la
configurazione finale di blocchi desiderata [1]
 Stato Iniziale: [2]
 Obiettivo: [1]
 Azioni Eseguibili: spostare un blocco libero per volta o sul
tavolo o su un altro blocco

Esempi di trasformazioni di stato
• Da 2 a 3
• Da 3 a 4 o 5
A
B
C
D
1
A
D
B
C
2
D
C
B
A
3
B
C
D
A
4
C
B
A D
5