Metody Sztucznej Inteligencji.pdf

(792 KB) Pobierz
Microsoft Word - Sztuczna Inteligencja - do druku.doc
Metody Sztucznej Inteligencji
Janusz Marecki
1
Artificial Intelligence A Modern Approach
Stuart Russell, Peter Norvig
[...Artificial Intelligence is one of the newest disciplines. It was formally
initiated in 1956, when the name was coined, although at that point work had
been under way for about five years. Along with modern genetics, it is regularly
cited as the “field I would most like to be in” by scientists in other disciplines. A
student in physics might reasonably feel that all the good ideas have already
been taken by Galileo, Newton, Einstein, and the rest, and that it takes many
years of study before one can contribute new ideas. Artificial Intelligence, on the
other hand, still has openings for a full-time Einstein.
The study of intelligence is also one of the oldest disciplines. For over
2000 years, philosophers have tried to understand how seeing, learning,
remembering, and reasoning could, or should, be done. The advent of usable
computers in the early 1950s turned the learned but armchair speculation
concerning these mental faculties into a real experimental and theoretical
discipline. Many felt that the new “Electronic Super-Brains” had unlimited
potential for intelligence. “Faster Than Einstein” was a typical headline. But as
well as providing a vehicle for creating artificially intelligent entities, the
computer provides a tool for testing theories of intelligence, and many theories
failed to withstand the test – a case of “out of the armchair, into a fire”.
Artificial Intelligence has turned out to be more difficult than many at first
imagined, and modern ideas are much richer, more subtle, and more interesting
as a result.
Artificial Intelligence currently encompasses a huge variety of subfields,
from general – purpose areas such as perception and logical reasoning, to
specific tasks such as playing chess, providing mathematical theorems, writing
poetry, and diagnosing diseases. Often, scientists in other fields move gradually
into artificial intelligence, where they find more tools and vocabulary to
systematize and automate the intellectual tasks on which they been working all
their lives. Similarly, workers in Artificial Intelligence san choose to apply their
methods to any area of human intellectual endeavor. In this sense, it is truly a
universal field...]
2
SPIS TREŚCI
1. Logicznie myślący agent....................................................................................................6
1.1 Agent oparty na bazie wiedzy....................................................................................6
1.2 Świat WUMPUS’a.....................................................................................................7
2. Logika zdań......................................................................................................................11
2.1 Składnia....................................................................................................................11
2.2 Semantyka................................................................................................................12
2.3 Poprawność i wnioskowanie....................................................................................12
2.4 Zasady wnioskowania dla logiki zdań .....................................................................14
2.5 Problem wumpusa w logice zdań.............................................................................15
2.6 Zadania.....................................................................................................................18
3. Logika pierwszego stopnia...............................................................................................20
3.1 Składnia i Semantyka...............................................................................................20
3.2 Logika wyższego stopnia.........................................................................................25
3.3 Używanie logiki pierwszego stopnia........................................................................26
3.4 Logiczny agent w świecie wumpusa........................................................................27
3.5 Zadania.....................................................................................................................30
4. Budowanie Bazy Wiedzy.................................................................................................32
4.1 Dobra i zła baza wiedzy...........................................................................................32
4.2 Baza Wiedzy dla układów scalonych.......................................................................34
4.3 Sposoby reprezentacji świata...................................................................................37
4.4 Zadania.....................................................................................................................44
5 Wnioskowania w logice pierwszego stopnia ...................................................................45
5.1 Reguły wnioskowania zawierające kwantyfikatory.................................................45
5.2 Rozszerzona zasada Modus-Ponens.........................................................................46
5.3 Wnioskowanie w przód i w tył.................................................................................48
5.4 Ostateczna procedura wnioskowania.......................................................................51
5.5 Procedura Unifikacyjna............................................................................................53
5.6 Indeksowanie bazy wiedzy.......................................................................................54
5.7 Zadania.....................................................................................................................55
6 Planowanie.......................................................................................................................56
6.1 Prosty agent planowania...........................................................................................56
6.2 Rozwiązywanie problemów i planowanie................................................................57
6.3 Planowanie w rachunku sytuacyjnym......................................................................59
6.4 Podstawowa reprezentacja planowania....................................................................60
6.5 Przykład tworzenia planu częściowego porządku....................................................66
6.6 Algorytm tworzący plan częściowego porządku .....................................................73
6.7 Planowanie przy częściowo zainicjowanych operatorach .......................................75
6.8 Inżynieria Wiedzy dla problemu planowania...........................................................77
6.9 Dekompozycja Hierarchiczna..................................................................................79
6.10 Analiza Dekompozycji Hierarchicznej ....................................................................82
6.11 Zadania.....................................................................................................................86
7 Nauczanie.........................................................................................................................89
Nauczanie na podstawie obserwacji.....................................................................................89
7.1 Nauczanie indukcyjne..............................................................................................90
7.2 Nauczanie przy pomocy drzew decyzyjnych...........................................................92
7.3 Korzystanie z teorii informacji...............................................................................100
7.4 Inne metody szukania hipotez................................................................................101
7.5 Zadania...................................................................................................................103
3
Spis ilustracji
Rysunek 1 Przykładowy świat WUMPUS'a ..............................................................................8
Rysunek 2 Kolejne etapy działania agenta.................................................................................9
Rysunek 3 Tabela wartościowań i funkcji ...............................................................................13
Rysunek 4 Zadanie znalezienia złota.......................................................................................19
Rysunek 5 Układ scalony realizujący dodawanie....................................................................35
Rysunek 6 Wydarzenia w przestrzeni i czasie.........................................................................40
Rysunek 7 Rozmieszczenie interwałów czasowych ................................................................42
Rysunek 8 Schemat 4 bitowego sumatora................................................................................44
Rysunek 9 Rozwiązywanie problemu zakupów przy przeszukiwaniu wprzód przestrzeni
wszystkich możliwych stanów.........................................................................................58
Rysunek 10 Diagram dla operatora Idź(tam). Warunki są powyżej akcji, a efekty poniżej....61
Rysunek 11 Plany inicjujące....................................................................................................64
Rysunek 12 Plan częściowy dla "Problemu zakłądania kół na rower" i jego 6 linearyzacji ...65
Rysunek 13 Diagram planu inicjacyjnego dla problemu "zakupów".......................................67
Rysunek 14 Problem "Zakupów" - 1 etap działania algorytmu...............................................68
Rysunek 15 Problem "Zakupów" - 2 etap działania algorytmu...............................................69
Rysunek 16 Problem "Zakupów" - 3 etap działania algorytmu...............................................70
Rysunek 17 Zabezpieczające połączenia przyczynowe...........................................................71
Rysunek 18 Problem "Zakupów" - 4 etap działania algorytmu...............................................71
Rysunek 19 Rozwiązanie problemu z "Zakupami"..................................................................73
Rysunek 20 Hierarchiczna dekompozycja przy budowie domu..............................................80
Rysunek 21 Zstępująca i wstępująca własność rozwiązania....................................................83
Rysunek 22 Wycinek przestrzeni poszukiwań przy dekompozycji hierarchicznej .................84
Rysunek 23 Problem obdarowywania prezentami...................................................................85
Rysunek 24 Świat Shakey'a......................................................................................................87
Rysunek 25 Problem Blokowy.................................................................................................88
Rysunek 26 Nauczanie indukcyjne - przykład geometryczny.................................................90
Rysunek 27 Oryginalne drzewo decyzyjne dla problemu "czekania na stolik".......................93
Rysunek 28 Działanie algorytmu tworzącego drzewo decyzyjne............................................98
Rysunek 29 Drzewo decyzyjne utworzone na podstawie 12 wzorców ...................................99
Rysunek 30 Schemat działania algorytmu Aktualnie-Najlepszej hipotezy ...........................102
4
WSTĘP
Czym jest „Sztuczna Inteligencja”?
Skrypt, który czytasz drogi czytelniku jest zbiorem kilku ważniejszych
zagadnień z dziedziny sztucznej inteligencji. Znajdziesz w nim wiele ciekawych
zagadnień opisujących zachowania sztucznych agentów w naturalnym
otoczeniu. Każde zagadnienie jest wnikliwie wytłumaczone, przez co szkice
algorytmów rozwiązujących poszczególne problemy nie są trudne do
zrozumienia. Na końcu każdego rozdziału znajduje się kilka zadań, których
samodzielne rozwiązanie powinno ułatwić każdemu utrwalenie zdobytego
materiału.
Sam temat Sztucznej Inteligencji jest tak wielki, że skrypt ten obejmuje
zaledwie jego cząstkę. Generalnie materiał można podzielić na 4 grupy: Logika
zdań, Logika Pierwszego Stopnia, Planowanie i Nauczanie. Są to ważne
elementy wykorzystywane do budowy inteligentnie zachowujących się
systemów. W skrypcie nie został poruszony ważny temat sieci neuronowych,
który jest naturalnie identyfikowany ze Sztuczną Inteligencją. Zagadnienie to
jest bowiem zbyt obszerne, do jego omówienia na stronach tego skryptu.
Dla kogo jest ten skrypt?
Skrypt kieruję docelowo do studentów informatyki wyższych lat, gdyż
zamieszczone w nim algorytmy są bardzo abstrakcyjne i do ich poprawnego
zaimplementowania czytelnik musi znać dosyć dobrze przynajmniej jeden język
programowania. Samodzielne zaprogramowanie omawianych sztucznych
agentów i rozwiązanie zamieszczonych w podręczniku zadań pozwala na
poznanie aktualnie panujących podstaw w dziedzinie Sztucznej Inteligencji
Jak czytać ten skrypt?
By zrozumieć omawiane w skrypcie problemy nie ma potrzeby
korzystania z innej literatury na ten temat. Niemniej jednak proponuję zapoznać
się wszystkim z pierwszymi 2 rozdziałami, w których znajdują się terminy
używane w kolejnych rozdziałach. Rozdziały 3, 4, 5 stanowią całość i powinny
być czytane razem. Rozdziały 6 i 7 można czytać osobno od całości, gdyż
omawiają one zagadnienia Planowania i Nauczania od podstaw.
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin