UNIT I PROBLEM SOLVING
Introduction to AI - AI Applications - Problem solving agents
– search algorithms – uninformed search strategies – Heuristic
search strategies – Local search and optimization problems –
adversarial search – constraint satisfaction problems (CSP)
1.1 Introduction to AI
It is the study of how to make computers do things at which, at
the moment, people are better.
Some definitions of artificial intelligence, organized into
four categories
I. Systems that think like humans
1. "The exciting new effort to make computers think machines with
minds, in the full and literal sense."(Haugeland, 1985)
2. "The automation of activities that we associate with human
thinking, activities such as decision-making, problem
solving, learning" (Bellman, 1978)
II. Systems that act like humans
3. "The art of creating machines that performs functions that
require intelligence when performed by people." (Kurzweil,
1990)
4. "The study of how to make computers do things at which, at
the moment, people are better." (Rich and Knight, 1991)
III. Systems that think rationally
5. "The study of mental faculties through the use of
computational models." (Chamiak and McDermott, 1985)
6. "The study of the computations that make it possible to
perceive, reason, and act." (Winston, 1992)
IV. Systems that act rationally
7. "Computational Intelligence is the study of the designof
intelligent agents." (Poole et al., 1998)
8. "AI is concerned with intelligent behavior in
artifacts." (Nilsson, 1998)
The definitions on the 1, 2, 3, 4 measure success in terms
of human performance, whereas the ones on the 5, 6, 7, 8
, measure against an ideal concept of intelligence.
A system is rational if it does the "right thing," given
what it knows.
The term AI is defined by each author in its own perceive,
leads to four important categories
i. Acting humanly: The Turing Test approach
ii. Thinking humanly: The cognitive modeling approach
iii. Thinking rationally: The "laws of thought" approach
iv. Acting rationally: The rational agent approach
(i) Acting humanly: The Turing Test approach
To conduct this test, we need two people and the
machine to be evaluated. One person plays the role of the
interrogator, who is in a separate room from the computer
and the other person. The interrogator can ask questions of
either the person or the computer but typing questions and
receiving typed responses. However, the interrogator knows
them only as A and B and aims to determine which the person
is and which is the machine.
The goal of the machine is to fool the interrogator into
believing that is the person. If the machine succeeds at this,
then we will conclude that the machine is acting humanly. But
programming a computer to pass the test provides plenty
to work on, to possess the followingcapabilities.
Natural language processing to enable it to
communicate successfully in English.
Knowledge representation to store what it knows orhears;
Automated reasoning to use the stored information toanswer
questions and to draw new conclusions
Machine learning to adapt to new circumstances and todetect
and extrapolate patterns.
Total Turing Test: the test which includes a video so that
the interrogator can test the perceptual abilities of the
machine. To undergo the total Turing test, the computer
will need
, computer vision to perceive objects, and
robotics to manipulate objects and move about
(ii) Thinking humanly: The cognitive modeling approach
To construct a machines program to think like a human,
first it requires the knowledge about the actual workings
of human mind. After completing the study about human mind
it is possible to express the theory as a computer program.
If the program’s inputs/output and timing behavior
matched with the human behavior then we can say that the
program’s mechanism is working like a human mind.
Example: General Problem Solver (GPS) – A problem solvers
always keeps track of human mind regardless of right answers.
The problem solver is contrast to other researchers, because
they are concentrating on getting the right answers
regardless of the human mind.
An Interdisciplinary field of cognitive science uses
computer models from AI and experimental techniques from
psychology to construct the theory of the working of the
human mind.
(iii) Thinking rationally: The "laws of thought" approach
Laws of thought were supposed to govern the operation of t h
e
mind and their study initiated the field called logic.
Example 1:"Socrates is a man; All men are mortal;
therefore, Socrates is mortal."
Example 2:“Ram is a student of III year CSE; All students
are good in III year CSE; therefore, Ram is a good student”
Syllogisms: A form of deductive reasoning consisting of a
major premise, a minor premise, and a conclusion
Syllogisms provided patterns for argument structures that
always yielded correct conclusions when given correctpremises
There are two main obstacles to this approach.
1. It is not easy to take informal knowledge and state it in the
formal terms required by logical notation, particularly when
the knowledge is less.
2. There is a big difference between being able to solve a
problem "in principle" and doing so in practice
, (iv) Acting rationally: The rational agent approach
An agent is just something that acts. A rational agent is
one that acts so as to achieve the best outcome or, when
there is uncertainty, the best expected outcome. The study
of rational agent has two advantages.
1. Correct inference is selected and applied
2. It concentrates on scientific development rather thanother
methods.
1.2. AI Applications
Robotic vehicles - AI provides robots with adequate computer
vision and motion control to better understand the environment
and act accordingly.
Autonomous planning and scheduling - AI ensures that schedules
follow all pre-determined business rules. AI will learn from
your decision-making and optimize the schedule based on
historical data
Machine translation- Machine translation is the process of
using artificial intelligence to automatically translate text
from one language to another without human involvement.
Speech recognition - A traveler calling United Airlines to book a
flight can have the entire conversation guided by an automated
speech recognition and dialog management system.
Recommendations - Companies such as Amazon, Facebook, Netflix,
Spotify, YouTube, Walmart, and others use machine learning to
recommend what you might like based on your past experiences
and those of others like you.
Game playing - IBM’s DEEP BLUE became the first computer
program to defeat the world champion in a chess match.
Spam fighting: Each day, learning algorithms classify over a
billion messages as spam, saving the recipient from having to
waste time deleting what, for many users, could comprise 80% or
90% of all messages, if not classified away by algorithms.
Because the spammers are continually updating their tactics, it
is difficult for a static programmed approach to keep up, and
learning algorithms work best.
Logistics planning: During the Persian Gulf crisis of 1991,
U.S. forces deployed a Dynamic Analysis and Replanning Tool,
DART (Cross and Walker, 1994), to do automated logistics
planning and scheduling for transportation. This involved up to
50,000 vehicles, cargo, and people at a time, and had to
account for starting points, destinations, routes, and conflict
resolution among all parameters. The AI planning techniques
generated in hours a plan that would have taken weeks with
older methods. The Defense Advanced Research Project Agency
(DARPA) stated that this single application more than paid back
Introduction to AI - AI Applications - Problem solving agents
– search algorithms – uninformed search strategies – Heuristic
search strategies – Local search and optimization problems –
adversarial search – constraint satisfaction problems (CSP)
1.1 Introduction to AI
It is the study of how to make computers do things at which, at
the moment, people are better.
Some definitions of artificial intelligence, organized into
four categories
I. Systems that think like humans
1. "The exciting new effort to make computers think machines with
minds, in the full and literal sense."(Haugeland, 1985)
2. "The automation of activities that we associate with human
thinking, activities such as decision-making, problem
solving, learning" (Bellman, 1978)
II. Systems that act like humans
3. "The art of creating machines that performs functions that
require intelligence when performed by people." (Kurzweil,
1990)
4. "The study of how to make computers do things at which, at
the moment, people are better." (Rich and Knight, 1991)
III. Systems that think rationally
5. "The study of mental faculties through the use of
computational models." (Chamiak and McDermott, 1985)
6. "The study of the computations that make it possible to
perceive, reason, and act." (Winston, 1992)
IV. Systems that act rationally
7. "Computational Intelligence is the study of the designof
intelligent agents." (Poole et al., 1998)
8. "AI is concerned with intelligent behavior in
artifacts." (Nilsson, 1998)
The definitions on the 1, 2, 3, 4 measure success in terms
of human performance, whereas the ones on the 5, 6, 7, 8
, measure against an ideal concept of intelligence.
A system is rational if it does the "right thing," given
what it knows.
The term AI is defined by each author in its own perceive,
leads to four important categories
i. Acting humanly: The Turing Test approach
ii. Thinking humanly: The cognitive modeling approach
iii. Thinking rationally: The "laws of thought" approach
iv. Acting rationally: The rational agent approach
(i) Acting humanly: The Turing Test approach
To conduct this test, we need two people and the
machine to be evaluated. One person plays the role of the
interrogator, who is in a separate room from the computer
and the other person. The interrogator can ask questions of
either the person or the computer but typing questions and
receiving typed responses. However, the interrogator knows
them only as A and B and aims to determine which the person
is and which is the machine.
The goal of the machine is to fool the interrogator into
believing that is the person. If the machine succeeds at this,
then we will conclude that the machine is acting humanly. But
programming a computer to pass the test provides plenty
to work on, to possess the followingcapabilities.
Natural language processing to enable it to
communicate successfully in English.
Knowledge representation to store what it knows orhears;
Automated reasoning to use the stored information toanswer
questions and to draw new conclusions
Machine learning to adapt to new circumstances and todetect
and extrapolate patterns.
Total Turing Test: the test which includes a video so that
the interrogator can test the perceptual abilities of the
machine. To undergo the total Turing test, the computer
will need
, computer vision to perceive objects, and
robotics to manipulate objects and move about
(ii) Thinking humanly: The cognitive modeling approach
To construct a machines program to think like a human,
first it requires the knowledge about the actual workings
of human mind. After completing the study about human mind
it is possible to express the theory as a computer program.
If the program’s inputs/output and timing behavior
matched with the human behavior then we can say that the
program’s mechanism is working like a human mind.
Example: General Problem Solver (GPS) – A problem solvers
always keeps track of human mind regardless of right answers.
The problem solver is contrast to other researchers, because
they are concentrating on getting the right answers
regardless of the human mind.
An Interdisciplinary field of cognitive science uses
computer models from AI and experimental techniques from
psychology to construct the theory of the working of the
human mind.
(iii) Thinking rationally: The "laws of thought" approach
Laws of thought were supposed to govern the operation of t h
e
mind and their study initiated the field called logic.
Example 1:"Socrates is a man; All men are mortal;
therefore, Socrates is mortal."
Example 2:“Ram is a student of III year CSE; All students
are good in III year CSE; therefore, Ram is a good student”
Syllogisms: A form of deductive reasoning consisting of a
major premise, a minor premise, and a conclusion
Syllogisms provided patterns for argument structures that
always yielded correct conclusions when given correctpremises
There are two main obstacles to this approach.
1. It is not easy to take informal knowledge and state it in the
formal terms required by logical notation, particularly when
the knowledge is less.
2. There is a big difference between being able to solve a
problem "in principle" and doing so in practice
, (iv) Acting rationally: The rational agent approach
An agent is just something that acts. A rational agent is
one that acts so as to achieve the best outcome or, when
there is uncertainty, the best expected outcome. The study
of rational agent has two advantages.
1. Correct inference is selected and applied
2. It concentrates on scientific development rather thanother
methods.
1.2. AI Applications
Robotic vehicles - AI provides robots with adequate computer
vision and motion control to better understand the environment
and act accordingly.
Autonomous planning and scheduling - AI ensures that schedules
follow all pre-determined business rules. AI will learn from
your decision-making and optimize the schedule based on
historical data
Machine translation- Machine translation is the process of
using artificial intelligence to automatically translate text
from one language to another without human involvement.
Speech recognition - A traveler calling United Airlines to book a
flight can have the entire conversation guided by an automated
speech recognition and dialog management system.
Recommendations - Companies such as Amazon, Facebook, Netflix,
Spotify, YouTube, Walmart, and others use machine learning to
recommend what you might like based on your past experiences
and those of others like you.
Game playing - IBM’s DEEP BLUE became the first computer
program to defeat the world champion in a chess match.
Spam fighting: Each day, learning algorithms classify over a
billion messages as spam, saving the recipient from having to
waste time deleting what, for many users, could comprise 80% or
90% of all messages, if not classified away by algorithms.
Because the spammers are continually updating their tactics, it
is difficult for a static programmed approach to keep up, and
learning algorithms work best.
Logistics planning: During the Persian Gulf crisis of 1991,
U.S. forces deployed a Dynamic Analysis and Replanning Tool,
DART (Cross and Walker, 1994), to do automated logistics
planning and scheduling for transportation. This involved up to
50,000 vehicles, cargo, and people at a time, and had to
account for starting points, destinations, routes, and conflict
resolution among all parameters. The AI planning techniques
generated in hours a plan that would have taken weeks with
older methods. The Defense Advanced Research Project Agency
(DARPA) stated that this single application more than paid back
