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 design...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2023
|
| Online Access: | https://hdl.handle.net/1721.1/152763 |
| _version_ | 1826214431300780032 |
|---|---|
| author | Hong, Sungkweon |
| author2 | Williams, Brian C. |
| author_facet | Williams, Brian C. Hong, Sungkweon |
| author_sort | Hong, Sungkweon |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T16:05:15Z |
| format | Thesis |
| id | mit-1721.1/152763 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T16:05:15Z |
| publishDate | 2023 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1527632023-11-03T03:05:47Z Risk-bounded Programming using Constrained, Hierarchical, Stochastic Shortest Path Problems Hong, Sungkweon Williams, Brian C. Massachusetts Institute of Technology. Department of Aeronautics and Astronautics 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. Ph.D. 2023-11-02T20:14:19Z 2023-11-02T20:14:19Z 2023-09 2023-09-20T15:15:21.262Z Thesis https://hdl.handle.net/1721.1/152763 In Copyright - Educational Use Permitted Copyright retained by author(s) https://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Hong, Sungkweon Risk-bounded Programming using Constrained, Hierarchical, Stochastic Shortest Path Problems |
| title | Risk-bounded Programming using Constrained, Hierarchical, Stochastic Shortest Path Problems |
| title_full | Risk-bounded Programming using Constrained, Hierarchical, Stochastic Shortest Path Problems |
| title_fullStr | Risk-bounded Programming using Constrained, Hierarchical, Stochastic Shortest Path Problems |
| title_full_unstemmed | Risk-bounded Programming using Constrained, Hierarchical, Stochastic Shortest Path Problems |
| title_short | Risk-bounded Programming using Constrained, Hierarchical, Stochastic Shortest Path Problems |
| title_sort | risk bounded programming using constrained hierarchical stochastic shortest path problems |
| url | https://hdl.handle.net/1721.1/152763 |
| work_keys_str_mv | AT hongsungkweon riskboundedprogrammingusingconstrainedhierarchicalstochasticshortestpathproblems |