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.
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 - Constraints satisfying A (CSA)
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
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85048200988&origin=recordpage
U2 - 10.1109/TII.2018.2844370
DO - 10.1109/TII.2018.2844370
M3 - 21_Publication in refereed journal
VL - 14
SP - 4264
EP - 4272
JO - IEEE Transactions on Industrial Informatics
JF - IEEE Transactions on Industrial Informatics
SN - 1551-3203
IS - 9
M1 - 8373749
ER -