Artificial Intelligence Basics E-Book

N. Gupta

• Herausgeber: Packt Publishing
• Kategorie: Fachliteratur
• Sprache: Englisch

Seitenzahl: 243

Veröffentlichungsjahr: 2024

Beschreibung

This book is designed as a self-teaching introduction to the fundamental concepts of artificial intelligence (AI). It begins with the history of AI, the Turing test, and early applications, providing a strong foundation. Later chapters cover the basics of searching, game playing, and knowledge representation. The journey continues with detailed explorations of expert systems and machine learning, equipping readers with essential AI techniques.
As the course progresses, you will delve into separate programming chapters on Prolog and Python, learning how to implement AI concepts in these languages. These chapters offer practical coding experience, enhancing your understanding of AI programming. The book culminates with a comprehensive chapter on AI machines and robotics, showcasing numerous modern applications and providing a glimpse into the future of AI technology.
Understanding these AI concepts is crucial as they form the basis of many modern technologies and applications. This book ensures a smooth transition from a beginner to a proficient AI practitioner, equipped with both theoretical knowledge and practical skills. By the end of the book, you will have a thorough understanding of AI's history, core principles, and practical implementations, ready to apply this knowledge to real-world problems and projects.

Leseprobe

ARTIFICIALINTELLIGENCEBASICS

Neeru Gupta, PhD&Ramita Mangla

MERCURY LEARNING AND INFORMATION

Dulles, VirginiaBoston, MassachusettsNew Delhi

Copyright ©2020 by MERCURY LEARNING AND INFORMATION LLC. All rights reserved.

Reprinted and revised with permission.

Original title and copyright: Foundation of Artificial Intelligence and Expert Systems.

Copyright ©2019 by Trinity Press (An imprint of Laxmi Publications Pvt. Ltd. All rights reserved.)

This publication, portions of it, or any accompanying software may not be reproduced in any way, stored in a retrieval system of any type, or transmitted by any means, media, electronic display or mechanical display, including, but not limited to, photocopy, recording, Internet postings, or scanning, without prior permission in writing from the publisher.

Publisher: David Pallai

MERCURY LEARNING AND INFORMATION

22841 Quicksilver Drive

Dulles, VA 20166

[email protected]

www.merclearning.com

1-800-232-0223

N. Gupta & R. Mangla. Artificial Intelligence Basics.

ISBN: 978-1-68392-516-3

The publisher recognizes and respects all marks used by companies, manufacturers, and developers as a means to distinguish their products. All brand names and product names mentioned in this book are trademarks or service marks of their respective companies. Any omission or misuse (of any kind) of service marks or trademarks, etc. is not an attempt to infringe on the property of others.

Library of Congress Control Number: 2020931301

202122321 Printed on acid-free paper in the United States of America.

Our titles are available for adoption, license, or bulk purchase by institutions, corporations, etc. For additional information, please contact the Customer Service Dept. at 800-232-0223(toll free).

All of our titles are available in digital format at academiccourseware.com and other digital vendors. The sole obligation of Mercury Learning And Information to the purchaser is to replace the book, based on defective materials or faulty workmanship, but not based on the operation or functionality of the product.

CONTENTS

Acknowledgments

1ARTIFICIAL INTELLIGENCE (AI)

1.1Computerized Reasoning

1.2Turing Test

1.3What is Intelligence?

1.4Artificial Intelligence

1.5Goals of Artificial Intelligence

1.6History of Artificial Intelligence

1.7Advantages of Artificial Intelligence

1.8Application Areas of Artificial Intelligence

1.9Components of Artificial Intelligence

2PROBLEM REPRESENTATION

2.1Introduction

2.2Problem Characteristics

2.3Problem Representation in AI

2.4Production System

2.5Conflict Resolution

3THE SEARCH PROCESS

3.1Search Process

3.2Strategies for Search

3.3Search Techniques

4GAME PLAYING

4.1Game Playing

4.2Game Tree

4.3Components of a Game Playing Program

4.4Game Playing Strategies

4.5Problems in Computer Game Playing Programs

5KNOWLEDGE REPRESENTATION

5.1Introduction

5.2Definition of Knowledge

5.3Importance of Knowledge

5.4Knowledge-based Systems

5.5Differences between Knowledge-based Systems and Database Systems

5.6Knowledge Representation Scheme

6EXPERT SYSTEMS

6.1Introduction

6.2Definition of an Expert System

6.3Characteristics of an Expert System

6.4Architectures of Expert Systems

6.5Expert System Life Cycle

6.6Knowledge Engineering Process

6.7Knowledge Acquisition

6.8Difficulties in Knowledge Acquisition

6.9Knowledge Acquisition Strategies

6.10Advantages of Expert Systems

6.11Limitations of Expert Systems

6.12Examples of Expert Systems

7LEARNING

7.1Learning

7.2General Model for Machine Learning Systems

7.3Characteristics of Machine Learning

7.4Types of Learning

7.5Advantages of Machine Learning

7.6Disadvantages of Machine Learning

8PROLOG

8.1Preliminaries of Prolog

8.2Milestones in Prolog Language Development

8.3What is a Horn Clause?

8.4Robinson’s Resolution Rule

8.5Parts of a Prolog Program

8.6Queries to a Database

8.7How does Prolog Solve a Query?

8.8Compound Queries

8.9The _ Variable

8.10Recursion in Prolog

8.11Data Structures in Prolog

8.12Head and Tail of a List

8.13Print all the Members of the List

8.14Print the List in Reverse Order

8.15Appending a List

8.16Find Whether the Given Item is a Member of the List

8.17Finding the Length of the List

8.18Controlling Execution in Prolog

8.19About Turbo Prolog

9PYTHON

9.1Languages Used for Building AI

9.2Why Do People Choose Python?

9.3Build AI Using Python

9.4Running Python

9.5Pitfalls

9.6Features of Python

9.7Useful Libraries

9.8Utilities

9.9Testing Code

10ARTIFICIAL INTELLIGENCE MACHINES AND ROBOTICS

10.0Introduction

10.1History: Serving, Emulating, Enhancing, and Replacing Man

10.2Technical Issues

10.3Applications: Robotics in the Twenty-First Century

10.4Summary

REVIEW QUESTIONS

INDEX

ACKNOWLEDGMENTS

While writing this book, many of our nears-and-dears helped us with their sincere suggestions and comments. We are thankful to them. We also express our gratitude to the Tata McGraw-Hills, Roger Schank, University of Texas, Rakesh Sharma, Intelligence Information Technology and Services. Besides, we also extend our thanks to the Dan W. Patterson, Electrical Engineering and Computer Science Department of the University of Texas at El Paso for the unrestrained use of their facilities.

Creative suggestions for improvement of the book shall be acknowledged gratefully.

—Authors

CHAPTER 1

ARTIFICIAL INTELLIGENCE (AI)

1.1 Computerized Reasoning

From the ancient times, human beings have tried to get their work done by using human strength or inanimate machines. One characteristic that is constant in the software industry today is that of “change.” Change is one the most critical aspects of software development and management. New tools and new approaches are announced almost every day. Thanks to the industrial revolution, many activities are carried out by machines. With the invention of digital computers, error-prone numerical problems and time-consuming tasks are done with accuracy and relative ease. Then, it struck people: “Why not seek the help of computers in the reasoning process?” How computers can help with the reasoning process was explained by Alan Turing. Before we explain the Turing Test, let’s look at Table 1.1, which presents the major differences between humans and computers.

Table 1.1 Differences between humans and computers

Humans

Computers

Have emotions

“Dumb” and have no emotions

Have a continuous nature

Discrete in nature

Have the capacity to learn

Must be programmed

Limited memory size

Unlimited memory size

Storage “devices” are electrochemical

Storage devices are electronic

in nature

and magnetic

Living “devices”

Non-living devices

Use Fuzzy logic

Use binary logic for computation

1.2 Turing Test

In 1950, Alan Turing wrote an article in Mind Magazine that considered the question “Can a machine think?” This article began the discussion that has become part of the philosophy of Artificial Intelligence (AI).

“Thinking” is difficult to define. There are two kinds of questions that philosophers have addressed:

a. Can a machine be intelligent? Can it solve all the problems that a human can solve by using intelligence?

b. Can a machine be built with a mind and experience a subjective consciousness [a quality of awareness]?

In the Mind Magazine article, Turing proposed the “imitation game,” which was later known as the “Turing Test.” The Turing Test measures the performance of a supposedly intelligent machine against that of human being. Turing’s imitation game places a human and a machine counterpart in rooms apart from a second human being, who is referred to as the interrogator. A diagrammatic representation of the Turing Test is given in Figure 1.1.

FIGURE 1.1 Representation of Turing Test.

Turing proposed that if the human interrogator in Room C is not able to identify who is in Room A or in Room B, then the machine possesses intelligence. Turing considered this test as sufficient for attributing thinking capacity to a machine.

However, the test is not easy as it seems. Humans are far superior to machines in regards to creativity, common sense, and reasoning. So humans are sure to excel in these areas while machines are faster and more accurate for numerical computations. Machines can never be wrong in their computations, whereas there exists a probability that humans may give incorrect answers, even after taking a long time. Therefore, Turing argued the machine may be assumed to be intelligent.

1.2.1 Weakness of the Turing Test

Turing did not explicitly state that the Turing Test could be used as a measure of intelligence or any other human quality. However, the Turing Test has come under severe criticism because it has been proposed as a measure of a machine’s “ability to think” or its “intelligence.” This proposal has received criticism from both philosophers and computer scientists. It assumes that an interrogator can determine if a machine is “thinking” by comparing its behavior with human behavior. Every element of this assumption has been questioned, including the value of comparing only behavior and the value of comparing a machine with a human. The reliability of the interrogator’s judgment has also been part of the discussion.

Because of these considerations, some AI researchers have questioned the relevance of the test, which brings us to the verge of a major question: “What is intelligence?”

1.3 What is Intelligence?

A typical definition of intelligence is “the ability to acquire and apply knowledge.” Intelligence includes the ability to benefit from past experience, act purposefully to solve problems, and adapt to new situations.

1.3.1 Types of Intelligence

In the 1980s and 1990s, psychologist Howard Gardner proposed the idea of eight kinds of intelligence, which are relatively independent of one another. These eight types of intelligence are:

1. Linguistic: Spoken and written language skills

2. Logical-Mathematical: Number skills

3. Musical: Performance or composition skills

4. Spatial: Ability to evaluate and analyze the visual world

5. Bodily-Kinesthetic: Dance or athletic ability

6. Interpersonal: Skills in understanding and relating to others

7. Intrapersonal: Skills in understanding the self

8. Nature: Skills in understanding the natural world.

In the 1980s and 1990s, Robert Sternberg proposed the Triarchic Theory of Intelligence that distinguished among three aspects of intelligence:

Componential Intelligence: The ability assessed by intelligence tests;

Experimental Intelligence: The ability to adapt to new situations and produce new ideas;

Contextual Intelligence: The ability to function effectively in daily situations.

1.4 Artificial Intelligence

The term Artificial Intelligence (AI) was coined by John McCarthy in 1956. Numerous definitions for AI have been proposed by scientists and researchers such as:

Artificial Intelligence is the study of how to make computers do things at which, at the moment, people are better;

Artificial Intelligence is a part of computer science that is concerned with designing intelligent computer systems, that is, systems that exhibit the characteristics we associate with intelligence in human behavior;

Artificial Intelligence is the branch of computer science that deals with the way of representing knowledge using symbols rather than numbers and with rules-of-thumb or heuristic methods for processing information.

1.5 Goals of Artificial Intelligence

The goals of AI are as follows:

To create expert systems: These are systems that exhibit intelligent behavior, learn, demonstrate, explain, and advise users.

To implement human intelligence in machines: Researchers want to create systems that understand, think, learn, and behave like humans.

1.6 History of Artificial Intelligence

1941: The electronic computer was first developed in 1941, but evidence of AI can be traced back to ancient Egypt and Greece. Eventually, the technology become available to create machine intelligence.

1949: The stored computer program made the job of entering a program easier, and advancements in computer theory led to the creation of the fields of computer science and AI.

1950: Alan Turing proposed the Turing Test. Turing considered this as a sufficient test for attributing thinking capacity to a machine.

1955: Newell and Simon developed the Logic Theorist. The program represented each problem as a tree model, which it would attempt to solve by selecting the branch that would most likely result in the correct conclusion.

1956: The field of AI research was founded at a conference on the campus of Dartmouth College in the summer of 1956. The father of AI is John McCarthy. He wrote programs that solved word problems in algebra, proved logical theorems, and used English words.

1958: John McCarthy announced his new development, the LISP language. LISP stands for List Processing and was soon adopted as the language of choice among most AI developers.

Knowledge Expansion: The next few years would later be called an “AI winter,” a period when funding for AI projects was hard to find.

1968: A multitude of programs, notably the SHRDLU and part of the MicroWorlds project, which consisted of research and programming using small words, were launched.

1970: In 1970, AI achieved commercial success with the “expert system,” a form of AI program that simulated the knowledge and analytical skills of one or more human experts. Another development during this time was the Prolog language.

1985: By 1985, the market for AI had reached over a billion dollars. At the same time, Japan’s fifth generation computer project inspired the U.S. and British governments to restore funding for academic research in the field.

1990: In the 1990s and early 21st century, AI achieved its greatest successes. Now AI is used for logistics, data mining, medical diagnosis, and many other areas throughout the technology industry.

FIGURE 1.2 A brief history of Artificial Intelligence.

1.7 Advantages of Artificial Intelligence

It is evident that artificial intelligence will have to fill the gaps of human knowledge, and it will make man’s work easier. Some advantages of AI are given below:

1. AI machines do not get sick. There is no need for sleep or breaks. AI can go, go, go. AI machines can definitely get a lot more work done than people can. Take the finance industry, for example, where there are numerous stories showing the value of AI.

2. AI techniques play a major role in science and medicine. AI methods have been employed recently to discover subtle interactions between medications that put patients at risk for serious side effects.

3. AI can help us to plan trips using GPS systems that rely on AI to cut through the complexity of millions of routes to find the best one to take.

4. AI can help perform calculations that are too challenging for humans.

5. AI algorithms detect faces as we take pictures with our phones and recognize the faces of individual people when we post those pictures to Facebook. With the help of AI machines, our smart phones can understand our speech.

6. AI provides accurate results with few errors and defects.

7. AI easily works in stressful and complex situations where humans may struggle or cannot accomplish the task.

8. AI can be used for longer problems, where more direct methods fail.

1.8 Application Areas of Artificial Intelligence

The concept of AI has been implemented in the following fields:

1. Problem Solving: This is first application area of AI research; the objective of this particular area of research is how to implement the procedures on AI Systems to solve problems like humans solve problems.

2. Game Playing: Much of early research in state space search was done using common board games such as checkers, chess, and 8-puzzle. The board configurations used in playing these games are easily represented in computers, requiring no complex formalisms. For solving large and complex AI problems, many techniques, like heuristics, are required. Game playing in AI is important because:

The rules of the games are limited. Hence, extensive amounts of domain-specific knowledge are seldom needed.

Games provide a structured task where success or failure can be measured with the least effort.

Games visualize real life situations in a constricted fashion. Moreover, game playing permits one to simulate real life situations.

Unfortunately, developments in computer game playing programs are not that easy because of problems with the combinatorial explosion of solutions. In chess, the number of positions to be examined is about 35100.

3. Natural Language Processing [NLP]: Natural language is the language of our routine; we speak it and understand it very well. The main goal of NLP is for people to ask questions to the computer in their mother tongue, and the computer will “understand” that particular language. The system will then give the response in the same language. Researchers are trying to make computers so intelligent that they can understand our natural language (such as English or any other language). NLP can be divided into two sub fields:

a. Natural language understanding: NLP researchers investigate some methods of allowing the machine to improve instructions given in ordinary English so that the computers can understand people more easily.

b. Natural language generation: This aims to have computers produce ordinary English so that people can understand the computers more easily.

4. Robotics: Robotics can be defined as the science or study of technology primarily associated with the design, fabrication, theory, and application of robots. The term “robot” is a Czech word meaning “slave.”

“Robots are machines that can be programmed to perform tasks.”

Many robots do jobs that are hazardous to people, such as defusing bombs and mines and exploring shipwrecks. Robots have electrical components which power and control the machinery. The major components of a robot are:

Manipulator: The manipulator arm performs the job that has been assigned to it by the control unit.

Control unit: This provides the necessary control signals for activating the various parts for manipulation. It acts as an interface to various sensors which determine what the external environment is.

Power source unit: This provides the necessary energy to make the robot perform activities. Many different types of batteries can be used as a power source for robots. Designing a battery powered robot needs to take into account factors such as safety, lifetime cycle, and weight.

5. Expert Systems: Expert systems are one of first AI technologies to help people solve important problems, and they are very important.

“Expert systems are comprised of knowledge based programs that can solve problems when technical expertise is required.”

Some examples of expert systems that are in use are as follows:

MYCIN, which is used in the medical field to diagnose diseases and

DENDRAL, which is used in life science to identify the structure of chemical molecules.

6. Vision Systems: These systems understand, interpret, and comprehend visual input on the computer. For example,

A spy plane takes photographs, which are used to figure out spatial information or map the area.

Police use computer software that can recognize the face of a criminal with a stored portrait created by a forensic artist.

7. Speech Recognition: Some intelligent systems are capable of hearing and comprehending language in terms of sentences and their meaning while a human talks to them. These systems can handle different accents, slang words, noise in the background, and even changes in a human’s voice due to a cold.

1.9 Components of Artificial Intelligence

Any AI system consists chiefly of the following components, such as a learning AI programming language, knowledge representation, problem-solving (mainly by heuristic search), and AI hardware.

a. Learning: Learning means adding new knowledge to the knowledge base and improving or refining previous knowledge.

The success of an AI program is based on the extent of knowledge it has and how frequently it acquires knowledge. Learning agents consists of four main components. They are the:

Learning element, the part of the agent responsible for improving its performance;

Performance element, the part that chooses the actions to take;

Critics, which tells the learning element how the agent is doing;

Problem generator, which suggests actions that could lead to new information experiences.

b. AI Programming Language: Today, just as we have specialized languages and programs for data processing and scientific applications, we have specialized languages and tools for AI programming using AI language programs and tools for the AI environment. LISP and Prolog are the primary languages used in AI programming.

LISP (List Processing): LISP is an AI programming language developed by John McCarthy in 1950. LISP is a symbolic processing language that represents information in lists and manipulates lists to derive information.

PROLOG (Programming in Logic): Prolog was developed by Alain Colmeraver and P. Roussel at Marseilles University in France in the early 1970’s. Prolog uses the syntax of predicate logic to perform symbolic, logical computations.

c. Knowledge Representation: The quality of the result depends on how much knowledge the system possesses. The available knowledge must be represented in an efficient way. Hence, knowledge representation is a vital component of the system. The best known representations schemes are:

• Associative Networks or Semantic Networks

• Frames

• Conceptual Dependencies and

• Scripts

d. Problem-solving: The objective of this particular area of research is how to implement the procedures on AI systems to solve problems like humans do. The inference process should also be equally good to obtain satisfactory results. The inference process is broadly divided into the brute and heuristic search procedures.

e. AI Hardware: Today, most of the AI programs are implemented on Von Neumann machines only. However, dedicated workstations have emerged for AI programming. Computers are classified into one of following four categories:

a) Single Instruction Single Data (SISD) Machines

b) Single Instruction Multiple Data (SIMD) Machines

c) Multiple Instruction Single Data (MISD) Machines

d) Multiple Instruction Multiple Data (MIMD) Machines

In these machines, numeric computations occupy a substantial chunk of the processing time, followed by symbolic processing.

CHAPTER 2

PROBLEM REPRESENTATION

2.1 Introduction

We face so many problems in day-to-day life and want to find the solutions for them. Our goal in AI is to construct working programs that solve these problems. The steps that are required to build a system to solve a particular problem are

1. Problem Definition: This must include precise specifications of what the initial situation will be, as well as what final situations constitute acceptable solutions to the problem.

2. Problem Analysis: This can have an immense impact on the appropriateness of various possible techniques for solving the problem.

3. Selection: This involves choosing the best techniques for solving the particular problem.

2.2 Problem Characteristics

In order to choose the most appropriate method for a particular problem, it is necessary to check the problem in light of the following considerations:

1. Is the problem decomposable into smaller or easier sub-problems?

A large and composite problem can be easily solved if it can be broken into smaller problems and recursion could be used. For example, let’s consider ∫x2 + 3x + Sin 2x Cos 2x dx.

This can be done by breaking it into three problems and solving each by applying some specific rules. By adding the results of these individual solutions, the complete solution can be obtained.

2. Can the solution steps be ignored or undone?

AI problems fall into three classes: ignorable, recoverable, and irrecoverable. These classifications are related to the steps of the solution to a problem. For example, consider the following:

a. Theorem proving, in which solution steps can be ignored;

b. The 8-puzzle game, in which solution steps can be undone;

c. Chess, in which the solution steps cannot be undone.

3. AI programs use an internally consistent knowledge base.

4. In order to classify a system as an AI program, the fundamental criterion is that it must require a lot of knowledge or it uses knowledge to constrain solutions.

5. AI programs require periodic interactions between humans and computer, since the programs assist humans in making the right decisions. AI systems also have the capacity to handle uncertainty and incomplete and irrelevant information.

6. AI programs use the heuristic search to solve a large class of problems. This search includes a variety of techniques. Heuristics are also used for problems where no general algorithms are known.

7. A vital characteristic of an AI program is its ability to learn. Learning is an essential feature without which the modern systems could not have achieved their advanced technological level.

2.3 Problem Representation in AI

Before a solution can be found, the most important condition is that the problem must be very precisely defined. By defining it properly, it is easy to understand and we can abstract it into different states. These states are opened by a set of operators and the decisions of which operators should be applied. When and where are dictated by the overall control strategy. The most common methods of problem representation in AI are State Space Representation and Problem Reduction.

1.State Space Representation: In this method, the problem is defined in the form of states. The straight forward approach for planning an algorithm is the state space search because it takes into account everything needed for finding a solution. Hence, “state” here means “the position at a certain time.” For example, consider the following:

Water in a pan is in a liquid state, but when the stove is turned on, the state of water is changed: now it is boiled water (vapor). The state space search involves finding a path from the initial state of a search problem to a goal state. To do this, we first build a search graph starting from the initial state (or goal state). We expand the state by applying search operators to that state which generate all of its successor states. The problem must cross the following states:

a. Initial state or starting state

b. Rule applied or operator used

c. Goal state

When we define problems according to states, the problems become easier and more understandable because the process shows every aspect of the problem. There are two ways available to solve a state space search:

• The forward state space search, which is sometimes called progression planning because it moves in the forward direction; and

• The backward state space search, which is sometimes called regression planning because it finds the solution from the goal to the starting stage.

Here are some examples of state space representation:

A. The 8-puzzle: This is the 8-puzzle with a 3 × 3 grid with 8 consecutively numbered tiles arranged on it. Any tiles adjacent to the space can be moved. A number of different goal states are used.

A state for this problem needs to keep track of the position of all the tiles on the game board, with 0 representing the blank position (space) on the board. The initial state could be represented as (5, 4, 0), (6, 1, 8), (7, 3, 2). The final state could be represented as (1, 2, 3), (8, 0, 4), (7, 6, 5). The operators can be thought of in terms of direction: a blank space effectively moves up, down, left, or right.

B. Water Jug Problem: Imagine a 3-liter jug, a 5-liter jug, and an unlimited supply of water. The goal is to get exactly 1 liter of water into either jug. Either jug can be emptied or filled, or poured into the other.

A state in this problem could be represented with just a pair of numbers, the first representing the number of liters of water in the 5-liter (large) jug and the second representing the number of liters of water in the 3-liter (small) jug.

• The initial state would typically be (0, 0), representing the fact that both jugs start empty.

• The final state would be represented as (0, 1).

• The operators for this problem could include

a. Fill the 5-liter jug to capacity from the water source.

b. Fill the 3-liter jug to capacity from the water source.

c. Empty the 5-liter jug into a drain.

d. Pour water from the 3-liter jug into the 5-liter jug until its capacity is reached. So, there is space for 2 liters of water in the 5-liter jug.

e. Again fill the 3-liter jug and put the water in the 5-liter jug. Now, the 5-liter jug is full, and there is exactly 1 liter of water remaining in the 3-liter jug.

f. Empty the 5-liter jug into a drain.

g. We have reached our goal state, i.e., (0,1).

Deficiencies of the state space representation:

a. It is not possible to display all states for a given problem.

b. This approach explores a monolithic (massive) model of the world, rather than applying a factored perspective.

c. The resources of the computer system are limited in handling this massive state space representation.

d. It is a time consuming process.

e. The program does not learn from mistakes, and hence tends to commit the same mistake repeatedly.

2. Problem Reduction: To overcome the problems of the state space method, the problem reduction technique is used. Problem reduction search is a basic problem-solving technique of AI involving reducing a problem to a set of easier sub-problems whose solutions, if found, can be combined to form a solution to the complex problem. Such a search is easily written as a recursive program. Problem reduction can be graphically represented with the help of AND and OR graphs or the AND-OR tree. The decomposition of the problem generates AND arcs. One AND may point to any number of successor nodes. All these must be solved so that the arc will give rise to many arcs, indicating several possible solutions.

• The AND relationship solutions for a problem is obtained by solving all the sub-problems, like the AND gate is true if, and only if, all the inputs are true.

• In the OR relationship, the solution for the problem is obtained by solving any of the sub-problems.

Figures 2.1 and 2.2 are helpful for understanding the AND-OR graph.

FIGURE 2.1 Problem Reduction Using the AND-OR Graph.

FIGURE 2.2 Problem Reduction Using the AND-OR Graph.

2.4 Production System