Artificial Intelligence and Machine Learning(21CS54)
MODULE 1- QUESTION BANK WITH ANSWERS
REFERENCE: Stuart Russel , 4th Edition 2015
CHAPTER 1-1.1, 1.2, 1.3
CHAPTER 3- 3.1,3.2, 3.3,3.4.1,3.4.3
1. Define AI. Explain factors to be considered while building AI
Thinking Humanly Thinking Rationally
“The exciting new effort to make “The study of mental faculties through
computers think . .. machines with the use of computational models.”
minds, in the full and literal sense.” (Charniak and McDermott, 1985)
(Haugeland, 1985) “The study of the computations that
“[The automation of] activities that make it possible to perceive, reason,
we associate with human thinking, and act.” (Winston, 1992)
activities such as decision-making,
problem solv- ing, learning .. .”
(Bellman, 1978)
Acting Humanly Acting Rationally
“The art of creating machines that “Computational Intelligence is the
per- form functions that require study of the design of intelligent
intelligence when performed by agents.” (Poole et al., 1998)
people.” (Kurzweil, 1990)
“The study of how to make “AI . . . is concerned with intelligent
computers do things at which, at the be- havior in artifacts.” (Nilsson,
moment, people are better.” (Rich and 1998)
Knight, 1991)
Acting Humanly: The Turing Test approach
The Turing Test, proposed by Alan Turing (1950), was designed to provide a satisfactory
operational definition of intelligence. A computer passes the test if a human interrogator, after
posing some written questions, cannot tell whether the written responses come from a person or
from a computer. For now, we note that programming a computer to pass a rigorously applied test
provides plenty to work on. The computer would need to possess the following capabilities:
Natural language processing to enable it to communicate successfully in English;
Knowledge representation to store what it knows or hears;
Automated reasoning to use the stored information to answer questions and to draw new
conclusions;
Machine learning to adapt to new circumstances and to detect and extrapolate patterns
Computer vision to perceive objects, and
Robotics to manipulate objects and move about.
Thinking Humanly: The cognitive modeling approach
We need to get inside the actual workings of human minds. There are three ways to do this:
through introspection—trying to catch our own thoughts as they go by; through psychological
experiments—observing a person in action; and through brain imaging—observing the brain
in action. Once we have a sufficiently precise theory of the mind, it becomes possible to express
the theory as a computer program. If the program’s input–output behavior matches corresponding
human behavior, that is evidence that some of the program’s mechanisms could also be operating
in humans. For example, Allen Newell and Herbert Simon, who developed GPS, the “General
Problem Solver” Newell and Simon, 1961. The interdisciplinary field of cognitive science brings
together computer models from AI and experimental techniques from psychology to construct
precise and testable theories of the human mind.
In the early days of AI there was often confusion between the approaches: an author would argue
that an algorithm performs well on a task and that it is therefore a good model of human
performance, or vice versa.
Thinking Rationally: The “laws of thought” approach
The Greek philosopher Aristotle was one of the first to attempt to codify “right thinking,” that is,
irrefutable reasoning processes. His syllogisms provided patterns for argument structures that
always yielded correct conclusions when given correct premises—for example, “Socrates is a man;
all men are mortal; therefore, Socrates is mortal.” These laws of thought were supposed to
govern the operation of the mind; their study initiated the field called logic.
Logicians in the 19th century developed a precise notation for statements about all kinds of
objects in the world and the relations among them. (Contrast this with ordinary arithmetic
notation, which provides only for statements about numbers.) By 1965, programs existed that
could, in principle, solve any solvable problem described in logical notation. (Although if no
solution exists, the program might loop forever.) The so-called Logicist tradition within artificial
intelligence hopes to build on such programs to create intelligent systems.
There are two main obstacles to this approach. First, 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 than 100% certain. Second, there is a big difference between solving a problem “in
principle” and solving it in practice. Even problems with just a few hundred facts can exhaust the
computational resources of any computer unless it has some guidance as to which reasoning steps
to try first. Although both of these obstacles apply to any attempt to build computational reasoning
systems, they appeared first in the Logicist tradition.
Acting Rationally: The rational agent approach
An agent is just something that acts (agent comes from the Latin agere, to do). Of course, all
computer programs do something, but computer agents are expected to do more: operate
autonomously, perceive their environment, persist over a prolonged time period, adapt to change,
and create and pursue goals. A rational agent is one that acts so as to achieve the best outcome
or, when there is uncertainty, the best expected outcome.
Making correct inferences is sometimes part of being a rational agent, because one way to act
rationally is to reason logically to theconclusion that a given action will achieve one’s goals and
then to act on that conclusion. On the other hand, correct inference is not all of ration- ality; in
some situations, there is no provably correct thing to do, but something must still be done. There
are also ways of acting rationally that cannot be said to involve inference. For example, recoiling
from a hot stove is a reflex action that is usually more successful than a slower action taken after
careful deliberation.
The rational-agent approach has two advantages over the other approaches. First, it is more
general than the “laws of thought” approach Second, it is more amenable to scientific
development than are approaches based on human behavior or human thought. The standard of
rationality is mathematically well defined and completely general, and can be “unpacked” to
generate agent designs that provably achieve it. Human behavior, on the other hand, is well
adapted for one specific environment and is defined by, well, the sum total of all the things
that humans do.
2. Explain various foundations of AI
[Link]
Philosophers (going back to 400 BCE) made AI conceivable by suggesting that the mind is in
some ways like a machine, that it operates on knowledge encoded in some internal language,
and that thought can be used to choose what actions to take.
• Can formal rules be used to draw valid conclusions?
• How does the mind arise from a physical brain?
• Where does knowledge come from?
• How does knowledge lead to action?
Rationalism
Dualism
Materialism
Empiricism
Induction
Logical positivism
Observation sentences
Confirmation theory
2. Mathematics
Mathematicians provided the tools to manipulate statements of logical certainty as well as
uncertain, probabilistic statements. They also set the groundwork for understanding
computation and reasoning about algorithms. Philosophers staked out some of the fundamental
ideas of AI, but the leap to a formal science required a level of mathematical formalization in three
fundamental areas: logic, computation, and probability.
• What are the formal rules to draw valid conclusions?
• What can be computed?
• How do we reason with uncertain information?
Algorithm
Incompleteness theorem
Computable
Tractability
NP-Completeness
Probability
3. Economics
Economists formalized the problem of making decisions that maximize the expected
utility to the decision maker.
• How should we make decisions in accordance with our preferences?
• How should we do this when others may not go along?
• How should we do this when the payoff may be far in the future?
Economics
Utility
Decision Theory
Game Theory
Operations Research
Satisficing
4. Neuroscience
Neuroscience is the study of the nervous system, particularly the brain.
Neuroscientists discovered some facts about how the brain works and the ways in
which it is like and different from computers.
How do brains process information?
5. Psychology
• Psychologists adopted the idea that humans and animals can be considered information
processing machines.
• How do humans and animals think and act?
• Behaviorism
• Cognitive Psychology
6. Computer Engineer
Computer engineers provided the ever-more-powerful machines that make AI
applications possible, and software engineers made them more usable.
• How can we build an efficient computer?
7. Control Theory
Control theory deals with designing devices that act optimally based on feedback from
the environment.
• How can artifacts operate under their own control?
• Cybernetics
• Homeostatic
• Objective function
8. Linguistics
• The study of how to put knowledge into a form that a computer can reason with , was tied
to language and informed by research in linguistics, which was connected in turn to
decades of work on the philosophical analysis of language.
• How does language relate to thought?
3. Define problem solving agent. Explain 4 Phases of problem solving process (
Goal formulation , Problem formulation, Search, Execution)
Agent is anything that can be viewed as perceiving its environment through sensors and acting
upon that environment through actuators. A human agent has eyes, ears, and other organs for
sensors and hands, legs, vocal tract, and so on for actuators. A robotic agent might have cameras
and infrared range finders for sensors and various motors for actuators. A software agent
receives keystrokes, file contents, and network packets as sensory inputs and acts on the
environment by displaying on the screen, writing files, and sending network packets
Agen Sensor
Percep
s
t ts
?
Action
Actuator s
s
Figure 2.1 Agents interact with environments through sensors and actuators.
Problem-solving agents use atomic representations, that is, states of the world are considered as
wholes, with no internal structure visible to the problem- solving algorithms.
We will see several uninformed search algorithms—algorithms that are given no information
about the problem other than its definition. Informed search algorithms, on the other hand, can do
quite well given some guidance on where to look for solutions.
4 phases of problem-solving process
1) Goal formulation
2) Problem formulation
3) Search
4) Execute
Imagine an agent in the city of Arad, Romania, enjoying a touring holiday. The agent’s
performance measure contains many factors: it wants to improve its suntan, improve its
Romanian, take in the sights, enjoy the nightlife (such as it is), avoid hangovers, and so on. The
decision problem is a complex one involving many tradeoffs and careful reading of guide-
books. Now, suppose the agent has a nonrefundable ticket to fly out of Bucharest the follow ing
day. In that case, it makes sense for the agent to adopt the goal of getting to Bucharest.
Courses of action that don’t reach Bucharest on time can be rejected without further
consideration and the agent’s decision problem is greatly simplified. Goals help organize
behavior by limiting the objectives that the agent is trying to achieve and hence the actions it
needs to consider. Goal formulation, based on the current situation and the agent’s performance measure, is the
first step in problem solving.
We will consider a goal to be a set of world states—exactly those states in which the goal
is satisfied. The agent’s task is to find out how to act, now and in the future, so that it reaches a
goal state. Before it can do this, it needs to decide (or we need to decide on its behalf) what
sorts of actions and states it should consider. If it were to consider actions at the level of “move
the left foot forward an inch” or “turn the steering wheel one degree left,” the agent would
probably never find its way out of the parking lot, let alone to Bucharest, because at that level
of detail there is too much uncertainty in the world and there would be too many steps in a
solution. Problem formulation is the process of deciding what actions and states to consider,
given a goal. We discuss this process in more detail later. For now, let us assume that the agent
will consider actions at the level of driving from one major town to another. Each state
therefore corresponds to being in a particular town.
Our agent has now adopted the goal of driving to Bucharest and is considering where to
go from Arad. Three roads lead out of Arad, one toward Sibiu, one to Timisoara, and one to
Zerind. None of these achieves the goal, so unless the agent is familiar with the geography of
Romania, it will not know which road to follow. 1 In other words, the agent will not know
which of its possible actions is best, because it does not yet know enough about the state that
results from taking each action. If the agent has no additional information—i.e., if the
environment is unknown, then it is having no choice but to try one of the actions at random.
This is called sad situation
But suppose the agent has a map of Romania. The point of a map is to provide the agent
with information about the states it might get itself into and the actions it can take. The agent
can use this information to consider subsequent stages of a hypothetical journey via each of the
three towns, trying to find a journey that eventually gets to Bucharest. Once it has found a path
on the map from Arad to Bucharest, it can achieve its goal by carrying out the driving actions
that correspond to the legs of the journey. In general, an agent with several immediate options
of unknown value can decide what to do by first examining future actions that eventually
lead to states of known value.
we assume that the environment is observable, so the agent always knows the current state.
For the agent driving in Romania, it’s reasonable to suppose that each city on the map has a
sign indicating its presence to arriving drivers. We also assume the environment is discrete, so
at any given state there are only finitely many actions to choose from. This is true for
navigating in Romania because each city is connected to a small number of other cities. We
will assume the environment is known, so the agent knows which states are reached by each
action. (Having an accurate map suffices to meet this condition for navigation problems.)
Finally, we assume that the environment is deterministic, so each action has exactly one
outcome. Under ideal conditions, this is true for the agent in Romania—it means that if it
chooses to drive from Arad to Sibiu, it does end up in Sibiu. Of course, conditions are not
always ideal, as we show in Chapter 4.
Under these assumptions, the solution to any problem is a fixed sequence of actions. “Of
course!” one might say, “What else could it be?” Well, in general it could be a branching
strategy that recommends different actions in the future depending on what percepts arrive.
For example, under less-than-ideal conditions, the agent might plan to drive from Arad to
Sibiu and then to Rimnicu Vilcea but may also need to have a contingency plan in case it
arrives by accident in Zerind instead of Sibiu. Fortunately, if the agent knows the initial state
and the environment is known and deterministic, it knows exactly where it will be after the
first action and what it will perceive. Since only one percept is possible after the first action, the
solution can specify only one possible second action, and so on
.
The process of looking for a sequence of actions that reaches the goal is called search. A
search algorithm takes a problem as input and returns a solution in the form of an action
sequence. Once a solution is found, the actions it recommends can be carried out. This is
called the execution phase. Thus, we have a simple “formulate, search, execute” design for the
agent, as shown in Figure 3.1. After formulating a goal and a problem to solve, the agent
calls a search procedure to solve it. It then uses the solution to guide its actions, doing
whatever the solution recommends as the next thing to do—typically, the first action of the
sequence—and then removing that step from the sequence. Once the solution has been
executed, the agent will formulate a new goal.
Notice that while the agent is executing the solution sequence it ignores its percepts
when choosing an action because it knows in advance what they will be. An agent that carries
out its plans with its eyes closed, so to speak, must be quite certain of what is going on.
Control theorists call this an open-loop system, because ignoring the percepts breaks the loop
between agent and environment.
4. Explain how a search problem can be defined formally( Initial State, Actions
Applicable, Transition Model, Goal Test, Path Cost)
A problem can be defined formally by five components:
• The initial state that the agent starts in. For example, the initial state for our agent in
Romania might be described as In(Arad ).
• A description of the possible actions available to the agent. Given a particular state s,
ACTIONS(s) returns the set of actions that can be executed in s. We say that each of
these actions is applicable in s. For example, from the state In(Arad ), the applicable
actions are {Go(Sibiu), Go(Timisoara ), Go(Zerind )}.
• A description of what each action does; the formal name for this is the transition
model, specified by a function RESULT(s, a) that returns the state that results from
doing action a in state s. We also use the term successor to refer to any state reachable from
a given state by a single action.2 For example, we have
RESULT(In(Arad ), Go(Zerind )) = In(Zerind ) .
Together, the initial state, actions, and transition model implicitly define the state space of
the problem—the set of all states reachable from the initial state by any sequence of
actions. The state space forms a directed network or graph in which the nodes are
states and the links between nodes are actions. (The map of Romania shown in Figure 3.2
can be interpreted as a state-space graph if we view each road as standing for two driving
actions, one in each direction.) A path in the state space is a sequence of states connected
by a sequence of actions.
• The goal test, which determines whether a given state is a goal state. Sometimes there is
an explicit set of possible goal states, and the test simply checks whether the given state
is one of them. The agent’s goal in Romania is the singleton set {In(Bucharest
)}.Sometimes the goal is specified by an abstract property rather than an explicitly enumer-
ated set of states. For example, in chess, the goal is to reach a state called “checkmate,”
where the opponent’s king is under attack and can’t escape.
• A path cost function that assigns a numeric cost to each path. The problem-solving agent
chooses a cost function that reflects its own performance measure. For the agent
trying to get to Bucharest, time is of the essence, so the cost of a path might be its length in
kilometers. In this chapter, we assume that the cost of a path can be described as the sum
of the costs of the individual actions along the path.3 The step cost of taking actiona in
state s to reach state sJ is denoted by c(s, a, sJ). The step costs for Romania are shown in
Figure 3.2 as route distances. We assume that step costs are nonnegative.
5. Explain Romania city search problem with diagram in detail mentioning all
components of the problem
Imagine an agent enjoying a touring vacation in Romania. The agent wants to take in the sights,
improve its Romanian, enjoy the nightlife, avoid hangovers, and so on. The decision problem is a
complex one. Now, suppose the agent is currently in the city of Arad and has a nonrefundable
ticket to fly out of Bucharest the following day. The agent observes street signs and sees that there
are three roads leading out of Arad: one toward Sibiu, one to Timisoara, and one to Zerind. None of
these are the goal, so unless the agent is familiar with the geography of Romania, it will not know
which road to follow.1
If the agent has no additional information—that is, if the environment is unknown—then the
agent can do no better than to execute one of the actions at random. This situation is called sad
.we will assume our agents always have access to information about the world, such as the map
in Figure 3.1. With that information, the agent can follow this four-phase problem-solving
process:
Goal formulation: The agent adopts the goal of reaching Bucharest. Goals organize behavior
by limiting the objectives and the actions to be considered
Problem formulation: The agent devises a description of the states and actions necessary to
reach the goal—an abstract model of the relevant part of the world. For our agent, one good
model is to consider the actions of traveling from one city to an adjacent city, and therefore the
only fact about the state of the world that will change due to an action is the current city.
Search: Before taking any action in the real world, the agent simulates sequences of actions in
its model, searching until it finds a sequence of actions that reaches the goal. Such a sequence is
called a solution. The agent might have to simulate multiple sequences that do not reach the
goal, but eventually it will find a solution (such as going from Arad to Sibiu to Fagaras to
Bucharest), or it will find that no solution is possible.
6. Explain Vacuum World problem with an example
A toy problem is intended to illustrate or exercise various problem-solving methods. It
can be given a concise, exact description and hence is usable by different researchers to
compare the performance of algorithms.
This can be formulated as a problem as follows:
• States: The state is determined by both the agent location and the dirt locations. The
agent is in one of two locations, each of which might or might not contain dirt. Thus,
there are 2 × 22 = 8 possible world states. A larger environment with n locations has
n · 2n states.
• Initial state: Any state can be designated as the initial state.
• Actions: In this simple environment, each state has just three actions: Left, Right, and
Suck. Larger environments might also include Up and Down.
• Transition model: The actions have their expected effects, except that moving Left in the
leftmost square, moving Right in the rightmost square, and Sucking in a clean square have
no effect. The complete state space is shown in Figure 3.3.
• Goal test: This checks whether all the squares are clean.
• Path cost: Each step costs 1, so the path cost is the number of steps in the path.
7. Explain 8 puzzle problem with an example
The 8-puzzle, an instance of which is shown in Figure 3.4, consists of a 3×3 board with
eight numbered tiles and a blank space. A tile adjacent to the blank space can slide into
the space. The object is to reach a specified goal state, such as the one shown on the right
of the figure. The standard formulation is as follows:
• States: A state description specifies the location of each of the eight tiles and the blank in
one of the nine squares.
• Initial state: Any state can be designated as the initial state. Note that any given goalcan
be reached from exactly half of the possible initial states
• Actions: The simplest formulation defines the actions as movements of the blank space
Left, Right, Up, or Down. Different subsets of these are possible depending on where
the blank is.
• Transition model: Given a state and action, this returns the resulting state; for example, if
we apply Left to the start state the resulting state has the 5 and the blank switched.
• Goal test: This checks whether the state matches the goal configuration (Other goal
configurations are possible.)
• Path cost: Each step costs 1, so the path cost is the number of steps in the path.
8. Explain 8- queen problem with an example
The goal of the 8-queens problem is to place eight queens on a chessboard such that no
queen attacks any other. (A queen attacks any piece in the same row, column or Diagonal.)
shows an attempted solution that fails: the queen in the rightmost column is attacked by the
queen at the top left.
Although efficient special-purpose algorithms exist for this problem and for the whole n-
queens family, it remains a useful test problem for search algorithms. There are two main kinds
of formulation. An incremental formulation involves operators that augment the state
description, starting with an empty state; for the 8-queens problem, this means that each action
adds a queen to the state. A complete-state formulation starts with all 8 queens on the board
and moves them around. In either case, the path cost is of no interest because onlythe final state
counts. The first incremental formulation one might try is the following:
• States: Any arrangement of 0 to 8 queens on the board is a state.
• Initial state: No queens on the board.
• Actions: Add a queen to any empty square.
• Transition model: Returns the board with a queen added to the specified square.
• Goal test: 8 queens are on the board, none attacked.
In this formulation, we have 64 · 63 ··· 57 ≈ 1.8 × 1014 possible sequences to investigate.
9. Distinguish between uninformed search and informed search algorithms
INFORMED SEARCH-An uninformed search algorithm is given no clue about how
close a state is to the goal(s).
For example, consider our agent in Arad with the goal of reaching Bucharest.
An uninformed agent with no knowledge of Romanian geography has no clue whether
going to Zerind or Sibiu is a better first step.
EG: BFS, DFS
INFORMED SEARCH- Strategies that know whether one non-goal state is “more
promising” than another is called informed search or heuristic search strategies.
informed agent who knows the location of each city likely to find the shortest path.
10. Explain BFS algorithm with example mentioning time complexity
Breadth-first search is a simple strategy in which the root node is expanded first, then all
the successors of the root node are expanded next, then their successors, and so on. In
general, all the nodes are expanded at a given depth in the search tree before any nodes
at the next level are expanded.
Breadth-first search is an instance of the general graph-search algorithm in which the
shallowest unexpanded node is chosen for expansion. This is achieved very simply by
using a FIFO queue for the frontier. Thus, new nodes (which are always deeper than
their parents) go to the back of the queue, and old nodes, which are shallower than the
new nodes, get expanded first. There is one slight tweak on the general graph-search
algorithm, which is that the goal test is applied to each node when it is generated rather
than when it is selected for expansion. This decision is explained below, where we
discuss time complexity. Note also that the algorithm, following the general template for
graph search, discards any new path to a state already in the frontier or explored set; it is
easy to see that any such path must be at least as deep as the one already found. Thus,
breadth-first search always has the shallowest path to every node on the frontier.
We can easily see that it is complete—if the shallowest goal node is at some finite depth
d, breadth-first search will eventually find it after generating all shallower nodes
(provided the branching factor b is finite). Note that as soon as a goal node is generated,
we know it is the shallowest goal node because all shallower nodes must have been
generated already and failed the goal test. Now, the shallowest goal node is not
necessarily the optimal one; technically, breadth-first search is optimal if the path cost is
a non decreasing function of the depth of the node. The most common such scenario is
that all actions have the same cost.
ALGORITHM
i. Enter starting node on QUEUE
ii. IF QUEUE is EMPTY, THEN return FAIL and stop
iii. IF first element on QUEUE is Goal Node, THEN return SUCCESS and stop
ELSE
iv. Remove and expand first element from QUEUE and place children at the end of
Queue
v. Go to STEP(ii)
Imagine searching a uniform tree where every state has b successors. The root of the
search tree generates b nodes at the first level, each of which generates b more nodes, for a
total of b2 at the second level. Each of these generates b more nodes, yielding b3 nodes at
the third level, and so on. Now suppose that the solution is at depth d. In the worst case, it
is the last node generated at that level. Then the total number of nodes generated is b +
b2 + b3 + · · · + b d = O(bd)
Advantages of BFS:
1. Used to find the shortest path between states.
2. Always finds optimal solutions.
3. There is nothing like useless path in BFS, since it searches level by level.
4. Finds the closest goal state in less time.
Disadvantages of BFS:
1. All the connected vertices must be stored in memory. So consumes more memory
11. Explain DFS algorithm with example mentioning time complexity
Depth-first search always expands the deepest node in the current frontier of the search
tree. The search proceeds immediately to the deepest level of the search tree, where the
nodes have no successors. As those nodes are expanded, they are dropped from the
frontier, so then the search “backs up” to the next deepest node that still has unexplored
successors.
• Depth-first search always expands the deepest node in the frontier first.
• Search proceeds immediately to the deepest level of the search tree, where the nodes
have no successors.
• The search then “backs up” to the next deepest node that still has unexpanded
successors.
• Depth-first search is not cost-optimal, it returns the first solution it finds, even if it is
not cheapest.
• It uses last in- first-out strategy and hence it is implemented using a STACK(LIFO).
Advantages: Depth-First Search uses a memory allocation proportional to the search
graph's size.
Disadvantages: Depth-First Search is not guaranteed to find the solution and there is no
guarantee to find a minimal solution, if more than one solution.
A variant of depth-first search called backtracking search uses even less memory.
In backtracking, only one successor is generated at a time rather than all successors each partially
expanded node remembers which successor to generate next.
we must be able to undo each action when we backtrack. Backtracking is critical to the success
of many problems with large state descriptions, such as robotic assembly
The time complexity of depth-first graph search is bounded by the size of the state space (which
may be infinite, of course). A depth-first tree search, on the other hand, may generate all of the
O(bm) nodes in the search tree, where m is the maximum depth of any node; this can be much
greater than the size of the state space. Note that m itself can be much larger than d (the depth of
the shallowest solution) and is infinite if the tree is unbounded.
ALGORITHM:
a. Enter ROOT node onto stack(PUSH)
b. Do UNTIL STACK is not empty
i. Remove node from the stack (POP)
ii. IF node=GOAL NODE , THEN STOP
iii. Push all children of node in stack
Bes for
ABC DS FG H TRLMN
AopL Bfs bee
cD
H.
ole
K
DEcGHLKI SA
B
A0pLy
favea
A
Drs
A
A
(8)
ASDGSCP