Show simple item record

dc.contributor.authorZhang, Yuening
dc.date.accessioned2021-03-02T23:13:24Z
dc.date.available2021-03-02T23:13:24Z
dc.date.issued2021-03-02
dc.identifier.urihttps://hdl.handle.net/1721.1/130057
dc.description.abstractSimple 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.en_US
dc.language.isoenen_US
dc.rightsCC0 1.0 Universal*
dc.rights.urihttp://creativecommons.org/publicdomain/zero/1.0/*
dc.subjecttemporal networksen_US
dc.subjectdynamic controllabilityen_US
dc.subjectbucket eliminationen_US
dc.subjectscheduling with uncertaintyen_US
dc.titleBucket Elimination Algorithm for Dynamic Controllability Checking of Simple Temporal Networks with Uncertaintyen_US
dc.typeTechnical Reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record