Augmenting Stream Constraint Programming with Eventuality Conditions
This work incrementally improves the expressiveness of stream constraint programming for planning and control applications.
The authors tackled the problem of limited expressiveness in stream constraint programming by introducing two new constructs: the 'until' constraint adapted from Linear Temporal Logic and the @ operator on streams, along with novel solving algorithms. They demonstrated competitive experimental results on the Missionaries and Cannibals puzzle and a grid path planning application compared to an existing CP method.
Stream constraint programming is a recent addition to the family of constraint programming frameworks, where variable domains are sets of infinite streams over finite alphabets. Previous works showed promising results for its applicability to real-world planning and control problems. In this paper, motivated by the modelling of planning applications, we improve the expressiveness of the framework by introducing 1) the "until" constraint, a new construct that is adapted from Linear Temporal Logic and 2) the @ operator on streams, a syntactic sugar for which we provide a more efficient solving algorithm over simple desugaring. For both constructs, we propose corresponding novel solving algorithms and prove their correctness. We present competitive experimental results on the Missionaries and Cannibals logic puzzle and a standard path planning application on the grid, by comparing with Apt and Brand's method for verifying eventuality conditions using a CP approach.