Bucket Elimination Algorithm for Dynamic Controllability Checking of Simple Temporal Networks with Uncertainty
Simple Temporal Networks with Uncertainty (STNU) can represent temporal problems where duration between events may be uncontrollable, e.g. when the event is caused by nature. An STNU is dynamically controllable (DC) if it can be successfully scheduled online. In this paper, we introduce a novel usag...
| Main Author: | |
|---|---|
| Format: | Technical Report |
| Language: | English |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/1721.1/130057 |
| _version_ | 1811095943403012096 |
|---|---|
| author | Zhang, Yuening |
| author_facet | Zhang, Yuening |
| author_sort | Zhang, Yuening |
| collection | MIT |
| description | Simple Temporal Networks with Uncertainty (STNU) can represent temporal problems where duration between events may be uncontrollable, e.g. when the event is caused by nature. An STNU is dynamically controllable (DC) if it can be successfully scheduled online. In this paper, we introduce a novel usage of bucket elimination algorithms for DC checking that matches the state of the art in achieving O(n^3) performance. Bucket elimination algorithms exist for STNs (path consistency and Fourier algorithms), but adapting it to STNUs is non-trivial. As a result, consistency checking becomes a special case of our algorithm. Due to the familiarity to bucket elimination algorithms, the final algorithm is easier to understand and implement. Additionally, conflict extraction is also easily supported in this framework. |
| first_indexed | 2024-09-23T16:35:10Z |
| format | Technical Report |
| id | mit-1721.1/130057 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T16:35:10Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/1300572021-03-03T03:01:52Z Bucket Elimination Algorithm for Dynamic Controllability Checking of Simple Temporal Networks with Uncertainty Zhang, Yuening temporal networks dynamic controllability bucket elimination scheduling with uncertainty Simple Temporal Networks with Uncertainty (STNU) can represent temporal problems where duration between events may be uncontrollable, e.g. when the event is caused by nature. An STNU is dynamically controllable (DC) if it can be successfully scheduled online. In this paper, we introduce a novel usage of bucket elimination algorithms for DC checking that matches the state of the art in achieving O(n^3) performance. Bucket elimination algorithms exist for STNs (path consistency and Fourier algorithms), but adapting it to STNUs is non-trivial. As a result, consistency checking becomes a special case of our algorithm. Due to the familiarity to bucket elimination algorithms, the final algorithm is easier to understand and implement. Additionally, conflict extraction is also easily supported in this framework. 2021-03-02T23:13:24Z 2021-03-02T23:13:24Z 2021-03-02 Technical Report https://hdl.handle.net/1721.1/130057 en CC0 1.0 Universal http://creativecommons.org/publicdomain/zero/1.0/ application/pdf |
| spellingShingle | temporal networks dynamic controllability bucket elimination scheduling with uncertainty Zhang, Yuening Bucket Elimination Algorithm for Dynamic Controllability Checking of Simple Temporal Networks with Uncertainty |
| title | Bucket Elimination Algorithm for Dynamic Controllability Checking of Simple Temporal Networks with Uncertainty |
| title_full | Bucket Elimination Algorithm for Dynamic Controllability Checking of Simple Temporal Networks with Uncertainty |
| title_fullStr | Bucket Elimination Algorithm for Dynamic Controllability Checking of Simple Temporal Networks with Uncertainty |
| title_full_unstemmed | Bucket Elimination Algorithm for Dynamic Controllability Checking of Simple Temporal Networks with Uncertainty |
| title_short | Bucket Elimination Algorithm for Dynamic Controllability Checking of Simple Temporal Networks with Uncertainty |
| title_sort | bucket elimination algorithm for dynamic controllability checking of simple temporal networks with uncertainty |
| topic | temporal networks dynamic controllability bucket elimination scheduling with uncertainty |
| url | https://hdl.handle.net/1721.1/130057 |
| work_keys_str_mv | AT zhangyuening bucketeliminationalgorithmfordynamiccontrollabilitycheckingofsimpletemporalnetworkswithuncertainty |