Efficient grid based techniques for solving the weighted region least cost path problem on multicomputers
MetadataShow full item record
This thesis explores the possibilities of developing fast grid parallel algorithms to solve the Weighted Region Least Cost Path problem. Two complimentary steps have been undertaken. First, an efficient sequential algorithm to solve the above problem was developed. the algorithm is a modification of a Gauss-Seidel-like algorithm for obtaining the minimum costs. The most salient feature of the algorithm is the reduction of the number of nodes and edges in cheaper regions of the grid. the reported experimental results ascertain the superiority of this algorithm with regard to computer running time at a modest reduction in the accuracy of the obtained solution. Parallel implementations of grid-based algorithms were studies. A simple grid-based variant was implemented on a network of Transputers. The overall approach is employed could be used to develop a parallel version of the above sequential algorithm on a Transputer network, combining both advantages of efficiency and parallelization.
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Rhoden, Christopher A. (Monterey, California. Naval Postgraduate School, 1994-06);The Simplex algorithm, developed by George B. Dantzig in 1947 represents a quantum leap in the ability of applied scientists to solve complicated linear optimization problems. Subsequently, its utility in solving finite ...
Huang, Jo-Wen (Monterey, California: Naval Postgraduate School, 2017-06);With the development and advancement in the technology of control and multi-robot systems, robot agents are likely to take over mine countermeasure (MCM) missions one day. The path planning coverage algorithm is an essential ...
Adaptive selections of sample size and solver iterations in stochastic optimization with applicåation to nonlinear commodity flow problems Vondrak, David A. (Monterey, California. Naval Postgraduate School, 2009-03);We present an algorithm to approximately solve certain stochastic nonlinear programs through sample average approximations. The sample sizes in these approximations are selected by approximately solving optimal control ...