Faster Dynamic Controllability Checking in Temporal Networks with Integer Bounds
Simple Temporal Networks with Uncertainty (STNUs) provide a useful formalism with which to reason about events and the temporal constraints that apply to them. STNUs are in particular notable because they facilitate reasoning over stochastic, or uncontrollable, actions and their corresponding durati...
| Príomhchruthaitheoirí: | , |
|---|---|
| Formáid: | Alt |
| Teanga: | en_US |
| Foilsithe / Cruthaithe: |
International Joint Conference in Artificial Intelligence
2019
|
| Ábhair: | |
| Rochtain ar líne: | https://hdl.handle.net/1721.1/121993 |
| _version_ | 1826200244868612096 |
|---|---|
| author | Bhargava, Nikhil Williams, Brian C. |
| author_facet | Bhargava, Nikhil Williams, Brian C. |
| author_sort | Bhargava, Nikhil |
| collection | MIT |
| description | Simple Temporal Networks with Uncertainty (STNUs) provide a useful formalism with which to reason about events and the temporal constraints that apply to them. STNUs are in particular notable because they facilitate reasoning over stochastic, or uncontrollable, actions and their corresponding durations. To evaluate the feasibility of a set of constraints associated with an STNU, one checks the network's \textit{dynamic controllability}, which determines whether an adaptive schedule can be constructed on-the-fly. Our work provides a dynamic controllability checker that is able to quickly refute the controllability of an STNU with integer bounds, such as those found in planning problems. Our work is faster than the existing best runtime for networks with integer bounds and executes in O(min(mn, m\sqrt{n}\log{N}) + km + k^2n + kn\log{n}). Our approach pre-processes the STNU using an existing O(n^3) dynamic controllability checking algorithm and provides tighter bounds on its runtime. This makes our work easily adaptable to other algorithms that rely on checking variants of dynamic controllability. |
| first_indexed | 2024-09-23T11:33:25Z |
| format | Article |
| id | mit-1721.1/121993 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:33:25Z |
| publishDate | 2019 |
| publisher | International Joint Conference in Artificial Intelligence |
| record_format | dspace |
| spelling | mit-1721.1/1219932019-08-15T17:30:02Z Faster Dynamic Controllability Checking in Temporal Networks with Integer Bounds Bhargava, Nikhil Williams, Brian C. temporal reasoning scheduling Simple Temporal Networks with Uncertainty (STNUs) provide a useful formalism with which to reason about events and the temporal constraints that apply to them. STNUs are in particular notable because they facilitate reasoning over stochastic, or uncontrollable, actions and their corresponding durations. To evaluate the feasibility of a set of constraints associated with an STNU, one checks the network's \textit{dynamic controllability}, which determines whether an adaptive schedule can be constructed on-the-fly. Our work provides a dynamic controllability checker that is able to quickly refute the controllability of an STNU with integer bounds, such as those found in planning problems. Our work is faster than the existing best runtime for networks with integer bounds and executes in O(min(mn, m\sqrt{n}\log{N}) + km + k^2n + kn\log{n}). Our approach pre-processes the STNU using an existing O(n^3) dynamic controllability checking algorithm and provides tighter bounds on its runtime. This makes our work easily adaptable to other algorithms that rely on checking variants of dynamic controllability. 2019-08-15T17:30:01Z 2019-08-15T17:30:01Z 2019-08 Article https://hdl.handle.net/1721.1/121993 en_US application/pdf International Joint Conference in Artificial Intelligence |
| spellingShingle | temporal reasoning scheduling Bhargava, Nikhil Williams, Brian C. Faster Dynamic Controllability Checking in Temporal Networks with Integer Bounds |
| title | Faster Dynamic Controllability Checking in Temporal Networks with Integer Bounds |
| title_full | Faster Dynamic Controllability Checking in Temporal Networks with Integer Bounds |
| title_fullStr | Faster Dynamic Controllability Checking in Temporal Networks with Integer Bounds |
| title_full_unstemmed | Faster Dynamic Controllability Checking in Temporal Networks with Integer Bounds |
| title_short | Faster Dynamic Controllability Checking in Temporal Networks with Integer Bounds |
| title_sort | faster dynamic controllability checking in temporal networks with integer bounds |
| topic | temporal reasoning scheduling |
| url | https://hdl.handle.net/1721.1/121993 |
| work_keys_str_mv | AT bhargavanikhil fasterdynamiccontrollabilitycheckingintemporalnetworkswithintegerbounds AT williamsbrianc fasterdynamiccontrollabilitycheckingintemporalnetworkswithintegerbounds |