Artificial Intelligence (PEC-IT501B) Complete Question Bank

Ans: Artificial Intelligence (AI) is the branch of computer science that aims to create systems capable of performing tasks that normally require human intelligence — such as learning, reasoning, problem-solving, perception, and language understanding.

Ans: Main problems of AI include: (i) Search and reasoning — finding solutions in large search spaces, (ii) Knowledge representation — representing knowledge in a form a computer can use, (iii) Uncertainty — reasoning under incomplete information, (iv) Learning — improving from experience, (v) Natural language processing — understanding human language, (vi) Perception — interpreting sensory data.

Ans: An AI technique is a method that allows computers to handle incomplete, uncertain, or vague information efficiently. It enables the system to adapt to new situations, recognize patterns, and make decisions in real-time by representing knowledge in a structured form.

Ans: The Tic-Tac-Toe problem is a classic AI game-playing example where the game tree has at most 9! (362,880) possible paths. It demonstrates how algorithm with alpha-beta pruning can be used to search the game tree and find optimal moves.

Ans: An Intelligent Agent is a system that perceives its environment through sensors and acts upon that environment through actuators to achieve its goals. Formally: Agent = Architecture + Agent Program.

Ans: PEAS stands for Performance measure, Environment, Actuators, Sensors. It is a framework for describing an agent's task environment. Example: For a self-driving car — Performance: safety, speed; Environment: roads, traffic; Actuators: steering, brakes; Sensors: cameras, GPS.

Ans: Environment types: (i) Fully/Partially Observable, (ii) Single/Multi-agent, (iii) Deterministic/Stochastic, (iv) Episodic/Sequential, (v) Static/Dynamic, (vi) Discrete/Continuous.

Ans: An Agent Function maps percept histories to actions: $f: P^* \to A$. An Agent Program is the concrete implementation of that function that runs on the agent's physical architecture.

Ans: A Rational Agent is one that, for every possible percept sequence, selects an action that maximizes its expected performance measure, given the evidence from its percepts and any built-in knowledge.

Ans: A Goal-based Agent has explicit goals and selects actions based on whether they help achieve those goals. It uses search and reasoning to determine the best sequence of actions to reach a goal state.

Ans: A Utility-based Agent uses a utility function that maps each possible state to a real number representing how "happy" the agent would be in that state. It maximizes expected utility, allowing trade-offs between conflicting goals.

Ans: A Learning Agent has four components: (i) Learning Element — improves from feedback, (ii) Performance Element — takes actions, (iii) Critic — evaluates performance, (iv) Problem Generator — suggests exploratory actions.

Ans: Problem Space is the set of all possible states reachable from the initial state. Search is the process of exploring this space to find a path from the initial state to a goal state using a search strategy.

Ans: State Space Search defines a problem as a 5-tuple: $(S, A, s_0, T, G)$ where $S$ is the set of states, $A$ is the set of actions, $s_0$ is the initial state, $T$ is the transition model, and $G$ is the goal test.

Ans: A Production System consists of: (i) a set of production rules (IF condition THEN action), (ii) a knowledge base (current state), and (iii) a control strategy that determines which rule to apply next.

Ans: Key problem characteristics: (i) Decomposability — can the problem be broken into smaller subproblems, (ii) State Space — size of the search space, (iii) Solution Path — single or multiple, (iv) Knowledge — amount of knowledge available.

Ans: A Search Strategy determines the order in which nodes are expanded. It is evaluated by: Time Complexity (growth rate with branching factor $b$ and depth $d$), Space Complexity, Optimality (finds best solution), and Completeness (finds solution if one exists).

Ans: BFS expands nodes level by level from the root. It uses a FIFO (First-In-First-Out) queue. It is complete and optimal for unit-cost actions, with time and space complexity $O(b^d)$.

Ans: DFS expands the deepest node first, using a LIFO (Last-In-First-Out) stack. It has time complexity $O(b^m)$ and space complexity $O(bm)$ where $m$ is the maximum depth. It is not optimal and may not be complete.

Ans: A Heuristic Function $h(n)$ estimates the cost from node $n$ to the goal. It is admissible if $h(n) \leq h^*(n)$ (never overestimates) and consistent if $h(n) \leq c(n,a,n') + h(n')$.

Ans: Greedy Best-First Search expands the node that appears closest to the goal using the heuristic $f(n) = h(n)$. It is fast but neither optimal nor complete, and can get stuck in local minima.

Ans: A* Search uses $f(n) = g(n) + h(n)$ where $g(n)$ is the actual cost from start to $n$ and $h(n)$ is the heuristic estimate to goal. It is optimal and complete when $h(n)$ is admissible.

Ans: Hill Climbing is a local search that repeatedly moves to the neighbor with the best value. It stops at a local maximum, ridge, or plateau. Variants include: Simple Hill Climbing, Steepest-Ascent, and Stochastic Hill Climbing.

Ans: Simulated Annealing is a probabilistic technique inspired by metallurgy. It allows occasional "bad" moves (uphill) with probability $P = e^{-\Delta E/T}$ to escape local maxima, where $T$ is temperature that decreases over time.

Ans: A Genetic Algorithm is an evolutionary search technique. It maintains a population of candidate solutions and applies: Selection, Crossover, and Mutation operators over generations to evolve better solutions.

Ans: A CSP is defined by: (i) a set of variables $X = \{X_1, ..., X_n\}$, (ii) a set of domains $D = \{D_1, ..., D_n\}$, (iii) a set of constraints $C$. A solution is a complete assignment satisfying all constraints.

Ans: Alpha-Beta Pruning eliminates branches in the search tree that need not be searched. $\alpha$ is the best value for MAX, $\beta$ is the best value for MIN. Pruning occurs when $\alpha \geq \beta$.

Ans: Knowledge Representation is the field of AI devoted to representing knowledge about the world in a form that a computer system can utilize to solve complex tasks. It involves choosing the right symbols and structures to encode information.

Ans: Predicate Logic (First-Order Logic) extends propositional logic by allowing quantifiers ($\forall$, $\exists$), variables, and predicates. It can express relationships and make general statements, e.g., $\forall x (\text{Student}(x) \to \exists y (\text{Enrolled}(x,y)))$.

Ans: Resolution is a refutation proof procedure. To prove a theorem, the negation of the goal is added to the knowledge base and resolution is applied until a contradiction (empty clause $\Box$) is derived. It is a complete inference method.

Ans: AI techniques apply to problems that are:

1. Too complex for traditional algorithms — e.g., playing chess, face recognition
2. Involving uncertainty — e.g., medical diagnosis, weather prediction
3. Requiring pattern recognition — e.g., handwriting recognition, spam filtering
4. Requiring learning from data — e.g., recommendation systems, fraud detection
5. Involving natural language — e.g., chatbots, translation
6. Involving planning and scheduling — e.g., logistics, robotics

For instance, a medical diagnosis system must reason under uncertainty using probabilistic methods, while a self-driving car needs perception, planning, and real-time decision-making.

Ans: The Tic-Tac-Toe problem is a 3×3 grid game with $3^9 = 19,683$ possible states. It demonstrates:

• Game Tree: A tree of all possible game states
• Algorithm: Evaluates each move by assuming optimal play from both sides
• Evaluation Function: +1 for X win, -1 for O win, 0 for draw
• Alpha-Beta Pruning: Reduces effective branching factor from ~9 to ~3

The key insight is that with perfect play, Tic-Tac-Toe always ends in a draw — making it a solved game. It serves as a simple introduction to adversarial search concepts.

Ans: An Intelligent Agent perceives its environment via sensors and acts via actuators. PEAS (Performance, Environment, Actuators, Sensors) is used to specify the task environment.

1. Self-Driving Car:
   P: Safety, speed, comfort
   E: Roads, traffic, pedestrians
   A: Steering wheel, brakes, accelerator
   S: Cameras, GPS, lidar, radar
2. Medical Diagnosis Agent:
   P: Accuracy of diagnosis, patient outcome
   E: Hospital, patient records, lab results
   A: Treatment recommendation, alert
   S: Patient symptoms, lab reports, imaging
3. Spam Filter:
   P: Correct classification rate, false positive rate
   E: Email inbox, incoming messages
   A: Move to spam folder, deliver to inbox
   S: Email content, sender info, headers

Ans: The environment is everything the agent interacts with. Key properties:

• Fully Observable vs Partially Observable: Can the agent access the complete state? (Chess = fully, Self-driving car = partially)
• Single-agent vs Multi-agent: Is there competition or cooperation? (Crossword puzzle = single, Chess = multi)
• Deterministic vs Stochastic: Is the next state completely determined by current state and action? (Chess = deterministic, Dice game = stochastic)
• Episodic vs Sequential: Are actions in one episode independent of others? (Image classification = episodic, Chess = sequential)
• Static vs Dynamic: Does the environment change while the agent deliberates? (Chess = static, Taxi driving = dynamic)
• Discrete vs Continuous: Are the state/action/time spaces finite? (Chess = discrete, Robot navigation = continuous)

Ans: Agent types by structure:

1. Simple Reflex Agent: Maps percepts directly to actions using condition-action rules. Ignores history. Fast but limited.
2. Model-Based Reflex Agent: Maintains an internal state (model) of the world to handle partial observability.
3. Goal-Based Agent: Uses goals to evaluate possible action sequences, allowing flexible behavior.
4. Utility-Based Agent: Maximizes a utility function that measures desirability of states. Can handle conflicting goals.
5. Learning Agent: Improves performance over time through learning. Has components: Performance, Critic, Learning, Problem Generator.

Each type adds more capability but requires more computation. A learning utility-based agent is the most capable.

Ans: State Space Search represents a problem as a graph where:

• States = nodes (e.g., configurations of a puzzle)
• Actions = edges (e.g., valid moves)
• Initial State = starting node
• Goal Test = check if a state is a solution
• Path Cost = sum of step costs along the path

Example — 8-Puzzle: Initial state has tiles in random positions. Actions: slide tile into empty space. Goal state: tiles in order. The search explores the state graph to find a sequence of moves from initial to goal state.

Ans: A Production System has three components:

1. Set of Rules (Productions): Each rule is of the form: IF condition THEN action. Examples: "IF goal is to cook rice AND rice is available THEN set pot on stove"
2. Knowledge Base: The current state of the world represented as facts/rules
3. Control Strategy: Determines which rule fires next. Strategies include: rule ordering, specificity ordering, recency ordering, and conflict resolution

Production systems are widely used in expert systems and rule-based AI.

Ans: Breadth-First Search (BFS):

• Strategy: Expands nodes level by level using a FIFO queue
• Algorithm: Enqueue root; while queue not empty — dequeue, check goal, enqueue all unexpanded children
• Completeness: Yes (finite branching factor)
• Optimality: Yes (for unit step costs)
• Time: $O(b^d)$, Space: $O(b^d)$

Example: In the 8-puzzle, BFS would explore all states at depth 1, then depth 2, etc., finding the shortest path to the goal.

Ans: Depth-First Search (DFS):

• Strategy: Expands the deepest node first using LIFO stack
• Algorithm: Push root; while stack not empty — pop, check goal, push all unexpanded children
• Completeness: No — can loop infinitely in infinite paths
• Optimality: No — may find non-optimal solution
• Time: $O(b^m)$, Space: $O(bm)$

Problems: (1) Can go deep down infinite paths, (2) Not optimal, (3) May miss shallow solutions. Solution: Use Depth-Limited Search (DLS) with a depth cutoff.

Ans:

Depth-Limited Search (DLS): DFS with a depth limit $l$. It avoids infinite paths by cutting off at depth $l$. Completeness: only if $l \geq d$ (solution depth).

Iterative Deepening DFS (IDDFS): Runs DLS with increasing limits $l = 0, 1, 2, ...$ until goal found. Combines BFS completeness/optimality with DFS space efficiency.

Bidirectional Search: Runs two simultaneous searches — one forward from initial state, one backward from goal. They meet at a common state. Time complexity: $O(b^{d/2})$ vs $O(b^d)$ for unidirectional.

Ans: Greedy Best-First Search uses $f(n) = h(n)$ to expand the most promising node first. The heuristic estimates closeness to goal.

Example — Route Finding: $h(n)$ = straight-line distance from $n$ to Bucharest. The algorithm expands the city closest to Bucharest regardless of actual path cost.

Properties: Complete? No (can loop). Optimal? No (not necessarily shortest). Time: $O(b^m)$ worst case. Space: $O(b^m)$.

Ans: A* Search uses $f(n) = g(n) + h(n)$ where:

• $g(n)$ = actual cost from start to $n$
• $h(n)$ = estimated cost from $n$ to goal
• $h^*(n)$ = actual cost from $n$ to goal

Optimality Conditions:

• $h(n)$ is admissible: $h(n) \leq h^*(n)$ (never overestimates)
• $h(n)$ is consistent: $h(n) \leq c(n,a,n') + h(n')$

When $h(n)$ is admissible, A* is both complete and optimal. Example heuristic for 8-puzzle: Manhattan distance (number of misplaced tiles) is admissible.

Ans: Simplified Memory-bounded A* (SMA*) is a variant of A* that uses a fixed amount of memory. When memory is full, SMA* drops the worst leaf node and writes it to disk, but remembers the best $f$-value among the forgotten descendants. When needed, it regenerates the node. This allows it to be optimally efficient in terms of $f$-values given a memory constraint.

Ans: Hill Climbing is a greedy local search. It moves to the neighbor with the highest value.

Algorithm:

while True:
    neighbors = generate_neighbors(current)
    best_neighbor = max(neighbors, key=evaluate)
    if evaluate(best_neighbor) <= evaluate(current):
        return current  # local maximum
    current = best_neighbor

Problems: Local maxima, Ridges, Plateaux. Variants: Simple Hill Climbing, Steepest-Ascent Hill Climbing, Stochastic Hill Climbing.

Ans: Simulated Annealing combines hill climbing with random moves. It accepts "bad" moves with probability:

$$P = e^{-\Delta E/T}$$

where $\Delta E = E_{new} - E_{old}$ and $T$ is temperature that decreases slowly.

Algorithm: Start with high $T$. For each move: if good, accept; if bad, accept with probability $e^{-\Delta E/T}$. Decrease $T$ gradually. This allows escaping local maxima while converging to a global optimum.

Ans: Local Beam Search maintains $k$ best states instead of one. At each step, it generates all successors of all $k$ states and selects the $k$ best successors. This provides diversification — if one path leads to a dead end, others may find a solution. Stochastic Beam Search selects successors probabilistically based on evaluation.

Ans: A Genetic Algorithm mimics natural selection:

1. Initialization: Create random population of candidate solutions (chromosomes)
2. Selection: Choose fit individuals (roulette wheel, tournament, rank)
3. Crossover: Combine two parents to create offspring (single-point, two-point, uniform)
4. Mutation: Randomly flip bits with small probability to maintain diversity
5. Termination: Stop when fitness threshold or max generations reached

Example: For the 8-queens problem, each chromosome is an 8-element array. Fitness = number of non-attacking queen pairs.

Ans: A CSP involves assigning values to variables subject to constraints. Backtracking Search assigns values one variable at a time, backtracking when a constraint is violated.

Improvements:

• MRV (Minimum Remaining Values): Select the variable with fewest legal values
• Degree Heuristic: Select variable involved in most constraints
• LCV (Least Constraining Value): Try the value that rules out fewest choices for neighbors
• Forward Checking: Track remaining legal values for unassigned variables

Ans: Adversarial Search (Game Playing) involves two or more agents with conflicting goals. The algorithm is used for deterministic, zero-sum, perfect-information games.

:

• MAX (our player) maximizes the utility
• MIN (opponent) minimizes the utility
• Value of a MAX node = max of children
• Value of a MIN node = min of children

$$(n) = \begin{cases} UTILITY(n) & \text{if } n \text{ is terminal} \\ \max_a (Result(a)) & \text{if } n \text{ is MAX} \\ \min_a (Result(a)) & \text{if } n \text{ is MIN} \end{cases}$$

Ans: Alpha-Beta Pruning avoids exploring branches that cannot affect the final decision.

• $\alpha$ = best value MAX can guarantee
• $\beta$ = best value MIN can guarantee
• Prune when $\alpha \geq \beta$

Example: If at a MAX node, we find a child with value 7, then $\alpha = 7$. If a MIN child returns $\leq 7$, we can prune the remaining children because MIN would never allow MAX to get more than 7.

With perfect ordering, Alpha-Beta achieves effective branching factor $\sqrt{b}$, reducing complexity from $O(b^d)$ to $O(b^{d/2})$.

Ans: Iterative Deepening DFS (IDDFS) runs DFS with increasing depth limits: $l = 0, 1, 2, ...$ until a solution is found.

Advantages:

1. It is complete and optimal (for unit costs)
2. Uses only $O(bd)$ space (like DFS)
3. Nodes near the root are generated only once overall
4. Works well when good heuristic ordering is available
5. Early iterations detect dead ends quickly

Ans: Key issues in KR:

1. Representational Adequacy: Can the scheme represent all needed knowledge?
2. Inferential Adequacy: Can the system derive new knowledge from existing facts?
3. Inferential Efficiency: Can reasoning be done efficiently?
4. Acquisitional Efficiency: Can new knowledge be added easily?
5. Truth Maintenance: Can the system track and update beliefs as new information arrives?

Ans: Predicate Logic represents facts as predicates with arguments:

• Father(Ram, Shyam) — Ram is father of Shyam
• Brother(Arun, Raj) — Arun is brother of Raj
• $\forall x (\text{King}(x) \to \text{Person}(x))$ — All kings are persons
• $\exists x (\text{Loves}(\text{John}, x))$ — Someone is loved by John

This allows expressing relationships, inheritance (ISA), and logical implications.

Ans: Resolution proves theorems by refutation:

1. Convert all axioms to conjunctive normal form (CNF)
2. Negate the goal and add to the knowledge base
3. Apply resolution rule: From $P \lor Q$ and $\neg P$, derive $Q$
4. Repeat until contradiction ($\Box$) is derived

Example: From $\text{Animal}(F(x))$ and $\neg\text{Animal}(x) \lor \text{Loves}(x, \text{Curious})$ resolve to get $\text{Loves}(F(x), \text{Curious})$.

Ans: Natural Deduction uses inference rules to derive conclusions from premises. Key rules:

• Modus Ponens: From $P \to Q$ and $P$, infer $Q$
• Modus Tollens: From $P \to Q$ and $\neg Q$, infer $\neg P$
• Universal Instantiation: From $\forall x P(x)$, infer $P(a)$
• Existential Generalization: From $P(a)$, infer $\exists x P(x)$
• And-Introduction/Elimination, Or-Introduction/Elimination

It mirrors natural reasoning and is used in proof assistants.

Ans: Dempster-Shafer Theory handles uncertainty using:

• Basic Probability Assignment (BPA): $m: 2^{\Theta} \to [0,1]$ where $m(\emptyset) = 0$ and $\sum_{A \subseteq \Theta} m(A) = 1$
• Belief Function: $Bel(A) = \sum_{B \subseteq A} m(B)$
• Plausibility: $Pl(A) = \sum_{B \cap A \neq \emptyset} m(B) = 1 - Bel(\neg A)$
• Dempster's Rule: Combines evidence from independent sources

Unlike Bayesian probability, it can represent ignorance directly.

Ans: Fuzzy Sets extend classical sets by allowing degrees of membership $[0,1]$:

• A Crisp Set has binary membership: $x \in A$ or $x \notin A$
• A Fuzzy Set has membership function $\mu_A(x) \in [0,1]$

Example: "Tall" as a fuzzy set: $\mu_{Tall}(170\text{cm}) = 0.3$, $\mu_{Tall}(180\text{cm}) = 0.8$

Fuzzy Logic operations: $\mu_{A \cap B}(x) = \min(\mu_A(x), \mu_B(x))$, $\mu_{A \cup B}(x) = \max(\mu_A(x), \mu_B(x))$

Fuzzy Rules: IF temperature is HIGH AND humidity is HIGH THEN fan speed is FAST

Ans: NLP has several processing levels:

1. Morphological Analysis: Breaking words into morphemes (prefix, root, suffix)
2. Syntactic Processing (Parsing): Analyzing sentence structure using grammar rules to build parse trees
3. Semantic Analysis: Determining the meaning of sentences (word sense disambiguation)
4. Discourse Processing: Understanding context across sentences (anaphora resolution)
5. Pragmatic Processing: Understanding the intended meaning, speech acts, and implicature

Ans: Forms of Machine Learning:

1. Supervised Learning: Learn from labeled examples (classification, regression)
2. Unsupervised Learning: Find patterns in unlabeled data (clustering, dimensionality reduction)
3. Reinforcement Learning: Learn by trial-and-error with reward/punishment signals
4. Semi-supervised Learning: Mix of labeled and unlabeled data
5. Online Learning: Learn continuously from streaming data
6. Batch Learning: Learn from a fixed dataset

Ans: Inductive Learning generalizes from specific instances to general rules. Given examples, it finds a hypothesis that explains them.

Example: Given training examples: "Rose is red", "Lily is white", "Lotus is pink" and background knowledge about flowers, inductive learning might derive: "Flowers can be red, white, or pink."

The Candidate Elimination Algorithm finds the most specific (S) and most general (G) consistent hypotheses.

Ans: Decision Tree Learning builds a tree where internal nodes test attributes, branches represent outcomes, and leaves represent class labels.

Algorithm (ID3/C4.5):

1. Select the best attribute using Information Gain or Gain Ratio
2. Create a branch for each value of the attribute
3. Recursively build subtrees for each branch
4. Stop when all examples belong to one class

$$IG(A) = Entropy(S) - \sum_v \frac{|S_v|}{|S|} Entropy(S_v)$$

Ans: Explanation-Based Learning takes a single training example and domain theory, constructs an explanation proving the example's classification, and generalizes the explanation into a rule.

Steps:

1. Given training example and goal concept
2. Construct a proof using domain theory
3. Identify sufficient conditions for the proof
4. Generalize the example by removing specific constants

Example: From "This king can move one square in any direction", EBL generalizes to "All pieces that are kings can move one square in any direction."

Ans: Neural Networks learn by adjusting weights through backpropagation:

1. Forward Pass: Input propagates through layers to produce output
2. Error Calculation: Compare output with target using loss function
3. Backward Pass: Propagate error backward using gradient descent
4. Weight Update: $w_{ij} \leftarrow w_{ij} - \eta \frac{\partial E}{\partial w_{ij}}$

$$y = f(\sum_{i} w_i x_i + b)$$ where $f$ is the activation function (ReLU, sigmoid, tanh).

Ans: An Expert System consists of:

1. Knowledge Base: Domain-specific facts and rules
2. Inference Engine: Applies rules to deduce conclusions (forward/backward chaining)
3. Working Memory: Stores facts about the current problem
4. Explanation Facility: Justifies reasoning ("Why" and "How" questions)
5. Knowledge Acquisition Module: Learns from experts or data
6. User Interface: Interacts with the user

Ans: An Expert System Shell is an empty expert system without domain knowledge — it provides the inference engine, user interface, and explanation facilities. Knowledge engineers populate it with rules for a specific domain.

Examples: MYCIN shell (EMYCIN), OPS5, CLIPS.

Knowledge Acquisition is the process of extracting knowledge from human experts and encoding it into the system. Challenges include: expert inconsistency, tacit knowledge, and knowledge transfer bottleneck. Methods include: interviewing, observing, protocol analysis, and automated learning from data.

Ans:

Definition and Scope:

Artificial Intelligence is the science and engineering of making intelligent machines, especially computer programs. It aims to understand the principles of intelligence to build useful systems.

History of AI:

1. 1943-1955: McCulloch & Pitts' neuron model, Turing's "Computing Machinery and Intelligence" (1950), Turing Test
2. 1956: Dartmouth Conference — term "Artificial Intelligence" coined by John McCarthy
3. 1952-1969: Early optimism — Newell & Simon's Logic Theorist, Samuel's checkers program
4. 1966-1974: First AI winter — limits of early systems became apparent
5. 1980-1987: Expert systems boom — MYCIN, DENDRAL
6. 1987-1993: Second AI winter — LISP machines failed
7. 1997: Deep Blue beats Kasparov
8. 2011-present: Deep learning revolution — AlexNet, AlphaGo, GPT, Large Language Models

Problems of AI:

• Search and reasoning in large spaces
• Knowledge representation and reasoning
• Uncertainty and probabilistic reasoning
• Machine learning from data
• Natural language understanding
• Perception and computer vision
• Robotics and physical interaction

Modern Applications: Virtual assistants (Siri, Alexa), self-driving cars, recommendation systems (Netflix, Amazon), medical diagnosis, fraud detection, game playing (AlphaGo), content generation (LLMs).

Ans:

Agent = Architecture + Agent Program

An agent perceives its environment through sensors and acts through actuators. The agent function maps percept histories to actions.

PEAS Analysis:

• Performance measure
• Environment
• Actuators
• Sensors

Environment Types (6 properties):

1. Fully/Partially Observable
2. Single/Multi-agent
3. Deterministic/Stochastic
4. Episodic/Sequential
5. Static/Dynamic
6. Discrete/Continuous

Agent Types (by increasing capability):

1. Simple Reflex: Condition-action rules. Fast but ignores history.
2. Model-Based Reflex: Maintains internal state model for partial observability.
3. Goal-Based: Uses goals to guide actions, enabling flexible behavior.
4. Utility-Based: Maximizes expected utility for trade-offs.
5. Learning: Improves over time via the learning element.

Rational Agent: Maximizes expected performance measure given percept sequence and prior knowledge.

Ans:

Problem Formulation: Before solving, a problem must be defined by specifying states, actions, initial state, goal test, and path cost.

State Space Search: The problem is represented as a search space where states are nodes and actions are edges connecting them.

Well-Defined Problem:

• Initial State: Starting configuration
• Actions: Set of possible moves
• Transition Model: $Result(s, a)$ = state after action $a$ in state $s$
• Goal Test: Checks if a state is a solution
• Path Cost: Sum of step costs
• Solution: Action sequence from initial to goal

Production System: Comprises (i) production rules (IF-THEN), (ii) knowledge base, and (iii) control strategy.

Issues in Search Programs: Branching factor, solution depth, time/space complexity, optimality, and completeness.

Ans:

Property	BFS	DFS	DLS	Bidirectional
Complete	Yes	No	If $l \geq d$	Yes*
Optimal	Yes	No	If $l \geq d$	Yes
Time	$O(b^d)$	$O(b^m)$	$O(b^l)$	$O(b^{d/2})$
Space	$O(b^d)$	$O(bm)$	$O(bl)$	$O(b^{d/2})$

BFS: Explores level by level. Optimal for unit costs. Very memory-intensive.

DFS: Goes deep first. Memory efficient but non-optimal.

DLS: DFS with depth limit $l$. May miss solution if $l < d$.

IDDFS: Iterative DLS. Optimal and complete with DFS memory.

Bidirectional: Searches from both ends. Most efficient but requires defining reverse actions.

Ans:

Heuristic Search uses problem-specific knowledge to guide search toward the goal more efficiently than blind search.

Greedy Best-First Search: Uses $f(n) = h(n)$ to expand the node closest to the goal. Fast but not optimal or complete.

A* Search: Uses $f(n) = g(n) + h(n)$. When $h(n)$ is admissible, A* is both complete and optimal. The key insight is that $h(n)$ "cancels out" remaining cost, ensuring the first goal found is optimal.

$$f^*(n) = g^*(n) + h^*(n)$$

where $g^*$ is actual cheapest path cost and $h^*$ is actual cheapest remaining cost.

SMA* (Simplified Memory-Bounded A*): When memory is exhausted, SMA* drops the worst leaf and writes it to disk. It remembers the best $f$-value among forgotten descendants. SMA* is optimally efficient among memory- bounded algorithms.

Heuristic Quality: A good heuristic dramatically reduces the search space. The effective branching factor $b^*$ measures quality — lower $b^*$ means better heuristic.

Ans:

Local Search operates on a state-space graph, keeping only the current node in memory. It is useful for optimization problems with large state spaces.

1. Hill Climbing:

• Moves to the best neighbor greedily
• Problems: Local maxima, ridges, plateaux
• Variants: Simple, Steepest-Ascent, Stochastic

2. Simulated Annealing:

• Accepts bad moves with probability $e^{-\Delta E/T}$
• Temperature $T$ decreases over time
• Escapes local maxima while converging to global optimum

3. Local Beam Search:

• Maintains $k$ best states simultaneously
• Diversifies search and shares information

4. Genetic Algorithms:

• Maintains a population of chromosomes
• Selection: chooses fit individuals
• Crossover: combines two parents
• Mutation: random bit flip for diversity

$$P(\text{select } i) = \frac{f_i}{\sum_j f_j}$$

Comparison: Hill climbing is fastest but can get stuck. SA escapes local optima. GA explores diverse regions of the search space simultaneously.

Ans:

CSP Formulation:

• Variables: $X = \{X_1, X_2, ..., X_n\}$
• Domains: $D = \{D_1, D_2, ..., D_n\}$
• Constraints: $C = \{C_1, C_2, ..., C_m\}$ specifying allowable value combinations

Backtracking Search:

def backtrack(assignment):
    if len(assignment) == len(variables):
        return assignment
    var = select_unassigned_variable(assignment)
    for value in order_domain_values(var, assignment):
        if consistent(var, value, assignment):
            assignment[var] = value
            result = backtrack(assignment)
            if result: return result
            del assignment[var]
    return None

Constraint Propagation:

• Node Consistency: Every value in a variable's domain satisfies unary constraints
• Arc Consistency (AC-3): For each arc $(X_i, X_j)$, ensure every value of $X_i$ is consistent with some value of $X_j$

Heuristics: MRV (fewest remaining values), Degree Heuristic (most constrained variable), LCV (least constraining value).

Ans:

Game Types:

• Perfect Information: Chess, Checkers (both players see all pieces)
• Imperfect Information: Poker, Bridge (hidden information)
• Zero-Sum: One player's gain is the other's loss
• Non-zero-Sum: Both can benefit or suffer

Algorithm:

Each level alternates between MAX (maximizing) and MIN (minimizing) players. The value of a terminal node is its utility. The algorithm assumes both players play optimally.

$$(s) = \max_{a} \min_{a'} (Result(s, a'))$$

Alpha-Beta Pruning:

• $\alpha$ = best (highest) value MAX can currently guarantee
• $\beta$ = best (lowest) value MIN can currently guarantee
• Prune at MAX node if $\alpha \geq \beta$
• With good move ordering: $O(b^{d/2})$ complexity

Evaluation Functions: For non-terminal states, estimate the "goodness" of a position. For chess: material + positional factors.

Iterative Deepening: Repeatedly run with increasing depth. Allows time-limited search while maintaining best move found so far.

Ans:

Knowledge Representation (KR) is the study of how to encode knowledge for AI systems.

Issues in KR:

• Representational adequacy — can we express all needed knowledge?
• Inferential efficiency — can we reason efficiently?
• Acquisitional efficiency — can we easily add new knowledge?

Approaches to KR:

1. Logical Representation: Uses predicate logic. Precise, sound, complete but computationally expensive.
2. Semantic Networks: Graph with nodes (concepts) and edges (relationships). Intuitive but ambiguous.
3. Frames: Data structures with slots and fillers for stereotypical situations. Supports default reasoning.
4. Scripts: Sequences of events for common scenarios (restaurant script, etc.). Good for natural language understanding.
5. Production Rules: IF-THEN rules. Easy to add/modify but can become inefficient with many rules.

Mapping & Inference: KR must support reasoning — deduction, induction, and default reasoning. The choice of representation affects the efficiency of inference.

Ans:

Predicate Logic (First-Order Logic):

• Extends propositional logic with quantifiers ($\forall, \exists$)
• Represents objects, properties, and relationships
• Syntax: Terms (variables, constants, functions), Predicates, Connectives, Quantifiers

$$\forall x (\text{Student}(x) \to \exists y (\text{Enrolled}(x, y)))$$

Representing Instant & ISA Relationships:

• Instantiation: $\text{Circle}(\text{bigCircle})$ — a specific instance
• ISA (Is-A): $\forall x (\text{Circle}(x) \to \text{Shape}(x))$ — every circle is a shape
• Subsumption: More specific → more general

Resolution: A refutation-based proof method.

1. Convert all sentences to CNF
2. Negate the theorem
3. Apply resolution until contradiction

Natural Deduction: A system of inference rules (Modus Ponens, Modus Tollens, Generalization, etc.) that mirrors natural reasoning.

Ans:

Uncertainty in AI: Real-world knowledge is often uncertain, incomplete, or changing. Traditional logic fails — we need probabilistic methods.

Bayesian Networks:

• Directed acyclic graph (DAG) where nodes = random variables, edges = conditional dependencies
• Each node has a conditional probability table (CPT)
• $$P(X_1, X_2, ..., X_n) = \prod_{i=1}^n P(X_i | Parents(X_i))$$

Inference: Compute posterior probabilities given evidence. Can use enumeration or sampling.

Dempster-Shafer Theory: Handles ignorance and conflict using belief and plausibility functions.

Fuzzy Logic:

• Deals with degrees of truth rather than binary true/false
• Membership function $\mu_A(x) \in [0,1]$
• Rules: IF $x$ is $A$ AND $y$ is $B$ THEN $z$ is $C$
• Applications: control systems (fridge, AC), decision making

Ans:

NLP enables computers to understand, interpret, and generate human language.

Levels of Processing:

1. Morphological: Word structure analysis, stemming, lemmatization
2. Syntactic: Grammar analysis, POS tagging, parsing

   import nltk
   sentence = "The cat sat on the mat"
   tokens = nltk.word_tokenize(sentence)
   pos_tags = nltk.pos_tag(tokens)
   print(pos_tags)  # [('The', 'DT'), ('cat', 'NN'), ('sat', 'VBD'), ...]

3. Semantic: Word meaning, sense disambiguation, named entity recognition
4. Discourse: Sentence-level coherence, anaphora resolution ("John went home. He was tired.")
5. Pragmatic: Context, speaker intent, speech acts

Challenges: Ambiguity (lexical, syntactic, semantic), contextual understanding, sarcasm/irony, multilingual support.

Ans:

1. Inductive Learning:

• Generalizes from examples to rules
• Uses Candidate Elimination to find S and G boundaries

2. Decision Tree Learning (ID3/C4.5):

• Selects attribute with highest Information Gain at each node
• Handles noise with pruning

$$Entropy(S) = -\sum_{i=1}^c p_i \log_2 p_i$$

3. Explanation-Based Learning (EBL):

• Constructs explanation from domain theory
• Generalizes by replacing constants with variables
• Speed up learning with domain knowledge

4. Neural Network Learning:

• Multi-layer perceptron with backpropagation
• Loss function: $E = \frac{1}{2}\sum(y - \hat{y})^2$
• Weight update: $\Delta w = -\eta \frac{\partial E}{\partial w}$

import torch
import torch.nn as nn
model = nn.Sequential(
    nn.Linear(4, 8), nn.ReLU(),
    nn.Linear(8, 3), nn.Softmax(dim=1)
)
criterion = nn.CrossEntropyLoss()
optimizer = torch.optim.Adam(model.parameters())

5. Genetic Learning: Evolution-based optimization through selection, crossover, and mutation.

Ans:

Expert System Architecture:

┌──────────────┐     ┌──────────────┐
│ User Interface│←───→│ Explanation  │
│   (Dialog)   │     │  Facility    │
└──────┬───────┘     └──────────────┘
       │
┌──────▼──────────────────────────────────┐
│          Inference Engine              │
│  (Forward Chaining / Backward Chaining) │
└──────┬──────────────────────────────────┘
       │
┌──────▼──────────────────────────────────┐
│         Knowledge Base                  │
│  (IF condition THEN action rules)       │
└──────┬──────────────────────────────────┘
       │
┌──────▼──────────────────────────────────┐
│      Working Memory                     │
│  (Facts about current problem)          │
└─────────────────────────────────────────┘

Types of Expert Systems:

• Rule-based: MYCIN (medical diagnosis), XCON (DEC computer config)
• Case-based: CREEK (medical diagnosis)
• Model-based: Uses mathematical models

Expert System Shell: A framework (like EMYCIN) providing the inference engine and explanation facility without domain knowledge. Knowledge engineers build expert systems by adding rules to shells.

Knowledge Acquisition: The process of extracting knowledge from experts. Methods: structured interviews, think-aloud protocols, observing expert behavior, and automated knowledge extraction from data.

Advantages: Captures scarce expertise, provides consistent decisions, documents expertise, available 24/7. Limitations: Knowledge acquisition bottleneck, cannot explain "why", limited to narrow domains.

Ans:

Bayesian Networks (Bayes Nets / Probabilistic Graphical Models):

A Bayesian Network is a DAG where:

• Nodes represent random variables
• Edges represent conditional dependencies
• Each node has a Conditional Probability Table (CPT)

Joint Probability Distribution:

$$P(X_1, X_2, ..., X_n) = \prod_{i=1}^n P(X_i | Parents(X_i))$$

Construction Steps:

1. Identify relevant variables
2. Determine causal/dependency structure
3. Specify CPTs for each node
4. Verify network with data or expert

Inference Types:

• Causal: Top-down, from cause to effect
• Diagnostic: Bottom-up, from effect to cause
• Inter-causal: Explaining away effect

Example — Alarm Network:

Applications: Medical diagnosis, spam filtering, fault diagnosis, computer vision, robotics, decision support systems.