The 2-Expert Approach to Online Constraint Solving

摘要: Modern constraint programming (CP) applications are inherently both online systems and mixed-initiative systems. Or at least they should be so. Applications such as satellite tasking, day of operations planning, maintenance scheduling and vehicle dispatching exhibit these requirements. The constraint satisfaction problems (CSPs) they solve are not static but change unpredictably during the schedule generation process. Likewise, these applications usually involve mixedinitiative reasoning where the user and the system work together to solve the CSP. The user is also an expert in the problem domain who embodies unstated constraints and may know good heuristics for finding solutions. Acknowledging this, the so-called 2-expert approach attempts to support collaboration between the user and system instead of completely automating the solution process. Traditional CP algorithms do not serve online and mixed-initiative applications well. New architectures are required which support: 1) dynamic constraint propagation methods; and 2) semi-systematic search algorithms. We believe that these two areas should be complementary foci of CP research. Our rationale is as follows.Online systems confront CSPs that change dynamically. Changes in the problem (environment) are seen as non-monotonic constraint addition, deletion and revision in the CSP model. Likewise, mixed-initiative reasoning views the user as an induced k-ary constraint on the CSP. Some k variables in the model are controllable (in part) by the user as unary constraints on these variables. This induced user constraint is also non-monotonic, changing spontaneously via user …