Transcript
Many of you, maybe most of you, will never have to work another search problem by hand in your natural life. Others Others will want to take another run out of it right out of it on the final. I've been much criticized for this way of doing grading in the class, but the way I look at it is that um the relationship between students and instructors ought to be less adversarial than it used to be in the good old days when I was when I was a student. I especially remember a examination we took all of us took on Rayleigh scattering. That was 803, I think. And back in the old days we had to take four physics courses, not just two, and we had to take four math courses, not just two, back in the days when well, I was going to say men were men, but most of us were men in those days.
I think we only had 20 women in our class. Anyway, we had a course we had a quiz on Rayleigh scattering. And I thought, well, this is pretty hard. And then um I got my quiz back. 26. I thought, well, I've been found out. I'm going to flunk out. My father will make me go to law school. I'll never attract anyone to marry. Horrible things will happen. Then the instructor announced class average was 18. I was two standard deviations above that. They gave us the same They gave us the same exam 2 weeks later, and accounts vary. Some people say that the class average went down. Anyway, today we're going to study some stuff.
We're going to study some stuff that will make it possible for you to understand how uh you can do that computation in just a couple of seconds even with the delays introduced by the uh by the redrawing. Now, this particular program I'm not real sure, and I don't have a proof, but I think it will take more than the lifetime of the universe to find a four-color to find a legitimate coloring of the continental United States. But by the end of the next class, you'll see how to do that lickety-split in just a couple of seconds even with the display delays. Now, we could, of course, do this in two ways.
One way is I could start off by saying, "Let's C be a constraint satisfaction problem." and just give you the the result. And anybody can do that. Uh that's great. Uh and you needed learn some stuff that way. But uh there are some things that you need to learn, I think, a different way. And And And that different way involves my telling you the story of how it all came to be. Uh this is a new field, pretty much, and therefore I know most of the people in it, and I know all of the people who did the work that I'm going to tell you about today. And I'm going to tell you a little bit about the struggle for coming up with the ideas that um led to the um led to one of the most powerful uh one of the most powerful methods you'll learn about in the subject.
It all has to do originally with an attempt to make a computer capable of seeing. And everybody said to themselves, "Well, let's start with seeing simple things like children's blocks." And so Adolfo Guzman, a graduate student of Marvin Minsky's, was charged with the summer project, which led to his PhD thesis, of writing a program that could look at a line drawing and determine how many objects are in the line drawing. So, for example, there behind my outline is a line drawing. And you know instantly or you believe instantly that there are two objects there even though in some deep sense it's ambiguous.
There are all sorts of ways that you could uh through trickery arrange something with even seven objects that look that way. But most most people would say there are two objects. So, Guzman set about the problem of figuring out how to do that, and then his work was followed up by Dave Huffman, and his work was followed up by Dave Waltz, and his work was followed up by Jean Freuder, who's not listed there quite yet. And I'm going to tell you a little bit of story of how that all happened. So, Guzman um took a lot of pictures. He went to Boston Baby, the precursor to Toys R Us, uh purchased a large block set on a government contract, and to went about the business of taking a lot of pictures of them so he could have feel for the domain.
And eventually he decided that he could build a program that could determine that there are two objects here by using the lines as as as quanta of evidence about which faces belong together in an object. So, he said after studying these for a long time that these drawings tend to have a lot of arrow-type junctions and a lot of fork-type junctions. And when you see a an arrow, it's a little bit of evidence that the objects on either side of the shaft are the same the face on either side of the shaft belong to the same object. And over here with the fork-type junction, it suggests that the pairwise three pairs of faces seem to belong to the same object.
So, with that idea, he could come back to a drawing like this and start decorating it with these so-called links, these quanta of evidence that faces belong to the same object. And if I've done it right, you get something that looks like so. It's a little hard to to see what's going on on the drawing itself, so let me number these. Now, I have an easier to deal with picture. There are two links between one and two and one and three, one link between two and three, one between two and four, two here, two here, and one each from all of these. So, Guzman produces this evidence for how the problem ought to be solved, and then he begins to think about various ways of using the evidence.
So, he could and did decide that one link is enough to presume that the faces belong to the same object. And you can see that that's a little bit too liberal. Because that says that the whole thing is just one object. So, Guzman rejected the one link the one link theory and went to the two link theory. And the two link theory says, "Oh, well, let's see. If we insist that two links have to be there before we are willing to decide that it's the same object, then these three faces are pulled together into one object. These three are pulled together into one object. But alas, seven doesn't share two links with anything, so it's left dangling out there.
So, plainly the two link theory is too conservative. So, that, as you would soon discover in any Euroc project, would lead you to the third theory, which is two links repeated. So, now that we've formed these super regions, we can come back and say we'll merge super regions if they're connected together by two or more links. So, nothing new happens up here, but this super region is joined to seven by more than by two or more links. So, it pulls everything together like so. So, that worked fine. Well, it didn't work fine. There were lots of examples of situations where it didn't work in nonsensical in in in situations that were considered nonsensical by us humans because they just didn't didn't seem it seemed silly the kind of conclusions that it reached.
Uh so, when Guzman presented this work in his PhD thesis defense, um it said uh and who knows if it's true, but it said that Marvin Minsky thought it was great work, and we should make him a professor. It happens that Dave Huffman was also on the committee and said that it was ad hoc, and the thesis should be rejected. So, we had two polar opposites of impressions there. Dave Huffman, by the way, you've heard that name before, I imagine. It's the It's the guy who invented Huffman coding as a term paper in a information theory course taught by Bob Fano. He got an A, they say. So, Huffman didn't like it.
He thought it was a little bit too ad hoc. It was too heuristic. It didn't take advantage of anything we might know about physics. And so, people began to say, "Well, why does it work, and when does it not work?" And that's just about the best question you can answer in a situation like this. And by playing with some more of Guzman's pictures and reflecting on them, it turned out that it worked because the world is full of three-face junctions. Or let say three phase vertices because they're out there in the world. We'll reserve the word junction for something else. And three phase vertices generally project into either an arrow or a fork.
So Guzman's whole program worked on the weak backward conclusion that if you see one of those, it probably came from one of these. So this is in the drawing, that's in the world. So by a process that's neither deduction nor induction, but rather abduction you see one of those guys and you say, well they often come from three phase vertices in the world. So if you see one, it probably came from a three phase vertex in the world. That's abduction. So once uh Huffman saw all that, being a mathematician he began to think about how one might develop a different and better theory. But we have to recognize that all of this work started off with the efforts of Guzman who was an experimentalist.
And Huffman was a mathematician. So naturally they approached the problem differently. So Huffman says I'm not going to concern myself too much with the actual problem that Guzman was trying to solve. Rather, I'm going to work in a very simple world which I can deal with mathematically. So he decided that he was going to work in a world which had several characteristics. Characteristic number one was that the world would be presented in general position. That is to say no screw cases. So if you see a cube it's going to look like this. And it's not going to look like this. So that's out and this is in.
And the idea here is that that's not general position because if you perturb your point of view a little bit, you'll change those T junctions into forks and arrows. So we don't have to deal with those kinds of weird uh kinds of cases. So this that's presumption number one. Presumption number two is that we're going to be dealing with a world that's trihedral. That means all vertices out there are going to be formed from three planes. So we're going to have the intersection of three planes. So how many kinds of junctions can you see if the world is composed that way is the question that Huffman set himself upon.
The next assumption was that there were going to be four kinds of lines. You see Guzman only recognized two kinds of lines, lines that have a link and lines that don't have a link. And they don't have very much to do with the physical world. So Huffman says, I want to get the constraint out of the physical world. So I'm going to deal with four kinds of lines. Concave convex and boundary. All right? So each of those kinds of lines is going to be is going to have its own notation. We'll call the convex lines plus the concave lines minus and the boundary lines are going to get an arrow on them depending on which side of the object you would see uh uh which side you would see the object if you walk along the direction of this little arrow.
Let me Yeah, sorry. Thank you. So concave, convex, and boundary. Thank you. So this down here that's a concave line. And that would get a minus label. Oh, I don't know. Uh these lines you're seeing here if there were stuff behind them instead of me, then all of those would be convex lines. Many times you see a boundary line. For example, now you don't see both sides of that line down here at the bottom, so that's a boundary line and the arrow would point in that direction so as to keep the stuff of the object on the right as you walk along. It's a kind of mathematical convention. So three kinds of lines, four kinds of labels, and there's some things left out.
That's because Huffman wanted to keep his problem simple, something he can manage by hand. What's left out? Cracks are left out, shadows are left out. There's nothing to do There's presumption that there's no nothing of of interest here with respect to that. So let's have a little vocabulary before I uh bef- before I go on and I'll try to stick to it. But there's the stuff out there and that consists of vertices and edges. And over here on the blackboard we'll have junctions and lines. And I'll try to stick to that vocabulary, all right? Yes, Christopher? Didn't you say there were four types of lines?
Yeah, there are four kinds of What I What Question is, didn't I say there are four kinds of lines? There are three kinds of lines, but since we can label a boundary line in either direction, we have four labels, okay? All right. Depends on which side of the object the stuff is on and that will be clear I clear I think as soon as I do an example. So one, two three assumptions, a little bit of vocabulary. So we have um the possibility of making a complete catalog. This is so simple, here we have the possibility of making a complete catalog of all the ways that lines can come together to form a junction with respect to these four labels.
Now at first you might say, oh my god that will take a couple of years. Uh but maybe it won't take a couple of years and in the end uh to um perhaps your surprise you discover that there are only 18 ways to arrange the labels around a junction in this world. Everything else is is excluded. If you have something that's not in the set we're going to produce now it can't be built with trihedral vertices. So I've listed up there six L's five forks four T's and three arrows. Let's see if I can figure out why there are those 18 and nothing else. Well if we have three phase three vertices coming together that means there are eight octants, right?
And the stuff of the object may fill one, two, three, four, five, six, seven, or all eight octants. Now of course, if you fill all eight octants, there's no junction, so we don't consider that case. If we don't fill any of the octants, there's no junction, so we there's no vertex, so we don't consider that case. But if just one of the eight octants is filled with stuff then we can look at it from any of the seven remaining octants. So right now you're looking at it from one of the seven remaining octants. And if I'm not mistaken, you're going to see a fork style junction there, right? And you're going to see a fork style junction in which all of the edges are con- vex.
An unfortunately an unfortunate selection of names because the linguists tell me that we index all of our words by the first phoneme and those have the same first phoneme, so they're easily confused. So here's a a fork style junction and we know that one way that's legitimate for the lines to come in is with four pluses. Now that's not the only way you can see that. And here's another way. There's an L style junction, right? And both of those are boundary lines. And we want to draw the boundary line indicators on there so that if we walk along the arrows, the stuff of the object would be on the right.
So I suppose to make it easier for me to do my drawing, I should look at it this way. And then I would say, well, that has to be a legitimate way of labeling a junction. Are there any more? Well, there's there are seven altogether, but many of them are the same. There is one more that's a little different though. I can hold this guy up like so. And if I'm holding it the right angle for you, you see an arrow style junction, right? Two boundaries and the barb is convex. So in this particular case I've got that. I've got that and I've got a plus there. And that's all there happened to be for the one octant filled with stuff case.
I happen to be able to reverse this though and here's the seven octants filled case, right? So that tells us that it's possible to have a vertex out there in the space that when reduced to a junction on the board deserves three minus labels because all of these that you're seeing now are concave. So, another fork style junction looks like so. And since there's only one octant to look at from, um that completes our analysis of the of the seven octants filled case. Now, we have a couple other possibilities here. We might have five octants filled with stuff. So, that means there are three octants that we can look from.
So, let's suppose that these little chalk pieces are little people. And they're looking at this junction down there where this white object is fused with the table. I'm fusing it with the table cuz I want to consider it to be one object. We can view it from the three objects indicated by those three little chalk pieces and ask ourselves, well, in the in the event that we look at it from those three places, what do we see? And if we look at it from the from the perspective of the piece of purple chalk, I'll have to walk around to be sure, looks like an arrow junction with two concaves and a convex.
Did I get that right? Yep. So, I'm looking at it from this perspective, it's an arrow. This is convex and these two are concave because I fused the paper the the paper box with the with the table. Looking at it from the perspective of this blue guy, let me rotate it so you can have a better understanding of the blue guy, it looks like a concave line and a boundary. So, it's an L. And this one is a boundary and that's concave and by a kind of symmetry we're also going to get that one from the other side, the the third of the three octants. Well, we're off and running, but we still have an awful lot to go and we we could we could manage to deal with it by thinking about this object once again.
Uh but instead of um instead of this situation out here, to turn it around and and look at at this vertex, think about the junctions that it can produce. I think I'll do that for you because you really have to play with this and move it around a little bit to to see how things are going to look. So, let me let me think about how that's going to work out. I know that one of the possibilities is going to look like so. I might as well not hide that from you. It's going to be what happens when there's a little man looking up at the junction. And this one's going to be minus. And now we got two more that are just like that.
They look like so. And you say, oops. You say, aren't those just rotational variants of each other? And the answer is sure. Uh I write them all down because if you get a fork style junction in space, there are three different ways it can be labeled depending on which of the which of the lines you put the the the minus minus label on. So, that takes care of that. And then there's one more of these fork style junctions and that's um plus plus minus that derives from this case. And there appear to be three more of these L style junctions and they look like let's see, plus then plus. I'm having to think this through as I go.
And then and that's it. Well, what about the Ts? Well, in this world the only way you can get a T is if some object is obscuring another object. And if an object is obscuring a line, it can be any line at all. So, that's why the four remaining ones are easy beyond description to label. And of course the cross pieces of the T are all boundary lines with the obscuring object on the right. Now, let's see. We've taken care now of the one, three, five and seven object octants filled cases. What about two, four, and six? Well, it turns out you can have vertices that are made that way, too, but they will have more than three faces.
They have six faces. They'll be like what happens when an object comes together at a point like so. Like that. You can play with it a little bit and see that if you have two, four, or six objects filled with stuff, there are more than three faces, so we're going to ignore those. So, our constraint is going to be a a little more a little more severe than uh would be suggested by the terminology Huffman uses. It's they're going to be trihedral, all right, but they're also going to be three faces. So, we went to a lot of work there, but what have we discovered? We discovered that in this world, this is a complete 100% nothing excluded, nothing else can be there, catalog of all possible ways that junctions can have line labels arranged around them.
There's nothing else in this world. So, that's a very powerful constraint. So, now let's see what we can do with it. This example is usually more fun when the Red Sox are doing better, but they're not at yet, we'll use it anyway. We're going to start with a with an object that looks like home plate. And now I ask you the question, can you build one of those? I don't know. Uh let's give it a shot. We're going to assume that this object is hanging floating in space, so therefore all of these lines around the boundary are boundary lines, like so. Now, that gets us off to a good This is hanging in space, Christian, all right?
You look confused. It's just hanging in space, so all the all the lines around the edges are places where you see only one one one only one side has stuff on it, so. So, that enables us to just quickly run around the periphery and put arrow labels on all those outside lines. Now, we have a lot of arrow style junctions on the boundary. That's commonly the case. So, we can run over to our catalog of all possible labels and we see that if we have an arrow with boundaries on its barbs, there's only one of those. So, we know instantly that there must be a plus on the shaft. So, we can come back here and take all of these arrows here and label them with plus lines on their shafts.
Now, a line can't change its nature along its length. So, if it's a plus line on one end, it's going to be a plus line on the other end. All right? So, what else can we do? Here is in the deep inside is a fork style junction. It's got concave markers con- sorry, convex markers on both of those two lines. So, we go over to our catalog and say, what can we say about it given that there are pluses on two of its lines? Whoop, that means that the third one has to be a plus as well. And now we're done. We've labeled everything except look at this. What about that guy? There's an arrow there's an L style junction with pluses on both of its two lines.
Is there one of those in my catalog? No. Therefore, I haven't passed a necessary condition for constructability in the world that I made. You can't make it. You can't construct it. So, Huffman's ideas give us a way of testing something to see if it's not possible for it to be in this world. If it passes the test, does that mean it's possible? No, it's a necessary but not sufficient condition. Uh this one blue collar occupation. On this one, maybe it will help if we put in another line. For example, we could put in a line like so. You feel better about it now? I don't know. May- let's see. This has to be a plus for the same argument we used on several other arrows before.
That gives us a arrow style junction here with a plus on everything. Is there such a junction label? No. We lose. Doesn't help. You think you can make it, but you can't. I I think You could actually construct it as a 3D object, though. He thinks you can construct it as a 3D object. He thinks you can construct it as a 3D object. Let me show you the next example, Christian. Consider this example. Can you make that? Your intuition is yes, so let's label it. I've already lost. We just boost that up a little bit to make it the situation more clear. So already I've got myself in a situation where I can't label that.
But you feel like you can make it. So what's what's wrong? What's wrong is What Elliot? We haven't obscured or we're assuming that we haven't obscured the concrete of valley. Yeah. From the upper left corner to the Putting a little interpretation on what Elliot has said. If you look at this situation back here, you get a four-faced junction there. So you can make it, but not with three faces. So some of these some of these look like you can make it, but they can't be labeled because you need more than four faces at a junction. And we can carry that idea back here. If you can you can make this okay, but this junction you got two in the back and two here, so it has four faces.
Same idea. All right, so that's that's that's that's Guzman's contribution. That's Huffman's contribution. Huffman was a mathematician, but we wanted to build robots back in those days and neither one of these guys solved the problem of dealing with natural objects with shadows, with cracks, with more than trihedral vertexes in space, and what to do about that. Well, that was a problem that another graduate student, David Waltz, set about to solve. So Waltz decided that he would not be content unless he added cracks, shadows, non-trihedral vertexes. Ah. Yeah, non-trihedral vertexes. And shadow non-trihedral vertexes and light.
These considerations led Waltz to go from four labels to 50 plus because he had to pack a lot of information into each of the labels that he put on a line. What kind of light was on the right? What kind of light was on the left? Maybe it's a crack. Maybe it's a crack that all sorts of considerations. Here we had 18 ways that lines can come together around junctions. That went to thousands of junctions in Waltz's world. So here's Guzman. He writes a program that sort of works. Down below, we have Huffman. Huffman who has a theory, but solves the wrong problem. So here's here comes Waltz and he's trying to solve the right problem with a with a satisfying um theory that has a generalizable principle.
So when we get all through with this, we'll talk about criteria for success and we'll conclude that to have a really successful thing, you need a problem to start with. You need a method that works and you have to show that it works because of some principle. So Guzman had the problem and something that worked. Huffman had a method, which worked on the wrong problem and it's left to Waltz to bring it all together. So Waltz does all of this work and now he has instead of 18 labels he has thousands instead of four line labels he has more than 50. So naturally it becomes difficult to work these by hand.
We were able to work those examples with uh and with with those those Huffman examples by hand. We started with labeling everything on the boundary and worked our way and there's no particular method there, which is easy to work out the puzzle. But um poor Waltz, uh he didn't have that luxury. So he might have uh in a typical scene he might have tens or even hundreds of junctions to label and no easy way of dealing with it. So naturally writes himself a depth-first search program. So here is vertex or rather junction number one. There are many choices for which label can be used on it. And for each of those choices, whatever he's decided junction number two uh is has its own suite of possibilities.
And so it becomes a simple depth-first search problem, right? So in actuality as soon as as soon as Waltz he was my office mate at the time, I can tell you this for a fact. As soon as he wrote this program, he kept looking over at the computer. They were big in those days. They all had lights. So he looked over the computer to see if the lights were still blinking because he'd start this depth-first search program up and nothing would happen. He thought the computer had crashed. Nothing happened. Why did nothing happen? Because the search space is exponential and much too big for an ordinary computer or maybe even an ordinary universe.
So Waltz has to do something else. He has to come up with a new method for using all of these labels that he's that he's after about a year and a half's worth of hard work with lots of paper on his desk and little blocks. After a year and a half hard work getting all these junction labels figured out, he he then has to come up with a method for figuring out how to use them. And so we don't know whether to think his big biggest contribution was that label set or his method. And probably both deserve about equal billing. Oh, I don't know how to how to explain what Waltz did. Well, one way is to do an example.
And I think I will hazard an example. Ah, god. Let's see. Let me find some space. I think I'm reduced to going over here, but that'll be convenient since the line labels are here. Here's my example. I say how can I give you just partial a part of a picture? Well, I can assume you can assume I'm looking at at this through a window. So the edges of the window form boundary lines and they exert no constraint whatsoever on what's behind them. So this is a legitimate drawing to have to think about. By the way, is this ambiguous or do you get a firm sense that there's an a a unique interpretation of all those lines?
I think it's there's a unique interpretation of all those lines. What I'm what I'm going to do is I'm actually going to solve this problem using Huffman's labels, but Waltz's method because I can't simulate on the blackboard something with with with 50 line types and thousands of line junctions. So I'm going to use Huffman set to demonstrate Waltz's algorithm. So Waltz's algorithm involves starting out by plopping on some junction all of the possible things that can all of the possible labels that the the answer has to be drawn from. So let me number these in the order that we're going to visit them.
Like so. And so far I've just put down the three fork options that are resident on that first um junction. And I have to uh take note of exactly what they do with the lines that come out of the junction. So let's see. I'll just copy them down. One possibility is this one. Another possibility is this one. And another possibility is plus plus minus. Oops, I've got plus plus No, that's right. So is that right so far? I've All I've done is copy the the junction labeling from my library. And at this point uh Waltz's algorithm says there's nothing else to do but go on to junction number two. And unfortunately, sadly, there are lots of labelings that have to be considered on number two.
Six of them. 1 2 3 4 5 6. So, one of them looks like that. Another one looks like that. One of them is plus here, arrow in. Another one is plus here. Arrow out. Another one is um minus here arrow down and minus here, arrow up. I think I've copied those all right. But now, having copied those down, Waltz's Waltz's algorithm looks around at the neighboring junctions and says "Are any of the things that I just placed on junction two disallowed by what I've already placed on a neighboring junction?" So, it looks over here in step number two and it sees that these three arrows require the line that joins junctions one and two to be either minus or plus.
Right? So, of the six possibilities, I can only keep the ones that are likewise content to put a plus on that line that joins the two. So, that means that the influence flowing from junction one eliminates that one eliminates that one. Eliminates that one and eliminates that one. So, half of them are gone. All of the ones that try to put a boundary line on that line between one and two are disallowed. All right? Now, likewise, we could say, "Well, of the remaining ones, do they restrict what I can do at junction one?" So, let's see. Here's a minus and here's a plus. So, both of those both all of these possibilities over here are still alive.
So, now uh continuing on we have to see what we can do at junction three. These are arrow labels again. So, we have to copy exactly the same label set as we had before. And now, we look down on we look down at junction two and say, "What what does that tell me about the three that I've just placed?" If we look up from junction two to see what kind of constraints it puts on here, we have this one alive and this one alive. I guess we've eliminated four of the six. So, we have these two alive and they both put boundary lines. I think I must have had this boundary line wrong, right? No, that's right.
Oh, yes, I see. Plus this one goes Hang on a second. You let me do something wrong. So, plus is out and this one goes up. This minus goes up. Oh, yes. I'm I'm too hasty and uncertain about what I was doing. So, let's see. This guy has a boundary going down and this guy has a boundary going up. All of the others have been eliminated. So, that means that something that tries to put a concave line there is gone. And something that tries to put a a plus line there is gone. So, the influence flowing up in this direction in the third step eliminates that guy and eliminates that guy leaving only this guy.
But now, the thing I was worried about is we have to also at this point go down to two and see if there's any further constraint on what can be what can survive down there based on what has happened over here at junction three. Now, let's see. This one goes up, which is compatible with the survivor. But this one goes down, which is not compatible with the survivor. So, when I bring this down uh in step three, this guy is eliminated. So, now I'm I'm down to just one interpretation for what can be going on at vertex number two and one interpretation for vertex number three. Now, let's see. This can propagate.
So, now that I've made a change on vertex number two, I have to also see if that causes a change at vertex number one. So, it's propagating through. And now, I can see that the only possibility here is a minus the label that's coming down from our survivor. So, that eliminates these two. Phew. It's hard to do this by hand, but I've got three of the four things labeled. And e- even with just three of the four labeled, I'm down to a single interpretation for all of the junctions in the lines between them. So, there's one left. We have to deal with that fork vertex. We better deal with it because for all we know, this is not a legal not a legal drawing in this world.
We have five fork vertices to place. But you know what? I don't have to draw much here because I know that this is forced to be a plus now and this is forced to be a plus now and there's only one fork vertex with any pluses on it at all. So, now I can come through and say, "Well, the only possible survivor is this one. These are gone. And now, I have an interpretation for all of the junctions and I see that the winners are this one and this one and this one and this one. So, I've got a unique interpretation. This line is convex, this one is concave, this is a boundary, that's a boundary and this line is convex and that's convex.
Phew. Now that's a lot of work. So, I better check and make sure I got it right. You'd like to see this demonstrated make sure I haven't made a mistake. I'm sure I'm sure of that, right? Let's see. That it? So, each of the places where a line is obscured has four possibilities labeled E. The arrow junctions are labeled A. The forks, there are five of them at the fork junction, five. So, let's just step through here and see what happens. Boom, I got it. I did do it right. So, let's try some more. What do you think will happen with this one? Unique solution? It stopped. Bug in my program? Unthinkable.
What's happened? It is genuinely ambiguous. It can be something hanging down from the ceiling or it could be something that we can think of as a step going up from left to right. Let's look at something more complicated. You think it'll work? Not enough constraint for us to figure that one out. It's equally ambiguous but a little bit larger example. What about this one? You have it the stuff is creeping up from the lower left up to the upper right. Yeah, bingo. It worked. It's unambiguous. It's variation on the same theme we had before, but let me just for fun take these two lines out. What do you think will happen now?
Seems to be doing just fine until it hits the upper right-hand corner and discovers it can't label stuff. So, it propagates back down and what looked okay in the lower left is no good after all. So, these results are kind of consistent with what we humans do when we look at these kinds of things. So, it's very likely that we in our heads do have some constraint propagation apparatus that we use in vision. But putting that aside, uh we can think about other kinds of intelligence different from human that might use this kind of mechanism to solve problems that involve a lot of constraint in finding a solution.
So, here uh we saw the constraint propagation activity at work in line drawing analysis, but next time what we're going to do is we're going to see it at work in map coloring and who cares about map coloring? People who do scheduling because that turns out to be the same problem.