0
$\begingroup$

When searching over a graph expressed as a uniform, 8-connected grid using the A* algorithm, is there any way to give a rough approximate of the number nodes expanded? I appreciate this is a somewhat complex problem, and am not expecting to make startling accurate predictions.

The information we have available is:

  • Start and goal vertices
  • Graph/grid configuration - vertex occupancy and connection information
  • Heuristic and cost functions used


Initial idea

We could use a log of previous searches between macro regions, and thus obtain a mean region-region node expansion count. However, it would be preferable to have a heuristic that does not depend on historical data; or to have a slightly more refined version of the above-mentioned approach.

  • 0
    Would using Markov Chains be helpful?2012-07-24
  • 0
    To clarify: Consider each graph expansion as a state, the expansion of a single node as an edge from the unexpanded to the expanded graph and give probabilities according to the heuristic and cost functions. Then we can use Markov chain methods to calculate the average number of explored notes in the final states of that Markov chain.2012-07-24
  • 0
    I am not really too familiar with that system being a programmer... (but apparently I should be! ;) Roughly how would it be applied, and is it feasible for an online algorithm?2012-07-24
  • 0
    Sounds interesting! I wonder if it will actually prove to be slower than the actual A* search, though?2012-07-24
  • 0
    The thing is that the Markov chain would have a largish state space, so I don't think this would work really well for an on-line algorithm. Maybe you could use the rate of decrease of the cost function as a crude estimate?2012-07-24
  • 0
    The cost function employed is usually the Euclidean distance, and the heuristic is usually the Manhattan distance. What about `f(d,c,k,n) = pow(d,c) * k * n` where `d` is the distance/cost function, `c` and `k` are constants determined experimentially and/or stochastically, and `n` is the number of occupied vertices in the rectangle that bounds the line segment `start->goal`?2012-07-24
  • 0
    A slightly cheaper alternative could be f(h,c,ratio_n) = pow(h,c*ratio_n) where `h` is the heuristic function, and `ratio_n` is the occupied:unoccupied vertex ratio on the whole graph.2012-07-24

0 Answers 0