Premium
Constraint Reasoning about Repeating Events: Satisfaction and Optimization[Note 1. Address correspondence to the author at NASA Ames Research ...]
Author(s) -
Morris Robert A.,
Khatib Lina
Publication year - 2000
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/0824-7935.00113
Subject(s) - constraint satisfaction problem , constraint satisfaction , computer science , job shop scheduling , local consistency , scheduling (production processes) , constraint programming , mathematical optimization , representation (politics) , range (aeronautics) , constraint satisfaction dual problem , semiring , theoretical computer science , artificial intelligence , mathematics , schedule , materials science , politics , probabilistic logic , stochastic programming , political science , law , composite material , operating system , pure mathematics
Effective manipulation of temporal information about periodic events is required for solving complex problems such as long‐range scheduling or querying temporal information. Furthermore, many problems involving repeating events involve the optimization of temporal aspects of these events (e.g., minimizing make‐span in job‐shop scheduling). In this paper, a constraint‐based formulation of reasoning problems with repeating events is presented, and its complexity is analyzed for a range of problems. Optimization constraints are interpreted formally using the Semiring CSPs (SCSP) representation of optimization in constraint reasoning. This allows for familiar algorithms such as branch‐and‐bound to be applied to solving them.