On discretization methods for generalized weighted region shortest path problems
- Resource Type
- Conference
- Authors
- Zheng Sun; Tian-Ming Bu; Li-Fen Zhang
- Source
- 2005 IEEE International Conference on Robotics and Biomimetics - ROBIO Robotics and Biomimetics (ROBIO). 2005 IEEE International Conference on. :180-185 2005
- Subject
- Robotics and Control Systems
Computing and Processing
Signal Processing and Analysis
Bioengineering
Shortest path problem
Computer science
Cost function
Anisotropic magnetoresistance
Search problems
Approximation algorithms
Sun
Path planning
Joining processes
Robots
- Language
The optimal path planning problems are very difficult for some of the generalized weighted region shortest path problems, where the cost metric varies not only in different regions of the space, but also in different directions inside the same region. If the classic discretization approach is adopted to compute an epsi-approximation of the optimal path, the size of the discretization (and thus the complexity of the approximation algorithm) is usually dictated by a number of geometric parameters and thus can be very large. In this paper we show a general method for choosing the variables of the discretization to maximally reduce the dependency of the size of the discretization on various geometric parameters. We use this method to improve the previously reported results on two optimal path problems with direction-dependent cost metrics