Intelligenza Artificiale e agenti - Appunti

Identificazione della situazione

Come chiamo questa situazione? Sicuramente possiamo dare un nome come S23, ma questo approccio ci obbligherebbe a dare un nome predefinito per ogni possibile situazione. C'è un'altra opzione comunque: invece di dare a questa situazione un nome, possiamo usare una descrizione definita, cioè possiamo identificare la nuova situazione come "il risultato di muovere A da B a C, iniziando da S0". Possiamo rappresentare questo in FOL con il termine funzionale do(move(A,B,C),S0) dove:

• result e move sono simboli funzionali
• un termine funzionale nella forma do(a,s) denota la situazione risultante dall'esecuzione dell'azione a nella situazione s
• un termine funzionale nella forma move(x,y,z) denota l'azione del muovere l'oggetto x da y a z.

Ora, se vogliamo dire che in questa situazione il blocco A è sopra il blocco C, possiamo usare lo statement:

On(A,C,do(move(A,B,C),S0))

che possiamo leggere come: A è sopra C nella situazione.

ottenuta muovendo A da B a C, iniziando da S0. Notare che il terzo argomento del predicato On è una situazione, denotata attraverso il termine funzionale do(move(A,B,C),S0). La funzione simbolo move può essere vista come rappresentante di un tipo di azione che può essere eseguita da un braccio meccanico: AB C do(move(A,B,C),S0).

Ora vogliamo descrivere tutte le possibili azioni. Più precisamente, per ogni possibile azione vogliamo specificare le precondizioni, cioè le condizioni sotto cui l'azione può essere eseguita, e gli effetti. La lista delle azioni di Block World include 27 possibili azioni logiche differenti, alcune di queste azioni, come move(A,B,B), sono inutili, ma ancora logicamente possibili: move(A,B,B), move(B,A,A), move(C,A,A), move(B,A,C), move(C,A,B), move(A,B,C), move(C,A,F), move(B,A,F), move(A,B,F), move(C,B,A), move(B,C,A), move(A,C,B), move(C,B,B), move(B,C,C), move(A,C,C), move(C,B,F), move(B,C,F), move(A,C,F), move(C,F,A), move(B,F,A), move(A,F,B).

move(C,F,B)move(B,F,C)move(A,F,C) move(C,F,F)move(B,F,F)move(A,F,F)Ora dovremmo provare a specificare le precondizioni e gli effetti di queste azioni con il minor numero di assiomi possibili, sfruttando il fatto che tali assiomi possano essere parametrici.

*Axiom A11. Muovendo x da y a z nella situazione s: è possibile s, in s, x è su y, x è libero e z è libero (precondizioni); e risulta in essere x sopra z (effetto):
∀ x y z s (On(x,y,s) Clear(x,s) Clear(z,s) → On(x,z,do(move(x,y,z),s)))

Questo asioma ha la forma di un condizionale, il cui antecedente specifica le precondizioni per l'esecuzione di ogni azione nella forma move(x,y,z) e il cui conseguente specifica un effetto dell'esecuzione di una stessa azione.

Per esempio suppongo che in S0, proviamo a eseguire l'azione move(A,B,C) con sostituzioni adatte, dall'assioma A11 deriviamo:
∧ ∧On(A,B,S0) Clear(A,S0) Clear(C,S0) →

On(A,C,do(move(A,B,C),S0)) ora, possiamo ripetutamente applicare la regola di Modus Ponens, sfruttando Assiomi A5, A8, e A9. Infine deriviamo On(A,C,do(move(A,B,C),S0)). L'assioma A11 comunque non specifica tutti gli effetti delle azioni nella forma move(x,y,z). Un altro effetto è che dopo l'esecuzione dell'azione, y sarà libero (questo è ovvio se y è il floor ma è anche vero se y è un blocco). *Axiom A12. Muovendo x da y a z nella situazione s: è possibile se, in s, x è sopra y, x è libero e z è libero (precondizioni); e risulta in essere y libero (effetto): ∀x ∀y ∀z ∀s (On(x,y,s) Clear(x,s) Clear(z,s) → Clear(y,do(move(x,y,z),s))) ora possiamo derivare Clear(B,do(move(A,B,C),S0)). Gli assiomi A11 e A12 descrivono 2 effetti che possiamo chiamare positivi nel senso che portano in fatti positivi. Vogliamo anche considerare A11 come specificante l'effetto principale delle azioni.

azioni della forma move(x,y,z,s) e A12 come specificante dell'effetto laterale. Comunque dobbiamo essere cauti: un effetto è principale o laterale solo relativamente a un goal. Così, se il nostro goal è quello di avere x sopra z, allora A11 descrive l'effetto principale e A12 descrive un effetto laterale; al contrario se il goal è quello di avere libero y, allora A12 descrive l'effetto principale e A12 descrive un effetto laterale. Un assioma nella forma move(x,y,z) potrebbe anche portare a un effetto negativo: se z è un blocco, allora non sarà più libero dopo l'esecuzione dell'azione.

Axiom A13. Muovendo x da y a z nella situazione s: è possibile se, in s, x è sopra y, x è libero e z è libero (precondizioni); e risulta nell'essere z non più libero se z è un blocco (effetto): ∀∀∀∀∧∧∧A13 x y z s (On(x,y,s) Clear(x,s) Clear(z,s) Block(z)→

<strong>¬Clear(z,do(move(x,y,z),s))</strong> ora possiamo derivare: <strong>¬Clear(C,do(move(A,B,C),S0))</strong> Sembra che con gli assiomi A11-A13 abbiamo descritto tutti gli effetti delle azioni nella forma <em>move(x,y,z)</em>, che a proposito, sono tutte le azioni che possiamo eseguire nel Block World. In un senso questo è vero; ma la nostra teoria è ancora incompleta e dovremmo vedere il perchè---The frame problem. A è libero nella situazione <em>do(move(A,B,C),S0)</em>? Una veloce sbirciata alla rappresentazione grafica suggerisce che questo è il caso; comunque non siamo in grado di dimostrare <strong>Clear(A,do(move(A,B,C),S0))</strong> dagli assiomi A11-A13. Questo perché abbiamo specificato quali facts sono gli effetti di <em>move(x,y,z)</em>, ma non abbiamo specificato i facts che sono rimasti immutati attraverso l'esecuzione di un'azione. Questo potrebbe sembrare superfluo, ma non lo è; sembra superfluo perché, come esseri umani, automaticamente assumiamo che ogni fact che non è un effetto.(positivo o negativo) di un azione è lasciato immutato quando si esegue l'azione. Questo modo di pensare è così naturale per noi, che è difficile capire perché un sistema logico non dovrebbe essere disponibile a derivare le stesse conseguenze. Prima di tutto, ricordiamo che la situazione che abbiamo in mente, è solo uno dei possibili modelli di teoria A1-A13. Le formule che sono vere in uno stesso modello non sono necessariamente vere in tutti i modelli della teoria, e quindi non sono necessariamente derivabili come teoremi. In particolare, che A è libero in do(move(A,B,C),S0) non è un teorema, anche se è vero nel modello che abbiamo in mente. E' plausibile assumere che quando l'uomo ragiona riguardo a Blocks World, non esegue inferenze logiche, ma manipola alcune forme di modello mentale, da cui può leggere cosa è vero e cosa è falso. Mai sistemi logici non lavorano in questo modo: essi lavorano.derivando teoremi e facendo questo essimantengono non un singolo modello inteso,ma tutti i possibili modelli della della teoria.Se vogliamousare la logica,allora dobbiamo rendere la nostra teoria più forte,così riducendo l'insieme deimodelli.Per essere in grado di derivare Clear(A,do(move(A,B,C),S0)),dobbiamo introdurre un nuovo assioma. Axiom A14: Muovendo x da y a z nella situazione s lasciando x libero: ∀x ∀y ∀z ∀s (On(x,y,s) Clear(x,s) Clear(z,s) → Clear(x,do(move(x,y,z),s))) In un senso,questo assioma non descrive un effetto,sia positivo che negativo,di un'azione della forma move(x,y,z);piuttosto dice che certi facts sono lasciati immodificati dalle stesse azioni.Gli assiomi di questo tipo sono chiamati frame axioms,il termini deriva dal frame dei cartoons che è lasciato immutato mentre i personaggi si muovono nella scena. Un altro frame axiom è: Axiom A15: Muovendo x da y a z nella situazione sil ragionamento logico. Il testo formattato con i tag HTML è il seguente:

lasciando y dove è in s:∀ ∀ ∀ ∀ ∀ ∧ ∧ ∧A15 x y z u s (On(x,y,s) Clear(x,s) Clear(z,s) On(y,u,s)→ On(y,u,do(move(x,y,z),s)))

Ma ora abbiamo una difficoltà: in qualsiasi problema di planning, dovremmo essere obbligati a specificare non solo gli effetti delle azioni, ma anche tutti i facts che sono lasciati immutati. Chiaramente, questo renderebbe le nostre teorie estremamente pesanti, in particolare quando il mondo è più complesso che Block World. Questa difficoltà è chiamata Frame Problem. Infatti, il frame problem può essere parzialmente risolto adottando una più complessa rappresentazione delle azioni, che permetti di specificare cosa è lasciato immutato usando un numero limitato di assiomi. In ogni caso, sarà ancora il caso in cui cosa è lasciato immutato da un'azione non è implicitamente nella rappresentazione, ma deve essere esplicitamente derivato attraverso il ragionamento logico.

inferenzeadatte.Questo problema ha portato gli specialisti AI ad abbandonare l'uso di FOL puro nel planning e adadottare differenti approcci,come STRIPS.

--Other problems of the logical approach to planning

Il frame problem non è l'unico difficoltà di un approccio logico al planning. Le altre due difficoltà sono conosciute come problema di qualificazione e di ramificazione.

Il problema di qualificazione è il problema di stabilire condizioni sufficienti per prendere parte agli effetti di un'azione. Per esempio l'assioma A11 dice che x sarà sopra z se muoviamo x da y a z in una situazione in cui:

- x è sopra y,

- x è libero,

- e z è libero.

Questo significa stiamo considerando una congiunzione di x essendo su y, essendo x libero e z essendo libero come condizioni sufficienti per una esecuzione di successo dell'azione. Ma questo è il caso? Cosa accade per esempio se il braccio meccanico rilascia il blocco x mentre cerca di

muoverlo da y verso z? In altre parole i nostri assiomi danno condizioni sufficienti per il successo di un'azione solamente sotto l'assunzione che nessun fatto esterno accada: ma non è sempre il caso nel mondo reale. Come possiamo risolvere il problema di quantificazione? È chiaro che non possiamo sperare di specificare in anticipo tutti gli eventi imprevisti: questo è logicamente impossibile, se consideriamo il termine "unforeseen event" seriamente. Quello che possiamo fare è di progettare un sistema che possa effettuare un ragionamento defettibile: da questo possiamo intendere che anche se una formula è derivata come un teorema, può essere negata successivamente senza introdurre una contraddizione logica. Questo tipo di soluzione è studiata da un branch della logica chiamata nonmonotonic logic. Il problema di ramificazione è il problema di mantenere la traccia di tutti gli effetti laterali (secondari) di un'azione.