Asynchronous,Iterative, and Parallel Procedures for Solving the Weighted-Region Least Cost Path Problem

A family of local, asynchronous, iterative, and parallel procedures (LAIPPs) are described. These procedures are designed to find least cost paths (LCPs) in bounded regions of the plane that have been partitioned into triangular subregions. The unit cost of traversing a given subregion is uniform within the subregion, but varies between subregions. In the case of one-dimensional chains of triangles, the procedures are guaranteed to converge to a global LCP. Although the procedures are guaranteed to terminate, we have so far been unable to prove, in the general case of a two-dimensional triangulation, that the procedures always terminate in admissible paths. Extensive experimental investigations, however, have revealed convergence to admissible paths in all cases examined. While counterexamples are constructed to prove that the procedures may converge to the local rather than global LCPs, convergence to the global LCP was found to occur in nearly all of our experimental investigations. The computational complexity of the procedures, as measured by the number of iterations required for convergence, was found experimentally to be independent of the size of the domain in which the paths lay, and to be slightly greater than linear in the Euclidian length of the paths. The complexity was also found to depend on the cost structure of the domain. Such LAIPPs appear to be promising procedures for both application and further investigation. In particular, the question of convergence is an interesting problem.