Sharon Rose Alterman

This week's lectures were very interesting to me. I had come across several of the concepts before in other classes in a much more theoretical sense. It was intersting to see an actual application for search trees. I was somewhat surprised to find that the same basic algorithm could be used for several kinds of searches.

The way that we, as humans, look at search problems is drastically different from the way that a computer interprets them. We look at the available paths and, seemingly taking them all in at once, quickly find the best path without going down paths that do not lead to productive answer. Thus, it is somewhat hard to imagine the way that the computer must find the answer using most search techniques. I think that this is one of the first places that we have seen the dramatic differences between machine intelligence and human intelligence.

Rohit Apte

Durell Bouchard

What has made working with the robots so appealing is that the robot is a physical realization of the things that we are studying in class. But this trait also is what makes programming them so difficult. Previously all of the labs have been very simple. It has been possible to write the behavior, and test it by putting the robot in the exact situation in which it will exhibit the behavior. With lab four that process has been made more difficult. It was still fairly simple to write subsumption based code for the robot that would accomplish the task in theory. However, when we drooped the robot into the toy world all sorts of unanticipated problems arose. The most notable was the robot getting stuck on walls because the angle at which it was stuck, none of it's sensors knew that there was a wall right in front of it. If that sort of thing happens with a restricted toy world I can only imagine the sort of problems would arise from trying to make a robot that operates in the real world.

Brianne Brown

Grace Chou

Dan Crown

Heuristic search algorithms give searching algorithms a deeper level than just using brute force to examine all possibilities until the goal node is found. They bring to mind the searches of pre-sorted binary trees, with which they share some similarities. In these cases, the value at the left child is less than the parent node, and the value at the right child is greater. In this case, the evalutation function is just a comparison of the values at each node and the value the algorithm is searching for. Real heuristic searching algorithms are a generalization of this, something which can be performed on objects other than numbers.

This does, however, present us with a problem we have seen earlier with genetic algorithms. What constitutes a good fitness, or, with heuristic search algorithms, evaluation function? In some cases, it is almost impossible to find an appropriate function. Some events simply don't have a conclusive "better" next step, let alone a progression of next steps that will lead closer and closer to the goal. In other cases, it may seem very simple. If we are programming a robot to find a wall and follow it, a good evaluation function would probably choose the step that brings the robot closest to the wall next. But, as Nilsson points out, this might not be the best choice, in which case we would still find ourselves going in completely the wrong direction. So even though heuristic search algorithms do provide some extra depth to blind searches, they are far from perfect, and may not help at all in the majority of cases.

Renee Findley

In Chapter 10, Nilsson describes the ideas behind agents that plan, and how the search methods within previous chapters, normally fail unless placed into modified searches. Each of these search methods, island search, hierarchial search, are sort of baby step searches in the sense/plan/act cycle.

This is because of the problems encountered with interleaved planning. Interleaved planning states that a programmer will design a robot that will do the following things, (implemented by graph search, we'll say for simplicity), unless something bad happens. To quote from the book, the trouble is considered something that should be kept marginal.

Difficulties in programming though, by Nilsson's own admission, and problems in the sense/plan/act cycle, are rather frequent.

The other method of robot planning is called improvisation. This method assumes that there is no real right way, since so much can go wrong.

What I'm curious is how to design an agent based on the improvisational method that is aware of a goal, but not necessarily of any way to achieve it. Is it based on a subsumption kind of architecture when it comes to decisions as it 'constantly redecides' what it will have to do as trouble arises, and if so how different is it from a well-trained S-R model at a basic level? Also, in a more controlled environment with limited abilities and a simplistic goal, how different is it in actual execution or performance from interleaved planning?

Scott Goldstein

Several things about this week's work confused me. I am not quite sure as to how the search algorithms we were examining would actually be applied. I wonder why we even bothered learning the less algorithms, when it is known that there is a superior one. Why use deprecated methods, when a better one exists? Even so, the book's explanations are fairly opaque. The beginning of Ch. 7 talked about the impossibility of a completely preplanned machine, since the programming of every possible situation would take an obscenely large amount of memory. If this is the case, then the only way to get a robot to adapt is to make sure it can plan. I do not really understand how the search algorithms we are using will help it make a useful plan in accomplishing its task.

The lab is an interesting exercise. The question that I have been developing is how to get the robot to know which way to turn to get away from the wall. That is the base of our motion system, when it hits the wall, it backs up, and turns around and then goes forward. Would it be possible to do this sort of thing with a neural net? I am having trouble figuring out what action the robot needs to make in order to get around and away from the various obstacles.

Maria Hristova

Agata Jose-Ivanina

I am still confused about genetic algorithms. I don't understand what exactly is the goal: to find an individual who will fit perfectly, or to make sure that the average individual will come up with a better solution? It seems that it is very easy to lose the perfect individual and never to get it again as mutation is not very common.

Archana Joshee

We spent most of the time last week discussing various search techniques. The blind search techniques were easy to follow. My confusion about the iterative deepening method was cleared by Thursday's lecture. After looking at the heuristically informed and the optimal search methods, we talked about how A* is the most efficient method. I was just wondering under what circumstances, it is the most efficient and if there are conditions under which the other methods are more efficient.

Kip Lewis

The recent in-class lectures and some of the textbook chapters have dealt with state based search techniques. Many different search techniques were explained, and it was usually clear how the various techniques varied in method. What was not usually clear, however, was the different advantages of each one. For instance, while it was clear that a breadth first search would find the optimal path, it was not clear whether or not their was any advantage gained by doing a depth first search rather than a breadth first. Likewise, it was more or less clear how an iterative depth first search worked, but it was very unclear as to why one would ever use that method over a breadth first search.

It's apparent that a state based search technique is a form of planning. One makes a representation of one's game/world with all the variables of your game/world (which may be three blocks and their locations or may be the 9 squares on tic-tac-toe board). You make the current state of your world be the initial node in your search tree, and then from there you construct every successive state that your world can move to. Assuming you have an eventual goal state in mind for your world or game, then you can search for that state in the tree. I have a hard time imagining this method working for planning in the world we live in, because every current state of the world seems to have an infinite number of possible successor states. Thus, it would be impossible to traverse the search tree to find your goal state.

Creence Lin

When we talked about searching and the robot getting from one corner of a room to another in the shortest distance while avoiding obstacles, it made me think about a show on the Discovery channel about octupi (sp? as in plural of octupus). The show was questioning the intelligence of an octupus. An octupus can actually zig-zag across a large area of the sea by feeling the region with its tentacles. Then when it gets to the end of the region or wherever it wants to go, it can actually travel back to its starting point in the shortest distance. I suppose this could be like Elman networks a little bit, but I really thought of it more this week. Like the robot in the subsumption architechture example as well as the ones we play with in lab and in the room example, an octupus has some sense of light and dark (light sensor), but not good vision. It's interesting to think of where algorithms for artificial intelligence might come from. If someone put me in a room with a lamp and I closed my eyes and after groping around had to walk the shortest distance to the light (avoiding objects) I'd probably be able to do for a small area but not a large one (ie. if the room was the size of Philly). I wonder if the octupus "reasons" the same way as the robot in the room.

Martin Lukac

This week was pretty much a review for me. We covered all the searches in data structues. What really interested me was the A* search algorithm. I had seen the shortest path algorithm before, but i had never seen it used with the estimates of the distances.

For the lab that was ue this week, we discovered something really interesting. We were able to get our robot to find the light using 3 simple consise behaviors with the subsumption. I had originally thought that the fewer the behaviors than the faster the robot would be able to get to where it was going. We discovered that the simpler and the more (not fewer and more complex) of each functions there are, the faster the robot seemed to be able to find the light. This is because the more inputs situations that you create reactions for, the better prepared the robot is. It will probbaly achieve the goal both ways, but it just seems better to cover more of the situations.

One thing you should warn us about in the future is that the IR sensors register direct light from any distance as something being pressed right against them.

Reshma Menghani

Lab has been unbelievably interesting yet challenging this week. Never before have my partner and I spent so much time on lab. The lab focuses on the concept of subsumption architecture.

The readings for this week have been quite different from the lab. It is somewhat of a reiteration of introduction of data structures. Yet a new issue brought up in this class or at least more emphasized is the issue of space.

I think that from all our readings for this week, I've learned that there are obviously certain advantages of using one particular search over another which is emphasized in the different parts of the reading. From this, one could basically say that it depends on the task and the size of the state space graph. Some assure us the minimum length to a given goal whereas others do not. What bewilders me is that how time can be more important than space? Likewise how can space be more important than time? How just by looking at the task and the state space graph can one make such a judgement.

Todd Miller

It's suprising that the basic search algorithm has so many variations. However, none of them 'feel like' the way most people find the shortest path -- more like how people would /verify/ it. In this, a nondeterministic machine with two passes -- best guess and then verify -- would more closely approximate how people work. The human brain is hard-wired for pattern recognition, and a great deal of processing is done on visual input before it really gets into the rest of the brain; it seems like this combination may have something to do with how we can just 'see' shortest paths. However, there is clearly a limit -- different from person to person -- on how complex the graph can be before the shortest path is 'non-obvious.' Might this be a restriction on the parallelism of the brain?

A sense/plan/act scheme doesn't seem to too closely mimic how people work, and, from my reading elsewhere, tends not to produce terribly effective 'bots -- they spend too much time planning. Goal-oriented subsumption certainly seems closer to nature, in that many activities in getting from here to the light are subconcious -- walking, turning, sensing walls, etc, aren't (don't seem to be) handled in the planning concious phase. For the most part, if the goal is still 'in sight' when encountering an obstacle, no decision-making is necessary to continue toward it. It may interesting to experiment with scale/zone-based planning, which is how most people handle things. That is, in the canonical BMC->HC example, most people will split it into several phases: how do I exit the room? how do I exit the building? -- each exit gives a larger zone/scale in which to work -- and now some decision making is necessary, bus or car or walk, but the tree is small, when only considering BMC->HC rather than BMC->room in HC*. At any rate, once off the roads, the domain shrinks again, to HC->building, then to building->room.

For zone-based planning, I was thinking about adapting the map->search graph algorithm. Basically, you only need to subsume the pt a to b behavior(s) when crossing zone boundaries. (Incidentally, if you want, you can do this recursively until the zone crossing is accomplished by moving in a straight line.) This is most useful for incomplete-knowledge situations, where you can see, for instance, the entrance into a box, but not the exit or the inside; exiting the box would be a zone-crossing and compel the bot to consider more than the local area for its next destination. In a way, I suppose, this is similar to what heurestic-aided searches do, in that the heurestic, AFAIK, isn't and can't be usefully generated from local information.

* The bus/car/walk solutions are presumambly weighted by time and possibility. Where they end up related to the final goal can be heurestically aproximated and incorporated into the weight. In general, the smaller scale decisions don't affect the larger to such an extent as to push you out of the 'acceptable error' range for optimality.

I've been considering the question of analyzing GAs. After some thought, it's become clear that there are two types of GAs -- those which have nonalgorithmic genomes, and those whose genomes /are/ algorithmic. The goal of analyzing a solution is to gain algorithmic insight; clearly, then, a nonalgorithmic genome will have no analysis. The analysis has already been performed in the selection of the fitness function. Clearly, an algorithmic genome can be analyzed the same way as any algorithm. Regarding the stock-picking example, my contention is that the genome must be algorithmic, as it must /predict/ the movement of the stock(s); it seems like you're contending that the fitness function could be executing some sort of parameterized prediction function/algorithm.* In this case, the 'analysis' of the genome is fully characterized by the decisions made in choosing the fitness function, and the degree to which (general -- nonalgorithmic) insight is gained from this 'anaylsis' is proportional to the insight of the fitness function and its generality*. If the fitness function is 'purely parametric,' e.g. a weighted sum of inputs, then the problem is one of optimization, to which other methods could be applied. (And the insight gained would be the same -- oh, hey, the biggest factor on tommorow's stock price is, suprise!, today's!)

Maria Pace

It's amazing how the subsumption architecture actually works better than the standard algorithmic approach. One would think that the seemingly more complex modeling and planning algorithm would result in the greatest "intelligence". A robot can easily employ a search algorithm such as A* to quickly find the optimal solution to its given problem. However, a robot that can only plan and model would be completely stupid in a dynamic environment. The subsumption approach, though it is built of very simple layers of behavior, allows for the robot to adapt easily to ever-changing surroundings. Thanks to subsumption architecture, my group's robot is so intelligent at this point that it can repeatedly bump into the same object AND find the light!

Heather Palmeter

The past couple of weeks the robot lab has become much more interesting. You can only watch a robot bumping into walls for so long, saying to yourself, "Boy, is he intelligent!". I realize that the behavior we are programming now isn't really that much more complicated, but the code we are creating seems to be utilizing more complex ideas, and I can visualize how these techniques could be utilized in the creation of more complex behaviors.

Class discussion has been dominated by search algorithms. Now, in the back of my mind I'm certain I understood that there were many different techniques that could be utilized to search a graph but I don't think it really hit home exactly how many until we began discussing them in class. Of course, when there are so many different ways to accomplish one task, it stands to reason that the differences between the many methods will be rather subtle. It seems to me that this was the cause of much of the confusion that arose in class. Another thing I would like to state, simply for the record, is that search algorithms that aren't optimal really annoy me. That's another thing that I learned in class over the past week. I know that each search method has it's own merits but I tend to lose track of the pro's in light of all of the ways that the algorithm can be improved. Just goes to show you that you learn something about yourself everyday.

Megan Rutter

Brian Simms

This past week we learned about searches. I guess I found the iterative deepening a little pointless, especially considering the fact that it has about the same Big O as Depth and Breadth first. I'm assuming that it is just another one of the basic searches that can be used depending on the expected info.

Other than searching, we worked on our robot for a while. Subsumption is a good thing. It seems to allow slightly easier programming than regular iterative or recursive methods, and our group was able to nail down a bunch of bugs. The only real problem left is the fact thhat the IR sensors go absolutely crazy when they hit a light source, such as the lamp we're supposed to be seeking in lab. Unfortunately, there is no easy way around this, other than getting a light source that throws off less IR output. The IR sensors work very well in every regard other than this.

Matthew Spigleman

Andreas Voellmy

Nicholas Yee

Talking about these searches reminded me about recursive tree traversals and prefix/infix/postfix notation in CS206 (anyone remember those days? J). I'm glad the confusion about iterative depth-first search was cleared up.

On the lab front, we discovered to our dismay that our IR triggered wall follower was distracted by light because normal light is detected by the IR sensors (in retrospect ­ duh) and the IR sensors cannot differentiate between a solid object and a beam of light. So we took the IR sensors off, and as we were fiddling with the code, we noticed that the wall following behavior was not necessary. The way we worked our bump and wander behavior allowed our robot to get to the goal without a separate wall-following behavior.

It took a while to get there, but when we did, it was really satisfying to watch the robot, and we also learned all about the fancy lighting functions in the room itself (having had to turn the lights off and on many times).

Back to CS 372 Course Materials | Back to Written Work Main Page