An Anytime Algorithm for Chance Constrained Stochastic Shortest Path Problems and Its Application to Aircraft Routing

Sungkweon Hong, Sang Uk Lee, Xin Huang, Majid Khonji, Rashid Alyassi, Brian C. Williams

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

10 Scopus citations

Abstract

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).

Original languageBritish English
Title of host publication2021 IEEE International Conference on Robotics and Automation, ICRA 2021
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages475-481
Number of pages7
ISBN (Electronic)9781728190778
DOIs
StatePublished - 2021
Event2021 IEEE International Conference on Robotics and Automation, ICRA 2021 - Xi'an, China
Duration: 30 May 20215 Jun 2021

Publication series

NameProceedings - IEEE International Conference on Robotics and Automation
Volume2021-May
ISSN (Print)1050-4729

Conference

Conference2021 IEEE International Conference on Robotics and Automation, ICRA 2021
Country/TerritoryChina
CityXi'an
Period30/05/215/06/21

Fingerprint

Dive into the research topics of 'An Anytime Algorithm for Chance Constrained Stochastic Shortest Path Problems and Its Application to Aircraft Routing'. Together they form a unique fingerprint.

Cite this