Poniższe laboratorium stanowi wstęp do bardzo ważnej i wszechobecnej (przemysł, robotyka, gry komputerowe, etc.) dziedziny AI, jaką jest planowanie. Zasadniczo planowanie polega na znalezieniu ciągu akcji (zwanego planem), który po zastosowaniu na stanie początkowym S
, doprowadzi do osiągnięcia stanu docelowego G
. Każda akcja posiada warunki, w których może zostać wykonana oraz skutki jej zastosowania. Planowanie jest trudne, o ile nie założy się odpowiednich ograniczeń na akcje, jego złożoność jest klasy PSPACE
-zupełnej (to gorzej niż problemy NP
, do której zaliczają się problemy optymalizacji dyskretnej). Trzeba ponadto zauważyć, że w realnych nie zabawkowych problemach występują dodatkowe czynniki zwiększające trudność problemu:
Ze względu na podstawowy charakter, na tych zajęciach zajmiemy się dostatecznie trudnym problemem klasycznego planowania.
Starym i lubianym problemem klasycznego planowania jest tzw. świat klocków. Problem jest pozornie mało ambitny: polega na znalezieniu odpowiedniej sekwencji ruchów, pozwalających na przestawienie klocków ze stanu początkowego do zadanego stanu końcowego. W świecie klocków istnieje określona liczba klocków (tradycyjnie każdy klocek wyróżnia narysowana na nim literka) oraz kilka kolumn, w których te klocki mogą leżeć. Każdy klocek leży na dnie jednej z kolumn (czyli na stole) lub umieszczony jest na innym klocku. Przykładowe stany początkowy i końcowy pokazane są na obrazie powyżej. Istnieje dwie możliwe akcje w świecie klocków:
Istnieją trzy względnie proste metody rozwiązywania tego problemu:
Standardową reprezentacją problemów planowania jest skierowany graf nazywany przestrzenią stanów — każdy węzeł w grafie odpowiada możliwemu stanowi świata. Dwa wierzchołki są połączone krawędzią, jeśli istnieje akcja, która pozwala na przejście z jednego stanu do drugiego. Problem planowania sprowadza się wtedy do znalezienia ścieżki łączącej wybrany wierzchołek (stan początkowy) z innym wierzchołkiem (stanem końcowym). Problem jest często ogromny (potencjalnie nieskończony) rozmiar przestrzeni stanów i brak oczywistych metod jej przeszukiwania. Poniżej pokazany jest przykład przestrzeni stanów dla bardzo prostej instancji problemu świata klocków:
Podstawową metodą przeszukiwania przestrzeni stanów jest zastosowanie heurystycznych algorytmów, np. A-star. Problemem tego podejścia jest zależność od heurystyki, która musi być dopuszczalna i nie przenosi się łatwo do innych problemów tego typu. Z drugiej strony jednak to właśnie dobrze dobrana heurystyka często sprawia, że problem daje rozwiązać się w rozsądnym czasie (dlatego też aktualnie jest wkładane dużo wysiłku w automatyczne odkrywanie heurystyk).
Często stosowanym podejściem w problemach posiadających rozbudowaną strukturę jest przetłumaczenie problemu planowania do problemu satysfakcji ograniczeń i zastosowanie istniejącego solvera. Takie tłumaczenie wiąże się jednak z pewnymi trudnościami:
end
) tak, aby był on zmienną o odpowiedniej dziedzinieend
end
Innym rozwiązaniem jest zastosowania generycznego programu planującego, który przyjmując na wejściu definicję problemu, będzie w stanie znaleźć dopuszczalny plan. Jednym z najbardziej znanych programów planujących jest powstały na Stanfordzie w latach 70 program STRIPS. Używana w nim reprezentacja wiedzy jest do dzisiaj podstawą większości narzędzi planujących. Przykładowa struktura problemu może być zdefiniowana następująco:
Mając taką reprezentację wiedzy, klasyczny program planujący działa według bardzo prostego wzorca (dla zadanego stanu końcowego G i początkowego S):
Efektem powyższej procedury będzie „odwrócony plan”, aby miał sens, należy go wypisać idąc od końca. Drugi haczyk polega na unikaniu zapętlenia w planowaniu - jeżeli chcemy osiągnąć warunki wykonania akcji A (punt 4.) należy wyłączyć ją z procesu planowania.
%TODO:
). Objaśnienia:EXAMPLES OF USAGE
):ontable/1
— dany klocek leży na stole, np. ontable(a)
on/2
— dany klocek leży na drugim klocku, np. on(a,b)
clear/1
— na danym klocku nic nie leży, np. clear(a)
holding/1
— dany klocek został właśnie podniesiony, np. holding(a)
handempty/0
— żaden klocek nie jest aktualnie podniesiony, czyli: handempty
X
na klocku Y
: wykonalna, o ile klocek X
jest aktualnie trzymany, a Y
jest czysty. Po wykonaniu akcji klocek X
leży na klocku Y
i jest czysty, klocek Y
przestaje być czysty i żaden klocek nie jest aktualnie podniesiony.X
z klocka Y
: wykonalna, o ile klocek X
jest czysty i aktualnie leży na klocku Y
. Po wykonaniu akcji klocek X
przestaje być czysty, przestaje leżeć na klocku Y
i zostaje podniesiony. Klocek Y
natomiast staje się czysty.X
na stole: analogicznie do akcji pierwszej z taką różnicą, że nie ma wymagań i zmian względem Y
X
ze stołu: analogicznie do akcji drugiejclear/1
i ponownie uruchomić planowanie dla czterech przypadków.