Week 8 Flashcards
What does a Search Problem consist of?
State Space: all possible states.
Start State
Goal Test: whether the goal state is achieved or not.
Successor (Transition) Function: what are the available actions and where will it land the agent.
Solution = sequence of actions that transforms start to goal state.
What is Depth-First Search?
Deepest node is expanded first.
Tie is broken left to right.
What is Breadth-First Search?
Move layer by layer.
What are the two types of Search Problems?
Planning: A sequence of actions.
Identification: An assignment - we care about goal, not path.
What is a Constraint Satisfaction Problem?
State is defined by variable Xi with values from a domain.
Goal test is a set of constraints specifying allowable combinations of values for subset of variables.
What does a CSP consist of?
A set of variables + constraints.
A domain for each variable.
Assignment is complete (a solution) if every variable has a value, otherwise partial.
What are Constraint Graphs?
Used to represent relations among constraints in CSPs.
Nodes are variables and arcs are constraints.
CSP algorithms use these to speed up search.
What are the different types of CSP?
Finite domain variables.
Infinite domain variables - e.g. time.
Unary constraints - single variable has reducing domains.
Binary, high-order constraints.
What is Generate and Test?
Exhaustive algorithm which generates all complete assignments, then tests, returning first one to satisfy all constraints.
Needs to store all d^n assignments.
What is Backtracking Search?
A DFS method.
Check constraints as you go and consider one variable at a layer.
How is Backtracking improved?
Filtering: Detect inevitable failure early.
Ordering: Assign variable with smallest domain first.
What is Forward Checking?
Cross of values that break constraints whenn adding to existing assignments.
What is a Local Search Method?
Find solutions quickly.
Start with arbitary complete assignment and improve iteratively.
What is Filtering?
Keep track of domains for unassigned variables and cross off bad options.
What are Soft Constraints in CSPs?
Preferences/objectives - need to optimize.
