State space search

 

Search and optimization

AI can solve many problems by intelligently searching through many possible solutions.^[68] There are two very different kinds of search used in AI: state space search and local search.

State space search

State space search searches through a tree of possible states to try to find a goal state.^[69] For example, Planning algorithms search through trees of goals and subgoals, attempting to find a path to a target goal, a process called means-ends analysis.^[70]

Simple exhaustive searches^[71] are rarely sufficient for most real-world problems: the search space (the number of places to search) quickly grows to astronomical numbers. The result is a search that is too slow or never completes.^[15] "Heuristics" or "rules of thumb" can help to prioritize choices that are more likely to reach a goal.^[72]

Adversarial search is used for game-playing programs, such as chess or Go. It searches through a tree of possible moves and counter-moves, looking for a winning position.^[73]

Local search

A particle swarm seeking the global minimum

Local search uses mathematical optimization to find a numeric solution to a problem. It begins with some form of a guess and then refines the guess incrementally until no more refinements can be made. These algorithms can be visualized as blind hill climbing: we begin the search at a random point on the landscape, and then, by jumps or steps, we keep moving our guess uphill, until we reach the top. This process is called stochastic gradient descent.^[74]

Evolutionary computation uses a form of optimization search. For example, they may begin with a population of organisms (the guesses) and then allow them to mutate and recombine, selecting only the fittest to survive each generation (refining the guesses).^[75]

Distributed search processes can coordinate via swarm intelligence algorithms. Two popular swarm algorithms used in search are particle swarm optimization (inspired by bird flocking) and ant colony optimization (inspired by ant trails).^[76]

Neural networks and statistical classifiers (discussed below), also use a form of local search, where the "landscape" to be searched is formed by learning.

Logic

Formal Logic is used for reasoning and knowledge representation.^[77] Formal logic comes in two main forms: propositional logic (which operates on statements that are true or false and uses logical connectives such as "and", "or", "not" and "implies")^[78] and predicate logic (which also operates on objects, predicates and relations and uses quantifiers such as "Every X is a Y" and "There are some Xs that are Ys").^[79]

Logical inference (or deduction) is the process of proving a new statement (conclusion) from other statements that are already known to be true (the premises).^[80] A logical knowledge base also handles queries and assertions as a special case of inference.^[81] An inference rule describes what is a valid step in a proof. The most general inference rule is resolution.^[82] Inference can be reduced to performing a search to find a path that leads from premises to conclusions, where each step is the application of an inference rule.^[83] Inference performed this way is intractable except for short proofs in restricted domains. No efficient, powerful and general method has been discovered.^[84]

Fuzzy logic assigns a "degree of truth" between 0 and 1 and handles uncertainty and probabilistic situations.^[85] Non-monotonic logics are designed to handle default reasoning.^[28] Other specialized versions of logic have been developed to describe many complex domains (see knowledge representation above).