Thursday, September 10, 2009

Google code jam, easy AI problem!!?

This is a good problem in google code jam... Relates to AI kind of...
1)You know your initial state completely
2) Environment observability is only local(next rooom), but it is static
3) Actions are deterministic...

The problem boils down to this:
"given your actions can you determine the configuration of your environment, in this case a maze..."
Here is the python solution... Kinda had fun time solving it.. took about 1.5 hours to figure the problem and solve it... Have fun!

Next on the reading list (for classes next week)

Once we are done with Bryce el al paper on belief-space planning, we will turn to atomic models for
decision-theoretic search--aka Markov Decision Processes.

The primary reading will be the following paper:

You should read until the end of Section 3 for now (section 4 is factored representations--we will discuss
that later)

I will also provide you with the relevant chapter from R&N.


Wednesday, September 9, 2009

A short writeup on use of binary decision diagrams (BDDs) in planning

You may want to look at the short write at the following URL to get an idea of how bdds get used in planning.


Thursday, September 3, 2009

Setup a wiki page for listing your presentation topic choices

I set up a wikipage accessible from the main 571 wikipage where you can write in your topic choice for reading/presentation.

It is also directly accessible via


Tuesday, September 1, 2009

Tomorrow's class agenda (and the possibility of a make-up class on 9/11)


 Tomorrow, we will complete the discussion of section 4.4 (belief-space search), and also cover 4.5 (online search).
If you haven't read section 4.5, please make sure you do.  Time permitting, we will start with Bryce paper. We will come back to it next week.

 We will also try to see if we can schedule a make-up class next week (perhaps on Friday the 11th). This is because I will be missing two classes on the week of 21st as I will be attending ICAPS 2009 in Greece (I know--someone has to do all this hard travel..), and prefer to make them up myself.  So, please come with your Friday 11th calendar.


New comment on Stochastic vs. Limited Senses.

The following comment sent last semester to 471 folks is relevant given the short philosophical discusson yesterday on this topic.


ps: The full thread is available at
---------- Forwarded message ----------
From: Subbarao Kambhampati <>
Date: Tue, Jan 27, 2009 at 7:42 PM
Subject: [cse471/598 Intro to AI Spring 2009 Blog] New comment on Stochastic vs. Limited Senses.

Jason Majors asks:

Tuesday, January 27, 2009

Stochastic vs. Limited Senses

While reading through the book today, I came up with a question. Where's the line between a lack of good senses and a stochastic environment? The examples we've had in class of what makes an environment stochastic (e.g. car trouble with the taxi) could be monitored with an appropriately advanced sensor array. An omniscient agent (or omniscient objective observer) would consider every environment fully deterministic.
So is there a clear line between the two? I would think that something that is beyond practical (such as monitoring the surfaces of a taxi's tires to know when it will weaken enough to burst from the pressure) would be in the stochastic column, but what about not knowing that a tire is going flat, because the taxi lacks a tire pressure monitoring system (which is practical)?


Subbarao Kambhampati has left a new comment on your post "Stochastic vs. Limited Senses":

This is a good question. When we do not have complete models of a world, then what is inherently a "deterministic world" may well look like a non-deterministic/stochastic one to the agent.

About the only "natural" world that can be said to be inherently stochastic is again the quantum world. In every other case, you can--if you prefer--think that the underlying world is deterministic and we just didn't model it adequately. [Even in the quantum case, many scientists--Einstein in particular--fought tooth and nail to convince the scientific community that the uncertainty is *not* inherent and that we get it only because we are not modeling the system completely. See the celebrated EPR paradox--and how it was eventually shown that the "paradox" is really not a paradox and quantum uncertainty is very much inherent: ]

Notice that the "completeness" we are talking about doesn't have to involve as high a granularity as "modeling the imperfections on the coin surface and the eddies in the room air to predict the coin toss outcome".

Remember that our ancestors, not too long ago, assumed that many phenomena that we now know as deterministic--such as eclipses-- are actually non-deterministic (and thus would associate with them superstitions like "the eclipse shows the gods being angry with the ruler"--as in Chinese belief of "Mandate from the Heaven" etc).


ps: Of course, we humans are also equally adept at introducing determinism where there is none (e.g. my favorite god created this whole darned entire universe and all its life forms over a weekend some 6000 years ago....

Check out

where Lisa laments that the expected answer to every question on her science test was "God made it" ;-)

Posted by Subbarao Kambhampati to cse471/598 Intro to AI Spring 2009 Blog at January 27, 2009 6:42 PM