GoalDistanceEstimate is wrong

[parthi2929]

Hi

The GoalDistanceEstimate numbers are not euclidean distance, nor the actual distance as per google. I understand you have taken directly from Norwis's AIMA, and I could not find any clue any where how they arrive at these values. Can you please check?

[justinhj]

The code nor the algorithm is from AIMA.

I assume you're talking about the findpath.cpp example.

In that example I assume you can move only vertically or horizontally on the map, therefore a good heuristic is the Manhattan distance (i.e the distance vertically or horizontally from the goal).

The goal distance code therefore uses this distance, so I don't believe it is incorrect

float MapSearchNode::GoalDistanceEstimate( MapSearchNode &nodeGoal )
{
    return fabsf(x - nodeGoal.x) + fabsf(y - nodeGoal.y);   
}

[parthi2929]

Thank you for response. I am talking about min_path_to_Bucharest.cpp, where it is mentioned so.

In that, in GoalDistanceEstimate, you are simply returning the SLD (Straight line distance) from lookup table. You have also mentioned it is calculated as Euclidean distance.

Here, how did you arrive at for eg, 366 for Arad to Bucharest Estimate? In the problem there are no coordinates given to calculate Euclidean distance. I tried using lat,lon, but they give totally different values.

[justinhj]

Thanks for the clarification. That code was submitted by a contributor and I had forgotten it was based on an example in AIMA

Looking at the code it returns the distance from a table, so presumably the distances are correct. They are simply the straight-line or euclidean distance (i.e. if a bird flies from this city to the goal city in a straight line how far will it fly?) From the point of view of the algorithm it should give good results.

[parthi2929]

AIMA does not provide any cartesian coordinates for us to calculate and verify Euclidean distance.

So I checked with latitude longitude, and they give a far underweighted values. For eg, from Arad to Bucharest, I get around 5 as Euclidean distance, whereas AIMA uses 366 as SLD.

I also tried to calculate distance between 2 lat,lon points using geodesic method (geopy), in miles. They too do not match except 1 or 2.

[parthi2929]

I am surprised how all assumed the values are ok without questioning how they were calculated, especially at least the heuristic h(n). No one raised a question.

[justinhj]

Hi Parthi

I just read the part of the book you’re talking about. The straight line distance is an admissible heuristic because it never overestimates the distance to the goal. So the code as provided is correct. It seems your issue is that the distances are wrong (it could be that they were not straight line distances but actual road distances taken from an atlas). That may be but it’s something you can take up with Norvig. :)

If you do want to submit a new dataset with the actual latitude and longnitude I would be happy to include it.

[parthi2929]

Yeah admissable heuristic, but they should explain how they arrived at 366 that too, that they are explaining about it for first time there :(

Mailed to Peter Norwig as well regarding this (just gave a shot, he didn't reply of course)

[justinhj]

Hmm, I think they should probably comment where the distances came from and that may not actually be straight line distances. For the purposes of the exercise in the book they probably felt that not dealing with coordinates makes it easier for the student to focus on the algorithm.

I'll add a note to the source file in case this causes confusion in the future.

[justinhj]

Updated the example code with a comment to explain this inaccuracy

[parthi2929]

Thanks :)