TY - GEN
T1 - An Anytime Algorithm for Chance Constrained Stochastic Shortest Path Problems and Its Application to Aircraft Routing
AU - Hong, Sungkweon
AU - Lee, Sang Uk
AU - Huang, Xin
AU - Khonji, Majid
AU - Alyassi, Rashid
AU - Williams, Brian C.
N1 - Funding Information:
The work was partially supported by the Boeing Corporation, under grant 6943358, and the Khalifa University, under grant reference KKJRC-2019-Trans1.
Publisher Copyright:
© 2021 IEEE
PY - 2021
Y1 - 2021
N2 - Aircraft routing problem is a crucial component for flight automation. Despite recent successes, challenges still remain when the environment is dynamic and uncertain. In this paper, we tackle the following two challenges. First, when the environment is uncertain, it is much safer if the route planner can guarantee a specified level of safety. Second, when the environment is dynamic, the planner needs to adapt to the changes in the environment quickly. To address these challenges, we present three contributions. First, we propose formulating the aircraft routing problem under a dynamic and uncertain environment as a chance constrained stochastic shortest path (CC-SSP) problem. Second, we introduce an anytime algorithm for the CC-SSP problem, which is effective in a dynamic environment with limited planning time. To be more specific, we present two versions of the algorithm and compare their performances. Third, we show that the algorithm can be generalized to solve a larger class of problems called chance constrained partially observable Markov decision process (CC-POMDP).
AB - Aircraft routing problem is a crucial component for flight automation. Despite recent successes, challenges still remain when the environment is dynamic and uncertain. In this paper, we tackle the following two challenges. First, when the environment is uncertain, it is much safer if the route planner can guarantee a specified level of safety. Second, when the environment is dynamic, the planner needs to adapt to the changes in the environment quickly. To address these challenges, we present three contributions. First, we propose formulating the aircraft routing problem under a dynamic and uncertain environment as a chance constrained stochastic shortest path (CC-SSP) problem. Second, we introduce an anytime algorithm for the CC-SSP problem, which is effective in a dynamic environment with limited planning time. To be more specific, we present two versions of the algorithm and compare their performances. Third, we show that the algorithm can be generalized to solve a larger class of problems called chance constrained partially observable Markov decision process (CC-POMDP).
UR - http://www.scopus.com/inward/record.url?scp=85124358515&partnerID=8YFLogxK
U2 - 10.1109/ICRA48506.2021.9561229
DO - 10.1109/ICRA48506.2021.9561229
M3 - Conference contribution
AN - SCOPUS:85124358515
T3 - Proceedings - IEEE International Conference on Robotics and Automation
SP - 475
EP - 481
BT - 2021 IEEE International Conference on Robotics and Automation, ICRA 2021
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2021 IEEE International Conference on Robotics and Automation, ICRA 2021
Y2 - 30 May 2021 through 5 June 2021
ER -