Fast execution of temporal plans with mixed discrete-continuous state constraints
Thesis: S.M., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2019
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2019
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/1721.1/122406 |
| _version_ | 1826212390183632896 |
|---|---|
| author | Chen, Jingkai(Scientist in aeronautics and astronautics)Massachusetts Institute of Technology. |
| author2 | Brian C. Williams. |
| author_facet | Brian C. Williams. Chen, Jingkai(Scientist in aeronautics and astronautics)Massachusetts Institute of Technology. |
| author_sort | Chen, Jingkai(Scientist in aeronautics and astronautics)Massachusetts Institute of Technology. |
| collection | MIT |
| description | Thesis: S.M., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2019 |
| first_indexed | 2024-09-23T15:20:56Z |
| format | Thesis |
| id | mit-1721.1/122406 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T15:20:56Z |
| publishDate | 2019 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1224062023-05-24T12:25:41Z Fast execution of temporal plans with mixed discrete-continuous state constraints Chen, Jingkai(Scientist in aeronautics and astronautics)Massachusetts Institute of Technology. Brian C. Williams. Massachusetts Institute of Technology. Department of Aeronautics and Astronautics. Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Aeronautics and Astronautics. Thesis: S.M., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2019 Cataloged from PDF version of thesis. Includes bibliographical references (pages 109-112). There has been a dramatic rise in networked embedded systems that play a central role in complex tasks. To achieve high performance and robustness, these systems need to configure and reconfigure on the fly, in light of the task requirements and system states. Communications networks, for example, plan routes and allocate bandwidth resources over time for different communication activities, while respecting through-put, delay, loss, and deadline constraints. However, existing approaches use simple discrete models to achieve goal sequences and thus cannot provide a high-fidelity plan for complex plan specifications in terms of time and state. In this thesis, we deliver Amundsen, an efficient configuration manager that supports complex concurrent tasks over time and state by reasoning over high-fidelity models. These models can encode different actuation modes with discrete and continuous specifications and temporal influences. Amundsen provides plans meeting mission requirements, which specify the timing of events, outline the mode changes throughout the mission, and allocate resources. The primary challenge of the configuration management problem is the computation required to handle the state and time constraints that are highly coupled. We address this challenge through the critical insight that the configuration management problem may be efficiently solved by dividing the problem into smaller subproblems such as scheduling and resource allocation, which is achieved by total ordering the events that represent time points in the goal specification. Each sub-problem may then be solved efficiently with existing highly optimized algorithms. We make two main technical contributions in this thesis. First, we identify the relevant sub-problems in the existing configuration management problems and provide tractable encodings. Second, we provide an algorithm to efficiently order the stages of the problem by learning and communicating the requirements for successful solutions to the sub-problems. We provide empirical evidence of the efficiency of Amundsen by benchmarking against UnifyHistory, a state-of-the-art solver to configure systems by unifying multiple timelines, on a communication network simulator. We show that our approach can dynamically manage hundreds of network requests over a network with hundreds of communication links in simulated missions given strict time limits. Our approach is also able to find plans in 10 times as many scenarios as the baseline solver. The work described in this thesis thus significantly advances the configuration management problem, both theoretically and practically. "Acknowledge DARPA for sponsoring this work for two and a half years"--Page 5 by Jingkai Chen. S.M. S.M. Massachusetts Institute of Technology, Department of Aeronautics and Astronautics 2019-10-04T21:32:46Z 2019-10-04T21:32:46Z 2019 2019 Thesis https://hdl.handle.net/1721.1/122406 1119723319 eng MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission. http://dspace.mit.edu/handle/1721.1/7582 112 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Aeronautics and Astronautics. Chen, Jingkai(Scientist in aeronautics and astronautics)Massachusetts Institute of Technology. Fast execution of temporal plans with mixed discrete-continuous state constraints |
| title | Fast execution of temporal plans with mixed discrete-continuous state constraints |
| title_full | Fast execution of temporal plans with mixed discrete-continuous state constraints |
| title_fullStr | Fast execution of temporal plans with mixed discrete-continuous state constraints |
| title_full_unstemmed | Fast execution of temporal plans with mixed discrete-continuous state constraints |
| title_short | Fast execution of temporal plans with mixed discrete-continuous state constraints |
| title_sort | fast execution of temporal plans with mixed discrete continuous state constraints |
| topic | Aeronautics and Astronautics. |
| url | https://hdl.handle.net/1721.1/122406 |
| work_keys_str_mv | AT chenjingkaiscientistinaeronauticsandastronauticsmassachusettsinstituteoftechnology fastexecutionoftemporalplanswithmixeddiscretecontinuousstateconstraints |