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 16:38] 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 28: | Line 32: | ||
| == 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 45: | 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 78: | Line 82: | ||
| {{ :en:dydaktyka:planning:dont-panic.jpg?nolink&200|}} | {{ :en:dydaktyka:planning:dont-panic.jpg?nolink&200|}} | ||
| - | - Download {{ :en:dydaktyka:planning:blocks_world_strips.pl |a simple STRIPS planner for the blocks worlds}} and edit it in an [[http://swish.swi-prolog.org/|on-line prolog IDE]]. 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. | + | - 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. |
| - Fill ''%TODO:'' sections: | - Fill ''%TODO:'' sections: | ||
| Line 87: | Line 91: | ||
| - ''holding/1'' --- block is currentle held by the robotic arm, e.g.. ''holding(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'' | - ''handempty/0'' --- the robotic arm doesn't hold anything, e.g. ''handempty'' | ||
| - | - we need four action (one of them is already implemented) | + | - we need four actions (one of them is already implemented) |
| - put block ''X'' on block ''Y'': | - 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. | - 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. | ||
| Line 96: | Line 100: | ||
| - take ''X'' of the table: | - take ''X'' of the table: | ||
| - simpler version of the seciond action | - simpler version of the seciond action | ||
| - | - Run planning on the three already specified problems. | + | - 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. | - Specify fourth custom problem. | ||
| - Remove ''clear'' conditions from every action and repeat the planning: | - Remove ''clear'' conditions from every action and repeat the planning: | ||
