Risk-bounded Programming using Constrained, Hierarchical, Stochastic Shortest Path Problems

The escalating demand for autonomous systems that enhance human lives has emphasized a pressing need to ensure their safety. However, guaranteeing safety in the face of extensive decision-making and uncertain scenarios has proven to be a formidable challenge. We argue that an autonomous agent designed for safety-critical and largescale domains must successfully overcome the following challenges: 1) the agent must be able to make decisions by adhering to risk bounds to ensure safety; 2) it needs to understand and make decisions over hierarchical tasks to address the issue of scalability; 3) the agent should be able to generate contingencies so that there are predefined backup plans for various possible scenarios; and 4) it must ensure timely planning to prevent catastrophic consequences in time-critical and safety-critical applications. This thesis addresses all four needs by first framing a constrained and hierarchical stochastic shortest path problem (HC-SSP) and then solving it using an anytime algorithm. In this thesis, we present an executive named Zeppelin, which employs a divide-and- conquer approach to solving HC-SSP, leveraging the hierarchical structure of the problem to generate solutions in an anytime fashion. Zeppelin consists of two main components: ACDC, a risk-bounded conditional planner responsible for addressing individual tasks, and RHCP, a coordinating planner that decomposes hierarchically structured tasks into individual tasks and resolves them through ACDC calls. To solve individual tasks while adhering to Zeppelin’s anytime property, ACDC employs a two-stage approach. First, it solves a Lagrangian dual of the planning problem to find a feasible solution swiftly. Then, it incrementally updates the solution by iteratively generating candidates, thereby achieving the anytime property. A key underlying both stages is the reformulation of the constrained problem into a series of unconstrained problems, allowing ACDC to leverage off-the-shelf state-of-the-art solvers. RHCP employs an iterative resource allocation strategy, providing a systematic approach for decoupling hierarchically structured tasks. To effectively guide the search towards promising resource allocations, RHCP leverages the outputs of ACDC, specifically lower and upper bounds on the solution quality. By incorporating these bounds, RHCP can direct the search toward resource allocations that hold the potential for better solutions. We demonstrate Zeppelin in the context of commercial aircraft operations by deploying it as a mission manager for automated decision-making processes from departure to arrival. The experiment demonstrated that Zeppelin could generate an initial safe plan in just 1/20 of the computation time required by the state-of-the-art method. In addition, Zeppelin successfully achieved a near-optimal solution with a 1.6% optimality gap with minimal additional computation time, demonstrating its anytime property. This practical application not only highlights the capabilities of Zeppelin but also facilitates the identification and bridging of gaps between theoretical foundations and real-world applications.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Aeronautics and Astronautics

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2023

Author dc:creator

• Hong, Sungkweon

Advisor dc:contributor.advisor

• Williams, Brian C.

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright retained by author(s)

Licence dc:rights.uri

• https://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/152763

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/152763