Risk-Bounded Dynamic Scheduling of Temporal Plans
Real-world activities often have uncontrollable durations, which is a scheduling challenge for temporal planners, where despite uncertainty, we need to meet deadlines and coordination constraints. Missing these requirements can be costly, but it may be impossible to guarantee complete success. Inste...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2023
|
| Online Access: | https://hdl.handle.net/1721.1/147542 |
| _version_ | 1811082942065147904 |
|---|---|
| author | Wang, Andrew J. |
| author2 | Williams, Brian C. |
| author_facet | Williams, Brian C. Wang, Andrew J. |
| author_sort | Wang, Andrew J. |
| collection | MIT |
| description | Real-world activities often have uncontrollable durations, which is a scheduling challenge for temporal planners, where despite uncertainty, we need to meet deadlines and coordination constraints. Missing these requirements can be costly, but it may be impossible to guarantee complete success. Instead, we aim to control the risk of scheduling failure, so we consider scheduling problems where activity durations are modeled with probability distributions. Then, by specifying a maximum allowable probability of failure, called a chance constraint, we gain access to solutions that are sufficiently safe. It is also known that reacting to duration outcomes throughout plan execution is key to avoiding failure. Thus, the goal of this thesis is to produce dynamic scheduling policies for chance-constrained temporal plans.
Our strategy is to build on prior art in chance-constrained static scheduling. First, we characterize more rigorously the reformulation of the original problem into that of risk allocation. This separates the probabilistic condition from the temporal conditions, but also introduces conservatism. Second, we generalize the static solution’s conflict-directed hybrid algorithm to produce dynamic policies. Due to the chance constraint, we still employ nonlinear programming (NLP) to generate risk allocations, but now we leverage dynamic controllability (DC) algorithms to generate scheduling conflicts. However, those conflicts’ resolutions are disjunctive constraints, which require combinatorial search and not just an NLP. So third, we map selected clauses into a form identical to that solved by the conflict-directed algorithm for static schedules. Our algorithmic architecture thus wraps the chance-constrained static solution within another layer of conflict discovery and resolution.
We evaluate our approach on lunar construction and car-sharing scenarios, which exemplify real-world complexity in coordinating parallel threads. We demonstrate that moving from chance-constrained static to dynamic policies dramatically increases the problem sizes we can schedule by at least 10 times. Additionally, our strategy for reallocating risk, based on discovered conflicts, solves an additional 10% of the benchmark scenarios over that achieved by uniform risk allocation. Finally, we show that our conflict-directed approach’s runtime is an order-of-magnitude faster than solving a full encoding. |
| first_indexed | 2024-09-23T12:14:35Z |
| format | Thesis |
| id | mit-1721.1/147542 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T12:14:35Z |
| publishDate | 2023 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1475422023-01-20T03:34:39Z Risk-Bounded Dynamic Scheduling of Temporal Plans Wang, Andrew J. Williams, Brian C. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Real-world activities often have uncontrollable durations, which is a scheduling challenge for temporal planners, where despite uncertainty, we need to meet deadlines and coordination constraints. Missing these requirements can be costly, but it may be impossible to guarantee complete success. Instead, we aim to control the risk of scheduling failure, so we consider scheduling problems where activity durations are modeled with probability distributions. Then, by specifying a maximum allowable probability of failure, called a chance constraint, we gain access to solutions that are sufficiently safe. It is also known that reacting to duration outcomes throughout plan execution is key to avoiding failure. Thus, the goal of this thesis is to produce dynamic scheduling policies for chance-constrained temporal plans. Our strategy is to build on prior art in chance-constrained static scheduling. First, we characterize more rigorously the reformulation of the original problem into that of risk allocation. This separates the probabilistic condition from the temporal conditions, but also introduces conservatism. Second, we generalize the static solution’s conflict-directed hybrid algorithm to produce dynamic policies. Due to the chance constraint, we still employ nonlinear programming (NLP) to generate risk allocations, but now we leverage dynamic controllability (DC) algorithms to generate scheduling conflicts. However, those conflicts’ resolutions are disjunctive constraints, which require combinatorial search and not just an NLP. So third, we map selected clauses into a form identical to that solved by the conflict-directed algorithm for static schedules. Our algorithmic architecture thus wraps the chance-constrained static solution within another layer of conflict discovery and resolution. We evaluate our approach on lunar construction and car-sharing scenarios, which exemplify real-world complexity in coordinating parallel threads. We demonstrate that moving from chance-constrained static to dynamic policies dramatically increases the problem sizes we can schedule by at least 10 times. Additionally, our strategy for reallocating risk, based on discovered conflicts, solves an additional 10% of the benchmark scenarios over that achieved by uniform risk allocation. Finally, we show that our conflict-directed approach’s runtime is an order-of-magnitude faster than solving a full encoding. Ph.D. 2023-01-19T19:57:20Z 2023-01-19T19:57:20Z 2022-09 2022-10-19T19:11:02.869Z Thesis https://hdl.handle.net/1721.1/147542 In Copyright - Educational Use Permitted Copyright MIT http://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Wang, Andrew J. Risk-Bounded Dynamic Scheduling of Temporal Plans |
| title | Risk-Bounded Dynamic Scheduling of Temporal Plans |
| title_full | Risk-Bounded Dynamic Scheduling of Temporal Plans |
| title_fullStr | Risk-Bounded Dynamic Scheduling of Temporal Plans |
| title_full_unstemmed | Risk-Bounded Dynamic Scheduling of Temporal Plans |
| title_short | Risk-Bounded Dynamic Scheduling of Temporal Plans |
| title_sort | risk bounded dynamic scheduling of temporal plans |
| url | https://hdl.handle.net/1721.1/147542 |
| work_keys_str_mv | AT wangandrewj riskboundeddynamicschedulingoftemporalplans |