Monday, January 30, 2012

Good news: In-class test on 2/9


 Another heads-up..  I am planning on having an in-class test on next Thursday. 

I normally only have one midterm and a final, mostly because I don't like to use up class time for exams.
However, since I am any way out of town next week, and since you are all here, it seems we can have 
two mid-term tests (I assume most of you realize that having one more test is better rather than worse for you..)

The test will cover everything we complete until end of this week (but not the make-up class for next Tuesday). 

You will have the opportunity  during Tuesday's class time to come to the class and have a recitation session with the 


ps: No--I am not trying to convert a missed class into a test--I still fully intend to make-up the Thursday's missed class too by 
an extra meeting+recording during the course of the semester. I am doing the test on Thursday (which is frankly more work for us ;-)
because I have the opportunity to do so without losing class time..

Project 0: Grading & Statistics


Project 0 has been graded and will be returned to you in class tomorrow.

The project was graded out of 60 points; 10 for each mandatory part (6 each).  In addition, there were 10 points of extra credit (EC) each for problems 7 and 8, and 5 points of EC for 5(d). The grading for this particular project was quite relaxed, since it was a refresher to Lisp. However, you do need to have at least shown your attempts at solving a problem to have got partial credit.

The undergraduate average was 49.25 and the graduate average score was 56. This does not take EC into account.

If you have any questions about the grading after your projects are returned to you, please e-mail me at krt at asu dot edu.


Saturday, January 28, 2012

My absence during the week of Feb 5th

Dear all

As I mentioned earlier,  I will miss the classes on Feb 6th and 8th due to travel. I am hoping to finalize my "make-up" plan by next Tuesday. My current thinking is to make-up/pre-record one of the classes next week, and make the other one up during the course of the semester (probably just before Spring break). 

I am considering holding the make-up class right after the normal class on Thursday (in the same room)--with a short break (so people don't have to come for a separate meeting on Friday). 

This is just a heads up. If you have any comments/concerns, let me know.


Friday, January 27, 2012

Re: Question on Homework 1

Note that you are searching on a finite depth tree where *all the solutions are at the leaf level, but are distributed non-uniformly. 

This means that if you make an early mistake in choosing the children at the top of the tree, you can get into barren parts of the tree and waste time.

What you need is a way to somehow probe different parts of the final level efficiently.

See if the search algorithm given facilitates this..


On Fri, Jan 27, 2012 at 12:49 PM, Elliot Drown <> wrote:

I am having some difficulty in understanding the algorithm in question 7.2, and why it might provide better performance than other search techniques. Can you clarify the algorithm and the idea behind it for me? Any additional information you can provide would be much appreciated.

Thank you for your time,
Elliot Drown

Gaming is a hard job, but someone has to do it!

Paper on how popular video games are NP Hard Problems -

Thursday, January 26, 2012

Next topic--Chap 10: Search with factored or propositional states (rather than atomic ones)


 For the next topic, we will jump clear across the book and go to 10th chapter--which is titled planning.
It is basically search with propositional states, and makes a very nice follow-on to atomic search we have
done until now. Here are the parts we hope to cover. 

10.1. Definition of Classical Planning ... 366 
      10.1.1. Example: Air cargo transport ... 369 
      10.1.2. Example: The spare tire problem ... 370 
      10.1.3. Example: The blocks world ... 370 
      10.1.4. The complexity of classical planning ... 372 
10.2. Algorithms for Planning as State-Space Search ... 373 
      10.2.1. Forward (progression) state-space search ... 373 
      10.2.2. Backward (regression) relevant-states search ... 374 
      10.2.3. Heuristics for planning ... 376 
10.3. Planning Graphs ... 379 
      10.3.1. Planning graphs for heuristic estimation ... 381 
      10.3.2. The Graphplan algorithm ... 383 
      10.3.3. Termination of Graphplan ... 385 


Monday, January 23, 2012

Re: [CSE471] Doubt in Project0

This seems to be a question that a lot of you have had.

A clarification for Project 0: If your program seems to give you the correct output, then testing it with a few input cases and showing that output alone will be sufficient for full credit. The output trace is intended for you to show that you tried something if the output is not as expected.

I hope this clears that doubt up. As a reminder, the project is due tomorrow, either at the beginning of class, or in Rao's mailbox before class-time.

On Mon, Jan 23, 2012 at 6:53 PM, abc <xyz> wrote:

For the submission of the project it is mentioned to give output trace and stack-trace. I had doubt regarding this, I understand that only if the program does not execute back trace comes up, but for a properly executing program how can I extract the trace.

I tried with the (trace) symbol. But I am not getting any trace output. It will be helpful if it can be explained how to get the output trace and stack trace.


paper related to the comment about the effect of cost-variance on uniform cost search


 I made an off-hand remark in the last class (recorded Friday) that while uniform-cost search is guaranteed to be complete and
optimal as long as the action costs are positive (strictly greater than zero), the efficiency itself does depend on the action cost 
variance (e.g. if one action costs 0.0001 and another costs 10 units). I mentioned a recent paper by Will Cushing in this context.

If you are curious, you can find that paper at 


Sunday, January 22, 2012

Email address for asking for help regarding the course


 Please use the following address   cse471-help  at 
to ask for any help regarding the course (projects, homework etc). This will send the mail to 
me, Will Cushing, Kartik Talamadupula and Tuan Nguyen--so one of us will get back to you. 


Project 1 made available


 I made the project 1 available in the projects page.  It is "officially" assigned on Jan 24th and is due Feb 14th (with love ;-).

Don't be daunted by the length of the project specification. It is long mostly because I am giving you most of the code and giving you enough hints on exactly what you need to do. 

I also put a link to another lisp lecture that I had recorded last time specifically to be useful with respect to the first project. 

You can ask additional questions on the project to the TAs on Tuesday in the (optional) class--or during the office hours.


Friday, January 20, 2012

Compressed video made available.. Re: Video and Audio of the make-up class lecture are online...


 I also put a link to a compressed video (that is <1gig instead of >2.5) for those of you with slower lines (only for this lecture).


On Fri, Jan 20, 2012 at 11:47 AM, Subbarao Kambhampati <> wrote:

Thanks to those of you who showed up! 
For the rest, the recordings of the class are now available online.

Make sure you view them before next Thursday.


Video and Audio of the make-up class lecture are online...

Thanks to those of you who showed up! 
For the rest, the recordings of the class are now available online.

Make sure you view them before next Thursday.


Thursday, January 19, 2012

Homework 1 is available on the class homepage..

This has three parts--part 1 is on agent models, part 2 is on blind search and part 3 is on A* search and heuristics. 


Re: CSE 471 Project0 and Tuesday's class

[I am cc'ing the response to the class list since others might have the same question]
Regarding Tuesday's class--what I would have covered in Tuesday's class will be covered by me in the make-up class tomorrow (10--11:15 in the same room). 

However,  as I mentioned,  one or more of the TAs plan to come to the class on Tuesday and answer any questions, review any algorithms and/or do any examples on the board. I encourage (but not require) people to make use of the meeting since you are all free at that time anyway.

[Don't think of this as me trying to foist extra learning on you; think of it as an opportunity that you can avail of, if you so choose.]

If you do not go to Tuesday's meeting, you can submit the project by leaving it with any of the TAs (all of who sit right across from my office BY560), or leave it at the department main office and ask them to put it in my mailbox. 


On Thu, Jan 19, 2012 at 8:27 PM, Denise Parada <> wrote:

On last Tuesday's class, you mentioned that we have until next Tuesday to turn in Project 0?  But class is cancelled that day? I just wanted to clarify this.

~Denise Parada

The clip of Ricky Ricardo showing DFS ;-) and cognitive plausibility of DFS

is here

The idea that DFS is more cognitively plausible is pretty well understood. In trying to do a problem P,
you may split it into sub-problems; and start doing p1. You may decide p1 is too hard still and 
split it into p11, p12...p1j  and start working on p11 (see the depth first nature?).

The advantage of going this way is that you need only a *STACK* to keep track of your goals (remember that LIFO--last in first out
queue--is really a stack). So you put P first on the stack. On top of it put in order. now you remove top of the stack (p1) and put all its 
subproblems p11..p1j on the stack. When all of those get done, the next one to be picked will be p2. 


Wednesday, January 18, 2012

Makeup class on Friday will be in the same class room (M1-09)--10AM--11:15AM


 I reserved the normal class room for the make-up class meeting on Friday. The class will be continuation of the
discussion from Thursday evening. 

I hope to see any of you who are free at that time (I saw a healthy number of raised hands yesterday). 
If you are unable to attend the make-up meeting, please make sure to watch the
video *before* the next Thursday (1/26)--as the 1/26 lecture will be continuation of the Friday one.


Monday, January 16, 2012

Project 0: Submission Instructions


Here are some instructions with respect to turning in Project 0: Lisp Refresher. Please take some time to read this in full.

The projects are due Jan 19th (Thursday) at the beginning of class. Please turn in a hard (printed) copy of your project with the following for each problem:

1. The full Lisp code, with comments indicating what each part of code achieves;
2. A transcript (output trace) that demonstrates your code in action. You should try each function with different inputs, and explain any discrepancies you see. You may edit the transcript to remove unnecessary stack-traces, etc. (but do not edit the results of computation); and
3. Follow the do-s and dont-s from the project page.

Since this project is intended as a refresher / introduction to Lisp, we will be a bit soft with the grading. However, it is imperative that you try as many problems as possible and turn in all your work to receive credit, and explain why you had trouble (if any). You may print double-sided if you wish to save paper, but please make sure we can read your font.

The submission instructions for future projects may vary, but you will always be notified well in advance of the due date. Good luck.

Kartik Talamadupula

Wednesday, January 11, 2012

Readings for tomorrow's class

With respect to the 3rd edition (
we have "covered" Chapters 1 and 2 (1 the first class, and 2 yesterday).

Starting tomorrow, we will discuss Chapter 3 (We will probably go up to Section 3.4).

You might want to start reading that chapter.


Extended Lisp Resources

For those of you interested in studying Lisp deeply (particularly Common Lisp) I can personally recommend Paul Graham's tome ("On Lisp"?) -- Rao has a link to it from the class web page.

Scheme should have been covered in your study of CSE 240, which ought to be a direct or indirect prerequisite.  Scheme is a dialect of Lisp -- not the most widely implemented nor standardized, but rather it is the academically purest dialect of Lisp.  So you should already know Lisp.  What you don't know (maybe) is Common Lisp.

Perhaps the most important difference to be aware of is the so-called Lisp-2/Lisp-1 distinction.  See answer [1-1] (the second answer, and the first technical answer) in "" for a quick explanation.  Deep explanation, of historical significance to boot, of all and only this distinction between Scheme and Common Lisp can be found at

A detailed look at the less theoretical and more practical differences can be seen at, for example.  Wikipedia is always a reasonable resource as well.

A list of resources wouldn't be complete without mentioning the Common Lisp HyperSpec, mirrored in many places, for example "" and "".  You would come across it anyways if you ask Google to define lisp concepts for you; for example, search for "listp".  This is a fantastic way to find out the smallest of details about even the most esoteric built-in aspects of Common Lisp, and especially useful if you start getting scads of compiler/interpreter errors/warnings.  This is to (Common) Lisp what "man" is to Unix dialects, in my opinion.  (Scheme advocates like to boast that their standard is smaller than its index!)

Something else to be aware of is CLOS, the Common Lisp Object System --- an extension of Common Lisp (now part of the standard?) for converting Common Lisp into the OOP paradigm.  If you like that sort of thing. 


On Wed, Jan 11, 2012 at 8:51 AM, Subbarao Kambhampati <> wrote:
Folks (and Will):

 I reserved M1-09, the class room. from 6--8pm. So the lisp recitation session can continue right after the regular class in the same room (with a small break).


Re: CSE 471: Problem with downloading the lecture video

Hmm.. Both links work for me. You should right-click on the link and save it to your local disk and then play it (they are very large files and don't play in streaming over network).   


On Wed, Jan 11, 2012 at 11:35 AM, Phien Pham <> wrote:
I was going to download the video from the lecture in order to review the lecture. But when I clicked the video link, nothing happened and I could not download the video. Can you check the video link, please?
Thank you 

Phien Pham

The Lisp Recitation will be in the same class room tomorrow from 6pm

Folks (and Will):

 I reserved M1-09, the class room. from 6--8pm. So the lisp recitation session can continue right after the regular class in the same room (with a small break).


Tuesday, January 10, 2012

TA Office Hours

I'll be holding open office hours from 11:00 to noon on Wednesdays in Rao's AI Lab, BYENG 557.  I'm in the back corner: 557BD.   The lab is left out of the elevator.

If that is an inconvenient time you are welcome to use email to either carry out the conversation or to make an appointment for some other time.  If you don't get some kind of response within a day, assume I didn't receive it.  Perhaps try another method, like walking up here so we can resolve the communication difficulty.  (I am usually around, and if not me, one of the honorary TAs surely will be.)

If there is general confusion about a subject (especially background material), say, LISP, and enough people tell me ahead of time I'll hold a recitation/refresher on the subject --- indeed, Rao just informed that such is happening with respect to specifically LISP.   Thursday, after class, room to be determined.  We'll take a brief look at the basics and maybe solve a few programming exercises (to the extent that is possible without actually doing Project 0!).  Feel free to ask any relevant questions.  You may receive relevant answers.  The advantage to you, incidentally, in a group setting rather than individual office hours is that your peers may ask the questions you didn't realize you had :).  If you are feeling particularly generous you can post your questions (whenever you have them) on the class blog, there to forever live as a perhaps useful resource.

Thinking Cap on Intelligent Agents

 By now I hope you all had enough time to get yourself signed up to the class blog. As I said, participation is "required" in this class. Participation involves doing assigned readings, being attentive in the class, and most importantly, taking part in the class blog discussions.

While any discussions you want to do on the blog are fine, I will occasionally throw in topics I want you to discuss. For historical reasons, we will call them thinking-cap topics.  Here is the first discussion topic  for your edification.  

As for the quantity vs. quality of your comments, I suggest you go by the Woody Allen's sage advice in Love and Death (start 2:30)   --Rao ]]

Here are some of the things that I would like to see discussion/comments from the class. Please add your thoughts as comments to this blog post. Also, please check any comments already posted to see if your viewpoint is already expressed (remember--this is not a graded homework, but rather a discussion forum). Make sure to sign your posts with your first name (so others can respond by name)

1. Explain what you understand by the assertion in the class that often it is not the hardest environments but rather the medium-hard ones that give most challenges to the agent designer (e.g. stochastic is harder in this sense than non-deterministic; multi-agent is harder than  much-too-many-agents; partially accessible/observable is harder than full non-observable).

2. We said that accessibility of the environment can be connected to the limitations of sensing in that what is accessible to one agent may well be inaccessible/partially accessible to another. Can you actually think of cases where partial accessibility of the environment has nothing to do with sensor limitations of the agent?

3. Optimality--given that most "human agents" are anything but provably optimal, does it make sense for us to focus on optimality of our agent algorithms? Also, if you have more than one optimality objective ( e.g., cost of travel and time of travel), what should be the goal of an algorithm that aims to get "optimal" solutions? 

4. Prior Knowledge--does it make sense to consider agent architectures where prior knowledge and representing and reasoning with it play such central roles (in particular, wouldn't it be enough to just say that everything important is already encoded in the percept sequence)? Also, is it easy to compare the "amount" of knowledge that different agents start with? 

5. Environment vs. Agent complexity--One big issue in agent design is that an agent may have very strong limitations on its memory and computational resources. A desirable property of an agent architecture should be that we can instantiate it for any <agent, enviornment> pair, no matter how complex the enviornment and how simplistic the agent. Comment on whether or not whether or not this property holds for each of the architectures we saw. 

6.  We said goals and performance metrics are set from outside. But often talk about "setting their own goals". How does this square with the external nature of performance metric?

7. Anything else from the first two classes that you want to hold-forth on. 


regarding seats in 471/598


We have several students interested in getting seats in the class, but no more seats due to the physical capacity of the room.

If any of you are currently registered for the course but expect to "swap" out before drop/add this evening, may I suggest that you do it by this afternoon as a courtesy?


Friday, January 6, 2012

Followups and links from the first class


1. While I said the course will focus on AI as "Acting rationally", I tried at least a few times, on why it is useful to consider the human angle (acting like humans, thinking like humans etc) at least as long as we are interested in having AI systems co-exist with humans. For an elaboration of this argument, here is a talk on "human-aware AI" that I gave sometime back: (and audio: ). 

2. Here is a little graphic that AAAI (association for the advancement of AI) made recently to give an idea of the AI landscape (and the kind of applications currently feasible)  (the emphasis was a bit more on the day-to-day life than stuff like planetary exploration but still it will give you an inkling for various subfield buzzwords).  AAAI ( also maintains AI-related news and  short introductions to various AI areas

3. Robots taking over all our jobs was only partly sensationalism; here is a recent NY Times story that says most new jobs are going to them robots (damn those robots; probably manufactured in foreign lands too ;-)  

4. Here is the book by Kahneman I was referring to, that talks about the many irrational aspects of human thinking (here is another recent book on that topic).  

5. In general, doing AI gives us ample opportunity to introspect on the side about to the rationality of our own decision making; that is the theme of  a lay-person lecture I gave  last April. 


ps:   Here is an image of the old German 10 DM note with Gauss on it (there is a sextant in the picture because Gauss spent a lot of time in improving surveying techniques).   Here is the wikipedia entry on Gauss. 

Thursday, January 5, 2012

Welcome to CSE471 Class Mailing List (+Important information)

You are getting this mail either because you are registered for CSE471/598 or have filled the survey sheets today expressing interest in getting a seat. 

I will use this mailing list to do all the announcements regarding the class. 

All mails sent to this list will be archived also at the class mail archive (accessible from the class homepage) and class blog (for which you should have received an 

Posting etiquette: 

The mailing list will primarily be used  by me and the TAs.

The blog can be used by any of you to post and respond to observations/questions/comments relevant to the course. Things posted on the blog are not automatically emailed. 

Some announcements:

 1. The video and audio recordings of today's class are available at the class page (see lecture notes). The video file is ~4gig and will take a bit of time to download if you don't have fast connection. They are MP4 files and can be played with players such as vlc viewer. 

 2. If you are registered for the class, and have not shown up today and turned in the survey, please let me know if you are planning to stay registered for the course.