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:

1. niepełna wiedza o aktualnym stanie. Przykładem może być brak odpowiednich sensorów w robocie lub gra w karty, w której nie znamy całego rozdania, a musimy planować wiele ruchów w przód (na przykład Brydż).
2. niepewność wynikająca z zawodności akcji. W tym przypadku nie jesteśmy pewni, czy wykonywana akcja na pewno się uda. Prostym modelem takiej sytuacji może być gra RPG, gdzie rzut kością decyduje o sukcesie. Plan rozegrania bitwy w tego typu grze powinien brać pod uwagę możliwość nieudanego rzutu. Przykładem bardziej „życiowym” jest praca robota, który próbują podjąć pewne akcje, często akcje.
3. wykonywanie akcji zajmuje czas — plan powinien brać pod uwagę temporalny wymiar problemu. Wszak rzadko kiedy środowisko, w którym się poruszamy, jest statyczne i przyjazne.
4. mogą wydarzać się zdarzenia niezależne od agenta — np. wypadek drogowy na drodze autonomicznego samochodu. Obsługa takich wyjątków również wchodzi w zakres planowania.

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. Jedyną możliwą akcją w świecie klocków jest podniesienie klocka, który jest na szczycie jakiejś kolumny i położenie go na szczycie dowolnej kolumny.

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.