AIMA - Search in Complex Environments
In which we relax the simplifying assumptions of the previous chapter, to get closer to the goal.
[[AIMA - Solving Problems by Searching]]N was all about fully observable, deterministic, static, known environments where the solution is a sequence of actions. But the real world is rarely like this, and different algorithms need to be used for partially observable, non deterministic, dynamic and unknown environments (not neccessarily all at once).
Flashcards
What is local search?
Where you only care about moving in the best direction from the current state.
What is another name for local search?
Hill climbing.
Why is it called hill climbing?
Because you’re trying to get to the maximum “peak” of a function.
What technique is used to stop hill climbing from getting too stuck at local maxima?
Simulated annealing
Why isn’t local beam search just running multiple hill climbing algorithms in parallel?
Because useful information is shared among threads.
What are the 5 steps to a genetic algorithm?
- Initial population
- Fitness
- Selection
- Crossover
- Mutation
What is the Baldwin effect?
Things that are hard to learn end up in the genome, but things that are easy to learn do not.
What is one cool way that actual evolution is different from genetic algorithms?
The genes not only encode the phentotypes of the organism but the mechanisms for the how the genes are translated.
What is the Hessian matrix?
The square matrix of second-order partial derivatives.
What is the formula for finding the stationary points of a $f(\pmb{x})$ using Newton’s method?
What do the solutions look like for searches in nondeterministic or partially observable environments?
Contingent plans.
What are contingent plans?
Trees of $\textsc{And}$ and $\textsc{Or}$ nodes.
Instead of searching state space for a problem, what do you search when you have only have partial observability?
Belief state-space
How can you create solutions in sensorless (no observability) environments?
Create an action sequence that always coerces the world into a certain state.
What is online searching?
Doing action and computation at the same time.