CS 372 (Artificial Intelligence) Fall 2004
Week3 (Due 9/20) Reactions & Thoughts
Ioana Butoi
Andrew Cantino
I wonder what variations on the search methods that we learned this week for searching state space exist. I saw the![[WWW]](/wiki/classic/img/moin-www.png){kind=small}
dynamic programming, which was briefly mentioned at the end of class on Thursday, in another class last year. There was also a technique called memoization, and I wonder if that could be applied to these search techniques as well. Memoization memorizes previous answers (paths?) so that they don't have to be recomputed. In working on the first two assignments, I realized what must be one of the fundamental difficulties of AI and robotics: ascertaining one's current location/orientation/motion accurately. We mentioned dead reckoning in class, but it seems that keeping a robot's internal map and location accurately updated with the real world must be very difficult. I was wondering how I could make my simulated robot build a mental map of it's surroundings so that it could figure out it's location and where it should go, but I'm not sure how to do this. I can build a large database of range readings as I wonder around the tutorial world, but since I don't know my actual position, I don't know how to turn those readings into an actual map. I imagine there is some sort of statistical process that I could use that would, over time, assemble the accumulated range findings into a probabilistic map of the world, but I don't know how to do this.
Addendum: I found this interesting article on robotic mapping which uses statistical techniques, but doesn't go into much depth on how they work.
Audrey Flattes
I think that I finally get it. All of these different ways of searching are finally embedded in my brain. Now the question is when do you use which. Since each has it pros how do you know when to use each of them. I was just thinking about how we search for things in comparison to these different searches that we are trying to implement in AI. Which search is the most natural way of searching.I really liked the video, it was really interesting, a lot of the things that the robots were doing seemed like they were learning especially the insect like robot that taught itself to walk. Also the lamp animation and how they were able to create children by taking pieces of both parents and creating a child that was more advance than its parents. Its interesting because when I think about it I wonder how much we have to start over and how much is already hard coded into us at birth. In some ways I feel that the lamps evolution is advanced than our own.
Christina Florio
The question is now when do we use which search to optimize both time and memory? Which also leads me to the question of what do we want any form of AI to retain regarding a search? Now that we know ways of keeping track of different possible moves a program can make (whether physically or abstractly), where do we draw the line at remembering these moves? I have found these searches to be very helpful in other classes, but my implementation of them has not been very extensive or complicated, so it makes me wonder how complicated the searches become as the problems get more and more complicated, mainly because of the concerns mentioned above: time and memory.
Kathleen Maffei
I find the idea of state-spaces to be very appealing. Rather than spending time considering what kinds of logic to use to account for all possibilities, I can delineate all the possibilities and how they’re related. It’s a clear, simple way of laying it all out before moving on to consider the next move. It sounds like something I might do on scrap paper to figure out my logic in a program.
Then the problem becomes one of creating efficient searches, not one of coming up with the logic of how to move. If the problem were one for which I had little information about the costs involved in various paths, then I might be restricted to a blind search. While a breadth-first search moves across the tree across then down (like reading), and a depth-first search goes down then across, iterative deepening combines these two to minimize the drawbacks. Blind searches will come up with the first solution they come across. A heuristically informed search will use estimated cost data associated with the nodes to select, each step of the way, what appears to be the best choice. Though you’re likely to get a better solution than in a blind search, it is still not necessarily the most efficient. An optimal search uses actual cost data, associated with each path, to decide on the best solution. In other words, the better your data, the better your search can plan out a solution.
Sara McCullough
I really enjoyed the video we watched in class on tuesday. The portion of the video about the stock-picker brings up a lot of issues that I am finding myself very interested in. I really liked to see such a practical and real life application of AI. I think such a useful and valuable application really brings out the issue of human superiority. Will we really trust a machine to make important finance decisions? One answer to the question of human supremacy is that supremacy is all within certain scopes. I think the example of the stock picker definitely pushes this answer. A machine may not be self-aware or emotional, but it is capable of making better stock buying decisions than humans. I also enjoyed the segment about the penguins. The creators and observers of the penguins expressed amazement at how the penguins looked in the end. This reminded me a lot of what my class in emergence did last year. There was this same sense of wonder upon seeing the outcome of almost every program we wrote towards the end of the semester. Examples of mergence and learning algorithms, as they were presented with the penguins in the video, are phenomenons that happen all the time naturally. It is just something that I find really impressive when created in a program. I would definitely like to work more with learning algorithms.
Ben Root
Algorithms! I'm really happy to start getting into nuts and bolts of tools of AI. It is interesting that we haven't learned about the iterative depth (or breadth) searching because it seems to have clear advantages to a non-iterative approach. Now we are able to have an AI which potentially could enumerate the future results of an action and then choose a path through state space that leads to a goal or even an optimal goal if enough information is known about the state graph. I'm especially happy to have the class linked to (through graph techniques) to the rest of my computer science knowledge.
It will be neat to see the new demos of robot behavior. I think there will be a lot of variation to the different robot behaviors, and some may actually seem to the casual observer like they are obeying much different rules than others (i.e. Braitenberg's vehicles). In that vein I would be interested in hearing about any really AwesomeBehaviorDescriptions that people get from uninformed participants. I think that people will start seeing a lot more intelligence in these newer iterations of the robots and I would like to see what reactions people get.
Sandeep Singh
When I first learned about binary search trees in high school, I was merely taught the basic and underlying ideas behind the method. Although we learned how various types of tree traversing worked, we did not discuss any practical uses for such trees. After last week's lecture, everything finally started to make sense. I began to see how these trees, along with the different searching and traversing techniques, could be used to find various solutions.During the latter half of my high school years I became increasingly interested in the Rubik's Cube. For a while I had toyed around with one in hopes of discovering an algorithm. While I did find some things, I was not able to pinpoint the algorithm itself. Out of complete depersation to understand the mechanics of the Cube, I began to search online for solvers. As much as I hated breaking the 'honor code' of the Rubik's Cube world, I needed to know the inner workings. Soon enough, I found a few programs that would allow you to visually construct your own cube using a graphical interface. Afterwards, the program would produce the solution by printing out the series of turns and twists needed to solve the cube. Depending on how intricate the cube was, the number of steps needed to solve it were, at times, over 25 moves. There was also an option to find the 'optimal' solution; while this took much longer to compute, it produced an answer that was usually under 15 moves. In retrospect, I finally see how the solver's search methods parallel with that of the search tree methods we discussed. As the program would run, it would state that it was 'searching a depth of x', where x was a number (usually in the teens). I now see that the program was searching a tree in an attempt to find a solution and that the overall length of the solution was determined by whatever node in the tree the program was searching.
I remember thinking how inconceivable such a program would be to write; however, all the program did was implement the ideas discussed during Thursday's lecture. This website briefly discusses how the AI algorithms we talked about can be used to solve the cube: http://ai.squeakydolphin.com/wiki.php?pagename=AIAWiki.KensRubik . Through a bit more searching, I found the following site interesting. It briefly talks about the mathematics behind speed cubing: http://ai.squeakydolphin.com/wiki.php?pagename=AIAWiki.KensRubik.
If anyone is interested, I can find/post the link to the Cube Solver mentioned earlier in this response
Darby Thompson
It was interesting to watch the demos of our first homework last week. Most of the algorithms seemed to be very similar, however the speed at which the robot was set to move forwards affected the behavior significantly. The demos for the next homework due this week should prove to be even more diverse since we have a choice of threshold values and there is much more room to add extra cases.
I really enjoyed the tv report that we watched on Tuesday and the demonstration of Nettalk. It was fascinating to be able to hear the speech program evolve! However the fact that this was made in the mid-eighties makes me wonder; is this still state-of-the-art technology or is there a new program out there that is so much better? Is the Festival Speech Synthesis System (that we use with Bubba) equivalent or better? How can we improve on such a program?
The piece on the penguins from Batman showed how techniques such as the ones used in the Lord of the Rings for the battle scenes were being developed (and looked very convincing) in 1992. The animators described their ‘sense of awe’ at the outcome of their program. I hope that this is a feeling that we might experience during some of our later programming homework assignments.
Although Gingus and the hopping lamp were also very interesting to watch, I was very interested in the stock-picker. There is an interesting conflict that we come accross with a program like this. Statistically it makes a good decision much more often than a human, however you cannot query it as to why it makes a decision. Humans have a serious control issue going on here... do we let a computer make a decision for us (knowing that it will probably be better than our decision) or do we ignore the advice from the computer and go on our instincts? We might argue that the computer only has knowledge of the history of the stock market and cannot take into account current risks or freak occurences. For an example, the weather actually has a very small affect on the stock market. The market generally does better on a sunny day than a rainy day. This will be taken into account by the computer since it has some knowledge of the time of year. However, if a hurricane is closing on New York very quickly (a rather strange occurance) the computer will most likely not have this information to predict the next days market.
In the same way, scientists are currently working on an intelligent system to govern an aircraft. The plan is to remove all the windows from the cockpit and have the computer pilot the aircraft. The reasoning behind this is that pilots may panic during a problem, look out the window and think that they are closer/farther away from the ground than they are, second guess their instruments, and make an incorrect decision. A computer will always make the correct decision provided there is nothing wrong with their instruments... So do we trust the human pilot or the program?
