I risponditori PRS come parte di una più ampia soluzione di classe.
Sistemia Regoledi’...
99
Sistemi a Regole di Produzione Stefano Bragaglia Fondamen( di Intelligenza Ar(ficiale M 4 Giugno 2013
Transcript of Sistemia Regoledi’...
Sistemi a Regole di Produzione
Stefano Bragaglia
Fondamen( di Intelligenza Ar(ficiale M 4 Giugno 2013
Sommario
1. Sistemi a regole 2. Sistemi a regole di produzione • JBoss Drools • Un caso d’uso
3. Pa9ern matching: l’algoritmo RETE 4. Risoluzione dei confliC & Esecuzione 5. RiferimenF 6. Informazioni
4 Giugno 2013 Sistemi a Regole di Produzione 2
SISTEMI A REGOLE FondamenF di Intelligenza ArFficiale M
Sistemi a Regole
• Le regole sono il principale modo di esprimere la conoscenza in molF campi dell’I.A.
• I Fpi di regole più comuni sono: – i programmi logici (es.: Prolog) – le regole di produzione (es.: Drools)
• Entrambi i Fpi sono molto comuni, basate su principi simili ma realizzate in modo duale
4 Giugno 2013 Sistemi a Regole di Produzione 4
Sistemi a Regole • Il Modus Ponens, anche de9o Principio di disgiunzione, Affermazione dell’antecedente o Ragionamento direFo, prevede che:
se è vero che p(X) implica q(Y) e p(x) è vero, allora q(y) è ugualmente vero
• Es.: Se piove, allora la strada si bagna. Qui piove. Dunque questa strada è bagnata.
q(y)
, p(x) p(X) q(Y)
4 Giugno 2013 Sistemi a Regole di Produzione 5
Sistemi a Regole • Il Modus Ponens, anche de9o Principio di disgiunzione, Affermazione dell’antecedente o Ragionamento direFo, prevede che:
se è vero che p(X) implica q(Y) e p(x) è vero, allora q(y) è ugualmente vero
• Es.: Se piove, allora la strada si bagna. implicazione Qui piove. premessa Dunque questa strada è bagnata. conseguenza
implicazione premessa
conseguenza q(y)
, p(x) p(X) q(Y)
4 Giugno 2013 Sistemi a Regole di Produzione 6
Sistemi a Regole
Programmi logici • Backward-‐chaining • Dal goal ai faC, applicando le regole all’indietro
• Generalmente conservaFvi
• Unificazione • Backtracking
Regole di produzione • Forward-‐chaining • I faC aCvano le regole che generano nuovi faC
• Potenzialmente distruCve
• Pa9ern matching • Parallelismo
4 Giugno 2013 Sistemi a Regole di Produzione 7
Sistemi a Regole
Programmi logici Regole di produzione
4 Giugno 2013 Sistemi a Regole di Produzione 8
Sistemi a Regole
Programmi logici Regole di produzione
4 Giugno 2013 Sistemi a Regole di Produzione 9
Sistemi a Regole
Programmi logici Regole di produzione
4 Giugno 2013 Sistemi a Regole di Produzione 10
Sistemi a Regole
Programmi logici Regole di produzione
4 Giugno 2013 Sistemi a Regole di Produzione 11
Sistemi a Regole
Programmi logici Regole di produzione
4 Giugno 2013 Sistemi a Regole di Produzione 12
Sistemi a Regole
Programmi logici Regole di produzione
4 Giugno 2013 Sistemi a Regole di Produzione 13
Sistemi a Regole
Programmi logici Regole di produzione
4 Giugno 2013 Sistemi a Regole di Produzione 14
SISTEMI A REGOLE DI PRODUZIONE FondamenF di Intelligenza ArFficiale M
Sistemi a Regole di Produzione
• I sistemi a regole di produzione, o ProducCon Rule Systems (PRS): – sono sistemi a regole, Rule Based Systems (RBS), – basaF sul principio deduCvo del Modus Ponens, – che ado9ano un approccio reaHvo/generaCvo.
4 Giugno 2013 Sistemi a Regole di Produzione 16
Sistemi a Regole di Produzione
Agenda
PM
WM
Pattern Matching!
Conflict Resolution! Execution!
Patterns "+ Actions!
triples "(now beans)!
Output!
Productions:!a
1 2 3
Facts:!
Schema archite9urale e principio di funzionamento
4 Giugno 2013 Sistemi a Regole di Produzione 17
Sistemi a Regole di Produzione
Agenda
PM
WM
Pattern Matching!
Conflict Resolution! Execution!
Patterns "+ Actions!
triples "(now beans)!
Output!
Productions:!a
1 2 3
Facts:!
ELABORAZIONE SUDDIVISA IN 3 STADI
Schema archite9urale e principio di funzionamento
4 Giugno 2013 Sistemi a Regole di Produzione 18
Sistemi a Regole di Produzione
Agenda
PM
WM
Pattern Matching!
Conflict Resolution! Execution!
Patterns "+ Actions!
triples "(now beans)!
Output!
Productions:!a
1 2 3
Facts:!
ELABORAZIONE SUDDIVISA IN 3 STADI
3 MEMORIE
Schema archite9urale e principio di funzionamento
4 Giugno 2013 Sistemi a Regole di Produzione 19
JBOSS DROOLS FondamenF di Intelligenza ArFficiale M
JBoss Drools
Expert (rule engine) Fusion (event processing)
jBPM (workflow) Guvnor (rule repo)
Planner (constraints)
• AlternaCve – OPS5, CLIPS, Jess, ILOG, Jrules, BizTalk, …
• Sistema di riferimento – JBoss Drools (h9p://www.jboss.org/drools)
• Perchè? – Open source, Java-‐based, integrato con Eclipse
• Parte di una piaRaforma integrata
4 Giugno 2013 Sistemi a Regole di Produzione 21
JBoss Drools
Expert (rule engine) Fusion (event processing)
jBPM (workflow) Guvnor (rule repo)
Planner (constraints)
• AlternaCve – OPS5, CLIPS, Jess, ILOG, Jrules, BizTalk, …
• Sistema di riferimento – JBoss Drools (h9p://www.jboss.org/drools)
• Perchè? – Open source, Java-‐based, integrato con Eclipse
• Parte di una piaRaforma integrata
4 Giugno 2013 Sistemi a Regole di Produzione 22
JBoss Drools • Sintassi del linguaggio Drools: regole rule "ID_regola" /* IMPLICAZIONE */ // attributi when /* premessa */ // pattern (composito) then /* conseguenza */ // azioni logiche // effetti collaterali end
4 Giugno 2013 Sistemi a Regole di Produzione 23
JBoss Drools • Sintassi del linguaggio Drools: regole rule "Cancella gli Stefano" /* IMPLICAZIONE */ salience 5 when /* premessa */ $p: Person ( name == "Stefano" ) then /* conseguenza */ retract($p); System.out.println($p); end
4 Giugno 2013 Sistemi a Regole di Produzione 24
JBoss Drools • Sintassi del linguaggio Drools: queries query "ID_query" /* premessa */ // pattern (composito) end
4 Giugno 2013 Sistemi a Regole di Produzione 25
JBoss Drools • Sintassi del linguaggio Drools: queries query "Trova gli Stefano" /* premessa */ $p: Person ( name == "Stefano" ) end
4 Giugno 2013 Sistemi a Regole di Produzione 26
JBoss Drools • Sintassi del linguaggio Drools: oggeH declare ID_Class /* dichiarazione */ // dichiarazione di campo // dichiarazione di campo end
4 Giugno 2013 Sistemi a Regole di Produzione 27
JBoss Drools • Sintassi del linguaggio Drools: oggeH declare Person /* dichiarazione */ name: String address: Address = new Address(...) end
Person -‐ name: String -‐ address: Address ...
Address -‐ street: String -‐ zip: long -‐ city: String ...
4 Giugno 2013 Sistemi a Regole di Produzione 28
JBoss Drools • Sintassi del linguaggio Drools: evenC declare ID_Event /* dichiarazione */ // annotazioni // annotazioni // dichiarazioni di campo // dichiarazioni di campo end
4 Giugno 2013 Sistemi a Regole di Produzione 29
JBoss Drools • Sintassi del linguaggio Drools: evenC declare Alarm /* dichiarazione */ @role( event ) @timestamp( time ) message: String time: long end
4 Giugno 2013 Sistemi a Regole di Produzione 30
JBoss Drools
• Sintassi del linguaggio Drools: – Operatori relazionali: == != >= > <= < – Operatori logici: && , || – Negazione: not – Operatori funzionali: min, max, count, accumulate
– Dot notaCon: name == "…" o $p.getName().equals("…")
4 Giugno 2013 Sistemi a Regole di Produzione 31
JBoss Drools • Caso d’uso: sistema marcatempo aziendale – Ogni dipendente ha un badge con RFID – Quando passa a9raverso un gate, la WM riceve un evento “passed” (marcato temporalmente) a9raverso l’entry-‐point corrispondente al dipendente • Filtrando il primo e l’ulFmo evento “passed” di ogni giorno per ogni dipendente, si determina quante ore ha lavorato
• Se non ci sono evenF “passed” per un dato dipendente in un dato giorno e non è in vacanza/malato, allora è assente
• Accumulando il numero di ore lavorate in un mese da un dipendente si può calcolare in proporzione la sua busta paga
• Sapendo che un dipendente è assegnato a un proge9o, l’azienda può calcolare i mesi/uomo dedicaF a quel proge9o
4 Giugno 2013 Sistemi a Regole di Produzione 32
PATTERN MATCHING: L’ALGORITMO RETE
FondamenF di Intelligenza ArFficiale M
1A REGOLA DI ESEMPIO Pa9ern Matching: l’algoritmo RETE
4 Giugno 2013 Sistemi a Regole di Produzione 34
rule "Trova gli Stefano" when $p: Person( name == "Stefano" ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE Root node
Entry Point nodes
4 Giugno 2013 Sistemi a Regole di Produzione 35
rule "Trova gli Stefano" when $p: Person( name == "Stefano" ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE Root node
Entry Point nodes
Object Type nodes
4 Giugno 2013 Sistemi a Regole di Produzione 36
rule "Trova gli Stefano" when $p: Person( name == "Stefano" ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE Root node
Entry Point nodes
Object Type nodes
Alfa nodes
4 Giugno 2013 Sistemi a Regole di Produzione 37
rule "Trova gli Stefano" when $p: Person( name == "Stefano" ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
4 Giugno 2013 Sistemi a Regole di Produzione 38
rule "Trova gli Stefano" when $p: Person( name == "Stefano" ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
NB: I faH contenuC in un (Alfa) Memory Node fanno match con un paRern semplice!
4 Giugno 2013 Sistemi a Regole di Produzione 39
rule "Trova gli Stefano" when $p: Person( name == "Stefano" ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
4 Giugno 2013 Sistemi a Regole di Produzione 40
rule "Trova gli Stefano" when $p: Person( name == "Stefano" ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
ALFA
NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
4 Giugno 2013 Sistemi a Regole di Produzione 41
rule "Trova gli Stefano" when $p: Person( name == "Stefano" ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
ALFA
NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
4 Giugno 2013 Sistemi a Regole di Produzione 42
rule "Trova gli Stefano" when $p: Person( name == "Stefano" ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
ALFA
NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
_ Person[Stefano, <null>] Person[Stefano, Address[Via Po 2, 40068, San Lazzaro]]
WM
p1: Person("Stefano", null) a1: Address("Via Po 2", 40068, ���
"San Lazzaro") p2: Person("Stefano", a1) p3: Person("Giacomo", a1)
4 Giugno 2013 Sistemi a Regole di Produzione 43
rule "Trova gli Stefano" when $p: Person( name == "Stefano" ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
ALFA
NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes p1
Person[Stefano, <null>] _ Person[Stefano, Address[Via Po 2, 40068, San Lazzaro]]
WM
p1: Person("Stefano", null) a1: Address("Via Po 2", 40068, ���
"San Lazzaro") p2: Person("Stefano", a1) p3: Person("Giacomo", a1)
4 Giugno 2013 Sistemi a Regole di Produzione 44
rule "Trova gli Stefano" when $p: Person( name == "Stefano" ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
ALFA
NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes p1
Person[Stefano, <null>] _ Person[Stefano, Address[Via Po 2, 40068, San Lazzaro]]
WM
p1: Person("Stefano", null) a1: Address("Via Po 2", 40068, ���
"San Lazzaro") p2: Person("Stefano", a1) p3: Person("Giacomo", a1)
4 Giugno 2013 Sistemi a Regole di Produzione 45
rule "Trova gli Stefano" when $p: Person( name == "Stefano" ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
ALFA
NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes p1, p2
Person[Stefano, <null>] Person[Stefano, Address[Via Po 2, 40068, San Lazzaro]] _
WM
p1: Person("Stefano", null) a1: Address("Via Po 2", 40068, ���
"San Lazzaro") p2: Person("Stefano", a1) p3: Person("Giacomo", a1)
4 Giugno 2013 Sistemi a Regole di Produzione 46
rule "Trova gli Stefano" when $p: Person( name == "Stefano" ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
ALFA
NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Person[Stefano, <null>] Person[Stefano, Address[Via Po 2, 40068, San Lazzaro]] _
WM
Memory nodes
p1: Person("Stefano", null) a1: Address("Via Po 2", 40068, ���
"San Lazzaro") p2: Person("Stefano", a1) p3: Person("Giacomo", a1) p1, p2
4 Giugno 2013 Sistemi a Regole di Produzione 47
2A REGOLA DI ESEMPIO Pa9ern Matching: l’algoritmo RETE
4 Giugno 2013 Sistemi a Regole di Produzione 48
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE Root node
Entry Point nodes
4 Giugno 2013 Sistemi a Regole di Produzione 49
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE Root node
Entry Point nodes
Object Type nodes
4 Giugno 2013 Sistemi a Regole di Produzione 50
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE Root node
Entry Point nodes
Object Type nodes
Memory nodes
4 Giugno 2013 Sistemi a Regole di Produzione 51
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE Root node
Entry Point nodes
Object Type nodes
Memory nodes
4 Giugno 2013 Sistemi a Regole di Produzione 52
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
4 Giugno 2013 Sistemi a Regole di Produzione 53
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
4 Giugno 2013 Sistemi a Regole di Produzione 54
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
Beta nodes
4 Giugno 2013 Sistemi a Regole di Produzione 55
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
Beta nodes
NB: I Beta Nodes fanno il prodoRo cartesiano degli oggeH filtraC dagli Alfa padre!
4 Giugno 2013 Sistemi a Regole di Produzione 56
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE
Memory nodes
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
Beta nodes
4 Giugno 2013 Sistemi a Regole di Produzione 57
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE
Memory nodes
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
Beta nodes
NB: Le tuple contenute in un (Beta) Memory Node fanno match con un paRern composito!
4 Giugno 2013 Sistemi a Regole di Produzione 58
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
Beta nodes
4 Giugno 2013 Sistemi a Regole di Produzione 59
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
Beta nodes
4 Giugno 2013 Sistemi a Regole di Produzione 60
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
Beta nodes
NB: Introduco la regola precedente: I nodi della RETE vengono condivisi quando possibile! 4 Giugno 2013 Sistemi a Regole di Produzione 61
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
Beta nodes
4 Giugno 2013 Sistemi a Regole di Produzione 62
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
ALFA
NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
Beta nodes
4 Giugno 2013 Sistemi a Regole di Produzione 63
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
ALFA
NETWORK
BE
TA NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
Beta nodes
4 Giugno 2013 Sistemi a Regole di Produzione 64
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
ALFA
NETWORK
BE
TA NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
Beta nodes
4 Giugno 2013 Sistemi a Regole di Produzione 65
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
ALFA
NETWORK
BE
TA NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
Beta nodes
_ Person[p1, -‐]/Address[a1] Person[p1, -‐]/Address[a2] Person[p2, -‐]/Address[a1] Person[p2, a1]/Address[a2]
WM
4 Giugno 2013 Sistemi a Regole di Produzione 66
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
ALFA
NETWORK
BE
TA NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
Beta nodes
_ Person[p1, -‐]/Address[a1] Person[p1, -‐]/Address[a2] Person[p2, -‐]/Address[a1] Person[p2, a1]/Address[a2]
WM
a1: Address("Via Po 2", 40068, ��� "San Lazzaro")
p1: Person("Stefano", null) a2: Address("Via Roma 5", 40128, "Bologna") p2: Person("Stefano", a1) p3: Person("Giacomo", a1)
a1���
4 Giugno 2013 Sistemi a Regole di Produzione 67
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
ALFA
NETWORK
BE
TA NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
Beta nodes
Person[p1, -‐]/Address[a1] _ Person[p1, -‐]/Address[a2] Person[p2, -‐]/Address[a1] Person[p2, a1]/Address[a2]
WM
a1: Address("Via Po 2", 40068, ��� "San Lazzaro")
p1: Person("Stefano", null) a2: Address("Via Roma 5", 40128, "Bologna") p2: Person("Stefano", a1) p3: Person("Giacomo", a1)
a1
p1
p1-a1
NB: Stampa semplificata e output prima regola omesso! 4 Giugno 2013 Sistemi a Regole di Produzione 68
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
ALFA
NETWORK
BE
TA NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
Beta nodes
Person[p1, -‐]/Address[a1] Person[p1, -‐]/Address[a2] _ Person[p2, -‐]/Address[a1] Person[p2, a1]/Address[a2]
WM
a1: Address("Via Po 2", 40068, ��� "San Lazzaro")
p1: Person("Stefano", null) a2: Address("Via Roma 5", 40128, "Bologna") p2: Person("Stefano", a1) p3: Person("Giacomo", a1)
a1���a2
p1
p1-a1 p1-a2���
NB: Stampa semplificata e output prima regola omesso! 4 Giugno 2013 Sistemi a Regole di Produzione 69
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
ALFA
NETWORK
BE
TA NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
Beta nodes
Person[p1, -‐]/Address[a1] Person[p1, -‐]/Address[a2] Person[p2, -‐]/Address[a1] Person[p2, a1]/Address[a2] _
WM
a1: Address("Via Po 2", 40068, ��� "San Lazzaro")
p1: Person("Stefano", null) a2: Address("Via Roma 5", 40128, "Bologna") p2: Person("Stefano", a1) p3: Person("Giacomo", a1)
a1���a2
p1���p2
p1-a1 p1-a2���p2-a1 p2-a2
NB: Stampa semplificata e output prima regola omesso! 4 Giugno 2013 Sistemi a Regole di Produzione 70
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
ALFA
NETWORK
BE
TA NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
Beta nodes
Person[p1, -‐]/Address[a1] Person[p1, -‐]/Address[a2] Person[p2, -‐]/Address[a1] Person[p2, a1]/Address[a2] _
WM
a1: Address("Via Po 2", 40068, ��� "San Lazzaro")
p1: Person("Stefano", null) a2: Address("Via Roma 5", 40128, "Bologna") p2: Person("Stefano", a1) p3: Person("Giacomo", a1)
a1���a2
p1���p2
p1-a1 p1-a2���p2-a1 p2-a2
NB: Stampa semplificata e output prima regola omesso! 4 Giugno 2013 Sistemi a Regole di Produzione 71
rule "Trova gli Stefano e indirizzi" when $a: Address() $p: Person( name == "Stefano" ) then System.out.println($p+"/"+$a+" "); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
ALFA
NETWORK
BE
TA NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Memory nodes
Beta nodes
Person[p1, -‐]/Address[a1] Person[p1, -‐]/Address[a2] Person[p2, -‐]/Address[a1] Person[p2, a1]/Address[a2] _
WM
a1: Address("Via Po 2", 40068, ��� "San Lazzaro")
p1: Person("Stefano", null) a2: Address("Via Roma 5", 40128, "Bologna") p2: Person("Stefano", a1) p3: Person("Giacomo", a1)
a1���a2
p1���p2
p1-a1 p1-a2���p2-a1 p2-a2
NB: Stampa semplificata e output prima regola omesso!
NB: WM = insieme delle memories (distribuita); oggeH ripetuC (ricondante): spazio vs tempo. 4 Giugno 2013 Sistemi a Regole di Produzione 72
3A REGOLA DI ESEMPIO Pa9ern Matching: l’algoritmo RETE
4 Giugno 2013 Sistemi a Regole di Produzione 73
rule "Trova Stefano col suo indirizzo" when $a: Address() $p: Person( name == "Stefano", address == $a ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Dummy nodes
Memory nodes
4 Giugno 2013 Sistemi a Regole di Produzione 74
rule "Trova Stefano col suo indirizzo" when $a: Address() $p: Person( name == "Stefano", address == $a ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Dummy nodes
Memory nodes
NB: Questo Alfa node conCene un riferimento incrociato che non si può ancora risolvere.
4 Giugno 2013 Sistemi a Regole di Produzione 75
rule "Trova Stefano col suo indirizzo" when $a: Address() $p: Person( name == "Stefano", address == $a ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Dummy nodes
Memory nodes
Beta nodes
4 Giugno 2013 Sistemi a Regole di Produzione 76
rule "Trova Stefano col suo indirizzo" when $a: Address() $p: Person( name == "Stefano", address == $a ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Dummy nodes
Memory nodes
Beta nodes
Delayed nodes
NB: Il precedente Alfa node è inserito qui perchè può risolvere il riferimento incrociato.
4 Giugno 2013 Sistemi a Regole di Produzione 77
rule "Trova Stefano col suo indirizzo" when $a: Address() $p: Person( name == "Stefano", address == $a ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Dummy nodes
Memory nodes
Beta nodes
Delayed nodes
4 Giugno 2013 Sistemi a Regole di Produzione 78
rule "Trova Stefano col suo indirizzo" when $a: Address() $p: Person( name == "Stefano", address == $a ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Dummy nodes
Memory nodes
Beta nodes
Delayed nodes
NB: I nodi della RETE vengono condivisi quando possibile! Questa è la prima regola… 4 Giugno 2013 Sistemi a Regole di Produzione 79
rule "Trova Stefano col suo indirizzo" when $a: Address() $p: Person( name == "Stefano", address == $a ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Dummy nodes
Memory nodes
Beta nodes
Delayed nodes
NB: I nodi della RETE vengono condivisi quando possibile! Questa è la seconda… 4 Giugno 2013 Sistemi a Regole di Produzione 80
rule "Trova Stefano col suo indirizzo" when $a: Address() $p: Person( name == "Stefano", address == $a ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Dummy nodes
Memory nodes
Beta nodes
Delayed nodes
NB: I nodi della RETE vengono condivisi quando possibile! Questa è l’ulCma regola! 4 Giugno 2013 Sistemi a Regole di Produzione 81
rule "Trova Stefano col suo indirizzo" when $a: Address() $p: Person( name == "Stefano", address == $a ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
ALFA
NETWORK
BE
TA NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Dummy nodes
Memory nodes
Beta nodes
Delayed nodes
4 Giugno 2013 Sistemi a Regole di Produzione 82
rule "Trova Stefano col suo indirizzo" when $a: Address() $p: Person( name == "Stefano", address == $a ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
ALFA
NETWORK
BE
TA NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Dummy nodes
Memory nodes
Beta nodes
Delayed nodes
_ Person[Stefano, Address[Via Po 2, 40068, San Lazzaro]]
WM
4 Giugno 2013 Sistemi a Regole di Produzione 83
rule "Trova Stefano col suo indirizzo" when $a: Address() $p: Person( name == "Stefano", address == $a ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
ALFA
NETWORK
BE
TA NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Dummy nodes
Memory nodes
Beta nodes
Delayed nodes WM
a1: Address("Via Po 2", 40068, ��� "San Lazzaro")
p1: Person("Stefano", null) a2: Address("Via Roma 5", 40128, "Bologna") p2: Person("Stefano", a1) p3: Person("Giacomo", a1)
a1
_ Person[Stefano, Address[Via Po 2, 40068, San Lazzaro]]
4 Giugno 2013 Sistemi a Regole di Produzione 84
rule "Trova Stefano col suo indirizzo" when $a: Address() $p: Person( name == "Stefano", address == $a ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
ALFA
NETWORK
BE
TA NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Dummy nodes
Memory nodes
Beta nodes
Delayed nodes WM
a1: Address("Via Po 2", 40068, ��� "San Lazzaro")
p1: Person("Stefano", null) a2: Address("Via Roma 5", 40128, "Bologna") p2: Person("Stefano", a1) p3: Person("Giacomo", a1)
a1���
_ Person[Stefano, Address[Via Po 2, 40068, San Lazzaro]]
p1���
NB: L’output delle prime due regole è stato omesso!
p1,a1���
4 Giugno 2013 Sistemi a Regole di Produzione 85
rule "Trova Stefano col suo indirizzo" when $a: Address() $p: Person( name == "Stefano", address == $a ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
ALFA
NETWORK
BE
TA NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Dummy nodes
Memory nodes
Beta nodes
Delayed nodes WM
a1: Address("Via Po 2", 40068, ��� "San Lazzaro")
p1: Person("Stefano", null) a2: Address("Via Roma 5", 40128, "Bologna") p2: Person("Stefano", a1) p3: Person("Giacomo", a1)
NB: L’output delle prime due regole è stato omesso!
a1���a2
p1���
p1,a1���p1,a2 _
Person[Stefano, Address[Via Po 2, 40068, San Lazzaro]]
4 Giugno 2013 Sistemi a Regole di Produzione 86
rule "Trova Stefano col suo indirizzo" when $a: Address() $p: Person( name == "Stefano", address == $a ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
ALFA
NETWORK
BE
TA NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Dummy nodes
Memory nodes
Beta nodes
Delayed nodes
Person[Stefano, Address[Via Po 2, 40068, San Lazzaro]] _
WM
a1: Address("Via Po 2", 40068, ��� "San Lazzaro")
p1: Person("Stefano", null) a2: Address("Via Roma 5", 40128, "Bologna") p2: Person("Stefano", a1) p3: Person("Giacomo", a1)
NB: L’output delle prime due regole è stato omesso!
a1���a2
p1���p2
p1,a1���p1,a2 p2,a1 p2,a2
p1,a1���
4 Giugno 2013 Sistemi a Regole di Produzione 87
rule "Trova Stefano col suo indirizzo" when $a: Address() $p: Person( name == "Stefano", address == $a ) then System.out.println($p); end
Pa9ern matching: l’algoritmo RETE
Terminal nodes
Memory nodes
ALFA
NETWORK
BE
TA NETWORK
Root node
Entry Point nodes
Object Type nodes
Alfa nodes
Dummy nodes
Memory nodes
Beta nodes
Delayed nodes
Person[Stefano, Address[Via Po 2, 40068, San Lazzaro]] _
WM
a1: Address("Via Po 2", 40068, ��� "San Lazzaro")
p1: Person("Stefano", null) a2: Address("Via Roma 5", 40128, "Bologna") p2: Person("Stefano", a1) p3: Person("Giacomo", a1)
NB: L’output delle prime due regole è stato omesso!
a1���a2
p1���p2
p1,a1���p1,a2 p2,a1 p2,a2
p1,a1���
4 Giugno 2013 Sistemi a Regole di Produzione 88
RISOLUZIONE DEI CONFLITTI ED ESECUZIONE
FondamenF di Intelligenza ArFficiale M
Risoluzione dei ConfliC & Esecuzione
ai
ai ai ai ai ai ai ai ai ai ai
E X E C
FIFO
ai ai
a i
!
AGENDA
4 Giugno 2013 Sistemi a Regole di Produzione 90
Risoluzione dei ConfliC & Esecuzione
ai
ai ai ai ai ai ai ai ai ai ai
E X E C
ai • oggeC filtraF • rif. regola -‐ salience -‐ codice
FIFO
ai ai
a i
!
AGENDA
4 Giugno 2013 Sistemi a Regole di Produzione 91
Risoluzione dei ConfliC & Esecuzione
ai
ai ai ai ai ai ai ai ai ai ai
E X E C
ai • oggeC filtraF • rif. regola -‐ salience -‐ codice
FIFO
ai ai
a i
!
AGENDA
4 Giugno 2013 Sistemi a Regole di Produzione 92
NB: In verità, una Map<Integer, Queue<Ac(va(on>> ordinata per chiavi decrescen(!
Risoluzione dei ConfliC & Esecuzione
ai
ai ai ai ai ai ai ai ai ai ai
E X E C
ai • oggeC filtraF • rif. regola -‐ salience -‐ codice
FIFO
ai ai
a i
Codice: -‐ Azioni logiche (pot. distruave) -‐ Effea collaterali (non rever(bili!)
!
AGENDA
4 Giugno 2013 Sistemi a Regole di Produzione 93
Risoluzione dei ConfliC & Esecuzione
PM
r1 r2
WM
f
Agenda a1 a2
rule "r1" when F() then assert(new G()); end
rule "r2" when $f: F() then retract($f); end ?!?
4 Giugno 2013 Sistemi a Regole di Produzione 94
Risoluzione dei ConfliC & Esecuzione
PM
r1 r2
WM
f
Agenda a1 a2
rule "r1" when F() then assert(new G()); end
rule "r2" when $f: F() then retract($f); end ?!?
a1 < a2
PM
Agenda WM
PM
Agenda WM
a2 < a1 r1 < r2
rule "r1" salience 10 ...
rule "r2" salience 5 ...
Prima inserisco G, poi elimino F.
Prima elimino F, a1 non sussiste più, G mai asserito.
Stabilisco un ordine di precedenza tra r1 e r2 (fisso).
4 Giugno 2013 Sistemi a Regole di Produzione 95
RIFERIMENTI FondamenF di Intelligenza ArFficiale M
RiferimenF • Charles L. Forgy, “RETE: A Fast Algorithm for the Many PaFer/
Many Object Match Problem”, ArFficial Intelligence, 19, pp. 17-‐37, 1982
• R.B. Doorenbos, “Produc(on Matching for Large Learning Systems”, Ph.D. Thesis, 1995
• Schmit, Struhmer and Stojanovic, “Blending Complex Event Processing with the RETE algorithm”, in Proceedings of iCEP2008, 2008
• h9p://en.wikipedia.org/wiki/Rete_algorithm • h9p://en.wikipedia.org/wiki/Complex_event_processing
4 Giugno 2013 Sistemi a Regole di Produzione 97
INFORMAZIONI FondamenF di Intelligenza ArFficiale M
Informazioni
• Domani esercitazione in laboratorio
• Possibilità di svolgere aCvità proge9uali o tesi – Drools, Event Calculus, Expecta(ons, MS-‐Kinect, Android SDK, SOA/Cloud, …
• Per domande, dubbi, richieste: [email protected]
4 Giugno 2013 Sistemi a Regole di Produzione 99
