Search in complex environments Flashcards
What is meant by hill-climbing in the context of search?
Going towards a local (or if lucky global) maximum.
Gradient descend and hill-climbing are opposites. What is the purpose of gradient descend?
Finding a global minimum.
What characterizes hill-climbing search?
Moves to neighbouring state with highest value. Terminates when it reaches a peak.
Optimal: No
What is meant by a complete-state formulation?
A state-formulation where every state has the components for a solution, but may not be in the right place. Example: n-queens.
What characterizes stochastic hill-climbing?
It chooses random uphill moves.
What characterizes first-choice hill-climbing?
It generates successors randomly until one is better than the original state.
What characterizes random-restart hill climbing?
Variation of first-choice hill-climbing, where it restarts if it doesn’t succeed.
Complete: Yes, because it will eventually generate a goal state as the initial state.
Number of restarts: 1/p
Number of steps: Cost of one successful iteration + (1-p)/p times the cost of failure.
What is the concept of simulated annealing based on?
Blacksmithing.
What characterizes simulated annealing?
Combines hill-climbing and random walks. A balance between exploration and exploitation.
Picks random moves if move improves situation, else accepts move with probability less than 1.
Probability of random move decreases exponentially with the “badness” of the move.
Probability decreases as temperature T goes down.
Bad moves more likely at the start when T is high.
What are the characteristics of local beam search?
Instead of keeping one node in memory at a given time, local beam search keeps track of k states.
Begins with k random states. At each step, all successors of all k states are generated, chooses the k best successors and repeat until it reaches a goal state or otherwise stopped.
What is the difference between local beam search and random-restart hill-climbing?
In local beam search information is stored between the search threads running in parallel.
In random-restart hill climb, each search process runs independently of each other.
What characterizes evolutionary/genetic algorithms?
Inspired by natural selection.
Selection: Selects individuals with probability proportional to fitness score or n individuals and select p most fit ones as parents.
Crossover: Randomly select a crossover point to split the parent strings, and recombine to form two new children.
Mutation rate: How often a mutation should happen (to a single value)
What is meant by an empirical gradient method?
A method that measures progress by change in value of an objective function between two nearby points.
Which concept is useful when dealing with non-deterministic environments?
Belief states: States the agent believes are possible.
What is the difference between AND- & OR-nodes in an AND/OR-tree
An OR-node doesn’t have to be expanded instantly. All states in an AND-node has to be expanded.
Can an agent act rationally in a sensorless environment?
Yes it can. For instance a vacuum cleaner will still be able to make a plan for cleaning if it can’t tell whether the tile it is on is clean.
What is the difference between offline- and online search agents?
Offline search agents: Computes complete solution before taking an action.
Online search agents: Takes an action, observes environment, computes next action, repeats. (Used for dynamic environments. Can also be useful for non-deterministic domains. Necessary for unknown environments)
What is meant by the competitive ratio?
A value to compare the online algorithm to the most optimal path.
What is a precondition for using Online DFS (depth-first search)?
State space needs to be safely explorable.
What makes LRTA* (Learning-real-time A) different from A?
It stores a current best estimate, H(s) of the cost to reach the goal from each state it has visited, and updates it for every new state it reaches, as it gets more information.
