Final Project in AI Programming

Laboratory Exercise 10


PLANNING

with Prolog

by Margit Lang


[Problem | Motivation | Description | Schedule | Domains | Actions |PlannerSource-Code | Further Readings]


Problem:

        I am very interested in Robotics. One thing a robot must be able to do is planning. It needs to plan its actions such as
        moves and anything else the robot should do.

        So I want to implement a planning agent for things a robot might have to do.



Motivation:

        I worked on a planner once in an other course, but it never worked right. I want to start this project again, and write
        a better working planner. And maybe I can use this planner for a real robot later on.

        The reason why I choose Prolog for this project is, I think it is more comfortable to write such programs, and I have
        more experience with Prolog than LISP.



Description:

        First I want to write a planner for the block world. So I will have to design some mini worlds, where my robot will have
        to work in. And I will have to find an appropriate data and knowledge representation. When this small planner works,
        I want to add some other actions. So my robot will be able to do more than just moving blocks.

        My robot will be a sort of housekeeper robot. It will be able to move things from one place to an other, it makes a plan
        how to clean the house and do some other nice things.



Schedule:

        Oct. 25 - Oct. 29:       Project Specification
        Oct. 30 - Nov.  05:      Search for Domains, and Readings
        Nov. 06 - Nov. 12:     Definition of actions and state descriptions
        Nov. 13 - Nov. 19:     Design of Planner
        Nov. 20 - Nov. 28:     ThanksGiving Break
        Nov. 29 - Dec. 03:      Planner source code
        Dec. 04 - Dec. 10:      Project Report, Test Report, Presentation



Domains:

        My planner will be a GPS- or STRIPS- like planner. Each action has a name, an add list, a can list and a del list.
        The can list contains all preconditions for the action. The add list contains all the new things, which have to be added to
        the world state after proceeding an action. And the del list lists everything that is not true anymore after an action was
        performed.

        Following a few domain attributes of my planner:

        for the blocks world:
                static information:

                        block(X) -> X is a block
                        slot(X) -> X is a slot

                 dynamic information:
                        on(X,Y) -> thing X is on thing Y
                        clear(X) -> there is nothing on thing X

                Initialstate =[on(a,a1),on(b,a),clear(b),clear(a2),on(c,a3),clear(c)].

           for the house
 

% static world description:

% room(X)-> X is a room.
% door(X,Y) -> there is a door between X and Y
% connected(X,Y) -> X and Y are connected rooms
% container(X) -> X is a container

% dynamic attributes
% at(X) -> the robot is currently in the room X
% in(X,Y) -> Thing X is in room Y
% have(X) ->the robot is holding thing X
% open(X,Y) -> door between room X and room Y is open
% closed(X,Y) -> door(X,Y) is closed
% dusty_floor(X) -> the floor in room(X) is dusty
% clean_floor(X) -> the floor in room(X) is clean
% full(X) -> container(X) is full
% empty(X) -> container X is empty

%Initialstate =[dusty_floor(bathroom), in(vacuum,bedroom), empty(vacuum), closed(kitchen,livingroom), closed(livingroom,kitchen),
                             closed(livingroom,bathroom), closed(bathroom,livingroom), closed(livingroom,bedroom),closed(bedroom,livingroom),
                             at(bedroom)]

%Goal1=[at(kitchen)]
%Goal2=[clean_floor(bathroom)]



Actions:

        These are some of the actions I implemented for the project. The whole bunch

For the Blocksworld:

% move(What,From,To) :- moves What from the place From to To
     can(move(What,From,To), [on(What,From), clear(What), clear(To)]):- block(What),
                       What\= =From,
                       What\= =To,
                       From\= =To.
     add(move(What,From,To),[on(What,To),clear(From)]):- From\= = To,From \= = What,What\= = To.
     del(move(What,From,To),[on(What,From), clear(To)]):- From\= = To,From \= = What,What\= = To.
For the housekeeping:
%  go(From,To) :- the robot goes from From to To
         can(go(From,To),[at(From),open(From,To)]):- connected(From,To).
         add(go(From,To),[at(To)]).
         del(go(From,To),[at(From)]).

%  pick_up(What):- picks What up
         can(pick_up(What),[in(What,Where), at(Where)]):-room(Where).
         add(pick_up(What),[have(What)]).
         del(pick_up(What),[in(What,Where)]).

% open_door(From,To):- the robot opens the door between room From and room To
         can(open_door(From,To),[at(From),closed(From,To)]):- connected(From,To).
         add(open_door(From,To),[open(From,To),open(To,From)]).
         del(open_door(From,To),[closed(From,To),closed(To,From)]).

% close_door(From,To):- the robot closes the door between From and To
         can(close_door(From,To),[at(From),open(From,To)]).
         add(close_door(From,To),[closed(From,To),closed(To,From)]).
         del(close_door(From,To),[open(From,To),open(To,From)]).

% clean_floor(Room) :- robot cleans the floor in Room
         can(clean_floor(Room),[at(Room),have(vacuum),empty(vacuum)]).
         add(clean_floor(Room) ,[clean_floor(Room),full(vacuum)]).
         del(clean_floor(Room) ,[dusty_floor(Room),empty(vacuum)]).

% empty(What):- the robot empties the What
         can(empty(What),[full(What)]):- container(What).
         add(empty(What),[empty(What)]).
         del(empty(What),[full(What)]).


 



Planner Source Code:

The following part contains the whole General Purpose Planner Code (including all helper-functions it needs).
A part of the code is taken from a course I took in Austria.
 

%   plan( State, Goals, Actions, FinalState)

plan( State, Goals, [], State)  :-
  satisfied( State, Goals).

plan( State, Goals, Plan, FinalState)  :-
  conc( PrePlan, [Action | PostPlan], Plan),
  select( State, Goals, Goal),      % Select an unsatisfied goal
  achieves( Action, Goal),
  can( Action, Condition),
  plan( State, Condition, PrePlan, MidState1),
  apply( MidState1, Action, MidState2),
  plan( MidState2, Goals, PostPlan, FinalState).    % Assemble whole plan

satisfied( State, []).

satisfied( State, [Goal | Goals])  :-
  member( Goal, State),
  satisfied( State, Goals).

select( State, Goals, Goal)  :-
  member( Goal, Goals),
  \+ member( Goal, State).

achieves( Action, Goal)  :-
  add( Action, Goals),
  member( Goal, Goals).

apply( State, Action, NewState)  :-
  del( Action, DelList),
  delete( State, DelList, State1), !,
  add( Action, AddList),
  conc( AddList, State1, NewState).

conc( [], L, L).

conc( [X | L1], L2, [X | L3])  :-
  conc( L1, L2, L3).

member(X,[]) :- !, fail.
member(X,[X|_]).
member(X,[_|L]) :- member(X,L).

delete([],_,[]).

delete( [X|L1],L2,Diff)  :-
  member(X,L2),  !,
  delete(L1,L2,Diff).

delete( [X|L1],L2, [X|Diff])  :-
  delete(L1,L2,Diff).

    Download whole project code:
     Textdocument: (Still under construction!) 
 



Further Readings:

    Michael Brady: Robot motion : planning and control

    AIRVL: Artificial Intelligence, Robotic and Vision Laboratory - University of Minnesota
            http://www-users.cs.umn.edu/~research/airvl/

    Prof. Eder Johann: Knowledge Engineering Skriptum, (Course book) University of Klagenfurt, Austria,
                   WinterSemester98/99

    Bratko Ivan: Prolog Programming for Artificial Intelligence, 1986, Addison Wesley
 


Margit Lang --- mlang@edu.uni-klu.ac.at