[MUSIC] Moving on I wanted to give some examples of what are maybe the core fundamental problems or some of the core fundamental problems in AI. Maybe to give it just, if nothing else a sense of the space? So Graph Search is perhaps, if you took an AI class, this would be the first thing you would be taught. In fact, you might even meet outside of an AI class, but it's a Santa Claus. So there's classic problem with, okay, I have. You may have found yourself in this situation. You have a boat and you have a cabbage and a wolf and a goat. I know I've been there myself. And the boat will only go across the river if you're in it. And the boat is only large enough to take one cabbage or one wolf or one goat, but no pair of them at a time. You have a very peculiar boat. And you'd like to get all of three of the items to the other side of the river. The situation I've shown in the bottom here. Okay, however, if you leave the goat alone with the cabbage the goat will eat the cabbage. And by the way, that's a bad thing, you don't want that to happen. And if you leave the wolf alone with a goat, the wolf will eat the goat. And again, in case you didn't know that that's a bad thing, you don't want that to happen. And so you need to figure out some way to fairing these things across, okay? So this is the sort of like logic puzzle that you might see in the idea of how could we solve this with the computer that would give us some idea about. What intelligence is because solving this problem is an example of intelligence. So the way to do is view these as sort of states of the world and think about the different actions I could take. So I could for instance ferry across the cabbage. Or I could ferry across the goat or the wolf. Or I can go across on my own and leave the three sitting there on the other side of the bank all by themselves, right? In this particular situation three of those will result in bad things happening because I've left the goat alone with either its food source or its nemesis. So I don't have to consider those. I can just consider this one thing that's left. But from there, I have some options I could. So in this case I've gone across with the goat and I've left the wolf in the cabbage on the other side because the wolf is is a carnivore so this is okay. And I could then for instance go back with the goat, put me back in the original position, or I could go back alone. Yep, and if I go back alone, then I have the choice of what I could do then okay? And this keeps branching into a variety of different situations that we represented the computer. And I'm looking for essentially a path through these situations, ones that are legal, that ends up in this final situation I'm interested in. Now, this is a very simple problem, there only sixteen possible states that so these situations. And so the search doesn't take much time but it gives you the general idea. That's a Graph Search problem. You can use it to solve the Rubik's Cube, for example. So first one is 16 states, this one has 43 quintillion states. So clearly, I'm not going to represent all of those states inside of a computer. Even the computers are big we can't represent 43 quintillion of anything. But you can imagine here's a cube and then I'm going to move it this way, I can move this way. And after that I move this way, this way, and go through the whole thing. And we've designed algorithms that can figure out maybe better ways of going through this tree or prune off certain. Now, that thing couldn't possibly help in such like that. So that's Graph Search. Graph Search sort of if you're interested in Graph Search it's related a star search is maybe the fundamental algorithm here. It's related to a number of other sort of research topics in this area. It's used in things like driving directions. So you get perhaps VLSI Layout, this is the layout of circuits on a chip. You try to figure out, well, I want an adder and a multiplier? And so they also met chip and then these have to communicate this way. How do I lay those little pads out on my chip so that it all fits in some piece of silicon? Assembly sequencing and factory protein design. I want to figure out how this molecule, what is conformational search could be so they could fit into this molecule for drug design, a robotic path planning, things like that. Simple projects would be things like Checkers, example or Minesweeper. From a different idea, maybe own interested in robotics. So let's take an example in robotics. Well, I've simplified a robotics problem way down. So here I have a robot. And the robot can be one of eight different positions in my building, let's say. The gray lines just represent the boundaries between the positions but the black lines represent walls, okay? So here are some problems in robotics just to give you a flavor of what might be interested in. So here's example there's that robot and then that robot senses something, okay? So maybe the robot senses what walls are around it, okay? So this is a representation of it sensing, is there a wall of the north, is there a wall of the east, the west, the south? This could be more general to general sensing robot. And then it moves, okay? So it moves along and then it gets another sensing, okay? And then it moves again and then it moves again and then if I like it moves again, okay? So this is what's happening in the world. But the problem is usually I only see the sensing sequence and I'd like to reconstruct where the robot was. Or at least know where the robot is right now. So this is what's called a localization problem. I have a map of the world and what I'd like to do is based on the sensing readings I've seen so far figure out where the robot could be, all right? But the problem is those sensors aren't actually perfect. So there's some chance that the sensor report the wrong thing, okay? So now, if you look at this sequence here, there's actually no sequence of moves that were generated that sequence of sensor readings exactly. And that's because those sensor readings have been corrupted by noise and I need to be able to process this. So I don't know for certain where I am, but I need some probability distribution over where I am that describes my uncertainty as it's related to those noisy measurements that made about the world. So a way one example of how this might work, a very simple examples. Well, if I know I started in this northwest corner, right? Then if I move I can say, well, there's some chance when I move. >> By the way, when I move, there maybe some error, too. When I move there's some chance I'd end up over here or here and then given that end up in he's those positions, I said, what's the chance? I would have seen this particular wall of configuration. And the answer is you want to see it in any of them but it's most likely in sort of the southwest corner there, right? So we place more probability distribution there. And then I continue this as I move and I sense things, I update a distribution over where I think I am using the laws of probability and by I mean, of course the robot. And then in the end, I have some distribution for instance like this. Okay, [COUGH] this the sort of models that are used or I just described is basically what's called a Hidden Markov Model. It's also used in genomics and it's used in speech recognition and a wide variety of other things. Most of robotics and a lot of AI now deals with probability and statistics. Another example that I just showed you the Kalman Filter, if you're familiar with control theory. These things are used in obviously robot navigation and DNA analysis. As I said, for Hidden Markov Models, video analysis, speech-to-text, protein folding, all these sorts of things rely on that kind of analysis there through probabilistic methods.
