  


Convergent Network Approximation for the Continuous Euclidean Length Constrained Minimum Cost Path Problem
Ranga Muhandiramge(rangatartarus.uwa.edu.au) Abstract: In many path planning situations we would like to find a path of constrained Euclidean length in 2D that minimises a line integral. We call this the Continuous LengthConstrained Minimum Cost Path Problem (CLCMCPP). Generally, this will be a nonconvex optimization problem, for which continuous approaches only ensure locally optimal solutions. However, network discretisations yield weight constrained network shortest path problems (WCSPPs), which can in practice be solved to global optimality, even for large networks; we can readily find a globally optimal solution to an approximation of the CLCMCPP. Solutions to these WCSPPs yield feasible solutions and hence upper bounds. We show how networks can be constructed, and a WCSPP in these networks formulated, so that the solutions provide lower bounds on the global optimum of the continuous problem. We give a general convergence scheme for our network discretisations and use it to prove that both the upper and lower bounds so generated converge to the global optimum of the CLCMCPP, as the network discretisation is refined. Our approach provides a computable lower bound formula (of course the upper bounds are readily computable). We give computational results showing the lower bound formula in practice, and compare the effectiveness of our network construction technique with that of standard gridbased approaches in generating good quality solutions. We find that for the same computational effort, we are able to find better quality solutions, particularly in cases when the length constraint is tighter. Keywords: constrained shortest paths; Eikonal equations; optimal trajectories; network optimisation; global optimisation Category 1: Network Optimization Category 2: Applications  Science and Engineering (Control Applications ) Category 3: Infinite Dimensional Optimization (Semiinfinite Programming ) Citation: School of Mathematics and Statistics, The University of Western Australia, Stirling Highway, Crawley, 6009, WA, Australia, September 2007 Download: [PDF] Entry Submitted: 02/04/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  