Scenari moderni
L’Intelligenza Artificiale (AI)
Il secondo teorema di Goedel
• Non c’è coincidenza tra dimostrabile e vero
• Ciò che si può effettivamente calcolare non
coincide non la verità formale: solo ciò che
è riconducibile a una funzione ricorsiva è
efettivamente calcolabile
• Esiste un dominio di problemi non
computabili
Problemi non computabili
• Non formalizzabili
• Non ricorsivi
• Non trattabili
Tesi di Mitchie
• L’uomo affronta con successo ance
problemi non computabili
• Se saremo in grado di descrivere abbastanza
dettagliatamente la strategia vincente
dell’uomo, allora saremo anche in grado di
scrivere un programma che si comporta allo
stesso modo
Breve storia
• 1956 - Seminario su “artificial intelligence”
• Prima fase: entusiasmo: Logical Theorist,
GPS
• Seconda fase: gli expert systems
• 1980 - La stanza cinese: AI forte e AI
debole
• 1986 - Algoritmo di back-propagation
Attualmente ...
• Contrapposizione tra approccio
cognitivista e connessionista
Rappresentazione della
conoscenza in AI
• Esplicita vs implicita
• Dinamica vs statica
• Probabilistica vs deterministica
• Non monotona vs monotona
Aree dell’AI
•
•
•
•
•
•
•
Elaborazione del linguaggio (NLP)
Problem solving
Planning
Theorem proving
Visione artificiale
Robotica
...
Risulzione dei problemi
• Rappresentazione del problema (teoria dei
grafi)
• Tecniche di ricerca cieca
• Tecniche di ricerca euristica
Rappresentazione del problema
• Operatori
• Spazio degli stati
• Spazio problemico
• Spazio di ricerca
Ricerca cieca
• In profondità (si passa di figlio in figlio)
• In ampiezza (si passa al nodo successivo
dello stesso livello)
Comparativamente ...
• Nella ricerca in profondità l’uso della
memoria cresce linearmente
• La ricerca in ampiezza è più robusta e tende
a trovare la soluzione migliore (di cammino
più breve)
Euristica
• E’ una funzione di valutazione della bontà
di un nodo
• Consente di dominare l’esplosione
combinatoria
• E’ strettamente dipendente dal problema
Algoritmi di ricerca euristica
• Hill climbing
• Best first
• Algoritmo A
La programmazione logica
• Forme a clausole
• Principio di risoluzione (da A o B e non-A
o C si può dedurre B o C)
• Metodo di refutazione
Linguaggio Prolog
• Fatti: scrisse(dante, commedia).
• Regole: autore(X) :- libro (Y),
scrisse(X,Y).
Planning
• Calcolo situazionale
• Frame problem
STRIPS
• Rappresentazione di una azione con le liste
di precondizioni, di aggiunte, di
cancellazioni
• Analisi mezzi/fini
• Limiti di STRIPS
Il trattamento degli obiettivi
congiunti
• Protezione degli obiettivi
• Regressione
• Modifica dei piani
La prianificazione gerarchica:
ABSTRIPS
•
•
•
•
Indice di criticalità
Graduare gli obiettivi
Graduare le azioni
Procedere top-down
Pianificazione non lineare:
NOAH
• Least commitment
• Uso dei critici
• Modifica dei piani
Azioni in parallelo
A
SPLIT
JOINT
B
Mentre parliamo ...
• La mente è nel cervello?
• Esiste il mentale?
• Approccio simbolico vs emulazione
dell’hardware
• Modelli ibridi ...