Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

Both sides previous revision Poprzednia wersja
Nowa wersja
Poprzednia wersja
pl:dydaktyka:psi:labs:lab_search [2019/10/17 21:58]
kkutt [LAB: Przeszukiwanie grafów i planowanie tras przejazdu]
pl:dydaktyka:psi:labs:lab_search [2020/10/05 19:30] (aktualna)
msl [7 Dla zainteresowanych]
Linia 91: 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 179: 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 211: 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)''​
pl/dydaktyka/psi/labs/lab_search.1571342288.txt.gz · ostatnio zmienione: 2019/10/17 21:58 przez kkutt
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0