Luke Hunsberger, Roberto Posenato |
PosterID:
67
PDF
Slides
BibTeX
|
| A Conditional Simple Temporal Network (CSTN) is a structure for representing and reasoning about time in domains where temporal constraints may be conditioned on outcomes of observations made in real-time. A CSTN is dynamically consistent (DC) if there is a strategy for executing its time-points such that all relevant constraints will necessarily be satisfied no matter which outcomes happen to be observed. The literature on CSTNs contains only one sound-and-complete DC-checking algorithm that has been implemented and empirically evaluated. It is a graph-based algorithm that propagates labeled constraints/edges. A second algorithm has been proposed, but not evaluated. It aims to speed up DC checking by more efficiently dealing with so-called negative q-loops. This paper presents a new approach to DC-checking for CSTNs that involves two phases. The first phase focuses on identifying negative q-loops and labeling key time-points within such loops. The second phase focuses on computing (labeled) distances from each time-point to a single sink node. The new algorithm, which is also sound and complete for DC-checking, is then empirically evaluated against both pre-existing algorithms and shown to be much faster across not only previously published benchmark problems, but also a new set of benchmark problems. The results show that, on DC instances, the new algorithm tends to be an order of magnitude faster than both existing algorithms. On all other benchmark cases, the new algorithm performs better than or equivalently to the existing algorithms. | |
| Canb | 10/29/2020, 03:00 – 04:00 |
| 10/31/2020, 10:00 – 11:00 |
| Paris | 10/28/2020, 17:00 – 18:00 |
| 10/31/2020, 00:00 – 01:00 |
| NYC | 10/28/2020, 12:00 – 13:00 |
| 10/30/2020, 19:00 – 20:00 |
| LA | 10/28/2020, 09:00 – 10:00 |
| 10/30/2020, 16:00 – 17:00 |
Online Traffic Signal Control through Sample-Based Constrained Optimization
Srishti Dhamija, Alolika Gon, Pradeep Varakantham, William Yeoh
Learning Model Parameters for Decentralized Schedule-Driven Traffic Control
Hsu-Chieh Hu, Stephen F. Smith
Faster Dynamic-Consistency Checking for Conditional Simple Temporal Networks
Luke Hunsberger, Roberto Posenato
Scheduling with Complex Consumptive Resources for a Planetary Rover
Wayne Chi, Steve Chien, Jagriti Agrawal