TY - JOUR
T1 - Shortest Path Planning for Energy-Constrained Mobile Platforms Navigating on Uneven Terrains
AU - Ganganath, Nuwan
AU - Cheng, Chi Tsun
AU - Fernando, Tyrone
AU - Iu, Herbert H.C.
AU - Tse, Chi K.
N1 - Funding Information:
Manuscript received March 5, 2018; revised May 1, 2018; accepted May 24, 2018. Date of publication June 6, 2018; date of current version September 4, 2018. This work was supported by the Hong Kong Ph.D. Fellowship Scheme, the Endeavour Research Fellowship from the Australian Government, and the Department of Electronic and Information Engineering, the Hong Kong Polytechnic University (Project G-YBXK). Paper no. TII-18-0598. (Corresponding author: Nuwan Ganganath.) N. Ganganath was with the Department of Electronic and Information Engineering, Hong Kong Polytechnic University, Hung Hom 999077, Hong Kong. He is now with the School of Electrical, Electronic and Computer Engineering, the University of Western Australia, Crawley, WA 6009, Australia (e-mail: [email protected]).
Publisher Copyright:
© 2005-2012 IEEE.
PY - 2018/9
Y1 - 2018/9
N2 - Finding a shortest feasible path between two given locations is a common problem in many real-world applications. Previous studies have shown that mobile platforms would consume excessive energy when moving along shortest paths on uneven terrains, which often consist of rapid elevation changes. Mobile platforms powered by portable energy sources may fail to follow such paths due to the limited energy available. This paper proposes a new heuristic search algorithm called constraints satisfying A∗ (CSA) to find solutions to such resource constrained shortest path problems. When CSA∗ is guided by admissible heuristics, it guarantees to find a globally optimal solution to a given constrained search problem if such a solution exists. When CSA∗ is guided by consistent heuristics, it is optimally efficient over a class of equally informed admissible constrained search algorithms with respect to the set of paths expanded. Test results obtained using real terrain data verify the applicability of the proposed algorithm in shortest path planning for energy-constrained mobile platforms on uneven terrains.
AB - Finding a shortest feasible path between two given locations is a common problem in many real-world applications. Previous studies have shown that mobile platforms would consume excessive energy when moving along shortest paths on uneven terrains, which often consist of rapid elevation changes. Mobile platforms powered by portable energy sources may fail to follow such paths due to the limited energy available. This paper proposes a new heuristic search algorithm called constraints satisfying A∗ (CSA) to find solutions to such resource constrained shortest path problems. When CSA∗ is guided by admissible heuristics, it guarantees to find a globally optimal solution to a given constrained search problem if such a solution exists. When CSA∗ is guided by consistent heuristics, it is optimally efficient over a class of equally informed admissible constrained search algorithms with respect to the set of paths expanded. Test results obtained using real terrain data verify the applicability of the proposed algorithm in shortest path planning for energy-constrained mobile platforms on uneven terrains.
KW - (CSA
KW - )
KW - Constraints satisfying A
KW - heuristic search
KW - multiple resource constraints
KW - outdoor navigation
KW - shortest paths
UR - http://www.scopus.com/inward/record.url?scp=85048200988&partnerID=8YFLogxK
U2 - 10.1109/TII.2018.2844370
DO - 10.1109/TII.2018.2844370
M3 - Journal article
AN - SCOPUS:85048200988
SN - 1551-3203
VL - 14
SP - 4264
EP - 4272
JO - IEEE Transactions on Industrial Informatics
JF - IEEE Transactions on Industrial Informatics
IS - 9
M1 - 8373749
ER -