## **Artificial Intelligence Online Course**
Unit 2, Video 2 Route Finding Question
This document contains the transcript of the audio described video.
## **Transcript** The answer is no, there is no solution that the agent can come up with because buceras doesn’t appear on the map, and so the agent doesn’t know any action 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, our 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?
*The figure shows a full map of Romania. The city Arad is circled in the upper left and the city of Bucharest is circled in the lower right.
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 Aran, taking this step first, and 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. A sequence of actions that are chained together that are garenteed to get us to the goal.
*The figure shows a route from Arad to Bucharest via several intermediate cities.
Now let’s formally defined 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 Aran. Next, a function actions that takes a state as input and returns a set of possible actions that the agent can execute when the agent is in this 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 takes, that would be the state, and takes the action of driving along route e671 towards Timisora then the result of applying that action in that state would be the new state where the agent is in the city of Timisora. Next, we need a function called goaltest which takes a state and returns a Boolean value of true or false telling us if this state is a goal or not. In the route-finding problem the only goal would be being in the destination city, the city of bukarast, and all the other states would return false for the goaltest. And finally, and 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 will make the pathcost 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 pathcost function in terms of stepcost function. A stepcost 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 the number of minutes it takes to get to that destination.
* The title of this page is definition of a problem. There are five bullet points. bullet point number 1, initial state. bullet point number 2. actions function. which takes a state s and return a sequence of actions a1 , a2, a3 and so on. buttlet point number 3, result function, which takes a state s and an action a, and returns a new state s prime. bullet point number 4, goal test function, which takes a state s and returns true of false. bullet point number 5,, path cost function which takes a sequence of states and returns a number n. the step cost function takes states s, action a, and the next state s’ returns the number n |