And the answer is no, there is no solution that the agent can come up with
because Bucharest doesn't appear on the map and so
the agent doesn't know any actions that can arrive there.
So let's give the agent a better chance.
Now we've given the agent the full map of Romania.
The start is in Arad and the destination, or
goal, is in Bucharest and the agent is given the problem
of coming up with a sequence of actions that will arrive at the destination.
Now is it possible for the agent to solve this problem?
And the answer is yes.
There are many routes or steps or
sequences of actions that will arrive at the destination.
Here's one of them.
Starting out in Arad taking this step first, then this one.
And then this one, then this one, and then this one,
to arrive at the destination.
So that would count as a solution to the problem.
So, sequence of actions,
chained together, that are guaranteed to get us to the goal.
Now, let's formally define what a problem looks like.
A problem can be broken down into a number of components.
First, the initial state that the agent starts out with.
In our route finding problem,
the initial state was the agent being in the city of Arad.
Next a function actions that takes a status input and
returns a set of
possible actions that the agent can execute when the agent is in the state.
In some problems,
the agent will have the same actions available in all states.
And in other problems they'll have different actions dependent on
the state.
In the route finding problem, the actions are dependent on the state.
When we're in one city we can take the routes to the neighboring cities, but
we can't go to any other cities.
Next, we have.
A function called result which takes as input a state.
And an action and delivers as its output, a new state.
So for example, if the agent is in the city of Arad,
and, that would be the state, and takes the action of driving along
route E671 towards Timisoara, then the result of applying that action in that
state would be the new state where the agent is in the city of Timisoara.
Next, we need a function.
Called GoalTest which takes a state.
And returns a boolean value true or false,
telling us if this data is a goal or not.
In a route finding problem,
the only goal would be being in the destination city, the city of Bucharest,
and all the other states would return false for the goal test.
And finally, one more thing, which is a path
cost function which takes a path,
a sequence of state action transitions
and returns a number which is the cost of that path.
Now for most of the problems we'll deal with we'll make the path cost function
be additive so that the cost of the path is just the sum of the individual steps.
And so we'll implement this path cost function
in terms of a step cost function.
The step cost function takes a state,
an action, and the resulting state from that action.
And returns a number n which is the cost of that action.
In the route finding example, the cost might be the number of miles traveled,
or maybe the number of minutes it takes to get to that destination.