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:

1. 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)
2. Uncertainty resulting from unreliability of actions. In this case we are not sure if used action will succeed. A simple model is a RPG game, where a roll of dice decides the success of an action. A plan of a battle should take into account the possibility of unsuccessful roll.
3. Execution of an action takes time. The plan should take into account the temporal aspect of the problem. Our environment rarely stays static and friendly.
4. Possibility of events independent from the agent – i.e.: a car crush in front of an automated car. Handling of such exceptions also comes within the scope of planning.

In view of its basic character, this class will cover the difficult question of classical planning.

An old and popular problem of classical planning is so called “blocks world”. The problem doesn’t seem very ambitious: it consists in finding a correct sequence of moves enabling shifting blocks from initial stage to a given goal state. There is a specified number of blocks in “blocks world” (traditionally, a block can be distinguished by letter written on it), and several columns, where the blocks can be positioned. Every block either lies on the bottom of a column (“on the table”), or is put on the top of another block. An example of initial and goal state is given in the above picture. There are two possible actions in the blocks world:

1. Picking a block up by a robot. This action can be executed if the block is accessible (there are no others blocks on its top) and the robot’s arm is empty (only one block can be picked up at a time)
2. Putting a block down by a robot. This action can be executed if the robot’s arm is not empty. A block can only be put on the top of a column.

There are three relatively simple solutions to this 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.

1. Please define admissible heuristics for the blocks world

Very often it is possible to translate a planning problem to a corresponding discrete optimization problem and then use discrete optimization techniques, e.g. constraint programming. This kind of translation is however limited:

1. we have to model the timeline; every moment requires a corresponding variables to store the state and action;
2. 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”.

1. please download the blocks world model:
   1. the blocks worlds defined in the model is simplified. Can you find the differences between model and the problem stated before?
   2. which constraint defines state transitions?
   3. please introduce following changes to the model:
      1. increase maximal length of the plan — what influence it has on the solution?
      2. change the domain of the last step (end) from int to something more constrained
      3. 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
      4. use search annotations, so the solver would start search with the smallestend possible and increase it later
      5. fix the output to display only relevant states

Other (the simplest) approach is to use an existing planning software. In the 70' Stanford has introduced the famous STRIPS solver. It's a bit old but the knowledge representation used there is still relevant and is often called a STRIPS representation. The STRIPS problem is represented as:

• state which consists of facts which are true at the specific model
  • fact is a simple logical statement, e.g. block A is lying on the table.
• list of available actions; every action is defined by four elements:
  • name of the action and arguments it takes
  • conditions: list of facts that have to be true before action is performed
  • added facts: list of facts that become true after performing the action
  • removed facts: list of facts that become false after performing the action

The simple planner may work according to the crude algorithm (G is the goal state, and S is the initial state):

1. Initiate stack to store the plan.
2. Check if the current state is equal to G. If yes, display the plan and exit.
3. Find fact F, which is true in G and false in the current state.
4. Find action A, which has F on the list of the added facts.
5. Remove A from the list of available actions (why?).
6. Call recursively planning routine to find plan P that goes to state, that satisfies the conditions of A.
7. Reintroduce A to the list of available actions.
8. Push elements of P and A on stack
9. Execute the plan and then action A to update the current state.
10. Restart the planning routine from the new state.

The algorithm's result will be a reversed plan.

1. Download a simple STRIPS planner for the blocks worlds and edit it in an on-line prolog IDE. If you know Prolog, read the last lines of the file a to understand, how the planner works. If you haven't seen Prolog before, don't panic.

1. Następnie należy uzupełnić go o informacje potrzebne do rozwiązania problemu bloków (sekcje %TODO:). Objaśnienia:
   1. 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):
      1. ontable/1 — dany klocek leży na stole, np. ontable(a)
      2. on/2 — dany klocek leży na drugim klocku, np. on(a,b)
      3. clear/1 — na danym klocku nic nie leży, np. clear(a)
      4. holding/1 — dany klocek został właśnie podniesiony, np. holding(a)
      5. handempty/0 — żaden klocek nie jest aktualnie podniesiony, czyli: handempty
   2. potrzebne są cztery rodzaje akcji (jedna z nich już jest zaimplementowana)
      1. 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.
      2. 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.
      3. połóż klocek X na stole: analogicznie do akcji pierwszej z taką różnicą, że nie ma wymagań i zmian względem Y
      4. zdejmij klocek X ze stołu: analogicznie do akcji drugiej
2. Proszę uruchomić planowanie dla trzech załączonych przykładów oraz dla jednej zamodelowanego samodzielnie.
3. Proszę usunąć z części warunkowej akcji wszystkie warunki o postaci clear/1 i ponownie uruchomić planowanie dla czterech przypadków.
   1. jaką wartość mają tak wygenerowane plany?
   2. przeczytać pobieżnie stronę wikipedii na temat relaksacji.