This is an old revision of the document!
Automated Planning
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:
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)
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.
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.
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.
Blocks World
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:
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)
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.
Solutions
There are three relatively simple solutions to this problem:
A-star
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
Please define admissible heuristics for the blocks world
Encoding as a Discrete Optimization Problem
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:
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”.
Assignments
-
the blocks worlds defined in the model is simplified. Can you find the differences between model and the problem stated before?
which constraint defines state transitions?
please introduce following changes to the model:
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 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
use search annotations, so the solver would start search with the smallestend
possible and increase it later
fix the output
to display only relevant states
Planner
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:
The simple planner may work according to the crude algorithm (G
is the goal state, and S
is the initial state):
Initiate stack to store the plan.
Check if the current state is equal to G
. If yes, display the plan and exit.
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.
Call recursively planning routine to find plan P that goes to state, that satisfies the conditions of A
Push elements of P
and A
on stack
Execute the plan and then action A
to update the current state.
Restart the planning routine from the new state.
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
Należy pobrać
kod programu planującego i otworzyć go w edytorze tekstu lub
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:
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?
-