AAAI Publications, Twenty-Second International Joint Conference on Artificial Intelligence

Font Size: 
Constraint Programming on Infinite Data Streams
A. Lallouet, Y. C. Law, J. H. M. Lee, C. F. K. Siu

Last modified: 2011-06-28


Classical constraint satisfaction problems (CSPs) are commonly defined on finite domains. In real life, constrained variables can evolve over time. A variable can actually take an infinite sequence of values over discrete time points. In this paper, we propose constraint programming on infinite data streams, which provides a natural way to model constrained time-varying problems. In our framework, variable domains are specified by ω-regular languages. We introduce special stream operators as basis to form stream expressions and constraints. Stream CSPs have infinite search space. We propose a search procedure that can recognize and avoid infinite search over duplicate search space. The solution set of a stream CSP can be represented by a Büchi automaton allowing stream values to be non-periodic. Consistency notions are defined to reduce the search space early. We illustrate the feasibility of the framework by examples and experiments.

Full Text: PDF