Intelligent agent paradigm

The "intelligent agent" paradigm became widely accepted during the 1990s.^[96] An intelligent agent is a system that perceives its environment and takes actions which maximizes its chances of success. The simplest intelligent agents are programs that solve specific problems. The most complicated intelligent agents are rational, thinking human beings.^[97] The paradigm gives researchers license to study isolated problems and find solutions that are both verifiable and useful, without agreeing on one single approach. An agent that solves a specific problem can use any approach that works — some agents are symbolic and logical, some are sub-symbolic neural networks and others may use new approaches. The paradigm also gives researchers a common language to communicate with other fields—such as decision theory and economics—that also use concepts of abstract agents.

Integrating the approaches

An agent architecture or cognitive architecture allows researchers to build more versatile and intelligent systems out of interacting intelligent agents in a multi-agent system.^[98] A system with both symbolic and sub-symbolic components is a hybrid intelligent system, and the study of such systems is artificial intelligence systems integration. A hierarchical control system provides a bridge between sub-symbolic AI at its lowest, reactive levels and traditional symbolic AI at its highest levels, where relaxed time constraints permit planning and world modelling.^[99] Rodney Brooks' subsumption architecture was an early proposal for such a hierarchical system.

Tools of AI research

In the course of 50 years of research, AI has developed a large number of tools to solve the most difficult problems in computer science. A few of the most general of these methods are discussed below.

Search

Main article: search algorithm

Many problems in AI can be solved in theory by intelligently searching through many possible solutions:^[100] Reasoning can be reduced to performing a search. For example, logical proof can be viewed as searching for a path that leads from premises to conclusions, where each step is the application of an inference rule.^[101] Planning algorithms search through trees of goals and subgoals, attempting to find a path to a target goal.^[102] Robotics algorithms for moving limbs and grasping objects use local searches in configuration space.^[75] Many learning algorithms have search at their core.^[103]

There are several types of search algorithms:

• "Uninformed" search algorithms eventually search through every possible answer until they locate their goal.^[104] Naive algorithms quickly run into problems when they expand the size of their search space to astronomical numbers. The result is a search that is too slow or never completes.
• Heuristic or "informed" searches use heuristic methods to eliminate choices that are unlikely to lead to their goal, thus drastically reducing the number of possibilities they must explore.^[105] The eliminatation of choices that are certain not to lead to the goal is called pruning.
• Local searches, such as hill climbing, simulated annealing and beam search, use techniques borrowed from optimization theory.^[106]
• Global searches are more robust in the presence of local optima. Techniques include evolutionary algorithms, swarm intelligence and random optimization algorithms.

Logic

Main articles: logic programming and automated reasoning

Logic^[107] was introduced into AI research by John McCarthy in his 1958 Advice Taker proposal. The most important technical development was J. Alan Robinson's discovery of the resolution and unification algorithm for logical deduction in 1963. This procedure is simple, complete and entirely algorithmic, and can easily be performed by digital computers.^[108] However, a naive implementation of the algorithm quickly leads to a combinatorial explosion or an infinite loop. In 1974, Robert Kowalski suggested representing logical expressions as Horn clauses (statements in the form of rules: "if p then q"), which reduced logical deduction to backward chaining or forward chaining. This greatly alleviated (but did not eliminate) the problem.^[101][109]

Logic is used for knowledge representation and problem solving, but it can be applied to other problems as well. For example, the satplan algorithm uses logic for planning,^[110] and inductive logic programming is a method for learning.^[111]

There are several different forms of logic used in AI research.

• Propositional or sentential logic^[112] is the logic of statements which can be true or false.
• First-order logic^[113] also allows the use of quantifiers and predicates, and can express facts about objects, their properties, and their relations with each other.
• Fuzzy logic, a version of first-order logic which allows the truth of a statement to be represented as a value between 0 and 1, rather than simply True (1) or False (0). Fuzzy systems can be used for uncertain reasoning and have been widely used in modern industrial and consumer product control systems.^[114]
• Default logics, non-monotonic logics and circumscription are forms of logic designed to help with default reasoning and the qualification problem.^[63]
• Several extensions of logic have been designed to handle specific domains of knowledge, such as: description logics;^[57] situation calculus, event calculus and fluent calculus (for representing events and time);^[58] causal calculus;^[59] belief calculus; and modal logics.^[60]

Probabilistic methods for uncertain reasoning

Main articles: Bayesian network, hidden Markov model, Kalman filter, decision theory, and utility theory

Many problems in AI (in reasoning, planning, learning, perception and robotics) require the agent to operate with incomplete or uncertain information. Starting in the late 80s and early 90s, Judea Pearl and others championed the use of methods drawn from probability theory and economics to devise a number of powerful tools to solve these problems.^[115]

Bayesian networks^[116] are very general tool that can be used for a large number of problems: reasoning (using the Bayesian inference algorithm),^[117] learning (using the expectation-maximization algorithm),^[118] planning (using decision networks)^[119] and perception (using dynamic Bayesian networks).^[120]

Probabilistic algorithms can also be used for filtering, prediction, smoothing and finding explanations for streams of data, helping perception systems to analyze processes that occur over time^[121] (e.g., hidden Markov models^[122] and Kalman filters^[123]).

Planning problems have also taken advantages of other tools from economics, such as decision theory and decision analysis,^[124] information value theory,^[66] Markov decision processes,^[125] dynamic decision networks,^[125] game theory and mechanism design^[126]

Classifiers and statistical learning methods

Main articles: classifier (mathematics), statistical classification, and machine learning

The simplest AI applications can be divided into two types: classifiers ("if shiny then diamond") and controllers ("if shiny then pick up"). Controllers do however also classify conditions before inferring actions, and therefore classification forms a central part of many AI systems.

Classifiers^[127] are functions that use pattern matching to determine a closest match. They can be tuned according to examples, making them very attractive for use in AI. These examples are known as observations or patterns. In supervised learning, each pattern belongs to a certain predefined class. A class can be seen as a decision that has to be made. All the observations combined with their class labels are known as a data set.

When a new observation is received, that observation is classified based on previous experience. A classifier can be trained in various ways; there are many statistical and machine learning approaches.

A wide range of classifiers are available, each with its strengths and weaknesses. Classifier performance depends greatly on the characteristics of the data to be classified. There is no single classifier that works best on all given problems; this is also referred to as the "no free lunch" theorem. Various empirical tests have been performed to compare classifier performance and to find the characteristics of data that determine classifier performance. Determining a suitable classifier for a given problem is however still more an art than science.

The most widely used classifiers are the neural network,^[128] kernel methods such as the support vector machine,^[129] k-nearest neighbor algorithm,^[130] Gaussian mixture model,^[131] naive Bayes classifier,^[132] and decision tree.^[103] The performance of these classifiers have been compared over a wide range of classification tasks^[133] in order to find data characteristics that determine classifier performance.

Neural networks

A neural network is an interconnected group of nodes, akin to the vast network of neurons in the human brain.

The study of artificial neural networks^[128] began in the decade before the field AI research was founded. In the 1960s Frank Rosenblatt developed an important early version, the perceptron.^[134] Paul Werbos developed the backpropagation algorithm for multilayer perceptrons in 1974,^[135] which led to a renaissance in neural network research and connectionism in general in the middle 1980s. Other common network architectures which have been developed include the feedforward neural network, the radial basis network, the Kohonen self-organizing map and various recurrent neural networks. The Hopfield net, a form of attractor network, was first described by John Hopfield in 1982.

Neural networks are applied to the problem of learning, using such techniques as Hebbian learning^[136] Holographic associative memory and the relatively new field of Hierarchical Temporal Memory which simulates the architecture of the neocortex.^[137]