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