YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← 02-02 What Is A Problem

Unit 2, Topic 2, Route Finding Question

Get Embed Code
20 Languages

Showing Revision 1 created 10/13/2011 by Amara Bot.

  1. And the answer is no.

    ΒΆ

  2. There is no solution that the agent can come up with
  3. because Bucharest doesn't appear on the map,
  4. and so the agent doesn't know any actions that can arrive there.
  5. So let's give the agent a better chance.
  6. Now we've given the agent the full map of Romania.
  7. To start, he's in Arad, and the destination--or goal--is in Bucharest.
  8. And the agent is given the problem of coming up with a sequence of actions
  9. that will arrive at the destination.
  10. Now, is it possible for the agent to solve this problem?
  11. And the answer is yes.
  12. There are many routes or steps or sequences of actions that will arrive at the destination.
  13. Here is one of them:
  14. Starting out in Arad, taking this step first, then this one, then this one,
  15. then this one, and then this one to arrive at the destination.
  16. So that would count as a solution to the problem.
  17. So sequence of actions, chained together, that are guaranteed to get us to the goal.
  18. [DEFINITION OF A PROBLEM]
  19. Now let's formally define what a problem looks like.
  20. A problem can be broken down into a number of components.
  21. First, the initial state that the agent starts out with.
  22. In our route finding problem, the initial state was the agent being in the city of Arad.
  23. Next, a function--Actions--that takes a state as input and returns
  24. a set of possible actions that the agent can execute when the agent is in this state.
  25. [ACTIONS (s) {a,a2,a3...}]
  26. In some problems, the agent will have the same actions available in all states
  27. and in other problems, he'll have different actions dependent on the state.
  28. In the route finding problem, the actions are dependent on the state.
  29. When we're in one city, we can take the routes to the neighboring cities--
  30. but we can't go to any other cities.
  31. Next we have a function called Result, which takes, as input, a state and an action
  32. and delivers, as its output, a new state.
  33. So, for example, if the agent is in the city of Arad, and takes--that would be the state--
  34. and takes the action of driving along Route E-671 towards Timisoara,
  35. then the result of applying that action in that state would be the new state--
  36. where the agent is in the city of Timisoara.
  37. Next, we need a function called Goal Test,
  38. which takes a state and returns a Boolean value--
  39. true or false--telling us if this state is a goal or not.
  40. In a route-finding problem, the only goal would be being in the destination city--
  41. the city of Bucharest--and all the other states would return false for the Goal Test.
  42. And finally, we need one more thing which is a Path Cost function--
  43. which takes a path, a sequence of state/action transitions,
  44. and returns a number, which is the cost of that path.
  45. Now, for most of the problems we'll deal with, we'll make the Path Cost function be additive
  46. so that the cost of the path is just the sum of the costs of the individual steps.
  47. And so we'll implement this Path Cost function, in terms of a Step Cost function.
  48. The Step Cost function takes a state, an action, and the resulting state from that action
  49. and returns a number--n--which is the cost of that action.
  50. In the route finding example, the cost might be the number of miles traveled
  51. or maybe the number of minutes it takes to get to that destination.