This notebook describes the planning.jl module, which covers Chapters 10 (Classical Planning) and 11 (Planning and Acting in the Real World) of Artificial Intelligence: A Modern Approach.
We'll start by looking at PDDL and Action data types for defining problems and actions. Then, we will see how to use them by trying to plan a trip from Sibiu to Bucharest across the familiar map of Romania.
The first step is to load the code:
In [1]:
include("aimajulia.jl");
using aimajulia;
To be able to model a planning problem properly, it is essential to be able to represent an Action. Each action we model requires at least three things:
Planning actions have been modelled using Action. It is interesting to see the way preconditions and effects are represented here. Instead of just being a list of expressions each, they consist of two arrays - precond_pos and precond_neg. This is to work around the fact that PDDL doesn't allow for negations. Thus, for each precondition, we maintain a seperate list of those preconditions that must hold true, and those whose negations must hold true. Similarly, instead of having a single array of expressions that are the result of executing an action, we have two. The first (effect_add) contains all the expressions that will evaluate to true if the action is executed, and the the second (effect_neg) contains all those expressions that would be false if the action is executed (ie. their negations would be true).
The constructor parameters, however combine the two precondition arrays into a single precond parameter, and the effect arrays into a single effect parameter.
PDDL is used to represent planning problems in this module. The following attributes are essential to be able to define a problem:
Now lets try to define a planning problem. Since we already know about the map of Romania, lets see if we can plan a trip across a simplified map of Romania.
Here is our simplified map definition:
In [2]:
knowledge_base = [
expr("Connected(Bucharest,Pitesti)"),
expr("Connected(Pitesti,Rimnicu)"),
expr("Connected(Rimnicu,Sibiu)"),
expr("Connected(Sibiu,Fagaras)"),
expr("Connected(Fagaras,Bucharest)"),
expr("Connected(Pitesti,Craiova)"),
expr("Connected(Craiova,Rimnicu)"),
];
Let us add some logic propositions to complete our knowledge about travelling around the map. These are the typical symmetry and transitivity properties of connections on a map. We can now be sure that our knowledge_base understands what it truly means for two locations to be connected in the sense usually meant by humans when we use the term.
Let's also add our starting location - Sibiu to the map.
In [3]:
for element in [
expr("Connected(x,y) ==> Connected(y,x)"),
expr("Connected(x,y) & Connected(y,z) ==> Connected(x,z)"),
expr("At(Sibiu)")
]
push!(knowledge_base, element);
end
knowledge_base
Out[3]:
We now define possible actions to our problem. We know that we can drive between any connected places. But, as is evident from this list of Romanian airports, we can also fly directly between Sibiu, Bucharest, and Craiova.
We can define these flight actions like this:
In [4]:
# Sibiu to Bucharest
precond_pos = [expr("ft(Sibiu)")];
precond_neg = [];
effect_add = [expr("At(Bucharest)")];
effect_rem = [expr("At(Sibiu)")];
fly_s_b = PlanningAction(expr("Fly(Sibiu, Bucharest)"), (precond_pos, precond_neg), (effect_add, effect_rem));
# Bucharest to Sibiu
precond_pos = [expr("At(Bucharest)")];
precond_neg = [];
effect_add = [expr("At(Sibiu)")];
effect_rem = [expr("At(Bucharest)")];
fly_b_s = PlanningAction(expr("Fly(Bucharest, Sibiu)"), (precond_pos, precond_neg), (effect_add, effect_rem));
# Sibiu to Craiova
precond_pos = [expr("At(Sibiu)")];
precond_neg = [];
effect_add = [expr("At(Craiova)")];
effect_rem = [expr("At(Sibiu)")];
fly_s_c = PlanningAction(expr("Fly(Sibiu, Craiova)"), (precond_pos, precond_neg), (effect_add, effect_rem));
# Craiova to Sibiu
precond_pos = [expr("At(Craiova)")];
precond_neg = [];
effect_add = [expr("At(Sibiu)")];
effect_rem = [expr("At(Craiova)")];
fly_c_s = PlanningAction(expr("Fly(Craiova, Sibiu)"), (precond_pos, precond_neg), (effect_add, effect_rem));
# Bucharest to Craiova
precond_pos = [expr("At(Bucharest)")];
precond_neg = [];
effect_add = [expr("At(Craiova)")];
effect_rem = [expr("At(Bucharest)")];
fly_b_c = PlanningAction(expr("Fly(Bucharest, Craiova)"), (precond_pos, precond_neg), (effect_add, effect_rem));
# Craiova to Bucharest
precond_pos = [expr("At(Craiova)")];
precond_neg = [];
effect_add = [expr("At(Bucharest)")];
effect_rem = [expr("At(Craiova)")];
fly_c_b = PlanningAction(expr("Fly(Craiova, Bucharest)"), (precond_pos, precond_neg), (effect_add, effect_rem));
And the drive actions like this.
In [5]:
# Drive
precond_pos = [expr("At(x)")];
precond_neg = [];
effect_add = [expr("At(y)")];
effect_rem = [expr("At(x)")];
drive = PlanningAction(expr("Drive(x, y)"), (precond_pos, precond_neg), (effect_add, effect_rem));
Finally, we can define a a function that will tell us when we have reached our destination, Bucharest.
In [6]:
function goal_text(kb::PDDL)
return ask(kb, expr("At(Bucharest)"));
end
Out[6]:
Thus, with all the components in place, we can define the planning problem.
In [7]:
prob = PDDL(knowledge_base, [fly_s_b, fly_b_s, fly_s_c, fly_c_s, fly_b_c, fly_c_b, drive], goal_test)
Out[7]: