Arificial Intelligence Unit 1

Unit 1

Introduction:

A branch of Computer Science named Artificial Intelligence pursues creating the computers or machines as intelligent as human beings.

What is Artificial Intelligence?

According to the father of Artificial Intelligence, John McCarthy, it is “The science and engineering of making intelligent machines, especially intelligent computer programs”.

Artificial Intelligence is a way of making a computer, a computer-controlled robot, or a software think intelligently, in the similar manner the intelligent humans think.

AI is accomplished by studying how human brain thinks, and how humans learn, decide, and work while trying to solve a problem, and then using the outcomes of

this study as a basis of developing intelligent software and systems.

History of AI

Here is the history of AI during 20th century −

Year	Milestone / Innovation
1923	Karel Čapek play named “Rossum's Universal Robots” (RUR) opens in London, first use of the word "robot" in English.
1943	Foundations for neural networks laid.
1945	Isaac Asimov, a Columbia University alumni, coined the term Robotics.
1950	Alan Turing introduced Turing Test for evaluation of intelligence and published Computing Machinery and Intelligence. Claude Shannon published Detailed Analysis of Chess Playing as a search.
1956	John McCarthy coined the term Artificial Intelligence. Demonstration of the first running AI program at Carnegie Mellon University.
1958	John McCarthy invents LISP programming language for AI.

1964	Danny Bobrow's dissertation at MIT showed that computers can understand natural language well enough to solve algebra word problems correctly.
1965	Joseph Weizenbaum at MIT built ELIZA, an interactive problem that carries on a dialogue in English.
1969	Scientists at Stanford Research Institute Developed Shakey, a robot, equipped with locomotion, perception, and problem solving.
1973	The Assembly Robotics group at Edinburgh University built Freddy, the Famous Scottish Robot, capable of using vision to locate and assemble models.
1979	The first computer-controlled autonomous vehicle, Stanford Cart, was built.
1985	Harold Cohen created and demonstrated the drawing program, Aaron.
1990	Major advances in all areas of AI − · Significant demonstrations in machine learning · Case-based reasoning · Multi-agent planning · Scheduling · Data mining, Web Crawler · natural language understanding and translation · Vision, Virtual Reality · Games
1997	The Deep Blue Chess Program beats the then world chess champion, Garry Kasparov.
2000	Interactive robot pets become commercially available. MIT displays Kismet, a robot with a face that expresses emotions. The robot Nomad explores remote regions of Antarctica and locates meteorites.

Philosophy of AI

While exploiting the power of the computer systems, the curiosity of human, lead him to wonder, “Can a machine think and behave like humans do?”

Thus, the development of AI started with the intention of creating similar intelligence in machines that we find and regard high in humans.

Goals of AI

· To Create Expert Systems − The systems which exhibit intelligent behavior, learn, demonstrate, explain, and advice its users.

· To Implement Human Intelligence in Machines − Creating systems that understand, think, learn, and behave like humans.

What Contributes to AI?

Artificial intelligence is a science and technology based on disciplines such as Computer Science, Biology, Psychology, Linguistics, Mathematics, and Engineering. A major thrust of AI is in the development of computer functions associated with human intelligence, such as reasoning, learning, and problem solving.

Out of the following areas, one or multiple areas can contribute to build an intelligent system.

Programming Without and With AI

The programming without and with AI is different in following ways −

Programming Without AI	Programming With AI
A computer program without AI can answer the specific questions it is meant to solve.	A computer program with AI can answer the generic questions it is meant to solve.
Modification in the program leads to change in its structure.	AI programs can absorb new modifications by putting highly independent pieces of information together. Hence you can modify even a minute piece of information of program without affecting its structure.
Modification is not quick and easy. It may lead to affecting the program adversely.	Quick and Easy program modification.

What is AI Technique?

In the real world, the knowledge has some unwelcomed properties −

· Its volume is huge, next to unimaginable.

· It is not well-organized or well-formatted.

· It keeps changing constantly.

AI Technique is a manner to organize and use the knowledge efficiently.

It should be perceivable by the people who provide it.

· It should be easily modifiable to correct errors.

· It should be useful in many situations though it is incomplete or inaccurate.

AI techniques elevate the speed of execution of the complex program it is equipped with.

Applications of AI

AI has been dominant in various fields such as,

· Gaming − AI plays crucial role in strategic games such as chess, poker, tic-tac- toe, etc., where machine can think of large number of possible positions based on heuristic knowledge.

· Natural Language Processing − It is possible to interact with the computer that understands natural language spoken by humans.

· Expert Systems − There are some applications which integrate machine, software, and special information to impart reasoning and advising. They provide explanation and advice to the users.

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

o A spying aeroplane takes photographs, which are used to figure out spatial information or map of the areas.

o Doctors use clinical expert system to diagnose the patient.

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

· Speech Recognition − Some intelligent systems are capable of hearing and comprehending the language in terms of sentences and their meanings while a human talks to it. It can handle different accents, slang words, noise in the background, change in human’s noise due to cold, etc.

· Handwriting Recognition − The handwriting recognition software reads the text written on paper by a pen or on screen by a stylus. It can recognize the shapes of the letters and convert it into editable text.

· Intelligent Robots − Robots are able to perform the tasks given by a human. They have sensors to detect physical data from the real world such as light, heat, temperature, movement, sound, bump, and pressure. They have efficient processors, multiple sensors and huge memory, to exhibit intelligence. In addition, they are capable of learning from their mistakes and they can adapt to the new environment.

Research Areas: The domain of artificial intelligence is huge in breadth and width. While proceeding, we consider the broadly common and prospering research areas in the domain of AI

Speech and Voice Recognition

These both terms are common in robotics, expert systems and natural language processing. Though these terms are used interchangeably, their objectives are different.

Speech Recognition	Voice Recognition
The speech recognition aims at understanding and comprehending WHAT was spoken.	The objective of voice recognition is to recognize WHO is speaking.
It is used in hand-free computing, map, or menu navigation.	It is used to identify a person by analysing its tone, voice pitch, and accent, etc.
Machine does not need training for Speech Recognition as it is not speaker dependent.	This recognition system needs training as it is person oriented.
Speaker independent Speech Recognition systems are difficult to develop.	Speaker dependent Speech Recognition systems are comparatively easy to develop.

Working of Speech and Voice Recognition Systems

The user input spoken at a microphone goes to sound card of the system. The converter turns the analog signal into equivalent digital signal for the speech processing. The database is used to compare the sound patterns to recognize the words. Finally, a reverse feedback is given to the database. This source-language text becomes input to the Translation Engine, which converts it to the target language text. They are supported with interactive GUI, large database of vocabulary, etc.

Real Life Applications of AI Research Areas

There is a large array of applications where AI is serving common people in their day-to- day lives:

.No.	Research Areas	Example
	Expert Systems Examples − Flight-tracking systems, Clinical systems.
	Natural Language Processing Examples: Google Now feature, speech recognition, Automatic voice output.
	Neural Networks Examples − Pattern recognition systems such as face recognition, character recognition, handwriting recognition.
	Robotics Examples − Industrial robots for moving, spraying, painting, precision checking, drilling, cleaning, coating, carving, etc.
	Fuzzy Logic Systems Examples − Consumer electronics, automobiles, etc.

Task Classification of AI

The domain of AI is classified into Formal tasks, Mundane tasks, and Expert tasks. Humans learn mundane (ordinary) tasks since their birth. They learn by perception, speaking, using language, and locomotives. They learn Formal Tasks and Expert Tasks later, in that order.For humans, the mundane tasks are easiest to learn. The same was considered true before trying to implement mundane tasks in machines. Earlier, all work of AI was concentrated in the mundane task domain.

Later, it turned out that the machine requires more knowledge, complex knowledge representation, and complicated algorithms for handling mundane tasks. This is the reason why

AI work is more prospering in the Expert Tasks domain now, as the expert task domain needs expert knowledge without common sense, which can be easier to represent and handle.

AI Techniques:

Artificial Intelligence problems span a very broad spectrum .They appear to have very little in common expected that they are hard. One of the few hard and fast results to come out of the first three decades of AI research is that intelligence requires knowledge.

· It is voluminous.

· It is hard to characterize accurately.

· It is constantly changing.

· It is differs from data by being organized in corresponds to the ways it will be used.

Tic-Tac-Toe:

Consider a board with the nine positions numbered as follows:

When X plays 1 as their opening move, then O should take 5. Then X takes 9 (in this situation, O should not take 3 or 7, O should take 2, 4, 6 or 8):

draw.

· X1 → O5 → X9 → O2 → X8 → O7 → X3 → O6 → X4, this game will be a

or 6 (in this situation, O should not take 4 or 7, O should take 2, 3, 8 or 9. In fact, taking 9

is the best move, since a non-perfect player X may take 4, then O can take 7 to win).

· X1 → O5 → X6 → O2 → X8, then O should not take 3, or X can take 7 to win, and O should not take 4, or X can take 9 to win, O should take 7 or 9.

· X1 → O5 → X6 → O2 → X8 → O7 → X3 → O9 → X4, this game will be a

draw.

· X1 → O5 → X6 → O2 → X8 → O9 → X4 (7) → O7 (4) → X3, this game will

be a draw.

· X1 → O5 → X6 → O3 → X7 → O4 → X8 (9) → O9 (8) → X2, this game will be a draw.

· X1 → O5 → X6 → O9, then X should not take 4, or O can take 7 to win, X should take 2, 3, 7 or 8.

draw.

· X1 → O5 → X6 → O9 → X2 → O3 → X7 → O4 → X8, this game will be a

· X1 → O5 → X6 → O9 → X3 → O2 → X8 → O4 (7) → X7 (4), this game will

be a draw.

· X1 → O5 → X6 → O9 → X7 → O4 → X2 (3) → O3 (2) → X8, this game will be a draw.

· X1 → O5 → X6 → O9 → X8 → O2 (3, 4, 7) → X4/7 (4/7, 2/3, 2/3) → O7/4

(7/4, 3/2, 3/2) → X3 (2, 7, 4), this game will be a draw.

In both of these situations (X takes 9 or 6 as second move), X has a property to win.

If X is not a perfect player, X may take 2 or 3 as second move. Then this game will be a draw, X cannot win.

· X1 → O5 → X2 → O3 → X7 → O4 → X6 → O8 (9) → X9 (8), this game will be a draw.

· X1 → O5 → X3 → O2 → X8 → O4 (6) → X6 (4) → O9 (7) → X7 (9), this

game will be a draw.

If X plays 1 opening move, and O is not a perfect player, the following may happen:

Although O takes the only good position (5) as first move, but O takes a bad position as second move:

· X1 → O5 → X9 → O3 → X7, then X can take 4 or 8 to win.

· X1 → O5 → X6 → O4 → X3, then X can take 2 or 9 to win.

· X1 → O5 → X6 → O7 → X3, then X can take 2 or 9 to win.

Although O takes good positions as the first two moves, but O takes a bad position as third move:

· X1 → O5 → X6 → O2 → X8 → O3 → X7, then X can take 4 or 9 to win.

· X1 → O5 → X6 → O2 → X8 → O4 → X9, then X can take 3 or 7 to win. O takes a bad position as first move (except of 5, all other positions are bad):

· X1 → O3 → X7 → O4 → X9, then X can take 5 or 8 to win.

· X1 → O9 → X3 → O2 → X7, then X can take 4 or 5 to win.

· X1 → O2 → X5 → O9 → X7, then X can take 3 or 4 to win.

· X1 → O6 → X5 → O9 → X3, then X can take 2 or 7 to win.

Many board games share the element of trying to be the first to get n-in-a-row, including Three Men's Morris, Nine Men's Morris, pente, gomoku, Qubic, Connect

Four, Quarto, Gobblet, Order and Chaos, Toss Across, and Mojo. Tic-tac-toe is an instance of an m,n,k-game, where two players alternate taking turns on an m×n board until one of them gets k in a row. Harary's generalized tic-tac-toe is an even broader generalization.

Other variations of tic-tac-toe include:

· 3-dimensional tic-tac-toe on a 3×3×3 board. In this game, the first player has an easy win by playing in the centre if 2 people are playing.

One can play on a board of 4x4 squares, winning in several ways. Winning can include: 4 in a straight line, 4 in a diagonal line, 4 in a diamond, or 4 to make a square.

Another variant, Qubic, is played on a 4×4×4 board; it was solved by Oren Patashnik in 1980 (the first player can force a win). Higher dimensional variations are also possible.

· In misère tic-tac-toe the player wins if the opponent gets n in a row. A 3×3 game is a draw. More generally, the first player can draw or win on any board (of any dimension) whose side length is odd, by playing first in the central cell and then mirroring the opponent's moves.

· In "wild" tic-tac-toe, players can choose to place either X or O on each move.

· There is a game that is isomorphic to tic-tac-toe, but on the surface appears completely different. It is called Pick15 or Number Scrabble Two players in turn say a number between one and nine. A particular number may not be repeated. The game is won by the player who has said three numbers whose sum is 15. If all the numbers are used and no one gets three numbers that add up to 15 then the game is a draw.Plotting these numbers on a 3×3 magic square shows that the game exactly corresponds with tic-tac-toe, since three numbers will be arranged in a straight line if and only if they total 15.

Question Answering:

In this series of programs that read in English text and then answer questions, also Stated in English about that text.

A QA implementation, usually a computer program, may construct its answers by querying a structured database of knowledge or information, usually a knowledge base. More commonly, QA systems can pull answers from an unstructured collection of natural language documents.Some examples of natural language document collections used for QA systems include:

A local collection of reference texts,

· Internal organization documents and web pages

· Compiled newswire reports

· A set of Wikipedia pages

· A subset of World Wide Web pages

For Example: Mary went shopping for a new coat. She found a red one she really liked. When she got it home, she discovered that it went perfectly with her favorite dress.

Consider the above paragraph, we make the Questions,

Q1: What did Mary go for shopping for? Q2: What did Mary find that she liked? Q3: Did Mary buy anything?

Question Patterns:

A set of templates that match common question forms and produce patterns to be used to match against inputs.

Templates and patterns are paired so that if a template matches successfully against an input question then its associated text patterns are used to try to find appropriate answers in the text.

The Algorithm:

To answer a question, do the following:

1. Compare each element of the question patterns against the Question and use all those that match successfully to generate a set of the text patterns.

2. Pass each of these patterns through a substitution process that generates alternative forms of verbs.

3. Apply each of these text patterns to text, and collect all the resulting answers.

4. Reply with the st of answers just collected

Problems, Problem Spaces and search:

To build a system to solve a particular problem, we need to do Four Things:

1. Define the Problem precisely.

2. Analyze the problem

3. Isolate and represent the task knowledge that is necessary to solve the problem.

4. Choose the best problem-solving technique(s) and apply it (them) to the particular problem.

Defining a Problem as a State Space Search:

• State space search

• Search strategies

• Problem characteristics

• Design of search programsProblem solving = Searching for a goal state

State Space Search: Playing Chess

• Each position can be described by an 8-by-8 array.

• Initial position is the game opening position.

• Goal position is any position in which the opponent does not have a legal move and his or her king is under attack.

• Legal moves can be described by a set of rules:

Ø Left sides are matched against the current state.

Ø Right sides describe the new resulting state.

• State space is a set of legal positions.

• Starting at the initial state.

• Using the set of rules to move from one state to another.

• Attempting to end up in a goal state.

State Space Search: Water Jug Problem

“You are given two jugs, a 4-litre one and a 3-litre one. Neither have any measuring markers on it. There is a pump that can be used to fill the jugs with water. How can you get exactly 2 litres of water into 4-litre jug?”

State Space Search: Water Jug Problem

• State: (x, y)

x = 0, 1, 2, 3, or 4

y = 0, 1, 2, 3

• Start state: (0, 0).

• Goal state: (2, n) for any n.

• Attempting to end up in a goal state.

1. (x, y) → (4, y) if x < 4

2. (x, y) → (x, 3) if y < 3

3. (x, y) → (x − d, y) if x > 0

4. (x, y) → (x, y − d) if y > 0

5. (x, y) → (0, y) if x > 0

6. (x, y) → (x, 0) if y > 0

7. (x, y) → (4, y − (4 − x)) if x + y ≥ 4, y > 0

8. (x, y) → (x − (3 − y), 3) if x + y ≥ 3, x > 0

9. (x, y) → (x + y, 0) if x + y ≤ 4, y > 0

10. (x, y) → (0, x + y) if x + y ≤ 3, x > 0

11. (0, 2) → (2, 0)

12. (2, y) → (0, y)

1. current state = (0, 0)

2. Loop until reaching the goal state (2, 0)

· Apply a rule whose left side matches the current state − Set the new current state to be the resulting state

(0, 0) (0, 3) (3, 0) (3, 3) (4, 2) (0, 2) (2, 0)

The role of the condition in the left side of a rule ⇒ restrict the application of the rule ⇒

more efficient

1. (x, y) → (4, y) if x < 4

2. (x, y) → (x, 3) if y < 3

Special-purpose rules to capture special-case knowledge that can be used at some stage in solving a problem

11. (0, 2) → (2, 0)

12. (2, y) → (0, y)

State Space Search: Summary

1. Define a state space that contains all the possible configurations of the relevant objects.

2. Specify the initial states.

3. Specify the goal states.

4. Specify a set of rules:

· What are unstated assumptions?

· How general should the rules be?

· How much knowledge for solutions should be in the rules?

Control Strategies

Requirements of a good search strategy:

1. It causes motion Otherwise; it will never lead to a solution.

2. It is systematic Otherwise; it may use more steps than necessary.

3. It is efficient Find a good, but not necessarily the best, answer.

Breadth-First Search

It starts from the root node, explores the neighboring nodes first and moves towards the next level neighbors. It generates one tree at a time until the solution is found. It can be implemented using FIFO queue data structure. This method provides shortest path to the solution.

If branching factor (average number of child nodes for a given node) = b and depth = d, then number of nodes at level d = b^d.

The total no of nodes created in worst case is b + b² + b³ + … + b^d.

Disadvantage

Since each level of nodes is saved for creating next one, it consumes a lot of memory space. Space requirement to store nodes is exponential. Its complexity depends on the number of nodes. It can check duplicate nodes.

Depth-First Search

It is implemented in recursion with LIFO stack data structure. It creates the same set of nodes as Breadth-First method, only in the different order.

As the nodes on the single path are stored in each iteration from root to leaf node, the space requirement to store nodes is linear. With branching factor band depth as m, the storage space is bm.

Disadvantage:

This algorithm may not terminate and go on infinitely on one path. The solution to this issue is to choose a cut-off depth. If the ideal cut-off isd, and if chosen cut-off is lesser than d, then this algorithm may fail. If chosen cut-off is more than d, then execution time increases.

Its complexity depends on the number of paths. It cannot check duplicate nodes.

Bidirectional Search

It searches forward from initial state and backward from goal state till both meet to identify a common state.

The path from initial state is concatenated with the inverse path from the goal state. Each search is done only up to half of the total path.

Uniform Cost Search

Sorting is done in increasing cost of the path to a node. It always expands the least cost node. It is identical to Breadth First search if each transition has the same cost. It explores paths in the increasing order of cost.

Disadvantage:

There can be multiple long paths with the cost ≤ C*. Uniform Cost search must explore them all.

Iterative Deepening Depth-First Search

It performs depth-first search to level 1, starts over, executes a complete depth-first search to level 2, and continues in such way till the solution is found.

It never creates a node until all lower nodes are generated. It only saves a stack of nodes. The algorithm ends when it finds a solution at depth d. The number of nodes created at depth d is b^d and at depth d-1 is b^d-1.

Comparison of Various Algorithms Complexities

Let us see the performance of algorithms based on various criteria −

Criterion	Breadth First	Depth First	Bidirectional	Uniform Cost	Interactive Deepening
Time	bd	Bm	bd/2	bd	bd
Space	bd	Bm	bd/2	bd	bd
Optimality	Yes	No	Yes	Yes	Yes
Completeness	Yes	No	Yes	Yes	Yes

Search Strategies: Heuristic Search

• Heuristic: involving or serving as an aid to learning, discovery, or problem-solving by experimental and especially trial-and-error methods. (Merriam-Webster’s dictionary)

• Heuristic technique improves the efficiency of a search process, possibly by sacrificing claims of completeness or optimality.

• Heuristic is for combinatorial explosion.

• Optimal solutions are rarely needed.

The Travelling Salesman Problem:

“A salesman has a list of cities, each of which he must visit exactly once. There are direct roads between each pair of cities on the list. Find the route the salesman should follow for the shortest possible round trip that both starts and finishes at any one of the cities.”

A 1 10 D 5 B5

Nearest neighbour heuristic:

1. Select a starting city.

2. Select the one closest to the current city.

3. Repeat step 2 until all cities have been visited. Nearest neighbour heuristic:

1. Select a starting city.

2. Select the one closest to the current city.

3. Repeat step 2 until all cities have been visited. O(n2) vs. O(n!)

• Heuristic function: state descriptions → measures of desirability

Problem Characteristics:

To choose an appropriate method for a particular problem:

• Is the problem decomposable?

• Can solution steps be ignored or undone?

• Is the universe predictable?

• Is a good solution absolute or relative?

• Is the solution a state or a path?

• What is the role of knowledge?

• Does the task require human-interaction?

Is the problem decomposable?

• Can the problem be broken down to smaller problems to be solved independently?

• Decomposable problem can be solved easily.

Start Goal Blocks World

CLEAR(x) → ON(x, Table) CLEAR(x) and CLEAR(y) → ON(x, y) ON(B, C) and ON(A, B)

ON(B, C) ON(A, B)

CLEAR(A) ON(A, B)

Can solution steps be ignored or undone?

Theorem proving a lemma that has been proved can be ignored for next steps.

Ignorable!

Can solution steps be ignored or undone?

The 8-Puzzle

3 8 2

3 2 1

4 6 1

Moves can be undone and backtracked. Recoverable!

Can solution steps be ignored or undone?

Playing Chess Moves cannot be retracted. Irrecoverable!

• Ignorable problems can be solved using a simple control structure that never backtracks.

• Recoverable problems can be solved using backtracking.

• Irrecoverable problems can be solved by recoverable style methods via planning.

Is the universe predictable?

The 8-Puzzle Every time we make a move, we know exactly what will happen. Certain outcome!

Few Examples:

· Playing bridge.

· Controlling a robot arm

· Helping a lawyer decide how to defend his against a murder charge.

Playing Bridge We cannot know exactly where all the cards are or what the other players will do on their turns.

Uncertain outcome!

• For certain-outcome problems, planning can be used to generate a sequence of operators that is guaranteed to lead to a solution.

• For uncertain-outcome problems, a sequence of generated operators can only have a good probability of leading to a solution.

Plan revision is made as the plan is carried out and the necessary feedback is provided.

Is a good solution absolute or relative?

1. Marcus was a man.

2. Marcus was a Pompeian.

3. Marcus was born in 40 A.D.

4. All men are mortal.

5. All Pompeians died when the volcano erupted in 79 A.D.

6. No mortal lives longer than 150 years.

7. It is now 2004 A.D.

Is a good solution absolute or relative?

1. Marcus was a man.

2. Marcus was a Pompeian.

3. Marcus was born in 40 A.D.

4. All men are mortal.

5. All Pompeians died when the volcano erupted in 79 A.D.

6. No mortal lives longer than 150 years.

7. It is now 2004 A.D

Is Marcus alive?

1. Marcus was a man.

2. Marcus was a Pompeian.

3. Marcus was born in 40 A.D.

4. All men are mortal.

5. All Pompeians died when the volcano erupted in 79 A.D.

6. No mortal lives longer than 150 years.

7. It is now 2004 A.D.

Is Marcus alive?

Different reasoning paths lead to the answer. It does not matter which path we

follow.

The Travelling Salesman Problem We have to try all paths to find the shortest one.

• Any-path problems can be solved using heuristics that suggest good paths to explore.

• For best-path problems, much more exhaustive search will be performed.

fork”.

Is the solution a state or a path?

Finding a consistent intepretation “The bank president ate a dish of pasta salad with the

– “bank” refers to a financial situation or to a side of a river?

– “dish” or “pasta salad” was eaten?

– Does “pasta salad” contain pasta, as “dog food” does not contain “dog”?

– Which part of the sentence does “with the fork” modify? What if “with vegetables” is there?

No record of the processing is necessary.

The Water Jug Problem The path that leads to the goal must be reported.

• A path-solution problem can be reformulated as a state-solution problem by describing

a state as a partial path to a solution.

• The question is whether that is natural or not.

What is the role of knowledge?

Playing Chess Knowledge is important only to constrain the search for a solution. Reading Newspaper Knowledge is required even to be able to recognize a solution.

Does the task require human-interaction?

• Solitary problem, in which there is no intermediate communication and no demand for an explanation of the reasoning process.

• Conversational problem, in which intermediate communication is to provide either additional assistance to the computer or additional information to the user.

Problem Classification

• There is a variety of problem-solving methods, but there is no one single way of solving all problems.

• Not all new problems should be considered as totally new. Solutions of similar problems can be exploited.

Search Strategies

Requirements of a good search strategy:

1. It causes motion Otherwise, it will never lead to a solution.

2. It is systematic Otherwise, it may use more steps than necessary.

3. It is efficient Find a good, but not necessarily the best, answer. Such as BFS,DFS….

Search and Search Techniques:

AI - Popular Search Algorithms

Searching is the universal technique of problem solving in AI. There are some single- player games such as tile games, Sudoku, crossword, etc. The search algorithms help you to search for a particular position in such games.

Single Agent Pathfinding Problems

The games such as 3X3 eight-tile, 4X4 fifteen-tile, and 5X5 twenty four tile puzzles are single-agent-path-finding challenges. They consist of a matrix of tiles with a blank tile. The player is required to arrange the tiles by sliding a tile either vertically or horizontally into a blank space with the aim of accomplishing some objective.

The other examples of single agent pathfinding problems are Travelling Salesman Problem, Rubik’s Cube, and Theorem Proving.

Search Terminology

· Problem Space − It is the environment in which the search takes place. (A set of states and set of operators to change those states)

· Problem Instance − It is Initial state + Goal state.

· Problem Space Graph − It represents problem state. States are shown by nodes and operators are shown by edges.

· Depth of a problem − Length of a shortest path or shortest sequence of operators from Initial State to goal state.

· Space Complexity − The maximum number of nodes that are stored in memory.

· Time Complexity − The maximum number of nodes that are created.

· Admissibility − A property of an algorithm to always find an optimal solution.

· Branching Factor − The average number of child nodes in the problem space

graph.

· Depth − Length of the shortest path from initial state to goal state.

State Space Search: Summary

1. Define a state space that contains all the possible configurations of the relevant objects.

2. Specify the initial states.

3. Specify the goal states.

4. Specify a set of rules:

******************Unit 1 Completed******************

Unit 1

one mark questions

1. ---------------- is the language used for AI programming.

2. ----------------search is a very general method to applicable to a large class of problems.

3. Is the Solution a STATE or a PATH?

4. Monotonic + Partially commutative = -------------------

5. Nonmonotonic + Not partially commutative = ----------------------

2 Mark questions

1. What is artificial intelligence?

2. What are mundane tasks?

3. What is EPAM?

4. Solve SEND

+MORE

-------------

MONEY

-------------

5. Write the assumption answers based on current situation

i) Q - Why did Russia do this?

A - ____________________________.

ii) Q - What should the United States do?

A - ____________________________.

15 mark questions

1. Describe the prior knowledge about the objects and situations involved in the text about the shopping script for C for entering A shopping Mall L and for Purchasing coat M.

2. Pick any topic among AI technique to recognize the given image

is a cat and not a dog or any other animal , using natural methods for proving mathematical theorems.

3. Solve the given decomposable problem both mathematically and write algorithm to decompose it
∫ (x²+3x+sin²x.cos²x)dx

1	2	3
8		4
7	6	5

4. i) Solve the puzzle with stepwise move using simple blocks world problem method.

Start Goal

2	8	3
1	6	4
7		5

ii) Explain three classes of problems ignorable, recoverable, irrecoverable problems with example.

5. For each of the following types of problems , try to describe a good heuristic function

i) Blocks world

ii) Theorem proving

iii) Missionaries and Cannibals