Hierarchical A* based path planning -: a case study

Usually it is impossible to know in advance how coarsely robot movements can be discretized in order to find a collision-free path from an initial robot position to a desired goal position in a presence of obstacles. Our solution to the problem is to introduce a new method of constructing hierarchical path planning algorithms. It is based on a novel application of the A* control strategy, called here Meta A*. We test four hierarchical path planning algorithms, two of which are based on Meta A*, using five simulated robot workcells. The simulations suggest that the Meta A* based planners, on average, find paths faster and consume less memory than the other two algorithms. (C) 2002 Elsevier Science B.V. All rights reserved.