=== p1 === Introduction to Artificial Intelligence Chapter 4 Search in Complex Environments Wei-Ta Chu (朱威達) 1 === p2 === • The search algorithms that we have seen so far are designed to explore search spaces systematically. When a goal is found, the path to that goal also constitutes a solution to the problem. • In many problems, however, the path to the goal is irrelevant. In the 8-queens problem, what matters is the final configuration of queens, not the order in which they are added. • We need algorithms not worrying about paths at all. Local Search Algorithms and Optimization Algorithms 2 === p3 === • Local search algorithms operate using a single current node and generally move only to neighbors of that node. • They use very little memory—usually a constant amount • They can often find reasonable solutions in large or infinite (continuous) state spaces for which systematic algorithms are unsuitable. • Local search algorithms are useful for solving pure optimization problems, in which the aim is to find the best state according to an objective function. Local Search Algorithms and Optimization Algorithms 3 === p4 === Local Search Algorithms and Optimization Algorithms 4 === p5 === • The hill-climbing search algorithm (steepest-ascent version) is simply a loop that continually moves in the direction of increasing value. It terminates when it reaches a “peak”. • 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 Search 5 === p6 === • 8-queens problem • The successors of a state are all possible states generated by moving a single queen to another square in the same column. The heuristic cost function h is the number of pairs of queens that are attacking each other. • Hill-climbing algorithms typically choose randomly among the set of best successors if there is more than one. Hill Climbing Search 6 === p7 === • Hill climbing is sometimes called greedy local search because it grabs a good neighbor state without thinking ahead about where to go next. • It turns out that greedy algorithms often perform quite well • Hill climbing often gets stuck for the following reasons: • Local maxima • Ridges (屋脊) • Plateaux (can be flat local maximum or a shoulder) Hill Climbing Search 7 === p8 === • For the 8-queens problem, steepest-ascent hill climbing gets stuck 86% of the time, solving only 14% of problem instances. It works quickly, taking just 4 steps on average when it succeeds and 3 when it gets stuck—not bad for a state space with 88 ≈ 17 million states. • 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? The answer is usually yes. 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. Hill Climbing Search 8 === p9 === • 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. • Random-restart hill climbing conducts a series of hill-climbing searches from randomly generated initial states until a goal is found. • The success of hill climbing depends very much on the shape of the state- space landscape. Hill Climbing Search 9 === p10 === • Annealing is the process used to temper or harden metals and glass by heating them to a high temperature and then gradually cooling them, thus allowing the material to reach a low-energy crystalline state. Simulated Annealing 10 === p11 === • Instead of picking the best move, however, it picks a random move. 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 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. Simulated Annealing 11 === p12 === • 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 of all k states are generated. If any one is a goal, the algorithm halts. Otherwise, it selects the k best successors from the complete list and repeats. • A local beam search seem to be nothing more than running k random restarts in parallel instead of in sequence. In a random-restart search, each search process runs independently of the others. In a local beam search, useful information is passed among the parallel search threads. • Stochastic beam search chooses k successors at random, with the probability of choosing a given successor being an increasing function of its value. Local Beam Search 12 === p13 === • A genetic algorithm (or GA) is a variant of stochastic beam search in which successor states are generated by combining two parent states rather than by modifying a single state. • GAs begin with a set of k randomly generated states, called the population. Each state, or individual, is represented as a string over a finite alphabet— most commonly, a string of 0s and 1s. Genetic Algorithms 13 === p14 === • A fitness function should return higher values for better states. The probability of being chosen for reproducing is directly proportional to the fitness score. • For each pair to be mated, a crossover point is chosen randomly from the positions in the string. Genetic Algorithms 14 === p15 === • Finally, each location is subject to random mutation with a small independent probability. In the 8-queens problem, this corresponds to choosing a queen at random and moving it to a random square in its column. Genetic Algorithms 15 === p16 === • Suppose we want to place three new airports anywhere in Romania, such that the sum of squared distances from each city on the map to its nearest airport is minimized. • The state space is then defined by the coordinates of the airports: (x1,y1), (x2,y2), and (x3,y3). This is a six-dimensional space; we also say that states are defined by six variables. Local Search in Continuous Spaces 16 === p17 === • Let Ci be the set of cities whose closest airport (in the current state) is airport i. The objective function is • To avoid continuous problems: discretize the neighborhood of each state. We can move only one airport at a time in either the x or y direction by a fixed amount ±δ. With 6 variables, this gives 12 possible successors for each state. We can then apply any of the local search algorithms described previously. Local Search in Continuous Spaces 17 === p18 === • Many methods attempt to use the gradient of the landscape to find a maximum. The gradient of the objective function is a vector ∇f that gives the magnitude and direction of the steepest slope. • In some cases, we can find a maximum by solving the equation ∇f = 0. In many cases, however, this equation cannot be solved in closed form. Local Search in Continuous Spaces 18 === p19 === • For example, with three airports, the expression for the gradient depends on what cities are closest to each airport in the current state. This means we can compute the gradient locally; for example, • Given a locally correct expression for the gradient, we can perform steepest- ascent hill climbing by updating the current state according to the formula where α is a small constant often called the step size. Local Search in Continuous Spaces 19 === p20 === • If α is too small, too many steps are needed; if α is too large, the search could overshoot the maximum. The technique of line search tries to overcome this dilemma by extending the current gradient direction until f starts to decrease again. • For many problems, the most effective algorithm is the Newton–Raphson method. This is a general technique for finding roots of functions—that is, solving equations of the form g(x)=0. It works by computing a new estimate for the root x according to Newton’s formula Local Search in Continuous Spaces 20 === p21 === Introduction 21 • The gradient of at , denoted by , is orthogonal to the tangent vector to an arbitrary smooth curve passing through on the level set • The direction of maximum rate of increase of a real-valued differentiable function at a point is orthogonal to the level set of the function through that point. • The gradient acts in such a direction that for a given small displacement, the function increases more in the direction of the gradient than in any other direction. === p22 === Newton’s Method 22 • Newton’s method for solving equations of the form is also referred to as Newton’s method of tangents. • If we draw a tangent to at the given point , then the tangent line intersects the x-axis at the point , which we expect to be closer to the root of . • Note that the slope of at is === p23 === • To find a maximum or minimum of f, we need to find x such that the gradient is zero (i.e., ∇f (x) = 0). Thus, g(x) in Newton’s formula becomes ∇f (x), and the update equation can be written in matrix–vector form as where Hf(x) is the Hessian matrix of second derivatives, whose elements Hij are given by . • Local search methods suffer from local maxima, ridges, and plateaux in continuous state spaces just as much as in discrete spaces. Random restarts and simulated annealing can be used and are often helpful. Local Search in Continuous Spaces 23 === p24 === • A constrained optimization problem is constrained if solutions must satisfy some hard constraints on the values of the variables. • The best-known category is that of linear programming problems, in which constraints must be linear inequalities forming a convex set and the objective function is also linear. • Linear programming is probably the most widely studied and broadly useful class of optimization problems. It is a special case of the more general problem of convex optimization, which allows the constraint region to be any convex region and the objective to be any function that is convex within the constraint region. Local Search in Continuous Spaces 24 === p25 === Simple Examples of Linear Programs 25 • Formally, a linear program is an optimization problem of the form where . The vector inequality means that each component of is nonnegative. • Several variations of this problem are possible. For example, we can maximize, or the constraints may be in the form of inequalities, such as or . In fact, these variations can all be rewritten into the standard form shown above. === p26 === Example 26 • A manufacturer produces four different products: there are three inputs to this production process: labor in person-weeks, kilograms of raw material A, and boxes of raw material B. Each product has different input requirements. In determining each week’s production schedule, the manufacturer cannot use more than the available amounts of labor and the two raw materials. The relevant information is presented in this table. Every production decision must satisfy the restrictions on the availability of inputs. These constraints can be written using the data in this table. === p27 === • A robot is placed in the maze-like environment. It is equipped with four sonar sensors that tell whether there is an obstacle in each of the four compass directions. • Assume that the sensors give perfectly correct data, and the robot has a correct map of the environment. But unfortunately the robot’s navigational system is broken, so when it executes a Move action, it moves randomly to one of the adjacent squares. The robot’s task is to determine its current location. Searching with Partial Observations 52 === p28 === Searching with Partial Observations 53 [IMAGE-ONLY] === p29 === • So far we have concentrated on agents that use offline search algorithms. They compute a complete solution before setting foot in the real world and then execute the solution. • In contrast, an online search agent interleaves computation and action: first it takes an action, then it observes the environment and computes the next action. • The canonical example of online search is a robot that is placed in a new building and must explore it to build a map that it can use for getting from A to B. Online Searching Agents with Unknown Environments 56 === p30 === • Online search algorithms • We stipulate (規定) that the agent knows only the following • The agent cannot determine RESULT(s,a) except by actually being in s and doing a. Online Searching Agents with Unknown Environments 57 === p31 === • Online search algorithms • In the maze problem shown in Figure 4.19, the agent does not know that going Up from (1,1) leads to (1,2); nor, having done that, does it know that going Down will take it back to (1,1). Online Searching Agents with Unknown Environments 58 === p32 === • Online search algorithms • Finally, the agent might have access to an admissible heuristic function h(s) that estimates the distance from the current state to a goal state. For example, in Figure 4.19, the agent might know the location of the goal and be able to use the Manhattan-distance heuristic. Online Searching Agents with Unknown Environments 59 === p33 === • Online search algorithms • Typically, the agent’s objective is to reach a goal state while minimizing cost. The cost is the total path cost of the path that the agent actually travels. It is common to compare this cost with the path cost of the path the agent would follow if it knew the search space in advance. This is called the competitive ratio; we would like it to be as small as possible. Online Searching Agents with Unknown Environments 60 === p34 === • Online search agents • After each action, an online agent receives a percept telling it what state it has reached; from this info., it can augment its map of the environment. • The current map is used to decide where to go next. This interleaving of planning and action means that online search algorithms are quite different from the offline search algorithms we have seen previously. • To avoid traveling all the way across the tree to expand the next node, an online algorithm better expands nodes in a local order. DFS has exactly this property. Online Searching Agents with Unknown Environments 61 === p35 === • Online local search • Like depth-first search, hill-climbing search has the property of locality in its node expansions. In fact, because it keeps just one current state in memory, hill-climbing search is already an online search algorithm! Unfortunately, it is not very useful in its simplest form because it leaves the agent sitting at local maxima with nowhere to go. Online Searching Agents with Unknown Environments 63