8063591499

Algorytm planowania:

Jest to pewien algorytm przeszukiwania przestrzeni stanów. Reprezentujemy go przez drzewo. Węzłami są stany, gałęzie to akcje prowadzące do kolejnych stanów.

sO............. 1 jaOl	i	| a 02	i	|a03
sil.....	sl2		sl3
ja 11	|a 12
s21s22

Korzystamy ze struktury danych - trójki opisu stanu: <stan aktualny, stan poprzedni, akcja przenosząca>

Utrzymujemy listę stanów poprzednich (w postaci listy opisów stanów) oraz kolejkę stanów aktualnie badanych (także lista opisów stanów).

Algorytm:

-    zdejmujemy stan z kolejki

-    tworzymy listę akcji, które można podejmować w tym stanie

-    wyznacz dla każdej akcji nowy stan

-jeżeli stan odpowiada celowi, to zwróć plan akcji

-    jeżeli stan różny od celu, twórz nowy opis stanu i dołącz go do kolejki stanów Przykładowy zapis - konstruowanie akcji:

[<LEZY_NA KLOCEK2 KLOCEK 5>, <LEZY NA KLOCEK1 POLE4>, ...]

[<POLE2 WOLNE>, <KLOCEKl WOLNE>, ...]

-    wyodrębnienie listy opisów statusu

-    przeszukanie listy opisów statusu w celu znalezienia klocka o opisie WOLNE (pomysł: dodatkowe pole typu KL / PL w opisie)

-    znalezienie klocka / pola, na którym leży

-    znalezienie na tej samej zasadzie wolnego pola

-    skonstruowanie akcji ze związanych elementów

Dygresja: ze względu na charakter symboli jako niepodzielnych jednostek, porównywanie symboli odbywa się technicznie przez porównywanie wskaźników.

Jakie kryteria musi spełniać język do przetwarzania danych symbolicznych / Al:

-    Potrzebujemy języka w którym prosto możemy manipulować danymi.

-    Wymagana jest także odpowiednia optymalizacja wszystkich operacji, aby software szybko działał.

-    Wreszcie, czasami potrzeba odpowiedniego sprzętu (istnieją wyspecjalizowane procesory LISPowe, przetwarzające w odpowiednio szybki sposób operacje, umożliwiające prostą manipulację z punktu widzenia sprzętu).

-Wbudowane przeszukiwanie przestrzeni możliwych rozwiązań (w Al trzeba przeszukiwać masywne przestrzenie - PROLOG ma to zaimplementowane, LISP nie) Przykład