Name
Abstract | ||
|---|---|---|
Path-planning problems are fundamental in many applications, such as transportation, artificial intelligence, control of autonomous vehicles, and many more. In this paper, we consider the deterministic path-planning problem, equivalently, the single-pair shortest path problem on a given grid-like graph structure. Current commonly used algorithms in this area include the A* algorithm, Dijkstra's algorithm, and their numerous variants. We propose an innovative beamlet-based graph structure for path planning that utilizes multiscale information of the environment. This information is collected via a bottom-up fusion algorithm. This new graph structure goes beyond nearest-neighbor connectivity, incorporating long-distance interactions between the nodes of the graph. Based on this new graph structure, we obtain a multiscale version of A* , which is advantageous when preprocessing is allowable and feasible. Compared to the benchmark A* algorithm, the use of multiscale information leads to an improvement in terms of computational complexity. Numerical experiments indicate an even more favorable behavior than the one predicted by the theoretical complexity analysis. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1109/TAC.2012.2191836 | IEEE Trans. Automat. Contr. |
Keywords | Field | DocType |
Partitioning algorithms,Heuristic algorithms,Algorithm design and analysis,Complexity theory,Search problems,Image edge detection,Path planning | Graph theory,Mathematical optimization,Shortest path problem,Graph bandwidth,Suurballe's algorithm,Connectivity,Graph (abstract data type),Moral graph,Widest path problem,Mathematics | Journal |
Volume | Issue | ISSN |
57 | 5 | 0018-9286 |
Citations | PageRank | References |
6 | 0.51 | 18 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yibiao Lu | 1 | 23 | 1.58 |
| Xiaoming Huo | 2 | 157 | 24.83 |
| Panagiotis Tsiotras | 3 | 839 | 126.74 |