A Brief History of Artificial Intelligence

Overview:

The field of Artificial Intelligence (AI) has increasingly expanded to create intelligent behaviour and consequently has improved the system(s) efficiency and performance. Automation had become necessary in various applications where human intervention necessarily needed to be minimised.

This article provides a brief history of Artificial Intelligence from traditional techniques of rule-based Artificial Intelligence, FSMs and Fuzzy Logic to more advanced Artificial Intelligence techniques used for learning, and looks at evolving autonomous behaviours in stochastic and dynamic environments. Evolution of these techniques over the past decades is discussed.

Introduction

Many Artificial Intelligence techniques have been implemented in various applications including health care, e-commerce, robotics, computer games, and the film industry. Artificial Intelligence has become a necessity in today’s world, particularly in applications where human intervention needs to be minimised as in space exploration, disaster recovery, and search and rescue operations. 

Research on Artificial Intelligence is often costly, specially if it involves creating hardware and using tools and laboratories. Computer games have provided useful testing environments for AI research. They initially require low set-up costs to implement and there is minimal associated risk. Games from traditional board games to the modern computer games of shooter and strategy genres have contributed a great deal to the development of Artificial Intelligence and the generation of simulated human-like characters and behaviours. Much research has been conducted on Artificial Intelligence using a variety of test beds.

History of Artificial Intelligence

The term Artificial Intelligence (AI) was first coined by John McCarthy to describe a conference held in 1956 at Dartmouth, where this field of study was established [1]. Later, McCarthy [2] stated that it would be more appropriate to use the term Computational Intelligence. Computational Intelligence is the science and engineering of making intelligent machines do tasks that humans are capable of [3]. Although some researchers consider Computational Intelligence to be a branch of Artificial Intelligence. Textbooks broadly consider Computational Intelligence a synonym of Artificial Intelligence [4, 5, 6]. 

Russell and Norvig [6] categorized the definition of Artificial Intelligence as the study of creating systems that think or act like humans, or think in a rational way, meaning that they do the ‘right thing’, given what they know of the environment. They preferred the notation of rational agents that receive input from the environment via sensors and provided outputs using effectors respectively, which has since been adopted by many in the AI community. 

Alan Turing proposed a test to measure computing intelligence and distinguished two different approaches to Artificial Intelligence known as Top-Down and Bottom-Up [7, 8]. Artificial Intelligence began as Top-Down, or the traditional symbolic AI approach, where cognition is a high-level concept independent of the lower-level details of the implementing mechanism [9]. The Bottom-Up approach aims for cognition to emerge from the operation of many simple elements similar to how the human brain processes information.

Neural Network is the core of this approach. The domain of Artificial Intelligence has evolved over the past 60 years. Many techniques linked to the modeling of cognitive aspects of human behavior have emerged; including, perceiving, reasoning, communicating, planning, and learning. Public perception of what Artificial Intelligence can achieve has been contaminated by science-fiction movies.

Like any domain, Artificial Intelligence has evolved smoothly and incrementally. For example, research in Neural Networks almost ceased after Minsky and Papert [10] showed limitations of Perceptrons in learning linearly inseparable problems.

During the 1980s, researchers [11, 12, 13] realized that such problems could be solved using a new learning method for Multi-Layer Perceptron (MLP) Neural Networks called backpropagation. These developments and many other significant contributions [14, 15, 16, 17, 18] aided in the resurgence of Neural Network research enabling the achievement of the original goals.

Good Old-Fashioned Artificial Intelligence

AI originally started with basic techniques that fall into the category of the symbolic computational approach. This was also referred to as Weak AI or Good Old-Fashioned Artificial Intelligence (GOFAI) [19]. Some developers considered those techniques that exhibited some limited form of intelligence to represent AI.

Several AI techniques suggested in the fields of computing, robotics, and gaming included those related to Search and Optimisation, Path Finding, Collision Avoidance, Chasing and Evading, Pattern Movement, Probability, Potential Function-Based Movement, Flocking, and Scripted AI.

Most of these techniques fall within the category of deterministic AI and are easy to understand, implement and debug. The main pitfall of deterministic methods is that developers must anticipate all scenarios and explicitly code all behaviors. This form of implementation becomes predictable after several attempts.

Modern Artificial Intelligence

A number of techniques were integrated or hybridized as the field evolved. There was a transition period where more modern techniques were progressively introduced. Some of these techniques include; “Rule-Based Artificial Intelligence, Finite State Machine (FSM), Fuzzy Logic, and Fuzzy State Machines (FuSM)” [6]. Rule-Based AI comprises If-Then rules that map the actions of the system based on various conditions and criteria. Finite State Machine and Fuzzy Logic fall into the general category of Rule-Based Artificial Intelligence.

Finite State Machine

A Finite State Machine is a mathematical model of computation that defines an abstract machine that can be in one of a finite number of states. The machine is in only one state at a time; it can change from one state to another when triggered by some input. The idea in the Finite State Machine is to specify a group of actions and/or states for agents and execute and make transitions between them.

Fuzzy Logic

Fuzzy Logic deals with fuzzy concepts that may not have discrete values and allows the representation of conditions by degrees of truth rather than a two-valued binary system [20, 21]. Fuzzy logic algorithms are used to approximate an unknown function by using a known function that is similar to it. This is done by finding a set of input values that produce the desired output values. Fuzzy logic algorithms are created to deal with imprecise or incomplete data. They are used in situations where a precise answer is not possible or would be too expensive to obtain.

Fuzzy State Machine

Fuzzy State Machine combines the concept of Fuzzy Logic with the Finite State Machine to create more realistic and somewhat less predictable behavior. It is a generalization of a finite state machine that uses fuzzy logic to represent the underlying transition function.

Expert Systems

These techniques have led to the emergence of Expert Systems. Expert systems are computer programs that emulate the decision-making ability of a human expert. Expert systems are designed to solve complex problems by reasoning through a set of rules that mimic the thought process of the human expert. Expert Systems are rule-based processing systems consisting of a knowledge base with working memory and an inference engine that processes data with a defined reasoning logic [22, 23]. Many expert systems have shown great success, including the Chess-playing program called Deep Blue which defeated the world champion in 1997 [24].

Advanced Artificial Intelligence

Advanced Artificial Intelligence techniques have evolved to exhibit cognitive aspects of human behavior including reasoning, learning, and evolving. Advanced Artificial Intelligence includes non-deterministic techniques that enable agents to evolve, learn, and adapt [25]. Bayesian Networks, Artificial Neural Networks, Reinforcement Learning, and Evolutionary Algorithms are the mainstream of these techniques.

Bayesian Networks

Bayesian Networks enable reasoning during uncertainty. A Bayesian network is a graphical model that encodes probabilistic relationships among variables of interest. Bayesian networks are ideal for representing situations where there is uncertainty, and they can be used to perform inference, making predictions about the state of variables based on observed values.

Artificial Neural Networks

Artificial Neural Networks mimic the function and information processing of biological neurons [6]. An artificial neural network is a computer program that is designed to simulate the way the human brain works. The program is made up of a series of interconnected nodes, or neurons, that can process information. The training algorithms of Neural NetworkS fall within three main categories of Supervised Learning, Unsupervised Learning, and Reinforcement Learning. These machine learning paradigms are briefly discussed below, and more detailed explanation of neural networks is discussed in this article: Introduction to Artificial Neural Network and Machine Learning Paradigms.

Supervised Learning

Supervised Learning in Neural Network is a process where the network is trained on a set of labeled data, and the labels are used to guide the learning process. In Supervised Learning the Neural Network is presented with a set of input data and corresponding desired target values to train it, and to find the mapping function between inputs and their correct (desired) outputs.

Unsupervised Learning

Unsupervised learning in neural networks is a type of machine learning algorithm that is used to learn patterns in data without the use of labels or any other form of supervision. In Unsupervised Learning, no specific target outputs are available and the Neural Network finds patterns in the data without receiving any help or feedback from the environment. 

Reinforcement Learning

Reinforcement Learning is a neural network learning algorithm that operates by trial and error. The algorithm is designed to learn by experience so that it can improve its performance over time. Reinforcement Learning allows the agent to learn by trial-and-error using feedback from the environment, which could be in a form of reward or punishment [18]. Some examples of this learning paradigm include Temporal Difference learning [26] and Q-Learning [27].

Evolutionary Algorithm

Evolutionary Algorithm techniques are within the category of Evolutionary Computation and have been used for learning. There are a number of different evolutionary algorithm techniques that can be used to solve optimization problems. Some of the more popular techniques include: Genetic Algorithm [28], Genetic Programming [29], Evolutionary Strategies [30, 31], Evolutionary Programming and Neuro-Evolution [32]. Each of these techniques has its own strengths and weaknesses, so it is often useful to try a few different techniques on a given problem to see which one works best.

Genetic Algorithm

Genetic Algorithm techniques offer opportunities for optimization and evolving Artificial Intelligence. A genetic algorithm is a search heuristic that is inspired by Charles Darwin’s theory of natural selection. This algorithm generates new solutions to a problem by combining existing solutions. The basic idea of a genetic algorithm is to start with a population of solutions (called individuals or chromosomes) and then apply a series of operators such as selection, crossover, and mutation to generate new solutions. The hope is that the new solutions will be better than the original solutions.

Neuro-Evolution Algorithms

Neuro-Evolution is a machine-learning technique that uses Evolutionary Algorithms to train neural networks. A Neuro-Evolution algorithm is a method of optimizing artificial neural networks through a process of natural selection. The algorithm is inspired by the process of evolution in nature, where the fittest individuals are selected for reproduction in order to pass on their genes to the next generation. In the same way, the fittest neural networks are selected for reproduction in order to produce offspring networks that are more capable of solving a given problem. Examples of Neuro-Evolution techniques include Neuro-Evolution of Augmenting Topologies (NEAT) [33], Feature Selective Neuro-Evolution of Augmenting Topologies (FS-NEAT) [33], and real-time NEAT [34, 35]. Some of these techniques are discussed in further detail in this article. 

The concept of Multi-Agent System (MAS) has emerged to tie together the isolated subfields of Artificial Intelligence. Multi-Agent System consists of teams of Intelligent Agent (IA) that are able to perceive the environment using their sensory information that process this information using different AI techniques to reason and plan actions in order to achieve certain goals [36, 37]. Intelligent Agent can be equipped with different capabilities including learning and reasoning. Consequently, these teams are able to communicate and interact with each other to share knowledge and skills to solve problems as a team. Multi-Agent Systems can be used in various applications to create intelligent behavior and improve the efficiency and performance of the system. Further information on Multi-Agent Systems is discussed in this article.

References and Credits

• [1] J. McCarthy. Programs with common sense. In Symposium on Mechanization of Thought Processes. National Physical Laboratory, Teddington, England, 1958.
• [2] P. McCorduck. Machines who think. Freeman. 1979, pages 1–375, 1979. San Francisco, CA, USA.
• [3] Marvin Minsky. Society of Mind. Simon and Schuster, Pymble, Australia, 1985.
• [4] N. Nilsson. Artificial Intelligence: A New Synthesis. Morgan Kaufmann Publishers, 1998.
• [5] D. Poole, A. Mackworth, and R. Goebel. Computational Intelligence: A Logical Approach. Oxford University Press, New York, 1998.
• [6] S. J. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice-Hall, Pearson Education, Inc., Upper Saddle River, NJ, USA, 2nd edition, 2003.
• [7] A. Turing. Intelligent machinery. In D. M. B. Meltzer, editor, Machine Intelligence, volume 5, pages 3–23. Edinburgh University Press, Originally, a National Physics Laboratory Report, 1948.
• [8] A Turing. Computing machinery and intelligence. In Mind, volume 59(236), pages 433 – 460. Unpublished until 1968, 1950.
• [9] M. T. Jones. AI Application Programming. Charles River Media, Inc. Hingham, Massachusetts, 2003.
• [10] M. L. Minsky and S. A. Papert. Perceptrons. Cambridge, MA: MIT Press, 1969.
• [11] H. Ackley, E. Hinton, and J. Sejnowski. A learning algorithm for Boltzmann machines. Cognitive Science, pages 147–169, 1985.
• [12] J. J. Hopfield. Neurons with graded responses have collective computational properties like those of two-state neurons. In Proceedings of the National Academy of Sciences (USA), volume 81, pages 3088–3092, 1984.
• [13] D.E. Rumelhart, G.E. Hinton, and R.J. Williams. Learning internal representations by error propagation. In D.E. Rumelhart and J.L. McClelland, editors, Parallel distributed processing: Explorations in the Microstructure of Cognition, volume 1. MIT Press, Cambridge, MA, 1986.
• [14] G. A. Carpenter and S. Grossberg. ART 2: Self-organization of stable category recognition codes for analog input patterns. Applied Optics, 26(23):4919–4930, 1987.
• [15] S. Grossberg. Competitive learning: From interactive activation to adaptive resonance. Cognitive Science, 11:23–63, 1987.
• [16] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671–680, 1983.
• [17] R. Linsker. Self-organization in a perceptual network. Computer, 21(3):105–117, 1988.
• [18] R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 1998.
• [19] J. Haugeland. Artificial Intelligence: The Very Idea. MIT Press, Cam- bridge, MA, 1985.
• [20] T. J. Ross. Fuzzy Logic with Engineering Application. Wiley, Chichester, UK, 3rd edition, 2010.
• [21] L. A. Zadeh. Fuzzy sets. Information and Control, 8(3):338–353, 1965.
• [22] E. Feigenbaum, P. McCorduck, and H. P. Nii. The Rise of the Expert Com- pany. Times Books, New York, 1988.
• [23] P. Jackson. Introduction to Expert Systems. Addison-Wesley, 3rd edition, 1999.
• [24] M. Campbell, A. J. Hoane Jr., and F. h. Hsu. Deep Blue. Artificial Intelligence, 134(1-2):57–83, 2002.
• [25] D. M. Bourg and G. Seeman. AI for Game Developers. O’Reilly Media, July 2004.
• [26] Richard S. Sutton. Learning to predict by the methods of temporal differences. Machine Learning, 3:9–44, 1988.
• [27] C. J. C. H. Watkins and Peter Dayan. Technical note: Q-learning. Machine Learning, 8(3):279–292, May 1992.
• [28] J. H. Holland. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press, Cambridge, 1975.
• [29] J. P. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, 1992.
• [30] I. Rechenberg. Evolutionary strategy. In J. M. Zurada, R. Marks II, and C. Robinson, editors, Computational Intelligence: Imitating Life, pages 147–159. IEEE Press, Los Alamitos, 1994.
• [31] H.-P Schwefel. Numerical Optimization of Computer Models. John Wiley, Chichester, UK, 1981.
• [32] S. Nolfi, J. L. Elman, and D. Parisi. Learning and evolution in neural networks. Technical report, Technical Report 9019, Center for Research in Language, University of California, San Diego, 1990.
• [33] K. O. Stanley and R. Miikkulainen. Evolving neural networks through augmenting topologies. Technical Report AI2001-290, Department of Computer Sciences, The University of Texas at Austin, 2002.
• [34] K. O. Stanley, B. D. Bryant, and R. Miikkulainen. Evolving neural network agents in the NERO video game. In Proceedings of the IEEE 2005 Symposium on Computational Intelligence and Games (CIG’05). Piscataway, NJ: IEEE, 2005.
• [35] K. O. Stanley, B. D. Bryant, and R. Miikkulainen. Real-time neuroevolution in the NERO video game. IEEE Transactions on Evolutionary Computation, 9:653–668, 2005.
• [36] N. Jennings and M. Wooldridge. Software agents. IEE Review, The Institution of Engineering and Technology (IET), United Kingdom, 42(1):17–20, 1996.
• [37] M. Wooldridge, J.P. Muller, and M. Tambe. Agent theories, architectures, and languages: A bibliography. In Intelligent Agents II Agent Theories, Architectures, and Languages, pages 408 – 31. Springer Berlin / Heidelberg, 1996.