Answers.Body: <p>This problem is indeed unclear because it's unclear where the goal is and we actually have 2 agents, while most search algorithms explained in that chapter do not apply to this scenario, but apply to cases where we have 1 agent and 1 goal. One algorithm in that chapter that seems to be related to this problem is the bidirectional search. I think that in maximum flows there's also something like that, but I studied them a long time ago.</p>
  <p>Now, let's consider the simplest case, where we have 2 cities, <span class="math-container">$A$</span> and <span class="math-container">$B$</span>. <span class="math-container">$d(A, B)$</span> is the distance between them, but, if the friends move at the same time, one starts at <span class="math-container">$A$</span> and the other at <span class="math-container">$B$</span>, then clearly it takes less than <span class="math-container">$d(A, B)$</span> for them to meet, and precisely it takes <span class="math-container">$d(A, B)/2$</span>.</p>
  <p>This is not the full explanation, but I think this is the start of the explanation.</p>
  <p>Now, this would only prove that heuristic 1 and 2 are inadmissible (because this is an example where they would overestimate), not that 3 is admissible. Maybe you can use <a href="https://en.wikipedia.org/wiki/Mathematical_induction" rel="nofollow noreferrer">induction</a> to prove it.</p>
  <p>Now, let's consider a more complicated scenario, where we have cities, <span class="math-container">$A$</span>, <span class="math-container">$B$</span> and <span class="math-container">$C$</span> in a straight line, such that <span class="math-container">$A$</span> is connected to <span class="math-container">$B$</span>, which is connected to <span class="math-container">$C$</span>, and <span class="math-container">$d(A, B) = d(B, C) = k$</span>. Assume that one friend is at <span class="math-container">$A$</span> and the other at <span class="math-container">$C$</span>. If they move to the next city, <span class="math-container">$B$</span>, at the same time, it takes only <span class="math-container">$k$</span> for them to meet, and not <span class="math-container">$k * 2$</span>, because both of them move at the same time.</p>
  <p>In this case, the goal is <span class="math-container">$B$</span>, so you could argue that <span class="math-container">$d(i, j)$</span> does not overestimate. But in the first case it would, and a heuristic is admissible if it never overestimates, so, if it overestimates at least once, it's not admissible.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-26T13:43:59.040Z
Answers.Text: > Now, let's consider the simplest case, where we have 2 cities. 
    
  Problem with that is that in that case the point between A and B is not a node in the search. But as you say, it is a great start towards understanding the full thing. 
  
  Thanks!
Answers.UserDisplayName: doubleOrt
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-26T14:06:45.997Z
Answers.Text: @doubleOrt You're right. I also thought about that, but in that case, for them to meet, at least one of them needs to move, but it seems we assume they both move at the same time, so they will need to meet in the middle, which is a bit weird. If there were 4 nodes in a row, they would end up in the same situation. Maybe we need to make more assumptions in order to show this more formally. This exercise is a bit tricky because it's unclear if the goal is where the other friend is (which is a moving goal except when they actually meet) or if it's the node where they meet (which is unknown).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-26T14:11:41.860Z
Answers.Text: If the goal is where the other friend is, then intuitively it makes sense that they will roughly meet in half of the time because they move towards each other at the same time. But even if we assume the goal is fixed but unknown somehow in their middle, it still makes sense that they will meet in half of the time of what it would take if one of them did not move. Now the question is which approach to use to formalise the problem so that we can prove this more comprehensively.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T16:25:42.077Z
Answers.LastActivityDate: 2024-12-23T23:18:31.493Z
Answers.LastEditDate: 2024-12-23T23:18:31.493Z
Answers.UserDisplayName: nbro
Answers.Body: <p><a href="https://en.wikipedia.org/wiki/Admissible_heuristic" rel="nofollow noreferrer">Admissible heuristic</a> <em>never overestimates</em> the lowest possible cost of reaching the goal.</p>
  <blockquote>
  <p>In computer science, specifically in algorithms related to pathfinding, a heuristic function is said to be admissible if it never overestimates the cost of reaching the goal, i.e. the cost it estimates to reach the goal is not higher than the <em>lowest possible</em> cost from the current point in the path. In other words, it should act as a lower bound.</p>
  </blockquote>
  <p>Therefore the reason <span class="math-container">$D(i,j)$</span> is inadmissible is nothing but your solution which depicts a best case scenario with the lowest actual cost <span class="math-container">$D(i,j)/2$</span>, therefore <span class="math-container">$D(i,j)$</span> still overestimates.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T12:56:27.117Z
Answers.Text: Thanks! So the difference lies in the perspective from which you look at the problem?
Answers.UserDisplayName: doubleOrt
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T12:57:38.433Z
Answers.Text: Also, might be too much to ask but I would be grateful if you could explain what exactly the best case is saying?
Answers.UserDisplayName: doubleOrt
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-23T03:47:31.027Z
Answers.Text: Admissible heuristic should act as a lower bound per above definition which is perspective-free, and the best case in your solution just says the lowest possible cost *per agent* for them to meet is $D(i,j)/2$ which obviously cannot go lower as they have to cover the entire distance $D(i,j)$ assuming no extra waiting time, if the lowest possible cost were, say $D(i,j)/3$, then some agent has to cover the remaining $2D(i,j)/3$ cost which is larger than $D(i,j)/2$. If the heuristic were to use the total cost, it's wrong for cooperative search here. Hope this clarifies your lingering confusion.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T07:36:01.350Z
Answers.LastActivityDate: 2024-12-22T07:36:01.350Z
Answers.UserDisplayName: cinch
Body: <p>I am working through the exercises of AIMA Chapter 3, and can't comprehend the solution given for the following problem (Exercise 3. ROMF):</p>
  <blockquote>
  <p>Suppose two friends live in different cities on a map, such as the
  Romania map shown in Figure 3.1. 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.</p>
  </blockquote>
  <p>The question:</p>
  <blockquote>
  <p>b. Let D(i, j) be the straight-line distance between cities i and j.
  Which of the following heuristic functions are admissible? (i) D(i,
  j); (ii) 2 · D(i, j); (iii) D(i, j)/2.</p>
  </blockquote>
  <p>I thought that only #2 would be admissible, since it obviously overestimates the cost. However, the solution given in the solutions manual says that only #3 is admissible:</p>
  <blockquote>
  <p>In the best case, the friends head straight for each other in steps of
  equal size, reducing their separation by twice the time cost on each
  step. Hence (iii) is admissible.</p>
  </blockquote>
  <p>However, #1 also never overestimates since it is literally equal to the SLD between the cities, and therefore should be admissible as well. I cannot wrap my head around the justification for only #3 being admissible.</p>
  <p>Why is #1 inadmissible?</p>
  
Tags: <search><heuristics><norvig-russell>
Title: Which of the following heuristics are admissible for the given problem?
UserDisplayName: doubleOrt
ThreadText: # Which of the following heuristics are admissible for the given problem?
  
  (Asked by: username_0 on 2024-12-22)
  
  I am working through the exercises of AIMA Chapter 3, and can't comprehend the solution given for the following problem (Exercise 3. ROMF):
  
  > Suppose two friends live in different cities on a map, such as the
  > Romania map shown in Figure 3.1. 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.
  
  The question:
  
  > b. Let D(i, j) be the straight-line distance between cities i and j.
  > Which of the following heuristic functions are admissible? (i) D(i,
  > j); (ii) 2 · D(i, j); (iii) D(i, j)/2.
  
  I thought that only #2 would be admissible, since it obviously overestimates the cost. However, the solution given in the solutions manual says that only #3 is admissible:
  
  > In the best case, the friends head straight for each other in steps of
  > equal size, reducing their separation by twice the time cost on each
  > step. Hence (iii) is admissible.
  
  However, #1 also never overestimates since it is literally equal to the SLD between the cities, and therefore should be admissible as well. I cannot wrap my head around the justification for only #3 being admissible.
  
  Why is #1 inadmissible?
  
  **Tags:** search, heuristics, norvig-russell
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2024-12-22. Score: 1 | Accepted answer
  
  This problem is indeed unclear because it's unclear where the goal is and we actually have 2 agents, while most search algorithms explained in that chapter do not apply to this scenario, but apply to cases where we have 1 agent and 1 goal. One algorithm in that chapter that seems to be related to this problem is the bidirectional search. I think that in maximum flows there's also something like that, but I studied them a long time ago.
  
  Now, let's consider the simplest case, where we have 2 cities, $A$ and $B$. $d(A, B)$ is the distance between them, but, if the friends move at the same time, one starts at $A$ and the other at $B$, then clearly it takes less than $d(A, B)$ for them to meet, and precisely it takes $d(A, B)/2$.
  
  This is not the full explanation, but I think this is the start of the explanation.
  
  Now, this would only prove that heuristic 1 and 2 are inadmissible (because this is an example where they would overestimate), not that 3 is admissible. Maybe you can use [induction](https://en.wikipedia.org/wiki/Mathematical_induction) to prove it.
  
  Now, let's consider a more complicated scenario, where we have cities, $A$, $B$ and $C$ in a straight line, such that $A$ is connected to $B$, which is connected to $C$, and $d(A, B) = d(B, C) = k$. Assume that one friend is at $A$ and the other at $C$. If they move to the next city, $B$, at the same time, it takes only $k$ for them to meet, and not $k \* 2$, because both of them move at the same time.
  
  In this case, the goal is $B$, so you could argue that $d(i, j)$ does not overestimate. But in the first case it would, and a heuristic is admissible if it never overestimates, so, if it overestimates at least once, it's not admissible.
  
  > **Comments:**
  > **username_0**: > Now, let's consider the simplest case, where we have 2 cities.     Problem with that is that in that case the point between A and B is not a node in the search. But as you say, it is a great start towards understanding the full thing.   Thanks!  
  > **username_1**: @doubleOrt You're right. I also thought about that, but in that case, for them to meet, at least one of them needs to move, but it seems we assume they both move at the same time, so they will need to meet in the middle, which is a bit weird. If there were 4 nodes in a row, they would end up in the same situation. Maybe we need to make more assumptions in order to show this more formally. This exercise is a bit tricky because it's unclear if the goal is where the other friend is (which is a moving goal except when they actually meet) or if it's the node where they meet (which is unknown).  
  > **username_1**: If the goal is where the other friend is, then intuitively it makes sense that they will roughly meet in half of the time because they move towards each other at the same time. But even if we assume the goal is fixed but unknown somehow in their middle, it still makes sense that they will meet in half of the time of what it would take if one of them did not move. Now the question is which approach to use to formalise the problem so that we can prove this more comprehensively.  
  
  ---
  
  ### Answer by username_2 on 2024-12-22. Score: 1
  
  [Admissible heuristic](https://en.wikipedia.org/wiki/Admissible_heuristic) *never overestimates* the lowest possible cost of reaching the goal.
  
  > In computer science, specifically in algorithms related to pathfinding, a heuristic function is said to be admissible if it never overestimates the cost of reaching the goal, i.e. the cost it estimates to reach the goal is not higher than the *lowest possible* cost from the current point in the path. In other words, it should act as a lower bound.
  
  Therefore the reason $D(i,j)$ is inadmissible is nothing but your solution which depicts a best case scenario with the lowest actual cost $D(i,j)/2$, therefore $D(i,j)$ still overestimates.
  
  > **Comments:**
  > **username_0**: Thanks! So the difference lies in the perspective from which you look at the problem?  
  > **username_0**: Also, might be too much to ask but I would be grateful if you could explain what exactly the best case is saying?  
  > **username_2**: Admissible heuristic should act as a lower bound per above definition which is perspective-free, and the best case in your solution just says the lowest possible cost *per agent* for them to meet is $D(i,j)/2$ which obviously cannot go lower as they have to cover the entire distance $D(i,j)$ assuming no extra waiting time, if the lowest possible cost were, say $D(i,j)/3$, then some agent has to cover the remaining $2D(i,j)/3$ cost which is larger than $D(i,j)/2$. If the heuristic were to use the total cost, it's wrong for cooperative search here. Hope this clarifies your lingering confusion.  
  
  ---
  
  