
Title:
0202 What Is A Problem

Description:
Unit 2, Topic 2, Route Finding Question


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.

To start, he's in Arad, and the destinationor goalis 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 is one of them:

Starting out in Arad, taking this step first, then this one, 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.

[DEFINITION OF A PROBLEM]

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 functionActionsthat takes a state as input and returns

a set of possible actions that the agent can execute when the agent is in this state.

[ACTIONS (s) {a,a2,a3...}]

In some problems, the agent will have the same actions available in all states

and in other problems, he'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 takesthat 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 Goal Test,

which takes a state and returns a Boolean value

true or falsetelling us if this state is a goal or not.

In a routefinding problem, the only goal would be being in the destination city

the city of Bucharestand all the other states would return false for the Goal Test.

And finally, we need 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 costs 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 numbernwhich 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.