What is the value of f(n), the path length of the solution you found?

What is the path length of the solution of greedy search? You can calculate it by adding up the lengths of each segment.

Now follow the same procedure with greedy search.

Use f(n) = h(n), everything else remains unchanged. If you used a spreadsheet you can fill the g(n) column with 0-s.

We have a simplified road map of Romania. Length of each road segment is shown.

Problem: find the path from S (Sibiu) to B (Bucharest).

We will use A* search. We need a heuristic function, for that we can use the distance of each point from the goal Bucharest:

Simulate the steps of the A* search with pen and paper (or a spreadsheet). The following table will help:

Then follow the algorithm:

1. select the row from the table with lowest f(n) that you haven't used yet. Mark it as "used".
2. If on this row the last city is "B" then the row contains the solution and its path length.
3. if it's not, find the cities you can move to from the last city. Add a row for each of these neighbor nodes to the table

Table after adding the neighbors of the initial state:

The Vaccuum World contains two rooms: A and B, and an intelligent agent, the vaccuum cleaner. The task of the agent is to keep the rooms clean.

def decide_action(room, status):
    if status == "dirty": return "Vacuum"
    elif room == "A": return "Right"
    else: return "Left"

The Vaccuum World contains two rooms: A and B, and an intelligent agent, the vaccuum cleaner. The task of the agent is to keep the rooms clean.

def decide_action(room, status):
    if status == "dirty": return "Vacuum"
    elif room == "A": return "Right"
    else: return "Left"

What happens in a dynamic world? Let's change the conditions so that at each step, after the agent's action, there is a 25% chance per room that dirt is created there. If the room was already dirty, nothing happens.

The performance measure we used until now is no longer good. It assumes that the vaccuum cleaner always successfully cleans everywhere and so only measures the energy cost. It is slightly more realistic to include the state of the rooms:

The formula takes the state before the agent's action.

Which agent is better now - the initial primitive agent or the agent with memory? Let's do 10 working steps from the same initial state as in the first question. The exact evaluation is difficult, but you can estimate the performance by assuming that dust is generated in both rooms at every fourth step. From the point of view of the vaccuum cleaner, the rooms will be dirty at step 1, 5, 9...

The given program cleans the rooms quickly and then just wastes energy, moving back and forth. How to improve the performance?

What could be the measured performance for an agent with memory? Let's assume the agent runs 10 steps from the same initial state, where the agent is in room A and both rooms are dirty.

The Vaccuum World contains two rooms: A and B, and an intelligent agent, the vaccuum cleaner. The task of the agent is to keep the rooms clean.

def decide_action(room, status):
    if status == "dirty": return "Vacuum"
    elif room == "A": return "Right"
    else: return "Left"