Home | | Artificial Intelligence | Constraint Satisfaction Problems (CSPS)

Chapter: Artificial Intelligence

Constraint Satisfaction Problems (CSPS)

state is a "black box“ – any data structure that supports successor function, heuristic function, and goal test

CONSTRAINT SATISFACTION PROBLEMS (CSPS)

 

•                      Standard search problem:

 

– state is a "black box“ – any data structure that supports successor function, heuristic function, and goal test

 

•                      CSP:

 

–  state is defined by variables Xi with values from domain Di

 

 

 

– goal test is a set of constraints specifying allowable combinations of values for subsets of variables

 

–  Simple example of a formal representation language

 

•                      Allows useful general-purpose algorithms with more power than standard search algorithms

 

Arc consistency:

 

1.                                  Arc refers to a directed arc in the constraint graph.

 

2.                                  Arc consistency checking can be applied either as a preprocessing. step before the process must be applied repeatedly until no more inconsistency remain.

 

Path consistency:

 

Path consistency means that any pair of adjacent variables can always be extended to a third neighboring variable, this is also called path consistency

 

K-consistency:

 

Stronger forms of propagation can be defined using the notation called K-consistency. A CSP is K-consistency if for any set of K-1 variables and for any consistent assignment to those variables, a constant value can always be assigned to any variable.

 

Example: Map-Coloring


 

•                      Variables WA, NT, Q, NSW, V, SA, T

 

•                      Domains Di = {red,green,blue}

 

•                      Constraints: adjacent regions must have different colors

 

e.g., WA ≠ NT, or (WA,NT) in ,(red,green),(red,blue),(green,red), (green,blue),(blue,red),(blue,green)}


• Solutions are complete and consistent assignments, e.g., WA = red, NT = green,Q = red,NSW= green,V = red,SA = blue,T = green

 

Constraint graph

 

•                      Binary CSP: each constraint relates two variables

•                      Constraint graph: nodes are variables, arcs are constraints


 

Varieties of CSPs

 

•                     Discrete variables

 

–  finite domains:

 

•                                                                     n variables, domain size d -O(dn) complete assignments

 

•                                                                     e.g., Boolean CSPs, incl.~Boolean satisfiability (NP-complete)

 

–  infinite domains:

 

•                                                                     integers, strings, etc.

 

•                                                                     e.g., job scheduling, variables are start/end days for each job

 

•                                                                     need a constraint language, e.g., StartJob1 + 5 ≤ StartJob3

 

•                                                                     Continuous variables

 

–  e.g., start/end times for Hubble Space Telescope observations

 

–  linear constraints solvable in polynomial time by linear programming

 

Varieties of constraints:

 

•                     Unary constraints involve a single variable,

 

–  e.g., SA ≠ green

 

•                     Binary constraints involve pairs of variables,

 

–  e.g., SA ≠ WA

 

–  Higher-order constraints involve 3 or more variables,

 

–  e.g., cryptarithmetic column constraints


Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Artificial Intelligence : Constraint Satisfaction Problems (CSPS) |


Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.