Różnice między wybraną wersją a wersją aktualną.
| Nowa wersja | Poprzednia wersja | ||
|
pl:dydaktyka:psi:labs:lab_search [2019/03/05 14:45] kkutt utworzono |
pl:dydaktyka:psi:labs:lab_search [2020/10/05 19:30] (aktualna) msl [7 Dla zainteresowanych] |
||
|---|---|---|---|
| Linia 2: | Linia 2: | ||
| Celem ćwiczenia jest zapoznanie się z możliwościami wykorzystania technik sztucznej inteligencji do planowania tras przejazdu oraz poznanie technik poszukiwania ścieżek w grafach. | Celem ćwiczenia jest zapoznanie się z możliwościami wykorzystania technik sztucznej inteligencji do planowania tras przejazdu oraz poznanie technik poszukiwania ścieżek w grafach. | ||
| + | |||
| + | ===== - Do przygotowania ===== | ||
| + | |||
| + | * **[ArtInt]** Sekcje 3.1-3.6 z [[https://artint.info/2e/html/ArtInt2e.Ch3.html|Chapter 3: Searching for Solutions]] | ||
| + | * **[AIMA]** Chapter 3: Solving problems by searching | ||
| + | * [[http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#heuristics-for-grid-maps|Heurystyki dla mapy w postaci siatki]] | ||
| Linia 85: | Linia 91: | ||
| * Ponownie zaobserwuj działanie algorytmów i zanotuj statystyki. Czy dodanie heurystyki poprawia działanie algorytmu? | * Ponownie zaobserwuj działanie algorytmów i zanotuj statystyki. Czy dodanie heurystyki poprawia działanie algorytmu? | ||
| - Jakie są najpopularniejsze heurystyki dla wyszukiwania na płaszczyźnie? | - Jakie są najpopularniejsze heurystyki dla wyszukiwania na płaszczyźnie? | ||
| - | * Przeczytaj [[http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#heuristics-for-grid-maps|artykuł]] i wprowadź opisane w nim heurystyki obserwując zmiany działania algorytmu (aby wykonać operację pierwiastkowania wpisz ''Math.sqrt(x)''). | + | * Przeczytaj [[http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#heuristics-for-grid-maps|artykuł]] i wprowadź opisane w nim heurystyki obserwując zmiany działania algorytmu (aby wykonać operację pierwiastkowania wpisz ''Math.sqrt(dx)''). |
| ==== Zadania ==== | ==== Zadania ==== | ||
| Linia 173: | Linia 179: | ||
| - Uruchom na gotowym grafie algorytm przeszukiwania i zapisz wyniki. | - Uruchom na gotowym grafie algorytm przeszukiwania i zapisz wyniki. | ||
| - | ===== - Dla zainteresowanych ===== | + | ===== - Zagadnienie automatycznego planowania ===== |
| - | Podczas tego laboratorium dotknęliśmy 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 [[http://en.wikipedia.org/wiki/PSPACE|PSPACE-zupełnej]]. Trzeba ponadto zauważyć, że w realnych nie zabawkowych problemach występują dodatkowe czynniki zwiększające trudność problemu: | + | Podczas tego laboratorium dotknęliśmy 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 [[http://en.wikipedia.org/wiki/PSPACE|PSPACE-zupełnej]]. Trzeba ponadto zauważyć, że w realnych niezabawkowych problemach występują dodatkowe czynniki zwiększające trudność problemu: |
| * niepełna wiedza o aktualnym stanie (np. brak odpowiednich sensorów w robocie) | * niepełna wiedza o aktualnym stanie (np. brak odpowiednich sensorów w robocie) | ||
| Linia 205: | Linia 211: | ||
| 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. | 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. | ||
| - | Poniższy kod jest jego prostą implementacją STRIPS w języku Prolog: | + | Pod [[https://swish.swi-prolog.org/p/block_strips_player_v2.pl|poniższym linkiem]] znajduje się prosta(cka) implementacja solvera STRIPS w języku Prolog. |
| - | + | ||
| - | <code prolog STRIPS regression planner> | + | |
| - | + | ||
| - | % Strips as a regression planner. | + | |
| - | % Top-level interface. | + | |
| - | strips(InitState, GoalList, Plan) :- | + | |
| - | strips1(InitState, GoalList, [], [], _, RevPlan), | + | |
| - | reverse(RevPlan, Plan). | + | |
| - | + | ||
| - | % Base case: All goals satisfied in State. | + | |
| - | strips1(State, GoalList, Plan, _, State, Plan) :- | + | |
| - | subset(GoalList, State). | + | |
| - | + | ||
| - | % Plan | + | |
| - | strips1(State, GoalList, Plan, BadActions, NewState, NewPlan) :- | + | |
| - | member(Goal, GoalList), | + | |
| - | not(member(Goal, State)), % Find unsatisfied goal. | + | |
| - | write('\nAttempting goal: '),write(Goal),nl, | + | |
| - | adds(Ac, Goal), % Find action that achieves it. | + | |
| - | write(' Choosing Action: '),write(Ac), | + | |
| - | not(member(Ac, BadActions)), % Do not repeat actions (dangerous). | + | |
| - | write(' -- not a bad action.'),nl, | + | |
| - | preclist(Ac, PrecList), % Find preconds and achieve them. | + | |
| - | strips1(State, PrecList, Plan, [Ac|BadActions], TmpState1, TmpPlan1), | + | |
| - | apply_rule(Ac, TmpState1, TmpState2), % Recurse w/new state and goals. | + | |
| - | strips1(TmpState2,GoalList,[Ac|TmpPlan1],BadActions,NewState,NewPlan). | + | |
| - | + | ||
| - | % Apply Rule | + | |
| - | apply_rule(Ac, State, NewState) :- | + | |
| - | write('\nSimulating '),write(Ac),nl, | + | |
| - | write('From: '), write(State), write('\n----> '), | + | |
| - | dellist(Ac, DelList), % find deleted props | + | |
| - | subtract(State, DelList, TmpState), % remove deleted props | + | |
| - | addlist(Ac, AddList), % find added props | + | |
| - | union(AddList, TmpState, NewState), % add props to old state | + | |
| - | write(NewState). | + | |
| - | + | ||
| - | % Utilities | + | |
| - | preclist(Action, Plist) :- strips_rule(Action, Plist, _, _). | + | |
| - | prec(Action, Cond) :- preclist(Action, Plist), member(Cond, Plist). | + | |
| - | addlist(Action, Alist) :- strips_rule(Action, _, Alist, _). | + | |
| - | adds(Action, Cond) :- addlist(Action, Alist), member(Cond, Alist). | + | |
| - | dellist(Action, Dlist) :- strips_rule(Action, _, _, Dlist). | + | |
| - | dels(Action, Cond) :- dellist(Action, Dlist), member(Cond, Dlist). | + | |
| - | + | ||
| - | % Pretty-print Init, Goal, and Plan. | + | |
| - | plan(InitState, Goal) :- | + | |
| - | strips(InitState,Goal,Plan), | + | |
| - | write('\n\nInit: '), write(InitState),nl, | + | |
| - | write('Goal: '),write(Goal),nl, | + | |
| - | write('Plan:\n'), | + | |
| - | writeplan(Plan),nl. | + | |
| - | % Pretty-print the plan. | ||
| - | writeplan([]). | ||
| - | writeplan([A|B]):- | ||
| - | write(' '),write(A),nl, | ||
| - | writeplan(B). | ||
| - | </code> | ||
| ==== Zadania ==== | ==== Zadania ==== | ||
| - | - Należy pobrać {{:pl:dydaktyka:psi:labs:strips_planner.pl|kod programu planującego}} i uzupełnić go o informacje potrzebne do rozwiązania problemu bloków (sekcje ''%TODO:''). Objaśnienia: | + | - Należy pobrać uzupełnić powyższy program w Prologu o informacje potrzebne do rozwiązania problemu bloków (sekcje ''%TODO:''). Objaśnienia: |
| - dla wygody planowania możemy pominąć numery kolumn, a stan może być reprezentowane przez pięć typów faktów (przykładowe stany można zobaczyć w sekcji ''EXAMPLES OF USAGE''): | - dla wygody planowania możemy pominąć numery kolumn, a stan może być reprezentowane przez pięć typów faktów (przykładowe stany można zobaczyć w sekcji ''EXAMPLES OF USAGE''): | ||
| - ''ontable/1'' --- dany klocek leży na stole, np. ''ontable(a)'' | - ''ontable/1'' --- dany klocek leży na stole, np. ''ontable(a)'' | ||
