Why is search important in AI?

Question

Why is search important in AI? What kinds of search algorithms are used in AI? How do they improve the result of an AI?

Answer 1

State space search is a general and ubiquitous AI activity that includes numerical optimization (e.g. via gradient descent in a real-valued search space) as a special case.

State space search is an abstraction which can be customized for a particular problem via three ingredients:

1. Some representation for candidate solutions to the problem (e.g. permutation of cities to represent a Travelling Salesman Problem (TSP) tour, vector of real values for numeric problems).

2. A solution quality measure: i.e. some means of deciding which of two solutions is the better. This is typically achieved (for single-objective problems) by having via some integer or real-valued function of a solution (e.g. total distance travelled for a TSP tour).

3. Some means of moving around in the space of possible solutions, in a heuristically-informed manner. Derivatives can be used if available, or else (e.g. for black-box problems or discrete solution representations) the kind of mutation or crossover methods favoured by genetic algorithms/evolutionary computation can be employed.

The first couple of chapters of the freely available "Essentials of Metaheuristics" give an excellent overview and Michalewicz and Fogel's "How to Solve It - Modern Heuristics" explains in more detail how numerical optimization can be considered in terms of state-space.

How shall the "search through possible plans" occur? The idea is to choose all 3 of the above for the planning problem and then apply some metaheuristic (such as Simulated Annealing, Tabu Search, Genetic Algorithms etc). Clearly, for nontrivial problems, only a small fraction of the space of "all possible plans" is actually explored.

CAVEAT: Actually planning (in contrast to the vast majority of other problems amenable to state-space search such as scheduling, packing, routing etc) is a bit of a special case, in that it is sometime possible to solve planning problems simply by using A* search, rather than searching with a stochastic metaheuristic.

Answer 2

Search has always been a crucial element of AI in multiple ways. First, what many people refer to as "search" is a reflection of how what we call "intelligence" frequently involves searching something: a physical realm, a "state space" of possible solutions, a "knowledge space" where ideas/facts/concepts/etc. are related as a graph structure, etc.

Look up some old papers on computer chess, and you'll see that a lot of that involves searching a "state space". As such, search algorithms that are efficient (in terms of time complexity and/or space complexity) have always been important to making advances there. And while computer chess is just one example, the principle generalizes to many other kinds of problem solving and goal seeking activities.

Here's a reference that explains more about some of these ideas.

Note too that "search" is closely related to the idea of "heuristics" in an important way. Many search problems in the real world are far too complex to solve by exhaustive brute-force search, so humans (and AI's) resort to heuristics to narrow the state space being searched. Using heuristics can yield search algorithms that allow for reasonable solutions in a realistic time-frame, where no simple, deterministic algorithm exists to do likewise.

For some more background you might want to read up on A* search, which is a widely used algorithm with many applications - and not just in AI.

The other major regard in which something you could call "search" applies in AI is through the use of algorithms which are also often referred to as "optimisation" techniques. This would be things like Hill Climbing, Gradient Descent, Simulated Annealing and perhaps even Genetic Algorithms. These are used to maximize or minimize the values of some function and one of the canonical uses in AI is for training neural networks using back-propagation, where you're trying to minimize the delta between the "correct" answer (from the training data) and the generated answer, so you can learn the correct weights within the network.

Answer 3

In regards to the question you mention (in the comments of the OP), these searches are related to optimization. I'm not sure of your background, so let me describe it from scratch, briefly:

Remember the derivative? The base idea is to talk about how the function changes in regards to changes in input. So now, we're out of high school and we're building neural nets. We've done the basic coding, and want to look at how our model is working. Back from our statistics class, we remember we use a certain measure of error (e.g. least squares) to determine the efficacy of the models from that class, so we decide to use that here. We get this error, and it's a bit too big for our liking, so we decide to fiddle with our model and adjust the weights to get that error down. But how?

This is where the 'search' comes into play. It's really a search for the best weights to put on the edges of our net to optimize it. We use the derivative (in some fancy ways, using the 'stochasitc' (think random sampling) and other ways the question mentions) to search for which way is 'down' in the high dimensional space of our weights. In other words, what we are searching for is minima or maxima to optimize our neural net, and we 'search' for it by doing a derivative which tells us which way to go, moving a bit in that direction, then doing that again and again iteratively to find (hopefully) the best weights.

This video here goes into all the detail you'd want, and I recommend the entire series as a robust but understandable intro to neural nets: Demystifying Neural Networks

Go and look up 'gradient descent' to get any related material. (Note, the gradient here is equivalent to multidimensional derivative direction to go in, and descent is just searching for the minima)

Answer 4

Every problem can be reduced to search. Every problem has an input within some range (the domain) and an output in some other range (codomain). That is, every problem can be formulated as a kind of map from one space to another, where the source is the givens of the problem, and the destination is the solution to the problem.

"Brute force" is the algorithm which solves every problem by inspecting every point in the codomain and asking: "Is this the solution?" Every other algorithm is an attempt to improve on brute force by not searching the entire codomain of possible solutions.

Typical software engineering problems can be solved by algorithms which arrive at the correct solution very quickly (sorting, arithmetic, partition, etc.). AI problems are generally those for which a strong polynomial algorithm is not known, and thus, we must settle for approximations. Basically every common problem that the human brain must solve falls into this category.

Consider the problem of moving a multi-jointed robotic arm to pick up an object. Reverse kinematics does not have unique solutions: there is more than one way to move your hand from a start position to a target position. This is due to the excessive degrees of freedom in your joints. If you want to minimize energy usage, then there is a unique solution (due to the asymmetry of joints and muscles).

But what if there is an obstacle in the pathway of the minimum-energy solution? There are many pathways which avoid the obstacle, but again, many of them will have a similar cost. Even if there is a unique minimum-energy solution, it might not be the most practical to compute. The brain is the most metabolically expensive organ in the body, so it is not always best to find an optimal solution. Thus, heuristics come into play.

But in all cases, the problem is not: "move your hand" or "move the robot arm." The problem is: "search the space of joint rotation sequences which best achieves the goal." And even though there is a closed-form solution for the simple minimum-energy case with no obstacles, it is too expensive to compute precisely when a set of cheap heuristics will get you very close with a small fraction of the computational effort.

If computation were free, then AI would be mere mathematics, and we would always compute the best answer to every question using logic, calculus, physics, at worst, numerical methods when we don't have closed-form solutions. In reality, time is money, and the time and effort to get an answer is as much a part of the cost as the quality of the solution. So it is an engineering tradeoff to decide how much effort should be expended in what way to obtain the best answer given the value of the response.

Or, in other words, AI problems are all about searching the space of solutions as quickly as possible to get an answer that is "good enough".

I might seem curious that such far-flung problems as natural language recognition and theorem proving would be search problems. But language parsers strive to determine the meaning of statements via part-of-speech tagging. A given phrase can be parsed in many different ways, yielding many different interpretations, and the space of parse trees is yet another search problem in deciding which parse tree is the most likely intended meaning by the speaker.

A theorem proof is graph starting with axioms, proceeding through lemmas, applying the rules of procedure until the theorem is derived or refuted (by proving its negation). There are many ways to represent this sequence, but at the end of the day, we are talking about a process of exploring the intermediate proof space and finding the derivation which reaches your goal. Everything is search, in the end.

Answer 5

Search is important for at least two reasons.

First, searching is one of the early and major consumers of advanced machine learning, as finding the correct result for a search query boils down to predicting the click-through rate for query-result combinations. More relevant results means more clicks, more traffic, and more revenue.

Second, many planning and optimization problems can be recast as search problems. An AI deciding on a plan to route packages through a network is searching the space of possible plans for a good one.

Answer 6

The aim of an AI is to fulfill one or the other task, say solve the task adequately. But there are results that are no solutions at all and there are results which are satisfying the task and thus are accepted as solutions. Since there are generally more results that are no solutions, the set of all possible solutions is just a subset of all results. But this means that the task involves the search for a suitable set of solutions.

Answer 7

Consciousness is an attention selection mechanism that searches over salient inputs. The robotic saccades of your eyeballs show you first hand the algorithmic nature of your brain's conscious attention mechanism, while it searches among salient inputs.

A smart search algorithm can help with dimensionality reduction.

Answer 8

Typical learning algorithms can be stated as a search problem, where we want to find the best possible solution, that successfully solves a particular task, among all the available candidate solutions in the solution space.

It is often the case where we can't find the best one or it is too hard to find it and thus we compromise with a sub-optimal solution.