Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:dydaktyka:planning:intro [2016/04/06 02:55] msl [Rozwiązywanie problemu] |
pl:dydaktyka:planning:intro [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 17: | Linia 17: | ||
| - położenie klocka przez robota. Warunkiem wykonania tej akcji jest swobodny niepuste ramię robota. Klocek może być położony jedynie na szczycie kolumny. | - położenie klocka przez robota. Warunkiem wykonania tej akcji jest swobodny niepuste ramię robota. Klocek może być położony jedynie na szczycie kolumny. | ||
| - | ==== Reprezentacja 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: | ||
| - | |||
| - | {{ :pl:dydaktyka:planning:blocks_world_state_space.png?300 |Przykładowa przestrzeń stanów w świecie klocków}} | ||
| ==== Rozwiązywanie problemu ==== | ==== Rozwiązywanie problemu ==== | ||
| Linia 29: | Linia 25: | ||
| === A-star === | === A-star === | ||
| - | Podstawową metodą rozwiązywania klasycznych problemów planowania jest zastosowania heurystycznych algorytmów grafowych, np. [[https://en.wikipedia.org/wiki/A*_search_algorithm|A-star]]. Problemem tego podejścia jest zależność od heurystyki, która musi być [[https://en.wikipedia.org/wiki/Admissible_heuristic|dopuszczalna]] i nie przenosi się łatwo do innych problemów tego typu. | + | 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: |
| - | - **Ćwiczenie:** proszę zdefiniować dopuszczalną heurystykę dla problemu świata klocków | + | {{ :pl:dydaktyka:planning:blocks_world_state_space.png?300 |Przykładowa przestrzeń stanów w świecie klocków}} |
| - | === Kodowanie do problemy satysfakcji ograniczeń === | + | Podstawową metodą przeszukiwania przestrzeni stanów jest zastosowanie heurystycznych algorytmów, np. [[https://en.wikipedia.org/wiki/A*_search_algorithm|A-star]]. Problemem tego podejścia jest zależność od heurystyki, która musi być [[https://en.wikipedia.org/wiki/Admissible_heuristic|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). |
| + | |||
| + | == Zadania == | ||
| + | |||
| + | - proszę zdefiniować dopuszczalną heurystykę dla problemu świata klocków | ||
| + | |||
| + | === Kodowanie do problemu satysfakcji ograniczeń === | ||
| + | |||
| + | 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: | ||
| + | |||
| + | - w problemach satysfakcji ograniczeń istnieje jeden globalny stan (aktualne wartości zmiennych). Aby modelować systemy stanowe, należy najczęściej zdefiniować po jednej kopii wszystkich zmiennych stanowych dla każdej chwili czasowej problemu. Następnie ograniczeniami wymusza się, aby następujące po sobie stany spełniały odpowiednie warunki. | ||
| + | - problem planowania może nie zakładać żadnego horyzontu czasowego ("deadline'u"), podczas, gdy w problemach dyskretnych nie mogą istnieć zmienne o nieskończonej dziedzinie. W horyzont czasowy reprezentuje się wtedy jako skończoną (dostatecznie dużą) wartość. Aby konstruować jak najkrótsze plany często wymusza się na solverze, by najpierw próbował przypisywać horyzontowi czasowemu jak najmniejsze wartości. | ||
| + | |||
| + | == Zadania == | ||
| + | |||
| + | - proszę pobrać {{:pl:dydaktyka:planning:blocks_world_minizinc.zip|model świata klocków napisany w MiniZincu}}: | ||
| + | - świat bloków opisany w tym modelu jest uproszczoną wersją problemu opisanego powyżej. Na czym polegają wprowadzone uproszczenia? | ||
| + | - które ograniczenia definiuje sposób przechodzenia między stanami? | ||
| + | - proszę teraz: | ||
| + | - zwiększyć wartość maksymalnej liczby kroków do odpowiednio dużej wartości - jaki ma to wpływ na długość planu? | ||
| + | - zmienić definicję ostatniego kroku (parametr ''end'') tak, aby był on zmienną o odpowiedniej dziedzinie | ||
| + | - zmienić definicję ograniczenia definiującego przejścia między stanami tak, aby przejście te następowały jedynie, gdy indeks czasowy stanu nie przekracza wartości nowej zmiennej ''end'' | ||
| + | - zmienić adnotację przy definicji celu tak, aby solver starał się zaczynać zawsze od jak najmniejszej wartości zmiennej ''end'' | ||
| + | - proszę poprawić wypisywanie wyniku tak, aby wypisywało tylko istotne stany | ||
| === Program planujący === | === Program planujący === | ||
| Linia 58: | Linia 77: | ||
| == Zadania == | == Zadania == | ||
| - | - Należy pobrać {{:pl:dydaktyka:ai:2015: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ć {{:pl:dydaktyka:planning:blocks_world_strips.pl|kod programu planującego}} i otworzyć go w edytorze tekstu lub [[http://swish.swi-prolog.org/|wygodnym środowisku on-line]]. W miarę możliwości (i znajomości prologa) proszę zapoznać się z implementacją plannera STRIPS na końcu pliku. Następnie należy uzupełnić go 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)'' | ||
| Linia 74: | Linia 93: | ||
| - jaką wartość mają tak wygenerowane plany? | - jaką wartość mają tak wygenerowane plany? | ||
| - przeczytać pobieżnie [[http://en.wikipedia.org/wiki/Relaxation_%28approximation%29|stronę wikipedii na temat relaksacji]]. | - przeczytać pobieżnie [[http://en.wikipedia.org/wiki/Relaxation_%28approximation%29|stronę wikipedii na temat relaksacji]]. | ||
| + | |||
| + | |||
