tags: classical ai
16:59; The doctor said we only care about the end goal, we can’t know the path
The successor function is what I do next, and it the assignment of a value to an unassigned variable.
The constraints can be a function like or a list off values like when A = 3, B = 4, etc..
The heuristics in search algorithms were always chosen depending on the problem, most of the time it would be the lower estimate to reach the goal. In CSP problems the heuristic is general purpose and mentioned later.
The domain consists of the values that are valid to represent my game or problem.
The end goal here is to satisfy some variables by giving them values that satisfy some constraints
I am given a bunch of statements, where I conclude my constraints from.
NOTE: In the section the TA concluded the time constraints of the problem using a time graph.
In binary constraint graph, the variables with their corresponding graphs are represented with circles or ovals and constraints are represented as rectangles between variables.
A possible world does not have to be a correct solution
Constraint types
Efficiency improved by changing the order of variable expansion
It is really not recommended to use BFS, because goals are always on the deepest layer, so doing BFS is only going to consume memory.
CSP Backtracking
It is a normal DFS search, but if we find an invalid path we don’t continue going deeper.
Notice the select ordering part, selecting the correct can lead to the solution faster.
CSP Backtracking with Constraint propagation
It is better for the algorithm to check the constraints before choosing the variables not after. It removes values from the domain of future variables.
Constraint propagation can be done by forward checking or arc consistency.
Due to forward checking we don’t have to really backtrack because we don’t have a large domain. Also forward checking only affects current neighbors, this is not arc consistency.
Most constrained variable, is the variable that has the fewest available legal values to choose from. In the first turn we usually can’t use the most constrained variable heuristic if all the domains have equal size.
Most constraining variable, is the variable which affects the most domains, the variable that when we choose a value for, will remove values from the most number of other variables.
The ordering heuristic is the order in which we will select values from the domain. Look at the pseudo code.
Least-constraining value heuristic: is an ordering heuristic which selects the value for the current variable that will cause the least domain constraints or alteration on other variables. It is only used for orderings when assigning to a variable.
Example
Constraint network
Arc consistency and domain consistency
NOTE: arc is the line connecting between a variable and its constraint, NOT between to variables.
To achieve this, look at the constraint and remove impossible values only until there is no more to prune. During this process all the values must satisfy the constraint to at least one value in the domain of the other side of the constraint, in other words we remove the value that is impossible to be.
Sometimes, even if a find all arcs consistent, there still could be contradiction and an impossible solution.
When constraints are initially satisfiable then I have to find a combination that satisfies - according to TA.
NOTE: Starting from 1:44:17, 4-queens problem is solved in the lecturing using forward checking and arc consistency.
The last line is return Dx but I couldn’t catch it in the slide.
