Agent Programming Assignment (#2)
Last modified: "December 4, 1996 18:36:07 by matt"
Tuesday/Thursday, 2:00-3:20.
Late Due date: Thursday, 12/5, 6PM.
The source code for programs in the Russell/Norvig textbook is located in
the directory /nfs/dryfly/imports/AIMA-lisp-code/. You should
feel free to browse through the source code there that you will be using in
your assignment.
You should copy the file program-wumpus-setup.lisp into your directory
(just follow the link here and copy & paste). You should load this
file whenever you first start lisp with the intention of doing this
assignment!
Look to normal.lisp for means of converting your Wumpus axioms into
Horn clauses, when you can't do so yourself. You can then use the
resulting Horn clauses as your knowledge base.
To get started, I suggest you build an agent that simply moves straight
ahead until bumping into a wall, in which case it turns left (or right, but
be consistent) and keeps moving forward.
Hints for the assignment
Here are the worlds you should get your agent to work on. The example
below shows how to run-wumpus using each of these worlds.
(setq world (make-wumpus-world :object-specs '((edge wall) ((1 1) (1 gold)))
:agents (list (wumpus-agent "your name"))))
(run-wumpus :env world :display t) ;DISPLAY T causes will display maze at each step.
(setq world (make-wumpus-world :object-specs '((edge wall) ((1 3) (1 gold)))
:agents (list (wumpus-agent "your name"))))
(run-wumpus :env world :display t)
(setq world (make-wumpus-world :object-specs '((edge wall) ((2 4) (1 gold)))
:agents (list (wumpus-agent "your name"))))
(run-wumpus :env world :display t)
(setq world (make-wumpus-world :object-specs '((edge wall) ((2 3) (1 gold)))
:agents (list (wumpus-agent "your name"))))
(run-wumpus :env world :display t)
(setq world (make-wumpus-world :object-specs '((edge wall) ((3 4) (1 gold)) ((2 3) (1 wumpus)))
:agents (list (wumpus-agent "your name"))))
(run-wumpus :env world :display t)
(setq world (make-wumpus-world :object-specs '((edge wall) ((3 3) (1 gold))
((2 3) (1 wumpus)) ((3 2) (1 pit)))
:agents (list (wumpus-agent "your name"))))
(run-wumpus :env world :display t)
Obviously, you should change "your name" to something more personal, and
you will have to use a function other than WUMPUS-AGENT. You might try
modelling WUMPUS-AGENT on the predefined STUPID-WUMPUS-AGENT. The
important thing about the 5th world is what your agent does when it detects
a stench. The 4th world attempts to test if your agent prefers to move
into previously unvisited squares. The 6th world is the most difficult of
all, and requires that the agent eventually choose to move into a
"dangerous" square in order to get to the gold.
Hints
First, there are many different ways to solve this assignment. The
overriding criteria for success is that your agent uses a KB to help it
decide what to do. I'm not particularly concerned at how successful your
agent is in terms of actually getting the gold. I will look for the agent
to (in order of preference):
a) Pick up the gold if it is present.
b) Do something reasonable when it bangs into a wall.
c) Retreat from smelly or breezy rooms whenever possible.
d) explore previously unexplored squares, whenever possible.
Infix vs. Prefix
I recommend that you not use infix notation for your KB.
Students have been having real trouble with the infix system. I recommend
that you stick with prefix notation. For example:
"all (a x s Holding(x, Result(a,s)) <=> ((a = grab) and present(x,s) and
portable(x)) or (holding(x,s) and (a /= release)))"
becomes
'(all (a x s) (<=> (holding x (result a s))
(or (and (= a grab) (present x s) (portable x))
(and (holding x s) (/= a release)))))
Simplify, simplify, simplify
You don't need to use all the rules of wumpus world to get your agent to
work. Simplify wherever possible. Thus, instead of using a complicated
successor axiom for Holding, you might use two simpler rules:
'(all (a x s) (=> (and (present x s) (portable x)) (holding x (result grab s))))
'(all (a x s) (=> (holding x s) (holding x (result a s))))
The first rule is a causal rule, indicating when Holding occurs. The
second rule is a frame axiom, which represents that the agent will continue
to hold any object once it picks it up.
I suggest that you avoid using state successor axioms where possible,
as they do not seem to convert well to Horn Normal form. Instead, use
frame axioms, as above. You really only need to implement a few actions:
Grab, Turn (or TurnLeft, TurnRight, depending on how you are implementing
turns), Forward. Thus, for each predicate, you will probably have one
causal rule and two frame axioms. For example, the At predicate is only
affected by the Forward action. You would need a frame axiom for Turn and
Grab to indicate that At does not change with those two actions.
Static predicates
You will need to assert some predicates that are independent of situation.
For example, one of the first things the agent should do is assert that the
square where it starts is Visited:
(tell *kb* '(Visited (1 1)))
(tell *kb* '(Safe (1 1)))
You will need predicates like these to differentiate between Good and
Medium actions.
KB enquiries
Your queries should probably be of the form:
(ask-pattern *kb* '?x '(Visited (?x 0)))
(ask *kb* '(Safe (1 3)))
Sample knowledge base entries
As we talked about in class, you'll probably want to define simple
mathematical relations, like EQUAL and DIFF1, as the Horn KB system
doesn't provide these for you. Below, I've provided a set of rules
that establish some of the basic predicates of the wumpus world:
(defun seed-kb ()
(tell kb '(equal 2 2))
(tell kb '(equal 3 3))
(tell kb '(equal 4 4))
(tell kb '(equal 1 1))
(tell kb '(diff1 2 3))
(tell kb '(diff1 3 4))
(tell kb '(diff1 1 2))
(tell kb '(diff1 3 2))
(tell kb '(diff1 4 3))
(tell kb '(diff1 2 1))
(tell kb '(=> (AND (equal ?x1 ?x2)(diff1 ?y1 ?y2))
(adj (?x1 ?y1) (?x2 ?y2))))
(tell kb '(=> (AND (diff1 ?x1 ?x2)(equal ?y1 ?y2))
(adj (?x1 ?y1) (?x2 ?y2))))
(tell kb '(=> (and (diff1 ?x1 ?x2) (diff1 ?y1 ?y2))
(diagonal (?x1 ?y1) (?x2 ?y2))))
)
You might use these predicates via queries such as:
> (ask-pattern kb '(?x ?y) '(diagonal (1 1) (?x ?y)))
(2 2)
I.e., yes, there is (at least) one square diagonal to (1 1), and it is (2
2). Or,
> (ask kb '(diagonal (2 2) (1 3)))
((?Y2_5354 . 3) (?X2_5353 . 1) (?Y1_5352 . 2) (?X1_5351 . 2))
I.e., yes, (2 2) is diagnonal to (1 3)). (Note that the return value isn't
really important except insofar as it does not equal NIL.) Or,
> (ask kb '(diagonal (2 2) (2 1)))
NIL
I.e., (2 2) is not diagonal to (2 1).
Note that you should not have a "definitional" rule where a the predicate
being defined (the right side of the implication) is also mentioned on the
left side. E.g:
(=> (diff1 ?x ?y) (diff1 ?y ?x))
Using this
rule, you could get into an infinite loop asking a question like,
(ask kb '(diff1 1 3))
...would cause an infinite loop: to prove that
(diff1 1 3)
...is true, the KB would want to prove (diff1 3 1), but to prove that, it would want to prove (diff1 1 3), ad infinitum.
The Grand Challenge:
To receive an A for this project, you need
only demonstrate that your agent satisfies the criteria listed above. If, by the due date, you can demonstrate an
agent (of your design) that will also successfully navigate any 4x4 wumpus world
example whenever possible, I will allow you to change the grade on any one
assignment during the semester to an 'A'. Alternatively, you may increase
your midterm or final exam grade by one half grade.