Beyond Classical Search Flashcards
What is the most well known local search method? What is an added feature that makes it more accurate? Describe how they work.
Local search methods such as hill climbing operate on complete-state formulations, keeping only a small number of nodes in memory. Several stochastic algorithms have been developed, including simulated annealing, which returns optimal solutions when given an appropriate cooling schedule.
How can local searches apply to problems in continuous spaces?
Many local search methods apply also to problems in continuous spaces. Linear pro- gramming and convex optimization problems obey certain restrictions on the shape of the state space and the nature of the objective function, and admit polynomial-time algorithms that are often extremely efficient in practice.
Describe a genetic algorithm
A genetic algorithm is a stochastic hill-climbing search in which a large population of states is maintained. New states are generated by mutation and by crossover, which combines pairs of states from the population.
How can agents search in a nondeterministic environment?
In nondeterministic environments, agents can apply AND–OR search to generate con-
tingent plans that reach the goal regardless of which outcomes occur during execution.
What is a nondeterministic environment?
In automata theory, a finite-state machine is called a deterministic finite automaton, if each of its transitions is uniquely determined by its source state and input symbol, and reading an input symbol is required for each state transition. A nondeterministic finite automaton, or nondeterministic finite-state machine, does not need to obey these restrictions. In particular, every DFA is also an NFA.
What is automata theory?
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them.
What is the belief state?
When the environment is partially observable, the belief state represents the set of
possible states that the agent might be in.
How can solutions be found in a partially observable problem?
Standard search algorithms can be applied directly to belief-state space to solve sensor- less problems, and belief-state AND–OR search can solve general partially observable problems. Incremental algorithms that construct solutions state-by-state within a belief state are often more efficient.
What is an exploration problem?
Exploration problems arise when the agent has no idea about the states and actions of its environment. For safely explorable environments, online search agents can build a map and find a goal if one exists. Updating heuristic estimates from experience provides an effective method to escape from local minima.
Describe the beam search
Has a beam width
Beam search will consider the width of the beam options, like BW = 3. It considers the top 3, and attempts all 3
