RiL3z.github.io

A Problem Solving Adventure

In an attempt to stay sharp, I've decided that I could work a bit more on my problem solving skills. To do that, I've pulled a problem straight out of a book I own. The book is called Artificial Intelligence: A Modern Approach and it's by Stuart Russell and Peter Norvig. The problem is number 3.3 on page 113. It reads:

Suppose two friends live in different cities on a map, such as the Romania map shown in Figure 3.2. On every turn, we can simultaneously move each friend to a neighboring city on the map. The amount of time needed to move from city i to neighbor j is equal to the road distance d(i,j) between the cities, but on each turn the friend that arrives first must wait until the other one arrives (and calls the first on his/her cell phone) before the next turn can begin. We want the two friends to meet as quickly as possible.
a. Write a detailed formulation for this search problem. (You will find it helpful to define some formal notation here.)
b. Let D(i,j) be the straight-line distance between cities i and j. Which of the following heuristic functions are admissable? (i) D(i,j); (ii) 2 * D(i,j); (iii) D(i,j)/2.
c. Are there completely connected maps for which no solution exists?
d. Are there maps in which all solutions require one friend to vist the same city twice?

Here is Figure 3.2, the simplified map of Romania. romania I like to tackle my problems piece-meal so, reading the first part of the problem description:

Suppose two friends live in different cities on a map, such as the Romania map shown in Figure 3.2.

Let us suppose we have two friends, I am going to call them "Jack" and "Jill". Suppose further that Jack lives in Oradea and Jill lives in Bucharest.
Ok, with this in mind, onto the next piece of the problem description:

On every turn, we can simultaneously move each friend to a neighboring city on the map.

Alright, so let's assume it's turn 0. That means Jack is in the city Oradea and Jill is in Bucharest. What can happen on turn 1? Well, according to the rules of this game, we can move each friend to a neighboring city on the map. So we could choose to move Jack to Zerind or Sibiu and we could choose to move Jill to Fagaras, Pitesti, Giurgiu, or Urziceni, since those are all neighboring cities to our two characters.
Onto the next piece:

The amount of time needed to move from city i to neighbor j is equal to the road distance d(i,j) between cities,

Alrighty. So if Jack moves from Oradea to Sibiu, looking at the map and the distances given, it is going to take him d(Oradea,Sibiu) = 151 units of time. If Jill moves from Bucharest to Pitesti it's going to take her d(Bucharest,Pitesti) = 101 units of time.

but on each turn the friend that arrives first must wait until the other one arrives (and calls the first on his/her cell phone) before the next turn can begin.

So, if Jack moves from Oradea to Zerind and Jill moves from Bucharest to Fagaras within a turn, then once Jack has arrived in Zerind he is going to have to wait for Jill to arrive in Fagaras and call him on her cell phone so that the next turn can begin because d(Oradea,Zerind) < d(Bucharest,Fagaras). (This is based off the two assumptions that Jack and Jill hit the road at the same time at the start of every turn and also that they both drive at the same rate. This last assumption may be a bad one because perhaps Jill is a speed demon.)

We want the two friends to meet as quickly as possible.

Ok, so the objective is really to minimize the distance traveled by the two since distance = time in this problem. If Jack calls Jill and tells her that he's going to meet her in Bucharest (meaning Jill doesn't have to travel), he could choose to travel from Oradea to Zerind to Arad to Timisoara to Lugoj to Mehadia to Drobeta to Craiova to Pitesti to Bucharest. This is obviously not the optimal way of doing things since the total distance Jack traveled is d(Oradea,Zerind) + d(Zerind,Arad) + d(Arad,Timisoara) + d(Timisoara,Lugoj) + d(Lugoj,Mehadia) + d(Mehadia,Drobeta) + d(Drobeta,Craiova) + d(Craiova,Pitesti) + d(Pitesti,Bucharest) = 71 + 75 + 118 + 111 + 70 + 75 + 120 + 138 + 101 = 879 over the course of nine turns! If Jack and Jill both traveled, Jack from Oradea to Sibiu to Rimnicu Vilcea and Jill from Bucharest to Pitesti to Rimnicu Vilcea, then the total distance traveled by both Jack and Jill is Jack's total distance plus Jill's total distance = d(Oradea,Sibiu) + d(Sibiu,Rimnicu Vilcea) + d(Bucharest,Pitesti) + d(Pitesti,Rimnicu Vilcea) = 231 + 198 = 429 over the course of two turns. Since Jack and Jill are traveling in parallel, however, the total amount of time taken for the two to meet in Rimnicu Vilcea is actually d(Oradea,Sibiu) + d(Pitesti,Rimnicu Vilcea) = 248.
With this understanding of the problem, let's proceed to try and answer question a.

Write a detailed formulation for this search problem. (You will find it helpful to define some formal notation here.)

What exactly is a "detailed formulation" of a search problem? Well, taking a look at page 66, this is what the book has to say about a formal definition of a problem:

A problem can be defined formally by five components:

The initial state that the agent starts in. For example, the initial state for our agent in Romania might be described as In(Arad).

A description of the possible actions available to the agent. Given a particular state s, ACTIONS(s) returns the set of actions that can be executed in s. We say that each of these actions is applicable in s. For example, from the state In(Arad), the applicable actions are {Go(Sibiu), Go(Timisoara), Go(Zerind)}.

A description of what each action does; the formal name for this is the transition model, specified by a function RESULT(s,a) that returns the state that results from doing action a in state s. We also use the term successor to refer to any state reachable from a given state by a single action. For example, we have
RESULT(In(Arad), Go(Zerind)) = In(Zerind).
Together, the initial state, actions, and transition model implicitly define the state space of the problem--the set of all states reachable from the initial state by any sequence of actions. The state space forms a directed network or graph in which the nodes are the states and the links between nodes are actions. (The map of Romania shown in Figure 3.2 can be interpreted as a state-space graph if we view each road as standing for two driving actions, one in each direction.) A path in the state space is a sequence of states connected by a sequence of actions.

The goal test, which determines whether a given state is a goal state. Sometimes there is an explicit set of possible goal states, and the test simply checks whether the given state is one of them. The agent's goal in Romania is the singleton set {In(Bucharest)}. Sometimes the goal is specified by an abstract property rather than an explicitly enumerated set of states. For example, in chess, the goal is to reach a state called "checkmate," where the opponent's king is under attack and can't escape.

A path cost function that assigns a numeric cost to each path. The problem-solving agent chooses a cost function that reflects its own performance measure. For the agent trying to get to Bucharest, time is of the essence, so the cost of a path might be its length in kilometers. In this chapter, we assume that the cost of a path can be described as the sum of the costs of the individual actions along the path. The step cost of taking action a in state s to reach state s' is denoted by c(s,a,s'). The step cost for Romania are shown in Figure 3.2 as route distances. We assume that step costs are nonnegative.

Phew, that is quite a bit of information to take in. Don't worry, let's take it one step at a time. To write a detailed formulation of our problem, we need five components, so let's just start with the first component, the initial state. Jack and Jill could be in any city on the map of Romania on turn 0. For example, we could start off with Jack being in Neamt and Jill being in Drobeta. For the sake of our problem solving agent, we could define this state of affairs more formally be using the notation JackIn(Neamt) and JillIn(Drobeta), meaning that Jack is in the city of Neamt and Jill is in the city of Drobeta.
The second component to our problem formulation is a description of possible actions that the agent can take. I'm going to represent the action of Jack moving to city Iasi with the formal notation JackGo(Iasi) and the action of Jill moving to city Mehadia as JillGo(Mehadia). In our problem the possible actions that we can take per turn are moving Jack AND Jill to adjacent cities. For example, if JackIn(Neamt) and JillIn(Drobeta), then the possible actions our problem solving agent can take is Jack can go to Iasi and Jill can go to Mehadia or Craiova. We can represent this situation more formally by saying that ACTIONS(JackIn(Neamt),JillIn(Drobeta)) = {JackGo(Iasi), JillGo(Mehadia), JillGo(Craiova)} (the set of possible actions given the state of affairs).
The third component is a description of what each action does, formally called the transition model. In our case, we can define the transition model by specifying the function RESULT(stateJack,stateJill,jackAction,jillAction), which returns the states that Jack and Jill are in (what cities they are located in) after Jack and Jill take their respect actions of moving to adjacent cities on each turn. For example, the combined state that results from RESULT(JackIn(Neamt),JillIn(Drobeta),JackGo(Iasi),JillGo(Craiova)) = {JackIn(Neamt),JillIn(Craiova)}.
The fourth component is the goal test. The goal test in our case is the determination that Jack and Jill are in the same city. In other words, if JackIn(x) and JillIn(x), where x is a city, then Jack and Jill are in the same city and the goal of getting the two friends to meet up has been accomplished!
The fifth and final component to our problem formulation is describing the path cost. The path cost in our problem is the amount of time it takes for the two friends to meet each other. For example, the path cost of moving Jack and Jill both to the city of Rimnicu Vilcea, assuming that Jack starts in Oradea and Jill starts in Bucharest and also assuming that Jack goes from Oradea to Sibiu and Jill goes from Bucharest to Pitesti in turn 1, and Jack goes from Sibiu to Rimnicu Vilcea and Jill goes from Pitesti to Rimnicu Vilcea in turn 2 is 248. The reason this is so is because the step cost of say, moving Jack from Oradea to Sibiu and Jill from Bucharest to Pitesti is max(d(Bucharest,Pitesti),d(Oradea,Sibiu)) = 151. Remember that Jack and Jill are moving to their neighboring cities at the same time, and one waits on the other if they are still traveling.

So, putting together everything into a concise problem formulation, we have this:

States: What city Jack and Jill are currently, in represented by JackIn(x) and JillIn(y).
Initial state: Jack and Jill could start in any city to begin with. An example would be JackIn(Oradea) and JillIn(Arad).
Actions: Jack and Jill can drive to adjacent cities x and y, represented by JackGo(x) and JillGo(y).
Transition model: Jack and Jill can arrive in an adjacent cities by driving to them, the successor states resulting from calling the function RESULT(JackIn(x),JillIn(y),JackGo(a),JillGo(b)).
Goal test: If Jack and Jill are in the same city, the goal test should evaluate to true.
Path cost: The sum of the step costs of Jack and Jill's path through Romania to arrive in the same city.

So, we have our answer to question a. Onto question b:

Let D(i,j) be the straight-line distance between cities i and j. Which of the following heuristic functions are admissable? (i) D(i,j); (ii) 2 * D(i,j); (iii) D(i,j)/2.

So, D(i,j) is the distance from city i to city j as the crow flies. We are given three heuristic functions: D(i,j), 2 * D(i,j), and D(i,j)/2, and we have to determine which of these functions is considered admissable. The first thing to understand is what is a heuristic function? According the book, a heuristic function, defined as h(n), is "the estimated cost of the cheapest path from the state at node n to a goal state. So, a heuristic function is just some function that attempts to estimate the cheapest path to a goal state. Okay, so which of these functions are admissable? Well, let's first understand what an admissable heuristic function is. Again, according to the book, an admissible heuristic function "is one that never overestimates the cost to reach the goal." So which of these functions never overestimates the cost to reach the goal of Jack and Jill being in the same city? Well, it is easy to see that D(i,j) (the straight-line distance) is admissable because the straight-line distance between two cities is always going to be less than or equal to the actual distance traveled along a route between those two cities. 2 * D(i,j) is NOT admissable because it CAN overestimate the actual distance traveled between to cities. For example, we know the straight-line distance between Fagaras and Sibiu is D(Fagaras,Sibiu) = d(Fagaras,Sibiu) = 99. 2 * D(Fagaras,Sibiu) = 2 * 99 = 198 > 99 (the actual route distance), therefore 2 * D(i,j) is not never an overestimate (wrap your head around that statement for a few minutes :dizzy_face:). What about function D(i,j)/2? It is easy to see that D(i,j)/2 is always less than D(i,j) (the result of dividing any quantity in half is always less than the original quantity) and since D(i,j) is admissable, that means D(i,j)/2 is admissable. So, our concise answer to problem b is:
D(i,j) is admissable, 2 * D(i,j) is NOT admissable, and D(i,j)/2 is admissable.
On to c:

Are there completely connected maps for which no solution exists?

First, what is meant by a completely connected map? I'm assuming the authors mean a map where all cities are connected by roads, that is, every city is reachable through a path from another city. If we are provided a completely connected map in this sense, then there is ALWAYS a city that Jack and Jill can meet up in, since they can always travel to any city within the map. So the concise answer to problem c is: No.

On to d:

Are there maps in which all solutions require one friend to visit the same city twice?

Again, I would say NO. I can't think of any map where, in order for the two friends to meet in the same city, one of the friends needs to visit the same city twice.

So, that is problem 3.3 in a nut-shell. Happy problem solving!