BE Computer Engineering (Pokhara University) Artificial Intelligence (PU, CMP 346) Question Paper 2079 Nepal

(a) Intelligent Agent and the PEAS Framework

An intelligent agent is anything that perceives its environment through sensors and acts upon that environment through actuators so as to maximize its expected performance measure. It is described by the mapping (agent function) from a percept sequence to an action.

To specify a task environment we use the PEAS framework:

• P – Performance measure: the criterion that defines success of the agent's behaviour.
• E – Environment: the surroundings in which the agent operates.
• A – Actuators: the components through which the agent acts on the environment.
• S – Sensors: the components through which the agent perceives the environment.

PEAS for an Automated Taxi-Driving Agent

(b) Classification of Task Environments

Most real-world environments (e.g. taxi driving) are partially observable, stochastic, sequential, dynamic and continuous, which makes them the hardest type.

(a) A* Search Algorithm

A* is a best-first informed search that selects for expansion the node with the lowest evaluation function:

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

where:

• $g(n)$ = actual cost of the path from the start node to $n$,
• $h(n)$ = heuristic estimate of the cheapest cost from $n$ to the goal,
• $f(n)$ = estimated cost of the cheapest solution path through $n$.

A* maintains an OPEN list (frontier, a priority queue ordered by $f$) and a CLOSED list. It repeatedly removes the node with minimum $f$, generates its successors and stops when the goal is removed from OPEN.

Admissibility and Consistency

• Admissible heuristic: $h(n) \le h^*(n)$ for every node $n$, where $h^*(n)$ is the true cheapest cost to the goal. An admissible heuristic never overestimates.
• Consistent (monotonic) heuristic: for every node $n$ and successor $n'$ reached by action of cost $c(n,n')$, $h(n) \le c(n,n') + h(n')$ and $h(goal)=0$. Consistency implies admissibility.

Proof of Optimality (Tree Search, Admissible h)

Let the optimal goal be $G$ with cost $C^* = f(G) = g(G)$ (since $h(G)=0$). Suppose a suboptimal goal $G_2$ with $g(G_2) > C^*$ is on the frontier. Let $n$ be a node on the optimal path to $G$ that is still on the frontier. Then:

$$f(n) = g(n) + h(n) \le g(n) + h^*(n) = C^*$$

(by admissibility)

$$f(G_2) = g(G_2) + h(G_2) = g(G_2) > C^* \ge f(n)$$

Since $f(n) \le C^* < f(G_2)$, A* will expand $n$ (and continue along the optimal path) before it ever selects $G_2$. Hence the suboptimal $G_2$ is never returned, so A* is optimal. $\blacksquare$

(b) Tracing A* from S to G

Given heuristics $h(S)=6, h(A)=4, h(B)=2, h(C)=2, h(G)=0$.

Step 1 — Expand S ($g=0$). Successors:

• A: $g=1, f=1+4=5$
• B: $g=4, f=4+2=6$

OPEN: {A=5, B=6}. Expand A (lowest f).

Step 2 — Expand A ($g=1$). Successor:

• C via A: $g=1+2=3, f=3+2=5$

OPEN: {C=5, B=6}. Expand C.

Step 3 — Expand C ($g=3$). Successor:

• G via C: $g=3+3=6, f=6+0=6$

(Note: B-C would give $g=4+1=5$ to C, but C already reached with $g=3$, which is cheaper, so it is not improved.)

OPEN: {G=6, B=6}. Expand G (goal reached; tie broken by goal).

Result

• Order of expansion: S → A → C → G
• Final path: S → A → C → G
• Total cost: $1 + 2 + 3 = 6$

(a) Resolution Refutation

Resolution refutation is a sound and complete inference procedure that proves a goal $\alpha$ from a knowledge base $KB$ by showing that $KB \wedge \neg\alpha$ is unsatisfiable. The single inference rule, resolution, takes two clauses containing complementary literals and produces a new clause (the resolvent) by removing the complementary pair:

$$\frac{(A \vee \ell), \quad (B \vee \neg\ell)}{(A \vee B)}$$

If repeated resolution derives the empty clause ($\square$, a contradiction), then $KB \models \alpha$.

Steps to Convert an FOL Sentence to CNF

1. Eliminate implications/biconditionals: replace $P \Rightarrow Q$ by $\neg P \vee Q$.
2. Move negation inwards (De Morgan's laws), converting to Negation Normal Form: $\neg \forall x\,P \equiv \exists x\,\neg P$, etc.
3. Standardize variables apart so each quantifier uses a unique variable.
4. Skolemize: remove existential quantifiers by introducing Skolem constants/functions.
5. Drop universal quantifiers (all remaining variables are implicitly universally quantified).
6. Distribute $\vee$ over $\wedge$ to obtain a conjunction of clauses.
7. Separate into clauses (the set of disjunctions).

(b) Proving "Tommy breathes"

FOL Representation

• All dogs are animals: $\forall x\,(Dog(x) \Rightarrow Animal(x))$
• All animals breathe: $\forall x\,(Animal(x) \Rightarrow Breathe(x))$
• Tommy is a dog: $Dog(Tommy)$
• Goal: $Breathe(Tommy)$

Clausal Form (CNF)

1. $\neg Dog(x) \vee Animal(x)$
2. $\neg Animal(y) \vee Breathe(y)$
3. $Dog(Tommy)$
4. Negated goal: $\neg Breathe(Tommy)$

Resolution

The empty clause is derived, so $KB \wedge \neg Breathe(Tommy)$ is unsatisfiable. Therefore "Tommy breathes" is proved. $\blacksquare$

(a) Single Artificial Neuron (Perceptron)

Structure (described): Inputs $x_1, x_2, \dots, x_n$ each enter through a weighted connection $w_1, w_2, \dots, w_n$. A bias $b$ is added. A summation unit computes the net input, which is passed through an activation function to produce the output $y$.

$$net = \sum_{i=1}^{n} w_i x_i + b, \qquad y = \varphi(net)$$

 x1 --w1--\
 x2 --w2---> ( Σ + b ) --> [ φ ] --> y
 xn --wn--/

Roles:

• Weights ($w_i$): strength/importance of each input; learned during training.
• Bias ($b$): shifts the activation threshold, allowing the neuron to fire independently of the inputs.
• Summation: computes the weighted sum (net input) $\sum w_i x_i + b$.
• Activation function ($\varphi$): introduces non-linearity and maps the net input to the output.

Comparison of Activation Functions

(b) Backpropagation Algorithm

Backpropagation trains a multilayer feed-forward network by gradient descent on the error, propagating the error backward from output to input layer:

1. Initialize weights and biases randomly.
2. Forward pass: present an input, compute activations layer by layer up to the output, obtaining predicted output $\hat{y}$.
3. Compute error at the output, e.g. $E = \frac{1}{2}\sum (t - \hat{y})^2$.
4. Backward pass: compute the error gradient with respect to each weight using the chain rule, propagating the delta ($\delta$) terms from the output layer back through the hidden layers.
5. Update weights: $w \leftarrow w - \eta \dfrac{\partial E}{\partial w}$, where $\eta$ is the learning rate.
6. Repeat over all training examples/epochs until the error converges.

Why a Non-linear, Differentiable Activation is Required

• Differentiable: backpropagation needs the derivative $\frac{\partial E}{\partial w}$ via the chain rule; a non-differentiable function (like the step) has no usable gradient.
• Non-linear: without non-linearity, a stack of layers collapses to a single linear transformation, so the network could not learn complex, non-linearly-separable patterns.

BFS vs. DFS

Let $b$ = branching factor, $d$ = depth of the shallowest goal, $m$ = maximum depth of the search tree.

Situation where DFS is preferred: When the search tree is very deep (or memory is limited) and solutions are dense/located deep in the tree — DFS uses far less memory ($O(bm)$ vs. $O(b^d)$), making it suitable for large state spaces where BFS would exhaust memory.

Expert System

An expert system is an AI program that uses a knowledge base of human expertise and an inference mechanism to solve problems in a specific domain at the level of a human expert (e.g. MYCIN for medical diagnosis).

Architecture of a Rule-Based Expert System (described)

  User <--> [User Interface] <--> [Inference Engine] <--> [Knowledge Base]
                                         |                      ^
                                  [Working Memory]      [Knowledge Acquisition]

Components:

• Knowledge Base: stores domain knowledge as facts and IF–THEN production rules supplied by domain experts.
• Inference Engine: the reasoning component that applies the rules to the known facts (using forward or backward chaining) to derive new facts and conclusions.
• User Interface: allows the user to enter queries/facts and presents the system's conclusions and explanations in an understandable form.

Forward vs. Backward Chaining

Semantic Networks and Frames

Semantic Network: A graphical knowledge representation where nodes represent objects/concepts and labelled directed arcs (edges) represent the relationships between them. Common relations are IS-A (class membership/inheritance) and HAS-A (property/part). Inheritance lets subclasses acquire the properties of their superclasses.

Frames: A frame is a structured record-like representation of a stereotyped object or situation. Each frame has slots (attributes) and fillers (slot values), which may include default values, constraints, and procedural attachments (if-needed/if-added demons). Frames support inheritance through is-a links and are convenient for representing structured, object-oriented knowledge.

Semantic Network for "A penguin is a bird that cannot fly but can swim"

   Animal
     ^ is-a
   Bird ---- can ----> Fly   (general default for birds)
     ^ is-a
  Penguin -- cannot --> Fly
          -- can ----> Swim

Description of the network:

• Penguin --IS-A--> Bird --IS-A--> Animal (inheritance hierarchy).
• Bird --can--> Fly (default property of birds).
• Penguin --cannot--> Fly (an exception that overrides the inherited default).
• Penguin --can--> Swim (specific property of penguins).

This demonstrates default reasoning with exceptions: a penguin inherits being a bird/animal but overrides the "can fly" default.

Types of Machine Learning

Overfitting

Overfitting occurs when a model learns the training data too well — including its noise and random fluctuations — so it has very low training error but performs poorly on unseen test data (poor generalization). It usually arises from an overly complex model relative to the amount of data.

Ways to Reduce Overfitting

• More training data / data augmentation.
• Regularization (L1/L2 penalty), or dropout in neural networks.
• Cross-validation for model/hyperparameter selection.
• Simplify the model (fewer parameters/features); pruning decision trees.
• Early stopping during training.

Hill-Climbing Search

Hill climbing is a local search / optimization technique that starts from an arbitrary solution and iteratively moves to a neighbouring state that has a better value of the objective (heuristic) function, until no neighbour is better. It is like climbing uphill always choosing the steepest ascent, keeping no record of past states (greedy, memory-efficient).

loop:
  neighbor = highest-valued successor of current
  if value(neighbor) <= value(current): return current
  current = neighbor

Problems and Remedies

These problems mean simple hill climbing is incomplete and non-optimal; stochastic variants and simulated annealing alleviate them.

Stages of Natural Language Processing

1. Morphological / Lexical Analysis: Breaks text into tokens (words) and analyzes word structure — roots, prefixes, suffixes, parts of speech. e.g. "unhappiness" → un + happy + ness.
2. Syntactic Analysis (Parsing): Checks the grammatical structure of a sentence and builds a parse tree according to grammar rules; rejects sentences that are not grammatically valid (e.g. "boy the school to went").
3. Semantic Analysis: Determines the literal meaning of the sentence by mapping syntactic structures to meaning representations and checking that the combination of words makes sense (e.g. rejecting "colourless green ideas" as meaningless).
4. Pragmatic Analysis: Interprets the sentence in its real-world context, handling intentions, references and implied meaning (e.g. understanding "Can you pass the salt?" as a request, not a yes/no question).

(Discourse integration is sometimes listed between semantic and pragmatic stages to handle inter-sentence context/references.)

Why Ambiguity is a Central Challenge

Natural language is inherently ambiguous at every level — lexical (a word with multiple meanings, e.g. "bank"), syntactic (multiple parse trees, e.g. "I saw the man with the telescope"), semantic, and pragmatic/referential. A single sentence can therefore have many valid interpretations, and the correct one depends on context and world knowledge that is hard to encode. Resolving this ambiguity to pick the intended meaning is the core difficulty in NLP.

Rules of Inference

1. Modus Ponens (affirming the antecedent):

$$\frac{P \Rightarrow Q,\quad P}{Q}$$

If $P \Rightarrow Q$ is true and $P$ is true, then $Q$ is true.

2. Modus Tollens (denying the consequent):

$$\frac{P \Rightarrow Q,\quad \neg Q}{\neg P}$$

If $P \Rightarrow Q$ is true and $Q$ is false, then $P$ is false.

3. Universal Instantiation:

$$\frac{\forall x\, P(x)}{P(a)}$$

From a universally quantified statement, we may infer the statement for any specific instance/constant $a$ in the domain.

Demonstrations

Modus Ponens:

• $P$: "It is raining." $Q$: "The ground is wet."
• Premise 1: If it is raining, then the ground is wet ($P \Rightarrow Q$).
• Premise 2: It is raining ($P$).
• Conclusion: The ground is wet ($Q$). ✓

Modus Tollens:

• Same rule: If it is raining, then the ground is wet ($P \Rightarrow Q$).
• Premise 2: The ground is not wet ($\neg Q$).
• Conclusion: It is not raining ($\neg P$). ✓

Short Notes (any two)

(a) Turing Test

Proposed by Alan Turing (1950) as an operational test of machine intelligence (the "Imitation Game"). A human interrogator converses, via text, with two hidden parties — one human and one machine. If the interrogator cannot reliably distinguish the machine from the human, the machine is said to exhibit intelligent behaviour. It tests behavioural indistinguishability (NLP, knowledge, reasoning, learning) rather than internal mechanism.

(b) Means-Ends Analysis (MEA)

A problem-solving technique that combines forward and backward reasoning. It repeatedly: (1) compares the current state with the goal state to find the most significant difference, (2) selects an operator relevant to reducing that difference, and (3) applies it, recursively solving any sub-problem if the operator's preconditions are not met. Used in the GPS (General Problem Solver); effective for goal-directed planning.

(c) Adversarial Search and the Minimax Algorithm

Used for two-player, zero-sum games (e.g. chess, tic-tac-toe). One player (MAX) tries to maximize the score while the opponent (MIN) tries to minimize it. Minimax explores the game tree to a depth, evaluating terminal/leaf nodes, then backs values up: MAX nodes take the maximum of their children, MIN nodes take the minimum. The move leading to the best guaranteed value is chosen. Alpha-beta pruning improves efficiency by cutting off branches that cannot affect the result.

(d) Fuzzy Logic

An extension of classical (Boolean) logic that allows degrees of truth between 0 and 1 rather than strict true/false. Variables belong to fuzzy sets with membership functions (e.g. "tall" might have membership 0.8). It uses linguistic rules (IF temperature is high THEN fan is fast) and processes them via fuzzification, inference, and defuzzification. Widely used in control systems (washing machines, air conditioners) where reasoning under vagueness is needed.