Celem ćwiczenia jest zapoznanie się z możliwościami wykorzystania Prologu do planowania tras przejazdu oraz poznanie technik poszukiwania ścieżek w grafach i ich implementacji w Prologu.
Modelem przestrzeni poszukiwań dla planowania tras przejazdu jest graf.
Graf to twór matematyczny składający się ze zbioru wierzchołków V (ang. nodes, vertices) oraz zbioru krawędzi E (ang. links, edges).
Najprostsza definicja grafu mówi, że graf to para postaci G=(V,E), gdzie V jest zbiorem węzłów a E ⊆ V×V jest zbiorem łączących je krawędzi.
Model ten reprezentuje schematycznie mapę, gdzie w zależności od poziomu abstrakcji węzły mogą np. reprezentować miasta, a krawędzie - łączące je drogi, lub też węzły mogą reprezentować skrzyżowania ulic a krawędzie ulice (lub ich odcinki).
Zapoznaj się, lub raczej przypomnij sobie podstawowe wiadomości o grafach.
Pamiętaj, że krawędź grafu może być skierowana (modeluje przejazd tylko w jedną stronę; np. ulica jednokierunkowa) lub nieskierowanym (modeluje przejazd w obie strony; np. ulica dwukierunkowa).
Odpowiednio, graf może być grafem skierowanym, nieskierowanym lub mieszanym.
Ponadto, z każdą krawędzią może być związany koszt przejazdu (odległość, czas).
Jeżeli dwa węzły grafu połączone są więcej niż jedną krawędzią, krawędzie te muszą być etykietowane dla umożliwienia ich rozróżnienia.
Zadanie planowania tras przejazdu to zadanie polegające na wyznaczeniu drogi łączącej zadany punkt początkowy i pożądany punk docelowy.
Zwykle dążymy do wyznaczenia trasy najkrótszej, najszybszej lub o najniższym koszcie.
Modelem zadania planowania trasy jest poszukiwanie ścieżki w grafie.
Zadania planowania trasy definiowane jest jako:
P = (v_I, v_G, V, E)
gdzie v_I to zadany węzeł początkowy, v_G to zadany węzeł docelowy, a V oraz E definiują graf (przestrzeń poszukiwań).
Rozwiązaniem zadania planowania trasy jest ciąg krawędzi e_1, e_2,…,e_n, taki, że:
Powyższy ciąg krawędzi tworzy ścieżkę stanowiącą plan przejazdu.
Zwykle wymaga się aby każdy węzeł leżący na ścieżce przejazdu odwiedzany był tylko raz (brak cykli).
Znanych jest wiele algorytmów przeszukiwania grafów, zarówno w obszarze teorii grafów, badań operacyjnych jak i sztucznej inteligencji.
Algorytmy z obszaru sztucznej inteligencji wyróżniają się tym, że:
Zapoznaj się z podstawowymi algorytmami:
Plan dopuszczalny to plan stanowiący rozwiązanie (ścieżka łącząca węzeł początkowy i docelowy) i ew. spełniający zadane ograniczenia (np. długości, omijania wybranych węzłów zabronionych, przechodzenia przez zadane węzły wymagające odwiedzenia, etc. Plan ten nie musi być 'najlepszy'.
Plan optymalny to plan najlepszy w sensie wybranego kryterium, np.
Więcej o metodach szukania w AI można znaleźć w podręczniku
Na zajęciach wykorzystujemy wbudowane predykaty do obsługi list. Zobacz dokumentację SWI: A.12 library(lists): List Manipulation
Możesz też zawsze przeczytać pomoc, np. help(append).
W Prologu można reprezentować grafy na kilka sposobów.
Najprostszą i efektywną metodą jest zadeklarowanie połączeń pomiędzy węzłami grafu w postaci faktów w Prologu.
Rozważmy następujący graf:
Przykład grafu - model połączeń drogowych (.pdf)
W grafie tym istnieje jedna ścieżka optymalna (lewa krawędź) oraz wiele ścieżek dopuszczalnych przechodzących przez węzły n1-n6.
Reprezentacja tego grafu w Prologu ma postać:
d(s,g). d(s,n1). d(s,n2). d(n1,n2). d(n1,n4). d(n1,n3). d(n2,n3). d(n3,n4). d(n3,n5). d(n4,n5). d(n4,n6). d(n5,n6). d(n6,g).
Jak widać, każda krawędź zapisywana jest w postaci relacji d(<węzeł_początkowy>,<węzeł_końcowy>).
W przykładowym grafie istnieje 13 krawędzi. Zgodnie z deklaracją w Prologu, są to krawędzie skierowane (dlaczego?)
Aby zadeklarować możliwość przejazdu w obie strony, należy zdefiniować domknięcie symetryczne relacji połączenie d/2.
%%% domknięcie symetryczne relacji d/2 przejazd(X,Y):- d(X,Y). przejazd(X,Y):- d(Y,X).
Tak więc, każda krawędź umożliwia przejazd w obie strony.
Rozważmy najprostszy program realizujący zadanie poszukiwania tras przejazdu:
%%% domknięcie tranzytywne relacji przejazd szukaj_trasy(Cel,Cel,Trasa,Trasa):- !. szukaj_trasy(Miasto,Cel,Robocza,Trasa):- przejazd(Miasto,NoweMiasto), not(member(NoweMiasto,Robocza)), szukaj_trasy(NoweMiasto,Cel,[NoweMiasto|Robocza],Trasa).
Predykat szukaj_trasy/4 ma 4 parametry:
Pierwszy wariant definiuje zakończenie poszukiwań: gdy znajdziemy się w węźle docelowym, trasa Robocza staje się docelową.
Drugi wariant definiuje sposób szukania trasy:
Zauważ, że:
Aby ułatwić uruchamianie programu wyposażymy go w klauzulę inicjującą:
%%% inicjacja szukania plan(Start,Cel,Trasa):- szukaj_trasy(Cel,Start,[Cel],Trasa).
Zauważ, że Start i Cel zamieniły się miejscami. Dlaczego?
Aby wyznaczyć automatycznie wszystkie plany uzupełnimy program o klauzulę:
%%% Find all plans from 's' to 'g'. fap(Plans) :- findall(Trasa, plan(s,g,Trasa),Plans).
Aby wyznaczyć automatycznie wszystkie plany i zapisać je do pamięci uzupełnimy program o klauzulę:
%%% Find all plans and assert; p(<plan>). fap-assert:- plan(s,g,Plan), assert(p(Plan)), fail. fap-assert.
Jaka to konstrukcja? Na czym polega jej działanie?
Pełny program znajdziesz tutaj: plan-robust-count.pl
Załączony program pozwala poszukiwać tras przejazdy pomiędzy wybranymi miastami w Polsce.
Prosty program planowania tras przejazdu: plan.pl
Przeanalizuj działanie programu.
Rozbuduj jego bazę wiedzy - dodaj nowe miasta.
Wypróbuj działanie.
Następujący program pozwala wyszukiwać trasy metodą wgłąb (go) i wgłąb z wyliczaniem głębokości.
Następujący program pozwala wyznaczać długość znalezionych tras.
Następujący program pozwala automatycznie wyznaczać długość znalezionych tras oraz trasę optymalną (branch and bound).
Wyznaczanie trasy optymalnej: plan_d_opt.pl
Przeanalizuj program i jego działanie.
Czy zaproponowana metoda jest efektywna? Na czym polegają jej niedoskonałości i ograniczenia?
Następujący program pozwala wyznaczać długość znalezionych tras oraz znajduje trasę optymalna z wykorzystaniem mechanizmu nawrotów w Prologu.
Planowanie trasy optymalne z nawrotami: plan_f.pl
Następujący program pozwala wyznaczać plan metodą wszerz (BFS)
Przeanalizuj działanie programu.
Heurystyka jest zadana w szukaj_trasy
.
Porównaj z wcześniejszymi alg. szukania.
Program bratko-fig12_3f.pl implementuje algorytm A*. Zobacz też: http://artint.info/html/ArtInt_56.html
Sam program wymaga podania opisu problemu przez predykat s(N,M,C).
:
Wymagane jest też podanie heurystyki h(N,H)
- gdzie H to heurystyczna estymacja kosztu najlepszej trasy z N do celu.
Poczytaj o 8-puzzle. W opisie tego problemu używamy innej miary odległości niż np. na drodze, tzw. odległości taksówkarskiej Manhattan_distance
Program bratko-fig12_6.pl implementuje opis tego problemu do rozwiązania przez w.w. algorytm A*.
Przykładowe wywołanie:
?- start1( Pos), bestfirst( Pos, Sol), showsol( Sol).
Zobacz rozwiązania dla inne stanów startowych.
Spróbuj zrealizować wizualizację grafu dla tras przez program Graphviz. Vide: programy w metaprogramowanie_i_potoki
Przeczytaj lab classicsearch. Spróbuj użyć programu AIspace: search najprościej wersji JAR.