This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
en:dydaktyka:planning:intro [2017/04/03 14:46] msl [Solutions] |
en:dydaktyka:planning:intro [2020/04/14 11:26] (current) msl |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== Automated Planning ====== | + | ====== Automated Planning: 101 ====== |
| - | This class is an introduction to a very important and omnipresent (i.e.: industry, robotics, video games etc.) discipline of AI – planning. Planning consist in finding a series of actions (called “a plan”), which used on a initial state S will conclude in achieving goal state G. Every action has conditions in which it can be executed, and effects of its application. Planning is difficult: without adequate constraints on actions, the complexity reaches the ''PSPACE''-complete class (worse than ''NP'' problems class, which includes the problems of discrete optimization). Furthermore, real (not toylike) problems may contain additional factors increasing their difficulty: | + | <WRAP center round important 60%> |
| + | Due to the COVID-19 outbreak, all files related to this class are stored in the [[https://gitlab.com/agh-krr/2019-2020/labs-planning|Gitlab repository]]. This class uses files stored in the ''00_intro'' folder. Please refer to the ''Readme.md'' on how to submit the solutions. | ||
| + | </WRAP> | ||
| + | |||
| + | This class is an introduction to a very important and omnipresent (i.e.: industry, robotics, video games etc.) discipline of AI – planning. Planning consists in finding a series of actions (called “a plan”), which used on a initial state S will conclude in achieving goal state G. Every action has conditions in which it can be executed, and effects of its application. Planning is difficult: without adequate constraints on actions, the complexity reaches the ''PSPACE''-complete class (worse than ''NP'' problems class, which includes the problems of discrete optimization). Furthermore, real (not toylike) problems may contain additional factors increasing their difficulty: | ||
| - Incomplete knowledge about actual state. For example, the lack of appropriate sensors in a robot, or a card game, where we don’t know the whole hand, but we must plan our moves in advance (like in bridge) | - Incomplete knowledge about actual state. For example, the lack of appropriate sensors in a robot, or a card game, where we don’t know the whole hand, but we must plan our moves in advance (like in bridge) | ||
| Line 25: | Line 29: | ||
| {{ :en:dydaktyka:planning:blocks_world_state_space.png?nolink&300|Example state space of the blocks worlds problem}} | {{ :en:dydaktyka:planning:blocks_world_state_space.png?nolink&300|Example state space of the blocks worlds problem}} | ||
| A standard representation of the planning problems is a directed graph called “state space” – every node in the graph correspond to a possible state of the world. Two nodes are connected by edge, if there exist an action, which enables moving from one state to another. The planning problem consists in this case in finding a path connecting given node (initial state) with the other (goal state). The state space is often enormous (potentially infinite), and there are no obvious methods of conducting a search. An example of a state space for a very simple instance of a blocks world problem is given below. | A standard representation of the planning problems is a directed graph called “state space” – every node in the graph correspond to a possible state of the world. Two nodes are connected by edge, if there exist an action, which enables moving from one state to another. The planning problem consists in this case in finding a path connecting given node (initial state) with the other (goal state). The state space is often enormous (potentially infinite), and there are no obvious methods of conducting a search. An example of a state space for a very simple instance of a blocks world problem is given below. | ||
| - | |||
| - | |||
| == Assignments == | == Assignments == | ||
| - | - Please define admissible heuristics for the blocks world | + | - Please define an [[https://en.wikipedia.org/wiki/Admissible_heuristic|admissible heuristics]] for the blocks world |
| === Encoding as a Discrete Optimization Problem === | === Encoding as a Discrete Optimization Problem === | ||
| Line 37: | Line 39: | ||
| - we have to model the timeline; every moment requires a corresponding variables to store the state and action; | - we have to model the timeline; every moment requires a corresponding variables to store the state and action; | ||
| - | - the timeline has to be finite; we don't know in advance what is the length of the plan but in dicreet optimization we have to specify fixed amount of variables. Therefore we often create redundant variables, making timeline "long enough". | + | - the timeline has to be finite; we don't know in advance what is the length of the plan but in discrete optimization we have to specify fixed amount of variables. Therefore we often create redundant variables, making timeline "long enough". |
| == Assignments == | == Assignments == | ||
| Line 47: | Line 49: | ||
| - increase maximal length of the plan --- what influence it has on the solution? | - increase maximal length of the plan --- what influence it has on the solution? | ||
| - change the domain of the last step (''end'') from ''int'' to something more constrained | - change the domain of the last step (''end'') from ''int'' to something more constrained | ||
| - | - change constraint defining the state transitions, so the transitions won't occur after the time stated in the ''end'' variable gdy indeks czasowy stanu nie przekracza wartości nowej zmiennej ''end'' | + | - change constraint defining the state transitions, so the transitions won't occur after the time stated in the ''end'' variable ' |
| - | - use search annotations, so the solver would start search with the smallest''end'' possible and increase it later | + | - use search annotations, so the solver would start search with the smallest ''end'' possible and increase it later |
| - fix the ''output'' to display only relevant states | - fix the ''output'' to display only relevant states | ||
| Line 68: | Line 70: | ||
| - Find fact ''F'', which is true in ''G'' and false in the current state. | - Find fact ''F'', which is true in ''G'' and false in the current state. | ||
| - Find action ''A'', which has ''F'' on the list of the added facts. | - Find action ''A'', which has ''F'' on the list of the added facts. | ||
| - | - Call recursively planning routine to find plan P that goes to state, that satisfies the conditions of ''A'' | + | - Remove ''A'' from the list of available actions (why?). |
| + | - Call recursively planning routine to find plan P that goes to state, that satisfies the conditions of ''A''. | ||
| + | - Reintroduce ''A'' to the list of available actions. | ||
| - Push elements of ''P'' and ''A'' on stack | - Push elements of ''P'' and ''A'' on stack | ||
| - Execute the plan and then action ''A'' to update the current state. | - Execute the plan and then action ''A'' to update the current state. | ||
| Line 74: | Line 78: | ||
| The algorithm's result will be a reversed plan. | The algorithm's result will be a reversed plan. | ||
| - | 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. | ||
| - | == Zadania == | + | == Assignments == |
| + | {{ :en:dydaktyka:planning:dont-panic.jpg?nolink&200|}} | ||
| - | - 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: | + | - Check [[ https://swish.swi-prolog.org/p/block_strips_player_v2.pl |a simple STRIPS planner for the blocks worlds]]. If you know Prolog, read the last lines of the file to understand how the planner works. If you haven't seen Prolog before, don't panic, keep calm and go to the next assignments. |
| - | - 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)'' | + | |
| - | - ''on/2'' --- dany klocek leży na drugim klocku, np. ''on(a,b)'' | + | |
| - | - ''clear/1'' --- na danym klocku nic nie leży, np. ''clear(a)'' | + | |
| - | - ''holding/1'' --- dany klocek został właśnie podniesiony, np. ''holding(a)'' | + | |
| - | - ''handempty/0'' --- żaden klocek nie jest aktualnie podniesiony, czyli: ''handempty'' | + | |
| - | - potrzebne są cztery rodzaje akcji (jedna z nich już jest zaimplementowana) | + | |
| - | - połóż klocek ''X'' na klocku ''Y'': wykonalna, o ile klocek ''X'' jest aktualnie trzymany, a ''Y'' jest czysty. Po wykonaniu akcji klocek ''X'' leży na klocku ''Y'' i jest czysty, klocek ''Y'' przestaje być czysty i żaden klocek nie jest aktualnie podniesiony. | + | |
| - | - zdejmij klocek ''X'' z klocka ''Y'': wykonalna, o ile klocek ''X'' jest czysty i aktualnie leży na klocku ''Y''. Po wykonaniu akcji klocek ''X'' przestaje być czysty, przestaje leżeć na klocku ''Y'' i zostaje podniesiony. Klocek ''Y'' natomiast staje się czysty. | + | |
| - | - połóż klocek ''X'' na stole: analogicznie do akcji pierwszej z taką różnicą, że nie ma wymagań i zmian względem ''Y'' | + | |
| - | - zdejmij klocek ''X'' ze stołu: analogicznie do akcji drugiej | + | |
| - | - Proszę uruchomić planowanie dla trzech załączonych przykładów oraz dla jednej zamodelowanego samodzielnie. | + | |
| - | - Proszę usunąć z części warunkowej akcji wszystkie warunki o postaci ''clear/1'' i ponownie uruchomić planowanie dla czterech przypadków. | + | |
| - | - jaką wartość mają tak wygenerowane plany? | + | |
| - | - przeczytać pobieżnie [[http://en.wikipedia.org/wiki/Relaxation_%28approximation%29|stronę wikipedii na temat relaksacji]]. | + | |
| + | - Fill ''%TODO:'' sections: | ||
| + | - every state is represented by five types of facts (example states are available in the ''EXAMPLES OF USAGE''): | ||
| + | - ''ontable/1'' --- block lies on a table, e.g. ''ontable(a)'' means that block ''a'' lies on a table | ||
| + | - ''on/2'' --- block lies on another block, e.g. ''on(a,b)'' | ||
| + | - ''clear/1'' --- there is nothing lying on the block, e.g. ''clear(a)'' | ||
| + | - ''holding/1'' --- block is currentle held by the robotic arm, e.g.. ''holding(a)'' | ||
| + | - ''handempty/0'' --- the robotic arm doesn't hold anything, e.g. ''handempty'' | ||
| + | - we need four actions (one of them is already implemented) | ||
| + | - put block ''X'' on block ''Y'': | ||
| + | - requires that the ''X'' is actually held in the robotic arm and ''Y'' is clear. After performing the action ''X'' lies on the ''Y'' and ''Y'' is no clear anymore. Also the robotic arm doesn't hold anything. | ||
| + | - take block ''X'' off the ''Y'': | ||
| + | - requires that ''X'' is clear and lies on the ''Y''. After performing the action, block ''X'' is no clear anymore; it doesn't lie on the ''Y'' anymore and it is held in the arm. Also ''Y'' becomes clear. | ||
| + | - put block ''X'' on the table: | ||
| + | - simpler version of the first action | ||
| + | - take ''X'' of the table: | ||
| + | - simpler version of the seciond action | ||
| + | - Run planning on the three already specified problems (just write ''problem1.'' or ''problem2.''... in the query window on the right and hit ''run''. | ||
| + | - Specify fourth custom problem. | ||
| + | - Remove ''clear'' conditions from every action and repeat the planning: | ||
| + | - is there any value in such plans? | ||
| + | - read about [[http://en.wikipedia.org/wiki/Relaxation_%28approximation%29|the relaxation]]. | ||
