Title: EAI / 05_complex_search

Explain hill-climbing.

Q: What are remedies against ridges in hill-climbing?
A: - Random-restart hill climbing
- Alternative neighbor selection

Q: Explain simulated annealing.
A: idea: escape local maxima by
- allowing some "bad" moves
- but gradually decrease their size and frequency

Q: Explain Local beam search.
A: Idea:
• keep k states instead of one
• choose top k of all their successors
Not the same as running k searches in parallel!
Searches that find good states recruit other searches to join them
Problem: quite often, all k states end up on same local hill Idea: choose k successors randomly, biased towards good ones
Observe the close analogy to natural selection!
Issue: states get too close
⇒ use a stochastic variant (akin to stochastic hill climbing)

Explain Genetic algorithms.

Q: When does crossover help in genetic algorithms?
A: Crossover only helps if and only if substring are meaningful components (blocks)

Q: What approaches are there in searches for continuous state spaces?
A: - Constraint optimization (formulate constraints that express conditions on variables)
- Discretizatiion (turn continuous into discrete space)
- Gradient methods (analytical approach to find an optimum)

Q: What does a solution in an And-Or Tree contain?
A: a solution is a subtree that
1. has a goal state at each leaf
2. has one action eat each or-node
3. includes each result state of each of its and-nodes

Q: What is online search?
A: Search where the environment may change

Q: What tradeoff are you confronted with in online search?
A: planning/waiting for information
vs.
losing control

Q: What problems are there in online search?
A: - Goal achievement (reach some goal from initial state)
- Explore environment (learn \(\text{Result}\), state space \(S\))
- Model building (learn \(\text{Actions}\), \(\text{Result}\), \(S\))

Q: What are the ingredients of online search problems?
A: - \(\text{Action}(s)\): set of actions doable in state \(a\)
- \(c(s,a,s')\): cost of taking action \(a\) in \(s\) with result \(s'\)
- \(\text{Is-Goal(s)}\): goal test
- (optional) \(h(s)\)

Q: What are the performance criteria of online search?
A: - competitive ratio: cost of path traveled / optimal path cost
- characteristics: size of the state space

Q: Whats a suitable algorithm for online search?
A: Depth-first search

Explain the online-search dfs algorithm.

Q: How can you escape local maxima in online local search?
A: Random walk
Alternative: use memory

Q: What problem arises in online local search (e.g. hillclimbing)?
A: local search is plagued with local maxima