Augmenting Stream Constraint Programming with Eventuality Conditions
COM2 Level 4
Executive Classroom, COM2-04-02
Abstract:
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 \verb~@~ 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. The talk will be augmented with a number of modeling examples to illustrate the ideas as well as the expressiveness of the stream constraint programming approach
Biodata:
Jimmy Lee obtained both his BMath (Hons) and MMath degrees at the University of Waterloo, and completed his doctoral studies at the University of Victoria. Upon graduation, he joined The Chinese University of Hong Kong (CUHK), where he is now Assistant Dean (Education) in the Faculty of Engineering and Professor in the Department of Computer Science and Engineering. His research focuses on the theory and practice of constraint satisfaction and optimization with applications in scheduling, resource allocation, and combinatorial problems. During 2017-18, Jimmy joined hand with Peter Stuckey to launch a series of MOOCs on Coursera in both Chinese and English on modeling and solving discrete optimization problems using the Fantasy-based Learning approach, and received good feedbacks from the learners' community. Jimmy is a two-time recipient (2004 and 2015) of the CUHK Vice-Chancellor's Exemplary Teaching Award and was bestowed in 2017 the CUHK University Education Award, the highest honor in education at CUHK.