Chapter 4: Beyond Classical Search (3751)

Chapter 4: Beyond Classical Search (3751)

1. 4.1 Local search algo's and optimisation problems

   • the path to the goal is irrelevant. The goal itself is all that matters
   • Local search algorithms operate using a single current node (rather than multiple paths) and generally move only to neighbors of that node.
   • local search algorithms are not systematic, they have two key advantages:
     • (1) they use very little memory-usually a constant ammmt;
     • (2) they can often find reasonable solutions in large or infinite (continuous) state spaces for which systematic algorithms are unsuitable.
   • useful for solving pure optimization problems in which the aim is to find the best state according to an objective function
   • we find it useful to consider the state-space landscape (as in Figure 4.1).
     • A landscape has both "location" (defined by the state) and "elevation" (defined by the value of the heuristic cost function or objective function)
     • If elevation corresponds to costs -> Then we want the lowest valley -> Global Minimum
     • If elevation corresponds to objective function -> Then we want the highest peak -> Global Maximum
     • A complete local search algorithm always finds a goal if one exists; an optimal algorithm always finds a global minimum/maximum.
   • 4.1.1 Hill-climbing search
     • The hill-climbing search algorithm (steepest-ascent version) is simply a loop that continually moves in the direction of increasing value-that is, uphill
     • The algorithm does not maintain a search tree, so the data structure for the current node need only record the state and the value of the objective function
     • Hill climbing does not look ahead beyond the immediate neighbors of the current state
     • Hill climbing is sometimes called greedy local search because it grabs a good neighbor state without thinking ahead about where to go next.
     • hill climbing often gets stuck for the following reasons:
       • • Local maxima: a local maximum is a peak that is higher than each of its neighboring states but lower than the global maximum.
         • Figure 4.1 illustrates the problem schematically.
       • • Ridges: a ridge is shown in figure 4.4. Ridges result in a sequence of local maxima that is very difficult for greedy algorithms to navigate.
       • • Plateau: a plateau is a flat area of the state-space landscape. It can be a flat local maximum, from which no uphill exit exists, or a shoulder, from which progress is possible. (See Figure 4.1.) A hill-climbing search might get lost on the plateau
     • Might it not be a good idea to keep going-to allow a sideways move in the hope that the plateau is really a shoulder?
       • One common solution is to put a limit on the number of consecutive sideways moves allowed.
       • This raises the percentage of problem instances solved by hill climbing from 14% to 94%. Success comes at a cost: the algorithm averages roughly 21 steps for each successful instance and 64 for each failure.
     • Many variants ofhill climbing have been invented
       • Stochastic hill climbing chooses at random from among the uphill moves; the probability of selection can vary with the steepness of the uphill move.
       • First-choice hill climbing implements stochastic hill climbing by generating successors randomly until one is generated that is better than the current state
       • algorithms described so far are incomplete-they often fail to find a goal when one exists because they can get stuck on local maxima.
   • 4.1.2 Simulated annealing
     • seems reasonable to try to combine hill climbing with a random walk in some way that yields both efficiency and completeness.
     • To explain simulated annealing, we switch our point of view from hill climbing to gradient descent (i.e., minimizing cost) and imagine the task of getting a ping-pong ball into the deepest crevicein a bwnpy surface.
     • The innermost loop ofthe simulated-annealing algorithm (Figure 4.5) is quite similar to hill climbing. Instead ofpicking thebestmove, however, itpicks a randommove. If the move improves the situation, it is always accepted. Otherwise, the algorithm accepts the move with some probability less than 1. The probability decreases exponentially with the "badness" of the move-the amount tJ.E by which the evaluation is worsened. The probability also decreases as the "temperature" T goes down: "bad" moves are more likely to be allowed at the start when T is high, and they become more unlikely as T decreases. Ifthe schedule lowers T slowly enough, the algorithm will find a global optimwn withprobability approaching l
   • 4.1.3 Local beam search
     • The local beam search algorithm keeps track of k states rather than just one. It begins with k randomly generated states. At each step, all the successors ofa]I k states are generated. Ifany one is a goal, the algorithm halts. Otherwise, it selects the k best successors from the complete list and repeats.
     • In a local beam search, useful information is passed among the parallel search threads.
     • In its simplest form, local beam search can suffer from a lack of diversity among the k states-they can quickly become concentrated in a small region ofthe state space
       • stochastic beam search, analogous to stochastic hill climbing, helps alleviate this problem. Instead of choosing the best k from the the pool of candidate successors, stochastic beam search chooses k successors at random, with the probability of choosing a given successor being an increasing function of its value
   • 4.1.4 Genetic algorithms
     • A genetic algorithm (orGA) is a variant ofstochastic beamsearch in which successor states are generated by combining two parent states rather than by modifying a single state.

2. 4.2 Local Search in continuous spaces

   • most real-world environments are continuous

3. 4.3 Searching with nondeterministic actions

   • When the environment is either partially observable or nondeterministic (or both), percepts become useful.
   • So the solution to a problem is not a sequence but a contingency plan (also known as a strategy) that specifies what to do depending on what percepts are received.
   • 4.3.2 AND-OR search trees
     • In a deterministic environment, the only branching is introduced by the agent's own choices in each state. We call these nodes OR nodes.
     • In a nondeterministic environment, branching is also introduced by the environment's choice of outcome for each action. We call these nodes AND nodes.
     • A solution for an AND-OR search problem is a subtree that
       • (1) has a goal node at every leaf
       • (2) specifies one action at each of its OR nodes
       • (3) includes every outcome branch at each of its AND nodes.
   • 4.3.1 The erratic vacuum world
     • solutions for nondeterministic problems can contain nested if-then-else statements; this means that they are trees rather than sequences
   • 4.3.3 Try, try again

4. 4.4 Searching with partial observations

   • The key concept required for solving partially observable problems is the belief state, representing the agent's current belief about the possible physical states it might be in, given the sequence of actions and percepts up to that point.
   • the agent's percepts do not suffice to pin down the exact state
   • 4.4.1 Searching with no observation
     • When the agent's percepts provide no information at all, we have what is called a sensorless problem or sometimes a conformant problem.
   • 4.4.2 Searching with observations
   • 4.4.3 Solving partially observable problems
   • 4.4.4 An agent for partially observable environments

5. 4.5 Online search agents and unknown environments

   • an online search agent interleaves computation and action: first it takes an action, then it observes the environment and computes the next action
   • good idea in dynamic or semidynamic domains-domains where there is a penalty for sitting around and computing too long.
   • Online search is a necessary idea for unknown environments where the agent does not know what states exist or what its actions do
     • In this state of ignorance, the agent faces an exploration problem and must use its actions as experiments in order to learn enough to make deliberation worthwhile.
   • 4.5.1 Online search problems
     • We assume a deterministic and fully observable environment (Chapter 17 relaxes these assumptions), but we stipulate that the agent knows only the following:
       • • ACTIONS(s), which returns a list of actions allowed in state s
       • • The step-cost function c(s, a, s')-note that this cannot be used until the agent !mows that s' is the outcome
       • • GOAL-TEST(s).
   • 4.5.2 Online search agents
   • 4.5.3 Online local search
   • 4.5.4 Learning in online search

Imágenes y archivos del mapa