Abstract
The problem of planning a path for a point robot from a source point s to a destination point d so as to avoid a set of polygonal obstacles in plane is considered. Using well-known methods, a shortest path from s to d can be computed with a time complexity of O(n2) where n is the total number of obstacle vertices. The focus here is in 1. (a) planning paths faster at the expense of setting for suboptimal path lengths and 2. (b) performance analysis of simple and/or well-known suboptimal methods. A method that enables a hierarchical implementation of any path planning algorithm with no increase in the worst-case time complexity, is presented; this implementation enables fast planning of simple paths. Then methods are presented based on the Voronoi diagrams, trapezoidal decomposition and triangulation, which compute (suboptimal) paths in O(n√log n) time with the preprocessing costs of O(n log n), O(n2) and O(n log n), respectively. Using existing navigational algorithms for unknown terrains, algorithms that run in O(n log n) time (after preprocessing) and yield suboptimal paths, are presented. For all these algorithms, upper bounds on the path lengths are estimated in terms of the shortest of the obstacles, etc.
Original language | English |
---|---|
Pages (from-to) | 265-289 |
Number of pages | 25 |
Journal | Theoretical Computer Science |
Volume | 140 |
Issue number | 2 |
DOIs | |
State | Published - Apr 3 1995 |
Funding
*Research sponsored by the Engineering Research Program of the Office of Basic Energy Sciences, of the U.S. Department of Energy, under Contract No. DE-AC05-84OR21400 with Martin Marietta Energy Systems, Inc. In addition, this work is also partially funded by National Science Foundation under grant No IRI-9108610. *Email: [email protected]. Part of this work was performed while the author was with the Department of Computer Science, Old Dominion University, Norfolk, VA 23529-0162, USA
Funders | Funder number |
---|---|
National Science Foundation | IRI-9108610 |
U.S. Department of Energy | DE-AC05-84OR21400 |
Directorate for Computer and Information Science and Engineering | 9108610 |
Basic Energy Sciences |