Due to the COVID-19 outbreak, all files related to this class are stored in the Gitlab repository. This class uses files stored in the 00_intro
folder. Please refer to the Readme.md
on how to submit the solutions.
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:
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:
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.
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:
end
) from int
to something more constrainedend
variable 'end
possible and increase it lateroutput
to display only relevant statesOther (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:
block A is lying on the table
.
The simple planner may work according to the crude algorithm (G
is the goal state, and S
is the initial state):
G
. If yes, display the plan and exit.F
, which is true in G
and false in the current state.A
, which has F
on the list of the added facts.A
from the list of available actions (why?).A
. A
to the list of available actions.P
and A
on stack A
to update the current state.The algorithm's result will be a reversed plan.
%TODO:
sections:EXAMPLES OF USAGE
):ontable/1
— block lies on a table, e.g. ontable(a)
means that block a
lies on a tableon/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
X
on block Y
: 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.X
off the Y
: 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.X
on the table: X
of the table:problem1.
or problem2.
… in the query window on the right and hit run
.clear
conditions from every action and repeat the planning: