Algorithmic Techniques in (Soft) Constraint Satisfaction and Temporal Reasoning


Satish Kumar Thittamaranahalli
University of California, Berkeley

“Constraint Reasoning” and “Temporal Reasoning” are fundamental to many applications in AI (Artificial Intelligence). In the first part of the talk, I will introduce the notion of “Smoothness” in Constraint Satisfaction and briefly describe some of its implications/generalizations. In the second part, I will speak about Temporal Reasoning and Scheduling problems (that may or may not involve reasoning about Preferences). I will briefly describe three different techniques for tackling some such problems: (a) Exploiting “Smoothness” in certain kinds of metric temporal constraints, (b) Using “circuit- based” SAT encodings of certain kinds of “disjunctive” temporal constraints, and (c) Representing certain kinds of temporal reasoning problems (with Preferences) using “Flow” problems. In the third part of the talk, I will briefly describe how several useful classes of Soft Constraint Satisfaction and Energy Minimization problems can be solved efficiently by relating them to Minimum Weighted Vertex Cover problems (in Bipartite graphs).

Dr. Satish Kumar Thittamaranahalli (alias T. K. Satish Kumar) is currently a Postdoctoral Research Scholar at the University of California, Berkeley. He holds a PhD in Computer Science from Stanford University (March 2005), and was also a Visiting Student at the NASA Ames Research Center during the summers of 2000 and 2001. His research interests include Constraint Reasoning, Planning and Scheduling, Knowledge Representation, Model-based Diagnosis, Approximation and Randomization Techniques, Probabilistic Reasoning, Qualitative Reasoning, and Temporal Reasoning. He has published several (single-authored) research papers, and has served on the Program Committee of multiple AI (Artificial Intelligence) conferences. He has also received a "Best Student Paper Award" at the Fifteenth International Conference on Automated Planning and Scheduling (ICAPS 2005).