Title
Resolving Uncontrollable Conditional Temporal Problems Using Continuous Relaxations.
Abstract
Uncertainty is commonly encountered in temporal scheduling and planning problems, and can often lead to over-constrained situations. Previous relaxation algorithms for over-constrained temporal problems only work with requirement constraints, whose outcomes can be controlled by the agents. When applied to uncontrollable durations, these algorithms may only satisfy a subset of the random outcomes and hence their relaxations may fail during execution. In this paper, we present a new relaxation algorithm, Conflict-Directed Relaxation with Uncertainty (CDRU), which generates relaxations that restore the controllability of conditional temporal problems with uncontrollable durations. CDRU extends the Best-first Conflict-Directed Relaxation (BCDR) algorithm to uncontrollable temporal problems. It generalizes the conflict-learning process to extract conflicts from strong and dynamic controllability checking algorithms, and resolves the conflicts by both relaxing constraints and tightening uncontrollable durations. Empirical test results on a range of trip scheduling problems show that CDRU is efficient in resolving large scale uncontrollable problems: computing strongly controllable relaxations takes the same order of magnitude in time compared to consistent relaxations that do not account for uncontrollable durations. While computing dynamically controllable relaxations takes two orders of magnitude more time, it provides significant improvements in solution quality when compared to strongly controllable relaxations.
Year
Venue
Field
2014
Proceedings of the International Conference on Automated Planning and Scheduling
Mathematical optimization,Relaxation algorithm,Controllability,Computer science,Control theory,Scheduling (computing),Order of magnitude,Empirical research
DocType
ISSN
Citations 
Conference
2334-0835
6
PageRank 
References 
Authors
0.58
9
3
Name
Order
Citations
PageRank
Peng Yu1313.62
Cheng Fang2133.16
B C Williams32404426.13