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 08:39] 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. Z drugiej strony jednak to właśnie dobrze dobrana heurystyka często sprawia, że problem daje rozwiązać się w rozsądnym czasie. | + | 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}} |
| + | |||
| + | 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ń === | === Kodowanie do problemu satysfakcji ograniczeń === | ||
| Linia 40: | Linia 42: | ||
| - 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. | - 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. | ||
| - | - **Ćwiczenie:** proszę pobrać {{:pl:dydaktyka:planning:blocks_world_minizinc.zip|model świata klocków napisany w MiniZincu}}: | + | == 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? | - ś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? | - które ograniczenia definiuje sposób przechodzenia między stanami? | ||
