Heuristic Algorithm for Robot Path Planning Based on Real Space Renormalization

**
Maritza Bracho de Rodríguez,
José Alí Moreno.
**

The development of a path planning algorithm based on an approximate cell decomposition of the workspace is presented. The free space of the robot is recursively decomposed into a set of non-overlapping cells through a real space renormalization procedure. The algorithm includes a previously calculated data base of heuristics defining the optimal paths that cross a cell between any two predefined edge points. The first step of the algorithm consists on the computation of a straight path from the initial configuration to the goal position. This initial proposed path is further recursively corrected in the following steps until a definitive path is obtained. The recursive process is stopped when the complete path lies on a free collision space or the size of the cell reaches some predefined value of resolution. The algorithm of path planning was experimentally tested on a workspace cluttered with thirty randomly distributed obstacles. In each case, with very little computational effort a good free collision path is calculated. The results indicate that the proposed path planning algorithm is very suitable for real time applications.

http://www.springerlink.com/content/fwrh0tcav0l8055w/

Biblioteca Digital Brasileira de Computação - Contato: bdbcomp@lbd.dcc.ufmg.br