On performance of path planning algorithms in unknown terrains

We consider the problem of planning a collision-free path for a point robot R from its present position to a specified destination position through an unknown terrain, i.e., a terrain whose model is not known a priori. R is equipped with a sensor system that is capable of detecting all visible vertices and edges of the obstacles. Algorithms that plan a required path for R have been reported earlier in literature. In this paper, we investigate some trade-offs in the performance of such algorithms in terms of distance traversed, number of sensor operations and computational complexity. These trade-offs accrue as a result of the details of an underlying graph search algorithm, and in this sense are independent of the other properties of the terrain. We show that among a general class of these algorithms (a) depth-first implementations result in minimum computational complexity, (b) shortest-path implementations result in a globally shortest path in each step, and that (c) among a set of implementations that attempt to optimize the distance to the destination, the A* implementation results in minimum number of scan operations. We also present some interesting intermediaries between the algorithms of (a) and (b).