Open or Interactive Constraint Satisfaction
I'm not altogether convinced by the previous work on open and interactive constraints.

An attempt to study the tractability questions was:


Martin J. Green and Christopher Jefferson, Structural Tractability of Propagated Constraints, CP 2008.
doi: 10.1007/978-3-540-85958-1_25


although this paper does leave several major questions unanswered.  The approach via propagators in this paper is closely related to existing constraint solver implementations.

I think work on SMT (satisfiability modulo theories) is also closely related to your question.  SMT theories are often motivated by problems from software and hardware verification, but there do exist theories with an AI flavour.  I look forward to more applications built with SMT as the core technology, and to more work in constraints applying ideas from SMT.