This is a multi-part message in MIME format.
--------------29C62F3B6E7
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Hello,
I am writing because I am a beginner LISP programmer and I have a very
simple problem that I can't seem to finish. I was just wondering if I
could get some assistance or advice.
<···············@cryogen.com>
####
I am trying to implement a forward planner which uses the STRIPS
representation for actions and states.
I have a search algoritm already setup, but I am having trouble getting
my get-neighbors function to work.
Description of Stripping and forward planning attached...
I would really appreciate any help or advice I can get.
Here is what I have so far...
(setf X)
(setf Y)
; Function to determine neighbors of a given node
(defun get-neighbors (State1 Action State2)
(setf i 0)
(setf j 0)
(dotimes (0 3)
(setf X (nth i BLOCKS))
(setf i (+ i 1))
(dotimes (j 3)
(setf Y (nth j BLOCKS))
; (if neighbor - action will work then copy to neighbors
; (if (preconds (nth i ACTIONS)) setf
; This is the hard part...
; neighbors are world2 after given action is applied to world1
(setf j (+ j 1))
)
)
neighbors ; return neighbor list
)
--------------29C62F3B6E7
Content-Type: text/plain; charset=us-ascii; name="n5.2"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="n5.2"
Nov 7
- Planning as Graph Searching
o Initial state
An arbitrary start situation representation, such as a logical
sentence of predicate calculus.
o Goal state
An arbitrary goal situation representation, such as a logical
sentence of predicate calculus.
o Operators
A set of descriptions of actions.
o Plans
A solution is a sequence of actions which lie on the
solution path.
- Basic representation elements for planning
o Representation of states
Initial state - intermediate states - goal state
| | |
given | given
created by
actions
All state representations are complete.
o Representation of actions
Actions are described by programs that generate successor
state descriptions
o Representation of plans
A sequence of actions which constitute the solution path.
6.5 Planning with STRIPS Representation
- The Frame Problem
The general problem of specifying the effects of an action is called
frame problem.
This name comes from considering the frame of a motion
picture film, where there is only a small change from
one frame to another.
Each individual action usually affects only a small number
of relations.
- The STRIPS Representation
o Strips assumption
The STRIPS planning representation is the name given to a logic-based
notation that makes a strong assumption about the effect of actions.
-----------------------------------------------
1. The STRIPS assumption is based on noticing that most things are not
------------------
affected by a single action.
---------------------------
2. The STRIPS states only what predicates are affected by an action
and assumes that all other predicates are unchanged.
In other words, the problem solving mechanism can assume that all relations
remain unchanged unless otherwise specified.
o Representations of actions
For each action:
1. The action description
2. The precondition of the action
preconditions list: those things that need to be true for the action
------------------ to occur;
3. The effect of the action
How the state is changed by the action:
delete list: those primitive relations no longer true after the
----------- action is performed;
add list: the primitive relations made true by the action.
---------
Ex.
Specify action: stack(X,Y)
stack(X,Y):
precondition: holding(X), cleartop(Y)
addlist: on(X,Y), handempty, cleartop(X)
deletelist: holding(X), cleartop(Y)
-Strip Representation for The Block World:
The precondition and effect for each action:
preconds( stack(X, Y), [cleartop(Y), holding(X)] );
preconds( unstack(X, Y), [handempty, cleartop(X), on(X, Y)] );
preconds( pickup(X), [handempty, ontable(X), cleartop(X)] );
preconds( putdwon(X), [holding(X)] );
addlist( stack(X, Y), [handempty, cleartop(X), on(X, Y)] );
addlist( unstack(X, Y), [cleartop(Y), holding(X)] );
addlist( pickup(X), [holding(X)] );
addlist( putdown(X), [handempty, ontable(X), cleartop(X)] );
deletelist( stack(X, Y), [cleartop(Y), holding(X)] );
deletelist( unstack(X, Y), [handempty, cleartop(X), on(X, Y)] );
deletelist( pickup(X), [handempty, ontable(X), cleartop(X)] );
deletelist( putdown(X), [holding(X)] );
Ex.
Initial state:
_|_ [ontable(a),
| | ontable(c),
cleartop(a),
cleartop(b),
b handempty]
a c
------------
|
|
Actions |
|
|
\|/
Goal state:
_|_
| |
[ontable(c),
b on(a,c),
a on(b,a),
c cleartop(b),
----------- handempty]
---------------------------------------------------------------
[on(b,c), (1)
_|_ ontable(a), (2)
| | ontable(c), (3)
cleartop(a), (4)
cleartop(b), (5)
b handempty] (6)
a c
----------- [1,2,3,4,5,6]
| [1,5,6]
_|_ unstack(b,c)
| b | | -[1,5,6]
| +[holding(b) (7), cleartop(c) (8)]
a c
----------- [2,3,4,7,8]
| [7]
_|_ putdwon(b)
| | | -[7]
| +[5,6,ontable(b) (9)]
a c b
------------ [2,3,4,8,5,6,9]
| [2,4,6]
_|_ pickup(a)
| a | | -[2,4,6]
| +[holding(a) (10)]
c b
------------ [3,8,5,8,9,10]
| [8,10]
_|_ stack(a,c)
| | | -[8,10]
a | +[4,6,on(a,c) (11)]
c b
------------ [3,4,5,6,9,11]
| [5,6,9]
_|_ pickup(b)
| b | | -[5,6,9]
a | +[7]
c
------------ [3,4,7,11]
_|_
| | | [4,5,7]
pickup(b)
b | -[4,5,7]
a | +[on(b,a) (12),5,6]
c
----------- [3,5,6,11,12]
[ontable(c), (3)
cleartop(b), (5)
handempty, (6)
on(a,c), (11)
on(b,a)] (12)
- The input of system:
an initial world description,
a goal description.
- The Planning Operation:
The problem solver's (planner) task is to find a sequence of
actions (plan) that will transform the initial world into one
in which the goal description is true.
- Define Neighbors:
Each node contains a state, actions that lead to this state,
the heuristic value and the previous state.
A node N2 is a neighbor of a node N1 if there is an action which
can take you from N1 to N2.
node_neighbor(Node, Neighbor) <-
neighbor(Node, Action, NewNode),
...
...
- Check Neighbor:
neighbor(World1, Action, World2)
It succeeds if performing the Action in World1 can result
in World2.
neighbor(State1, Action, State2) <-
preconds(Action, Pre),
subset(Pre, State1),
addlist(Action, AddList),
deletelist(Action, DelList),
remove(DelList, State1),
append(AddList, State1, State2);
- Forward Planning:
The strategy is to begin at the start node, i.e., with all
things that are true in the initial world state, and search
forward looking for a solution node.
* Any of the methods for considering heuristic information
while "graph walking" are applicable.
* A suggested heuristic is the number of elements (facts)
is in the goal state but not presented in the current state.
difference (current) = | current - goal |
difference (initial) = max
difference (goal) = 0
- Backward Planning
The strategy is to begin with the goal description, and accumulates
actions, as required, until it finds an action sequence that determinate
with an action can be performed on the initial state.
--------------29C62F3B6E7--
From: Martti Halminen
Subject: Re: help - block world
Date:
Message-ID: <3472C758.E21@dpe.fi>
Troy McKinnon wrote:
>
> Hello,
>
> I am writing because I am a beginner LISP programmer and I have a very
> simple problem that I can't seem to finish. I was just wondering if I
> could get some assistance or advice.
>
> <···············@cryogen.com>
>
> ####
> I am trying to implement a forward planner which uses the STRIPS
> representation for actions and states.
> I have a search algoritm already setup, but I am having trouble getting
> my get-neighbors function to work.
>
> Description of Stripping and forward planning attached...
> I would really appreciate any help or advice I can get.
>
Generally, this piece of code gives the impression that you are doing
your thinking in some other language ( C or BASIC are the usual
suspects) and are trying to translate it to Lisp command by command. You
are doing several blunders that could be avoided by first reading some
actual Lisp programs. I'd suggest some good book, for example Graham's
ANSI Common Lisp or Winston & Horn: LISP (3rd ed.).
Also, either changing to a decent CL implementation or reading the error
messages if you are already using one might help.
For example (using ACL 4.3):
USER(3): (setf X)
Error: Odd number of subforms to setf.
[condition type: PROGRAM-ERROR]
...
USER(7): (get-neighbors 1 2 3)
Error: Cannot bind 0 -- not a symbol.
[condition type: PROGRAM-ERROR]
Restart actions (select using :continue):
0: Prompt for a new variable name.
[1c] USER(8): :zoo
Evaluation stack:
(CERROR "Prompt for a new variable name." PROGRAM-ERROR ...)
->(DOTIMES (0 3) (SETF X #) ...)
(GET-NEIGHBORS 1 2 ...)
(EVAL (GET-NEIGHBORS 1 2 ...))
(TPL:TOP-LEVEL-READ-EVAL-PRINT-LOOP)
(TPL:START-INTERACTIVE-TOP-LEVEL
#<TEXT stream socket connected from localhost/9666 to
localhost/1248 @
#x203a641a>
TPL:TOP-LEVEL-READ-EVAL-PRINT-LOOP ...)
Or, when compiled:
; While compiling GET-NEIGHBORS:
Warning: Free reference to undeclared variable I assumed special.
Warning: Free reference to undeclared variable J assumed special.
Error: syntax error detected during compilation: Illegal first subform
to dotimes: (0 3)
These would show that you are using setf a little oddly, and have number
zero in your dotimes form in a place where there should be a variable.
> Here is what I have so far...
>
> (setf X)
> (setf Y)
- If you are trying to declare global variables, defvar might be what
you are after. At the same time you might investigate stuff like lexical
vs. dynamic scoping and special variables etc.
>
> ; Function to determine neighbors of a given node
> (defun get-neighbors (State1 Action State2)
> (setf i 0)
> (setf j 0)
- whatever you are trying to do here, is probably not working as
expected. This j and the j inside the dotimes are not the same thing!
> (dotimes (0 3) -- shouldn't this 0 be i ?
> (setf X (nth i BLOCKS))
- if BLOCKS is a special variable defined elsewhere it is usually
considered stylish to surround the name with asterisks: *BLOCKS*
> (setf i (+ i 1))
- if i is the loop variable, it should not be changed inside the loop,
dotimes already does this!
> (dotimes (j 3)
> (setf Y (nth j BLOCKS))
- If you are just going through every component in BLOCKS why not use
dolist?
> ; (if neighbor - action will work then copy to neighbors
> ; (if (preconds (nth i ACTIONS)) setf
> ; This is the hard part...
> ; neighbors are world2 after given action is applied to world1
> (setf j (+ j 1))
- again, messing with the loop counter is likely to create problems.
> )
> )
> neighbors ; return neighbor list
> )
>
--
________________________________________________________________
^. Martti Halminen
/ \`. Design Power Europe Oy
/ \ `. Tekniikantie 12, FIN-02150 Espoo, Finland
/\`. \ | Tel:+358 9 4354 2306, Fax:+358 9 455 8575
/__\|___\| ······················@dpe.fi http://www.dpe.fi