Sign in to follow this  
sidwinda

Need help to understand HPA*

Recommended Posts

I want to try to implement HPA*, which in the paper "Near Optimal Hierarchical Path-Finding by A.Botea,M Muller, and J.Schaeffer. http://www.cs.ualberta.ca/~jonathan/Papers/Papers/jogd.pdf However I have difficulty in understanding it. May be partly because my first language is not English. The part that confuse me is the Table 1 results (page 25) for the example results that is given. I just can not figure out how to get the number of expanded nodes in L-1 and L-2 rows. The explanation in the paper is on page 12-15, however when I read it just make me confuse. Can someone please help to understand it? Thank you

Share this post


Link to post
Share on other sites
"I just can not figure out how to get the number of expanded nodes in L-1 and L-2 rows."

They most likely count the number of unique nodes that have been put on A*'s open list during the A* searches for level 1 respectively 2.

William

Share this post


Link to post
Share on other sites
First, Thank you for the response.

That's is what I think too.
However on the table1 the L-1 row for the SG part, it has 16 nodes. When I try to calculate it by my own it is 17. Did I make a mistake ?

One more question, for the low-level search, the heuristic that the paper used is Manhattan distance. How about for the level 1 and 2 abstraction ?

Thank you

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this