I wonder, is it possible to do planning in Prolog using the knowledge base modified by retract and assert during the runtime?
My idea is as follows: assume that I need to replace a flat tire of a car. I can either put something on the ground or move something from the ground to some free place.
So I came up with such a code:
at(flat, axle).
at(spare, trunk).
free(Where) :- at(_, Where), !, fail.
remove(What) :- at(What, _), retract(at(What, _)), assert(at(What, ground)).
put_on(What, Where) :- at(What, _), free(Where), retract(at(What, _)), assert(at(What, Where)).
(I am a rookie in Prolog so maybe that it is even wrong, if so, please advise me how to correct it.)
The idea is: I have a flat tire on the axle and a spare one in the trunk. I can remove a thing X if X is somewhere and to remove it, I remove the fact specifying where it is and add a fact that it is on the ground. Similarly, I can put a thing X to location Y if X is somewhere and Y is free and to do so, I remove X from where it is and add the fact that X is at Y.
And now I am stuck: I have no idea how to use this code now, since at(spare, axle)
just says nope, even with tracing.
So the question: can such an approach be used and if so, how?
I hope it makes sense.
Using the example code from "Artificial Intelligence - Structures and Strategies for Complex Problem Solving" by George F Luger (WorldCat)
%%%
%%% This is one of the example programs from the textbook:
%%%
%%% Artificial Intelligence:
%%% Structures and strategies for complex problem solving
%%%
%%% by George F. Luger and William A. Stubblefield
%%%
%%% Corrections by Christopher E. Davis (chris2d@cs.unm.edu)
%%%
%%% These programs are copyrighted by Benjamin/Cummings Publishers.
%%%
%%% We offer them for use, free of charge, for educational purposes only.
%%%
%%% Disclaimer: These programs are provided with no warranty whatsoever as to
%%% their correctness, reliability, or any other property. We have written
%%% them for specific educational purposes, and have made no effort
%%% to produce commercial quality computer programs. Please do not expect
%%% more of them then we have intended.
%%%
%%% This code has been tested with SWI-Prolog (Multi-threaded, Version 5.2.13)
%%% and appears to function as intended.
%%%%%%%%%%%%%%%%%%%% stack operations %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% These predicates give a simple, list based implementation of stacks
% empty stack generates/tests an empty stack
member(X,[X|_]).
member(X,[_|T]):-member(X,T).
empty_stack([]).
% member_stack tests if an element is a member of a stack
member_stack(E, S) :- member(E, S).
% stack performs the push, pop and peek operations
% to push an element onto the stack
% ?- stack(a, [b,c,d], S).
% S = [a,b,c,d]
% To pop an element from the stack
% ?- stack(Top, Rest, [a,b,c]).
% Top = a, Rest = [b,c]
% To peek at the top element on the stack
% ?- stack(Top, _, [a,b,c]).
% Top = a
stack(E, S, [E|S]).
%%%%%%%%%%%%%%%%%%%% queue operations %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% These predicates give a simple, list based implementation of
% FIFO queues
% empty queue generates/tests an empty queue
empty_queue([]).
% member_queue tests if an element is a member of a queue
member_queue(E, S) :- member(E, S).
% add_to_queue adds a new element to the back of the queue
add_to_queue(E, [], [E]).
add_to_queue(E, [H|T], [H|Tnew]) :- add_to_queue(E, T, Tnew).
% remove_from_queue removes the next element from the queue
% Note that it can also be used to examine that element
% without removing it
remove_from_queue(E, [E|T], T).
append_queue(First, Second, Concatenation) :-
append(First, Second, Concatenation).
%%%%%%%%%%%%%%%%%%%% set operations %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% These predicates give a simple,
% list based implementation of sets
% empty_set tests/generates an empty set.
empty_set([]).
member_set(E, S) :- member(E, S).
% add_to_set adds a new member to a set, allowing each element
% to appear only once
add_to_set(X, S, S) :- member(X, S), !.
add_to_set(X, S, [X|S]).
remove_from_set(_, [], []).
remove_from_set(E, [E|T], T) :- !.
remove_from_set(E, [H|T], [H|T_new]) :-
remove_from_set(E, T, T_new), !.
union([], S, S).
union([H|T], S, S_new) :-
union(T, S, S2),
add_to_set(H, S2, S_new).
intersection([], _, []).
intersection([H|T], S, [H|S_new]) :-
member_set(H, S),
intersection(T, S, S_new),!.
intersection([_|T], S, S_new) :-
intersection(T, S, S_new),!.
set_diff([], _, []).
set_diff([H|T], S, T_new) :-
member_set(H, S),
set_diff(T, S, T_new),!.
set_diff([H|T], S, [H|T_new]) :-
set_diff(T, S, T_new), !.
subset([], _).
subset([H|T], S) :-
member_set(H, S),
subset(T, S).
equal_set(S1, S2) :-
subset(S1, S2), subset(S2, S1).
%%%%%%%%%%%%%%%%%%%%%%% priority queue operations %%%%%%%%%%%%%%%%%%%
% These predicates provide a simple list based implementation
% of a priority queue.
% They assume a definition of precedes for the objects being handled
empty_sort_queue([]).
member_sort_queue(E, S) :- member(E, S).
insert_sort_queue(State, [], [State]).
insert_sort_queue(State, [H | T], [State, H | T]) :-
precedes(State, H).
insert_sort_queue(State, [H|T], [H | T_new]) :-
insert_sort_queue(State, T, T_new).
remove_sort_queue(First, [First|Rest], Rest).
%%%%%%%%% Simple Prolog Planner %%%%%%%%
%%%
%%% This is one of the example programs from the textbook:
%%%
%%% Artificial Intelligence:
%%% Structures and strategies for complex problem solving
%%%
%%% by George F. Luger and William A. Stubblefield
%%%
%%% Corrections by Christopher E. Davis (chris2d@cs.unm.edu)
%%%
%%% These programs are copyrighted by Benjamin/Cummings Publishers.
%%%
%%% We offer them for use, free of charge, for educational purposes only.
%%%
%%% Disclaimer: These programs are provided with no warranty whatsoever as to
%%% their correctness, reliability, or any other property. We have written
%%% them for specific educational purposes, and have made no effort
%%% to produce commercial quality computer programs. Please do not expect
%%% more of them then we have intended.
%%%
%%% This code has been tested with SWI-Prolog (Multi-threaded, Version 5.2.13)
%%% and appears to function as intended.
:- [adts].
plan(State, Goal, _, Moves) :- equal_set(State, Goal),
write('moves are'), nl,
reverse_print_stack(Moves).
plan(State, Goal, Been_list, Moves) :-
move(Name, Preconditions, Actions),
conditions_met(Preconditions, State),
change_state(State, Actions, Child_state),
not(member_state(Child_state, Been_list)),
stack(Child_state, Been_list, New_been_list),
stack(Name, Moves, New_moves),
plan(Child_state, Goal, New_been_list, New_moves),!.
change_state(S, [], S).
change_state(S, [add(P)|T], S_new) :- change_state(S, T, S2),
add_to_set(P, S2, S_new), !.
change_state(S, [del(P)|T], S_new) :- change_state(S, T, S2),
remove_from_set(P, S2, S_new), !.
conditions_met(P, S) :- subset(P, S).
member_state(S, [H|_]) :- equal_set(S, H).
member_state(S, [_|T]) :- member_state(S, T).
reverse_print_stack(S) :- empty_stack(S).
reverse_print_stack(S) :- stack(E, Rest, S),
reverse_print_stack(Rest),
write(E), nl.
/* sample moves */
move(pickup(X), [handempty, clear(X), on(X, Y)],
[del(handempty), del(clear(X)), del(on(X, Y)),
add(clear(Y)), add(holding(X))]).
move(pickup(X), [handempty, clear(X), ontable(X)],
[del(handempty), del(clear(X)), del(ontable(X)),
add(holding(X))]).
move(putdown(X), [holding(X)],
[del(holding(X)), add(ontable(X)), add(clear(X)),
add(handempty)]).
move(stack(X, Y), [holding(X), clear(Y)],
[del(holding(X)), del(clear(Y)), add(handempty), add(on(X, Y)),
add(clear(X))]).
go(S, G) :- plan(S, G, [S], []).
test :- go([handempty, ontable(b), ontable(c), on(a, b), clear(c), clear(a)],
[handempty, ontable(c), on(a,b), on(b, c), clear(a)]).
Most of the code stays the same, the only changes needed to solve your question are the predicates move/3
and the query test
. Either comment out or remove the predicates move/3
and test/0
from the above code before adding predicates to solve your question.
Below is all of the new predicates needed, move/3
and test/0
. The first move/3
is shown and the remainder need to be revealed (click Reveal spoiler
) so that you can see them if needed but you should try to do them yourself.
move(take_from_trunk(X), [hand(empty), trunk(X)],
[del(hand(empty)), del(trunk(X)),
add(hand(X)), add(trunk(empty))]).
The state keeps track of four locations, hand
, ground
, axle
, and trunk
, and three values, flat
, spare
, and empty
for the locations. The predicate move/3
also makes uses of variables so that they are not fixed in what they can do.
The move/3
predicate has 3 parameters.
take_from_trunk(spare)
.state
for the move to be applied.assert
and retract
. The changes are very simple, you remove some of the properties of state, e.g. del(hand(empty))
and add some, e.g. add(hand(X))
. For your given problem, this solution is simple in that for each change, for every del
there is a matching add
.The query:
test :- go([hand(empty), trunk(spare), axle(flat), ground(empty)],
[hand(empty), trunk(flat), axle(spare), ground(empty)]).
Example run:
?- test.
moves are
take_from_trunk(spare)
place_on_ground(spare)
take_off_axle(flat)
place_in_trunk(flat)
pickup_from_ground(spare)
place_on_axle(spare)
true.
Other move/3
predicates needed. Try to do this on your own.
move(take_off_axle(X), [hand(empty), axle(X)],
[del(hand(empty)), del(axle(X)),
add(hand(X)), add(axle(empty))]).
move(place_on_ground(X), [hand(X), ground(empty)],
[del(hand(X)), del(ground(empty)),
add(hand(empty)), add(ground(X))]).
move(pickup_from_ground(X), [hand(empty), ground(X)],
[del(hand(empty)), del(ground(X)),
add(hand(X)), add(ground(empty))]).
move(place_on_axle(X), [hand(X), axle(empty)],
[del(hand(X)), del(axle(empty)),
add(hand(empty)), add(axle(X))]).
move(place_in_trunk(X), [hand(X), trunk(empty)],
[del(hand(X)), del(trunk(empty)),
add(hand(empty)), add(trunk(X))]).
In writing these predicates some of move/3
were not working as I expected so I created simple test queries for each to check them.
Using the test also helped me to change what was in state
and how it was represented, e.g, instead of handempty
and holding(X)
it was changed to hand(empty)
and hand(X)
which was easier to understand, follow, and check for consistency of the code, but most likely made the code more inefficient.
test_01 :- go([hand(empty), trunk(spare), axle(flat), ground(empty)],
[hand(spare), trunk(empty), axle(flat), ground(empty)]).
test_02 :- go([hand(empty), trunk(spare), axle(flat), ground(empty)],
[hand(flat), trunk(spare), axle(empty), ground(empty)]).
test_03 :- go([hand(flat), trunk(spare), axle(empty), ground(empty)],
[hand(empty), trunk(spare), axle(empty), ground(flat)]).
test_04 :- go([hand(empty), trunk(spare), axle(empty), ground(flat)],
[hand(flat), trunk(spare), axle(empty), ground(empty)]).
test_05 :- go([hand(spare), trunk(empty), axle(empty), ground(flat)],
[hand(empty), trunk(empty), axle(spare), ground(flat)]).
test_06 :- go([hand(flat), trunk(empty), axle(spare), ground(empty)],
[hand(empty), trunk(flat), axle(spare), ground(empty)]).
Some of these test work as expected using just one move, while others return many moves. I did not modify the move/3
here so that only one move/3
is considered, but they can be modified if you so choose. Think guard statements or constraints.
The other reason the test results are listed here is to show that some of the moves are not picked in the way you would think, or intended and don't work exactly as you would expect, but yet the query to the posted question works as expected. So if you write test cases and they return something like this, don't assume your move/3
is invalid, or has bugs, they may not. When you get all of the move/3
and the final query working as expected, then go back and try to understand why these multiple moves are happening, and then modify them if you desire.
?- test_01.
moves are
take_from_trunk(spare)
true.
?- test_02.
moves are
take_from_trunk(spare)
place_on_ground(spare)
take_off_axle(flat)
place_in_trunk(flat)
pickup_from_ground(spare)
place_on_axle(spare)
take_from_trunk(flat)
place_on_ground(flat)
take_off_axle(spare)
place_in_trunk(spare)
pickup_from_ground(flat)
true.
?- test_03.
moves are
place_on_ground(flat)
true.
?- test_04.
moves are
take_from_trunk(spare)
place_on_axle(spare)
pickup_from_ground(flat)
place_in_trunk(flat)
take_off_axle(spare)
place_on_ground(spare)
take_from_trunk(flat)
place_on_axle(flat)
pickup_from_ground(spare)
place_in_trunk(spare)
take_off_axle(flat)
true.
?- test_05.
moves are
place_on_axle(spare)
true.
?- test_06.
moves are
place_on_ground(flat)
take_off_axle(spare)
place_in_trunk(spare)
pickup_from_ground(flat)
place_on_axle(flat)
take_from_trunk(spare)
place_on_ground(spare)
take_off_axle(flat)
place_in_trunk(flat)
pickup_from_ground(spare)
place_on_axle(spare)
true.