Optimization Online


Convergent Network Approximation for the Continuous Euclidean Length Constrained Minimum Cost Path Problem

Ranga Muhandiramge(ranga***at***tartarus.uwa.edu.au)
Natashia Boland(natashia***at***unimelb.edu.au)
Song Wang(swang***at***maths.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 Length-Constrained Minimum Cost Path Problem (C-LCMCPP). Generally, this will be a non-convex 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 C-LCMCPP. 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 C-LCMCPP, 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 grid-based 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 (Semi-infinite 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
Entry Accepted: 02/07/2008
Entry Last Modified: 02/04/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society