.png){kind=icon}
.png){kind=icon}
Return
Efficient solution techniques for disjunctive temporal reasoning problems
.png){kind=icon}
OA
AI
DOI：10.1016/S0004-3702(03)00113-9.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Over the past few years, a new constraint-based formalism for temporal reasoning has been developed to represent and reason about Disjunctive Temporal Problems (DTPs). The class of DTPs is significantly more expressive than other problems previously studied in constraint-based temporal reasoning. In this paper we present a new algorithm for DTP solving, called Epilitis, which integrates strategies for efficient DTP solving from the previous literature, including conflict-directed backjumping, removal of subsumed variables, and semantic branching, and further adds no-good recording as a central technique. We discuss the theoretical and technical issues that arise in successfully integrating this range of strategies with one another and with no-good recording in the context of DTP solving. Using an implementation of Epilitis, we explore the effectiveness of various combinations of strategies for solving DTPs, and based on this analysis we demonstrate that Epilitis can achieve a nearly two order-of-magnitude speed-up over the previously published algorithms on benchmark problems in the DTP literature. (C) 2003 Elsevier B.V. All rights reserved.
Keywords:
constraint-based temporal reasoning
constraint satisfaction
scheduling
planning
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
13.9
Papers:
6.1K
Citations:
1.9W
Organization
No organization information available