IAI Chapter 3 Problem Solving as Search
Questions about the lecture 'Introduction to Artificial Intelligence' of the RWTH Aachen Chapter 3 Problem Solving as Search
Questions about the lecture 'Introduction to Artificial Intelligence' of the RWTH Aachen Chapter 3 Problem Solving as Search
-
- 1 / 59
-
Lernkarten
What is the definition of the exploration problem?
Incomplete knowledge about world and actions
What are the characteristics of the 8-queens problem? [4+2]
1. States are any placement of eight queens (1), placement of safe eight queens (2), placement of eight queens one per column (3)
2. Operators are placing queens on the board (1), from left on the board (2), moving an unsafe queen in the same column (3)
3. Goal is to place eight queens safe on the board
4. Path cost is zero
(1) has to many states
(2) has dead end states
What are the characteristics of the 8-puzzle? [4+1]
1. States are location of tiles // ~ 180k states
2. Operator is the movement of blank
3. Goal is reaching a matching tile map
4. Path cost is 1 unit
Search cost is NP-complete in the size of the puzzle to find the shortest solution
What are the characteristics of the vacuum world? [4+1]
1. States are all combinations of robot and dust presence (1), all subsets of other states (2)
2. Operators are moving the robot and sucking dust
3. Goal is that no dust is present (1), no dust anywhere in the state set (2)
4. Path cost is 1 unit
Single-state problem
What are the characteristics of the missionaries and cannibals? [4+3]
1. States are the triple x the number of cannibals, y the number of missionaries and z the boat on the left side of the river // Initial state (3,3,1) and not all states are reachable
2. Operators are two humans change river sides with the boat
3. Goal is reaching state (0,0,0)
4. Path cost is 1 unit per river crossing
Are all relevant information available? // Non-intended solutions
What can happen normally? // Sabotaging the correct solution
Solved by Saul Amarel (1968)
What is the definition of best-first (BeFS)?
Expand node with best node value
What is the definition of greedy (GS)? [4]
1. Estimate cost h(n) from current node n to goal state
2. Expand cost minimizing node
3. Completeness (if h unequal 0)
4. Memory and time cost in O(b^h)
What is the definition of A*? [2]
1. Combine UCS and GS
2. Estimate cost f(n) the sum from initial node to current node g(n) and from current node n to goal state h(n)
What is the definition of admissible?
h is called admissible if h(n) \leq h*(n) with h* the cost of the optimal path from current node to goal state
What holds for monotone and nondecreasing functions? [2]
1. Path-max equation can be guaranteed
2. f(n’) = max(f(n) or g(n’)+h(n’)) with n parent of n’
What are the characteristics of the effective branching factor b*? [3]
1. Number of successors generated by a "typical" node
2. N+1 = 1+b*+b*²+...+b*^d // No closed form solution for b*
3. Smaller b* is better for h
What is the definition of IDA*? (2)
1. Perform IDS with respect to the heuristic of A*
2. Do not consider an increasing depth (1...d) but the increasing value to the goal node (f(root),...,f(goal))
What is the definition of simplified memory-bounded A* (SMA*)? [3]
1. Apply A* on deepest node in Queue with smallest f
2. Assign max(f(parent), g(node)+h(node)) to node or inf if at max depth
3. Update ancestors of node if necessary and add/remove nodes from Queue
What is the definition of hill-climbing? [2]
1. Find successor node with higher value as current node
2. Current node is solution if no successor has a higher value
What is the definition of simulated annealing (SAS)? [4]
1. Choose successor randomly after scheduling index to T
2. If T!=0 AND successor value is greater than current value update current node // Difference deltaE
3. Else update current node only with probability e^(deltaE/T)
4. Theorem “For every search space a schedule exists such that SAS converges to global maximum.”
What are examples of heuristics for the 8-Puzzle? [2]
1. Number of tiles in wrong position // Simplified to placing tiles arbitrary
2. Sum of (Manhattan) distance of tiles to goal location
What are examples of heuristics for chess? [2]
1. Material value
2. Safety of king, pawn structure
What are the characteristics of heuristics? [2]
1. Easy to compute
2. Weighted linear functions // Criteria independent from each other
How can a heuristic be found? [2]
1. Cost of exact solution for simplified problem
2. Pattern databases with maximizing pattern // Sum of pattern is not admissible due to shared moves
