3-3. Informed Search

The answer is that we’re not done yet, because the algorithm works by doing the goals tests when we take a path off the frontier not when we put a path on the frontier. Instead, we just continue in the normal way and choose the node on the frontier which has the lowest value. And … Read more

And the answer is that we expand this path, the Fagaras, next because its F total, 415, is less than all the other paths in the frontier.

So we expand this node, giving us two more paths. This one with an f-value of 417 and this one with an f-value of 526. And the question, again, which path are we going to expand next?

The answer is we expand this path next because its total, 413, is less than all the other ones on the frontier. Although only slightly less than the 415 for this path.

Let’s go ahead and expand this node now. So we’re going to add three paths. This one has a path cost of 291. And an estimated distance to the goal of 380 for a total of 671. This one has a path costs of 239 and an estimated distance of 176 for a total of … Read more

The answer is that we select this path first, the one from Arad to Sibiu, because it has the smallest value, 393, of the sum f = g + h.

Our description of the algorithm has talked about paths in the state space. I want to say a little bit now about how to implement that in terms of a computer algorithm. We talk about paths, but we want to implement that in some ways and the implementation we talk about nodes. A node is … Read more

A* Search works by always expanding the path that has a minimum value of the function f, which is defined as a sum of the g and h components. Now, the function g of a path, it’s just the path cost. And the function h of a path is equal to the h value of … Read more

Now, we’re trying to build an artificial intelligence that can solve problems like this all on it’s own. You can see that the search algorithms do a great job of finding solutions to problems like this. But you might complain that in order for the search algorithms to work, we had to provide it with … Read more

h1 is admissible because every tile that’s in the wrong position must be moved at least once to get into the right position. So, h1 never overestimates. How about h2? h2 is also admissible because every tile in the wrong position can be moved closer to the correct position, no faster than one space per … Read more

I want to introduce one more problem that can be solved with search techniques. And this is a sliding blocks puzzle called the 15 Puzzle. You may have seen something like this. So there are a bunch of little squares or blocks or tiles and you can slide them around, and the goal is to … Read more

The answer is that the number of states is the crossproduct of the numbers of all the variables, since they’re each independent and any combination can occur. So for the power, we have three possible positions. The camera has two, the Brush Height has five. The dirt has two for each of the ten positions. … Read more

Here’s a diagram of the state space for the vacuum world. Note that there are eight states and we have the actions connecting the states. Just as we did in the Romania problem. Now, let’s look at a path through this state. Let’s say we start out in this position and then we apply the … Read more

And the answer is, there are 8 states. There are two physical states that the robot vacuum cleaner can be in, either in state A or in state B. But in addition to that, there are states about how the world is, as well as where the robot is in the world. So, state A … Read more

So far, we’ve looked at the state space of cities in Romania, a two-dimensional physical space. But the technology for problem-solving through search can deal with many types of state spaces. Dealing with abstract properties, not just x-y position in a plane. Here I introduce another state space, the vacuum world. It’s a very simple … Read more

Here we give you an intuition as to why an optimistic heuristic function, h, finds the lowest-cost path. When a* ends, it returns a path, p, with estimated cost, C. And turns out that C is actually also the actual cost, because at the goal, the h component is 0. And so the path cost … Read more

The answer is that it depends on the h function. A* will find the lowest cost path if the h function for a state is less than the true cost of the path to the goal through that state. In other words, we want the h to never overestimate the distance to the goal. We … Read more

So let’s expand the node at Pitesti, we have to go down this direction, up, then we reach a path we’ve seen before then we go in this direction and now we reach Bucharest which is a goal and the H value is going to be 0 because we’re at the goal and the G … Read more

Let’s try to understand a little better how uniform cost search works. We started on start state, and then we start expanding out from there looking at different paths. And what we end up doing is expanding in terms of contours like on a topological map. Where first we expand out to a certain distance, … Read more