A* Search G, H Weight Generation

Hi All,

I’m looking for advice and recommendations on how to generate g and h weights (w_g, w_h respectively) for the a* search procedure.

My initial approach was as follows: given the average state cost c_ave, the expected path length p_est and distance to goal function d(n), we want

 sum_from(i=1)_to(p_est) w_g * c_ave = C, and: sum_from(i=1)_to(p_est) w_h * d(node_i) = C, // Where C is an arbitrary constant so: w_g = C/(c_ave * p_est) w_h = C/(p_est * d_ave ) = (2*C)/(p_est*d(n_goal)) // given d_ave = d(goal) / 2 

In large state spaces (~1,000,000 elements) the generated weights make the search take prohibitively long – with the same input, with manually set weights, the search can can take fractions of a second.

For background the search is to generate a high level trajectory through an environment for a quadrupedal robot. get_cost(n) returns the cost of stepping at the position defined by n, and heuristic(n) returns the distance from n to n_goal. Please note get_cost(n,n’) ∈ [0,1], and heuristic(n) ∈ [0,+inf]

a search procedure for reference*

... for each neighbor of current ... g_tentative := g[current] + w_g*get_cost(current, neighbor) if g_tentative < g[neighbor] g[neighbor] := g_tentative f[neighbor] := g[neighbor] + w_h*heuristic(neighbor, goal) ... 

submitted by /u/sun_dragn
[link] [comments]