typo in homework question 4.2 corrected..

Cameron pointed out that I mis-copied the textbook problem. I corrected the mistake now.

Rao

---------- Forwarded message ----------
From: Cameron L <noreply-comment@blogger.com>
Date: Fri, Feb 27, 2009 at 5:05 PM
Subject: [cse471/598 Intro to AI Spring 2009 Blog] New comment on *Important change to homework 2*--a new problem ad....
To: subbarao2z2@gmail.com


Cameron L has left a new comment on your post "*Important change to homework 2*--a new problem ad...":

Re the unicorn problem- I just noticed the wording is a little different in the book than on the blog post. The blog says "but if it's not mythical, then it's a mortal ANIMAL." The book says "but if it's not mythical, then it's a mortal MAMMAL".



Posted by Cameron L to cse471/598 Intro to AI Spring 2009 Blog at February 27, 2009 4:05 PM

Results of the class feedback survey

Here are the results of the class feedback survey done today. The summary of the results was kindly provided by
Adam Gerbens. The only changes I made were to color-code columns (yellow for UG; blue for grad and green for total), and
add a percentage column next to the raw stats.

You may not be able to see the summary on the blog, but should be able to see it on your email client. If not, you can also find it
on the mail archive ( http://rakaposhi.eas.asu.edu/s09-cse471-mailarchive/msg00034.html )

Rao

Let's make the office hours most efficient

Rao told me that many of the students have difficulties with lisp but I don't see many people show up in the office hour. I am wondering what could be the best way to make use of it. Rao suggested that I move my office to instructional lab which is located in the second floor of Brickyard where you can get access to computers. That might help because I can actually see your code and find out what the problem might be, of course, if you show up.  And I also have computer in my office with lisp-in-box installed. You are welcome to bring or send me a copy of the code and run it there.  
Which ever you prefer, please give me your opinions so that I can tell you a place to find me and serve you better.
Of course, other suggestions are welcome too.


--
Meng,Yunsong
Teaching Assistant

*Important change to homework 2*--a new problem added and due date extended to 3/5 (!)

Folks:

 I added part 4 to the homework to cover the propositional logic discussion. It is now due on 3/5

The rationale is that your midterm will cover all topics from homework 1 and 2. I will make the solutions for homework
available on 3/5.

Rao

ps: Here is what is added:

Part 4(Added new):

• Consider the following inference rule: if we know A V B; and we know ~A, we can derive B. Show that this inference is sound using truth-table method. Is this inference complete? Can you show that this is a special case of resolution?
• (Problem 7.9 from the text book) Given the following, can you prove that the unicorn is mythical? How about magical? Horned?
  "If the unicorn is mythical, then it is immortal, but if it is not mythical, then it is a mortal animal. If the unicorn is either immortal or a mammal, then it is horned. The unicorn is magical if it is horned."

Re: CSE471/598 TA office hours update

Hi folks,
   Just a reminder, I will have office hour on Wednesday for project 1, 2:00PM-3:00PM.


--
Meng,Yunsong
Teaching Assistant (CSE 471/598)
Department of Computer Science and Engineering
School of Computing & Informatics
Arizona State University

Part II D. help

Do we have to write a lisp function to find eb?
The project description says that eb is found by solving the equation eb^gd = ne
in other words eb = ne^ 1/gd right? I'm not sure how I could write a lisp function to compute this.

if you are having trouble getting reasonable numbers for timing, use this time-it macro..

Cut the following code, paste it into your file and use it as

(time-it (your function that you want to time))

Lisp's macro facility is among the very best. Unlike defun, defmacro first constructs lisp code and then evaluates it. the backquote macro is a great way to
make templates...

(defmacro time-it (code)
  `(let ((begtime (get-internal-run-time)))
    ,code
   (float (/ (- (get-internal-run-time) begtime)
       internal-time-units-per-second))))

rao

Project Question

For printing the path from start to goal, should we be printing the move taken, the new puzzle state, both, or something else?

lisp time function

I am noticing that the results of the time function when I run it on my system are in seconds. Thus most of the results are rounded to 0.0 secs for runtime, etc. As far as I can tell, the time function has no other parameters than the form being timed. I am wondering if anyone has figured out how to force the time function to output in any smaller unit of time.

Project submission instructions

Hi folks,
    Here are instructions for project submissions: for all projects except the previous Lisp refresher, please summit BOTH soft copy (source code) and hard copy (print-out).

    1. Please send your soft copy to the email address cse471spring@gmail.com
        WITH SUBJECT OF THE FORM "project x by your name" where x is the project number,
        for example "project 1 by Yunsong Meng".

    2. Please summit the hard copy in class on the due date.

   Following the instructions will help us evaluate your work properly and efficiently.

  Thank you.

 
--
Meng,Yunsong
Teaching Assistant

*Important*: Policies regarding skipping lectures..

Dear all:

 I just wanted to remind everyone about the policy regarding missing classes that I had already stated explicitly in the
first class; for both the students and the instructor of this class:

1. attendance in lectures is mandatory

2. If you must miss a class due to extenuating circumstances, you are expected to send me an email letting me know (I will do the
    same if I have to miss). 
   
The availability of lecture notes and audio online as should not be misinterpreted as   a sign of flexibility on my part about class attendance.
The only flexibility you have is whether to stay in the class or drop it (not unlike  the epistemological commitment made by non-fuzzy-logics :)

If it helps, please note that I do have statistics on attendance--in terms of unclaimed home-works, as well as occasional attendance sheets.
In today's class about eight students--who are apparently still registered for the class--were missing; only one of them
sent me a courtesy mail before the class letting me know they would be missing the class.

regards
Rao

-----------
  "do or do not; there is no try"
                  --Yoda

URL for non-expiring version of the first lisp lectures..

Someone said at the beginning of today's class that the  link for the first lisp lecture already expired because they only allow 20 downloads

Here is a link from my webspace that will not expire, but is likely to be slower in downloading:

http://rakaposhi.eas.asu.edu/cse471/lisp-anatomy.avi

(I will also put the second lisp lecture from today at

http://rakaposhi.eas.asu.edu/cse471/lisp-functions-are-first-class.avi 

)

Rao

Second lisp lecture: Functions as first-class objects in lisp

Folks:

 Here is the second installment on lisp. In this, I discuss how functions can be passed as arguments to other functions
and how this leads to a very flexible abstraction. I also discuss the implication of this for the A* search code I gave.

The avi file is a little longer than 1gb, and so I had to split it into two parts. You can put them together by
using hjsplit (free at http://www.download.com/HJ-Split/3000-2248_4-10550268.html )


http://www.transferbigfiles.com/Get.aspx?id=2be376aa-b70a-493a-8c1f-47ba4ab7ed5c

http://www.transferbigfiles.com/Get.aspx?id=caa2b0b5-929a-48cc-b5bc-aea271500423

the links expire on Feb 24th.


Rao

a paper for people interested in implementing pattern database heuristics extra credit for the first project

http://rakaposhi.eas.asu.edu/korf-search.pdf

(this give a short description in page 2 second column of the approach to computing the pattern databases by a backward search)

rao

Please make sure to read the slime manual so you can use lisp-in-a-box appropriately

Folks

 Based on my conversations with a few of you, it looks like some of you don't quite realize the power of the emacs-lisp interface that comes
free with lisp-in-a-box.  Part of the problem may be that the intallation doesn't come directly with a help manual.

There is however a lot of help information on the lisp-in-a-box homepage itself (http://common-lisp.net/project/lispbox/ )

The most important of the lot is the slime manual which is available at

http://common-lisp.net/project/slime/doc/slime.pdf

Make sure you read it--or you will be wasting your time by doing all development at the command-line. (When in doubt as to whether or not
certain interactive program development support is available for lisp, remind yourself that all interactive programming development ideas
originally *came* from lisp environments!)

Rao

Re: CSE 471 Homework #2 questions

Yes--you have to do all the questions in pdf (actually that pdf contains only two questions, which happens to have sub-parts :-)).

For the manhattan distance heuristic--no you don't consider obstacles (if you do, you will be getting the "real" distance). The whole point of the heuristic is to relax the problem (and in this case you relax by ignoring obstacles).

rao

On Mon, Feb 16, 2009 at 11:10 PM, Todd MacLeod <todd.macleod@asu.edu> wrote:

Hi Professor,

I have a few questions about Homework #2...

1. For part A, questions 3 and 4, you give us a link to a pdf.  Must we do all the problems contained on this pdf?

2. Part A [4] (used in question 3 and 4) of the pdf asks some questions about the manhattan distance of a grid with obstacles.  When counting the total moves for a given tile using manhattan distance, do we consider obstacles, or does the manhattan distance heuristic ignore obstacles, and go right over them?  Perhaps a better way to ask this is given the grid in the pdf, what would be the total manhattan distance of a tile moved from A to F?  Would it be 5 (which would avoid the obstacles) or would it be 3 (which ignores the obstacles.)


Thanks,

Todd MacLeod
todd.macleod@asu.edu

Lisp refresher lecture 1: Anatomy of lisp (23min--video)

Folks:

 The following link (from transferbigfiles) gets you a nearly 1gb sized video that plays for 23min and explaining
some much needed concepts of the anatomy of lisp. Note that depending on your connection the file may take from 10min to much longer to download.

http://www.transferbigfiles.com/Get.aspx?id=c5ecfa14-ea6e-4eed-ab83-e581fd995485

(Link expires Feb 21st)

Let me know if you find it useful, and I might continue a few more.

Rao

ps: If you want to see how it sort of looks like, you can check it out on google video.
http://video.google.com/videoplay?docid=-959600139447653507&hl=en
Note however that you will have hard time reading most of the writing since google video
compresses to quite a low resolution (which is why I had to put the original on transferbigfiles)

Re: CSE471/598 TA office hours update

Since homework 2 & project 1 both due on 24th Feb, I will have extra office hour on Wednesday 18th Feb, 2:00PM-3:00PM.


--
Meng,Yunsong
Teaching Assistant (CSE 471/598)
Department of Computer Science and Engineering
School of Computing & Informatics
Arizona State University

(No recitation session; will have a recitation video posted) Re: partial solutions to the lisp refresher posted; offer to hold lisp recitation session on Monday afternoon

I received mails from 10 students who were interested in such a recitation. Unfortunately, 6 are available at 4pm while the other 4
have conflicts for that time. If I try another time, I am sure I will just shift the conflict around without eliminating it. I could use the thinking cap idea, and say the 4 who have the conflict don't have to be accommodated, but it might be wise to save such meanness to later parts of the semester.

Instead, I will try to post, as an experiment, a video recitation on lisp (using a screen capture program)--that everyone can see at their leisure.

regards
Rao

On Fri, Feb 13, 2009 at 6:15 AM, Subbarao Kambhampati <rao@asu.edu> wrote:

Folks:
 I posted solutions to some of the exercises on lisp refresher exercise.

I am also willing to hold a recitation session on Monday afternoon if there is sufficient interest (a possible
time for such a session is 4pm on Monday). If you are interested in such a session let me know by replying to
this message. If there is sufficient interest, I will confirm with details of where it will be held.

rao

Thinking Cap 2: Informed Search and CSP

Here is the second edition of the thinking cap questions:


1. In the standard CSP problms, all variables must be given assignments--and all solutions are of equal cost. We also
considered an "optimizing" variation of CSP, where each constraint has a cost, and a solution violating that constraint
incurs that cost (with costs being additive); the goal is to find the solution with the least cost.

In both cases above, all variables must be assigned values.

In some problems, we would like to model not assigning any value to a variable--just to keep the solution cost low.
For example, in finding a time for a party for all your friends, you might decide to go ahead without one of your friends,
if he/she is too hard to accommodate. Can you think of how to model such problems within an optimizing CSP?



2. The "informedness" of a heuristic is not as great an idea as it is touted to be. You will likely find, during your project 1,
that the search with manhattan distance heuristic sometimes does *more* expansions than the search with misplaced tiles
heuristic! In this thinking-cap question you will try to understand why this happens.

In particular, given a heuristics h2 which is
more informed than h2 (in that forall nodes n, h2(n) >= h1(n)), we can only show that the "interior f-contour" nodes expanded by search
with h1 are also expanded by h2.

Specifically, consider a node n' such that f2(n') = g(n') + h2(n') <  f*   (where f*, the optimal cost of the goal node, is the same for both
heuristics). So, n' will clearly be expanded by the search with h2. Since h1 <= h2, clearly  f1(n') is also less than f*, and so search with h1 also expands
node n'. This shows that the number of nodes on the interior f-contours for h1 can not be fewer than the nodes on the interior f-contours for h1. (An interior f-contour
is the set of equi-f-value nodes with  f-values less than f*)

The tricky part is that this subsumption doesn't necessrily hold for nodes that are on the "f* contour"--i.e. nodes that have
f1 or f2 equal to f*. Based on the tie-breaking strategy, a subset of these nodes will likely be expanded before the search terminates.
If the subset expanded by h2 is more than that expanded by h1, search with h2 can do more expansions even though it is more informed.

See if you can think of possible reasons why this could happen. [hint: there is a slide in the informed search lecture--with annotation "advanced"--that
gives the insights needed, if you are having trouble..]


rao

partial solutions to the lisp refresher posted; offer to hold lisp recitation session on Monday afternoon

Folks:
 I posted solutions to some of the exercises on lisp refresher exercise.

I am also willing to hold a recitation session on Monday afternoon if there is sufficient interest (a possible
time for such a session is 4pm on Monday). If you are interested in such a session let me know by replying to
this message. If there is sufficient interest, I will confirm with details of where it will be held.

rao

Homework 1 solutions posted; homework 2 posted--due 2/24

CSE 471 project 0 & homework 1 statistics

Hi friends,
  Here are some statistics about the first two assignments.

Project 0 :   full score 100+10
       graduate students: 
                    highest:    110
                    average:    81.36
                    lowest:      30
       undergraduate students:
                    highest:   100
                    average:   83.17
                    lowest:     20

Homework 1:  full score   45+5
       graduate students: 
                    highest:   45
                    average:  39.9
                    lowest:    23
       undergraduate students: 
                    highest:  44
                    average: 34.8 
                    lowest:   24


--
Meng,Yunsong
Teaching Assistant
Department of Computer Science and Engineering
School of Computing & Informatics
Arizona State University

Project 1 / Task 5

I'm having a hard time understanding what to do with task 5. I have everything setup to this point including both heuristic functions, but I'm not sure of what the ending structure should look like. Could I get someone to point me in the right direction?

lisp question

Does anyone know if you can reference earlier slots when using the defstruct macro? For instance:

CL-USER> (defstruct thing a b c)
THING
CL-USER> (setq q (make-thing :a 1 :b 2 :c (+ a b)))
; Evaluation aborted (didn't work)
CL-USER> (setq q (make-thing :a 1 :b 2 :c (+ :a :b)))
; Evaluation aborted (didn't work)

So what I would like to do is reference :a and :b when defining :c. Google searches haven't really helped out.

Readings for next week (Topic: CSP)

Folks:

 Next week we will start discussion of Constraint Satisfaction Problems. Please read

[R&N Ch 5.1--5.3; Ch 4 4.3]

regards
rao

Project 1 released; due 24th

You can find it on the homepage under projects link.

(direct link here: http://rakaposhi.eas.asu.edu/cse471/projects.html )

rao

Homework Question 1

Is anyone else having a terribly hard time coming up with environments for question 1? I need some inspiration here...

A few Questions/Clarifications

In 5.1 ii) it asks if A2 will be able to acheive _all_ goals that A1 can acheive. I assume this refers to the two states with two clean rooms (one with the agent in each room)?

part iii) asks about the "quality" of the actions the two agents can perform. I'm really not sure what the "quality" of an action is... does it just refer to whether or not the action moves closer to the goal state?

Thanks

Question on HW1, Problem 7.1

This question asks us to consider the case where solution nodes are distributed non-uniformly throughout a search tree- they can be clustered. It asks whether we should prefer depth-first search or breadth first search.

I guess I'm not sure how clustered solutions matters? I assume b is finite and the search tree has a finite depth. It seems to me that if b is large relative to d, breadth-first would take longer to get "down into the branches" and find a cluster. So we should go with depth-first.

On the other hand, if the tree is deep, but has a small branching factor, breadth-first might be better because we could fairly quickly get down to where clusters might be?

I feel like these are weak, wishy-washy arguments. And neither one has much to do with clustering. I'm not sure how to reason about this. Help?

Space complexity of width-first search

Hi All,

I am confused about the space complexity of the width-first search, which is discussed in the first paragraph of page 74 in the textbook as

"Every node that is generated must remain in memory, because it is either part of the fringe or is an ancestor of a fringe node. The space complexity is, therefore, the same as the time complexity (plus one node for the root)."

To me, the ancestors of fringe nodes are already expanded and thus do not need to be in memory.

Shuiwang