trulla : An Algorithm For Path Planning Among Weighted Regions By Localized Propagations

摘要

This paper discusses an approach to mo- bile robot path planning which utilizes a wavefront- like propagation method for determining near-optimal paths. This approach is different from previous wave propagation methods in three aspects: it attempts to find near-optimal paths from all locations in the free space to the destination instead of one optimal path from the source location to the destination, may per- form repeated propagations to converge to a solution, and is composed of simplified computations based on local information to facilitate a VLSI implementation. I. INTRODUCTION Wavefront propagation methods for robot path plan- ning have been proposed by other researchers. The tradi- tional approach is to start with a list containing only the destination point (or a region representing a small area around the destination point) and propagate a value rep- resenting the cost of traveling between the two regions to each unvisited neighbor of the region. The region is removed from the list and all its newly visited neighbors are added to the list. The list is sorted by increasing cost and the process is repeated with the lowest cost region in the list. This process terminates when the source region is reached. The actual path is then constructed between the endpoints using the computed cost values. Jahanbin and Fallside(l) have presented some wavefront propagation path planning algorithms consisting only of free-space and obstacles in configuration space. They pre- sented two solutions to the planning problem, one for uniform region sizes and another for non-uniform region sizes. The propagation was performed by the use of a mask which was placed over successive positions on the wavefront. Various shape wavefronts could be propagated depending on the weights in the mask. Once the propa- gation was completed the path was constructed from the source to the lowest cost neighbor and this process was repeated until the destination was reached. There are two