Good news: In-class test on 2/9

Folks

 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 

TA. 

cheers

Rao

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

Folks,

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.

Thanks.

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.

Rao

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..

Rao

On Fri, Jan 27, 2012 at 12:49 PM, Elliot Drown <edrown@asu.edu> wrote:

Hello,

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

edrown@asu.edu

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

Paper on how popular video games are NP Hard Problems - http://arxiv.org/abs/1201.4995

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

Folks

 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 

Rao

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:

Hi,

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.

Thanks

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

Folks

 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 http://rakaposhi.eas.asu.edu/cse471/surrogate-search.pdf 

cheers

Rao

Email address for asking for help regarding the course

Folks

 Please use the following address   cse471-help  at asu.edu 

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. 

regards

Rao

Project 1 made available

Folks

 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.

Rao

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

Folks

 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).

FYI

rao

On Fri, Jan 20, 2012 at 11:47 AM, Subbarao Kambhampati <rao@asu.edu> 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.

Rao

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.

Rao

Homework 1 is available on the class homepage..

rakaposhi.eas.asu.edu/cse471/home-work-s12.html

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. 

Rao

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. 

Rao

On Thu, Jan 19, 2012 at 8:27 PM, Denise Parada <denise.parada@asu.edu> wrote:

Professor:

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 

http://www.youtube.com/watch?v=IPy9-zVEhVY

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 p1...pk; 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 p1...pk 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. 

Rao

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

Folks

 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.

Rao

Project 0: Submission Instructions

Folks,

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

Video of Lisp recitation lecture by Will Cushing

is on the lecture notes (see the recitation material).

Rao

Readings for tomorrow's class

With respect to the 3rd edition (http://aima.cs.berkeley.edu/contents.html ) 

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.

Rao

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 "http://www.faqs.org/faqs/lisp-faq/part1/" 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 http://www.nhplace.com/kent/Papers/Technical-Issues.html.

A detailed look at the less theoretical and more practical differences can be seen at http://community.schemewiki.org/?scheme-vs-common-lisp, 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 "http://www.lispworks.com/documentation/HyperSpec/Front/" and "http://clhs.lisp.se/".  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. 

-Will

On Wed, Jan 11, 2012 at 8:51 AM, Subbarao Kambhampati <rao@asu.edu> 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).

Rao

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).   

Rao

On Wed, Jan 11, 2012 at 11:35 AM, Phien Pham <pdpham@asu.edu> wrote:

Hi,

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).

Rao

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

[[Folks:
 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. 

Rao

regarding seats in 471/598

Folks

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?

thanks

Rao

Followups and links from the first class

Folks:

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: 
http://rakaposhi.eas.asu.edu/uw-haai-talk.ppt (and audio: http://rakaposhi.eas.asu.edu/rao-uw-talk.WAV ). 


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) http://www.aaai.org/Magazine/Poster/ailandscape.jpg  (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 ( www.aaai.org) 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. 

rao

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. 

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 

invitation). 

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. 

regards

Rao