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

(a) Rational Agent and the PEAS Framework (6 marks)

A rational agent is an agent that, for each possible percept sequence, selects an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has. Rationality is not omniscience; it depends on the performance measure, the agent's prior knowledge, the available actions, and the percept sequence to date.

To design a rational agent we must first specify the task environment completely. This is done using the PEAS description:

• P — Performance measure: the criterion that defines success (e.g., for a taxi: safe, fast, legal, comfortable trip, maximize profit).
• E — Environment: the world in which the agent operates (e.g., roads, traffic, pedestrians, weather).
• A — Actuators: the components through which the agent acts on the environment (e.g., steering, accelerator, brake, horn, display).
• S — Sensors: the components through which the agent perceives the environment (e.g., cameras, GPS, speedometer, sonar).

Fully specifying PEAS lets us judge whether the agent behaves rationally.

(b) PEAS for an Autonomous Vacuum-Cleaning Robot (4 marks)

(c) Classifying the Task Environment (4 marks)

• Partially observable: The robot's sensors detect only the current cell (dirt + location); it cannot perceive the dirt status of the other room at once. Hence the environment is partially observable.
• Stochastic (in practice): If actions always succeed deterministically (clean removes dirt, move always reaches the target), it is deterministic; but with wheel slip, sensor noise, or unpredictable re-appearing dirt, it is stochastic. A real robot is best modelled as stochastic.
• Sequential: The current decision (which cell to clean/where to move) affects future states and future cleaning, so it is sequential, not episodic.
• Single-agent: Only one robot acts; there is no other agent whose behaviour the robot must reason about, so it is single-agent.

(Additionally it is static during deliberation, discrete if cells/actions are finite, and known if the robot knows the effects of its actions.)

(a) Uninformed vs Informed (Heuristic) Search (4 marks)

(b) A* Evaluation Function and Heuristic Properties (6 marks)

A* evaluates each node $n$ by:

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

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

A* always expands the frontier node with the lowest $f(n)$.

Admissible heuristic: $h(n)$ never overestimates the true cost $h^*(n)$ of reaching the goal from $n$, i.e.

$$0 \le h(n) \le h^*(n) \quad \text{for every } n.$$

An admissible heuristic is optimistic. (e.g., straight-line distance for road navigation.)

Consistent (monotonic) heuristic: For every node $n$ and every successor $n'$ reached by action with step cost $c(n,a,n')$,

$$h(n) \le c(n,a,n') + h(n').$$

This is a form of the triangle inequality. Consistency implies admissibility and guarantees that $f$ is non-decreasing along any path, so A* graph search is optimal without re-expanding nodes.

(c) Proof that A* Tree Search is Optimal with an Admissible Heuristic (6 marks)

Claim: If $h(n)$ is admissible, A* tree search returns an optimal solution.

Proof (by contradiction):

Let $C^*$ be the cost of the optimal solution. Suppose A* terminates by selecting a sub-optimal goal node $G_2$ with cost

$$g(G_2) > C^*.$$

Since $G_2$ is a goal, $h(G_2) = 0$, therefore

$$f(G_2) = g(G_2) + h(G_2) = g(G_2) > C^*. \quad (1)$$

Now consider the optimal solution path. At the moment $G_2$ is chosen for expansion, there must exist some node $n$ on the frontier that lies on an optimal path to the optimal goal (because the optimal path starts at the root and the root's descendants are on the frontier until expanded). For this node $n$:

Because $h$ is admissible, $h(n) \le h^*(n)$, so

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

(Here $g(n) + h^*(n) = C^*$ since $n$ is on an optimal path.)

A* always expands the frontier node with the lowest $f$ value. Since it selected $G_2$ instead of $n$, we must have

$$f(G_2) \le f(n). \quad (3)$$

Combining (1), (2) and (3):

$$C^* < f(G_2) \le f(n) \le C^*,$$

which gives $C^* < C^*$ — a contradiction.

Therefore A* can never select a sub-optimal goal for expansion before an optimal one, i.e. A* tree search is optimal when $h$ is admissible. $\blacksquare$

(a) Resolution Rule and Conversion to CNF (6 marks)

Resolution inference rule (propositional): Given two clauses, one containing a literal $P$ and the other its negation $\lnot P$, resolution produces a new clause (the resolvent) consisting of all the remaining literals of both clauses:

$$\frac{(A_1 \lor \dots \lor P), \quad (\lnot P \lor B_1 \lor \dots)}{(A_1 \lor \dots \lor B_1 \lor \dots)}$$

Resolution is sound and refutation-complete: to prove $KB \models Q$, we add $\lnot Q$ to the KB and derive the empty clause (a contradiction, $\square$).

Steps to convert a sentence to CNF (a conjunction of disjunctions of literals):

1. Eliminate biconditionals: replace $A \Leftrightarrow B$ with $(A \Rightarrow B) \land (B \Rightarrow A)$.
2. Eliminate implications: replace $A \Rightarrow B$ with $\lnot A \lor B$.
3. Move negations inward using De Morgan's laws and double-negation, so $\lnot$ applies only to literals: $\lnot(A \lor B) \equiv \lnot A \land \lnot B$, $\lnot(A \land B) \equiv \lnot A \lor \lnot B$, $\lnot\lnot A \equiv A$.
4. Distribute $\lor$ over $\land$: apply $A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$ until the sentence is a conjunction of clauses.

(b) Resolution Refutation Proof that the KB entails Q (8 marks)

Step 1 — Convert each sentence to clauses (CNF). Using $A \Rightarrow B \equiv \lnot A \lor B$:

Step 2 — Negate the goal $Q$ and add it: clause 8 = $\lnot Q$.

Step 3 — Apply resolution to derive the empty clause:

1. Resolve 5 $(\lnot A \lor \lnot B \lor L)$ with 6 $(A)$ $\Rightarrow$ 9: $\lnot B \lor L$.
2. Resolve 9 $(\lnot B \lor L)$ with 7 $(B)$ $\Rightarrow$ 10: $L$.
3. Resolve 3 $(\lnot B \lor \lnot L \lor M)$ with 7 $(B)$ $\Rightarrow$ 11: $\lnot L \lor M$.
4. Resolve 11 $(\lnot L \lor M)$ with 10 $(L)$ $\Rightarrow$ 12: $M$.
5. Resolve 2 $(\lnot L \lor \lnot M \lor P)$ with 10 $(L)$ $\Rightarrow$ 13: $\lnot M \lor P$.
6. Resolve 13 $(\lnot M \lor P)$ with 12 $(M)$ $\Rightarrow$ 14: $P$.
7. Resolve 1 $(\lnot P \lor Q)$ with 14 $(P)$ $\Rightarrow$ 15: $Q$.
8. Resolve 15 $(Q)$ with 8 $(\lnot Q)$ $\Rightarrow$ $\square$ (the empty clause).

The empty clause is derived, so the assumption $\lnot Q$ leads to a contradiction. Therefore $KB \models Q$. $\blacksquare$

(Note: clause 4 is not needed; the proof goes through using clauses 5, 6, 7, 3, 2, 1.)

(a) Architecture of a Single Artificial Neuron / Perceptron (5 marks)

A single neuron takes several inputs, computes a weighted sum plus a bias, and passes the result through an activation function to produce one output.

Diagram (described): Inputs $x_1, x_2, \dots, x_n$ each enter the neuron along an edge carrying a weight $w_1, w_2, \dots, w_n$. Inside the neuron a summing junction computes the net input, a constant bias $b$ is added, and the sum is fed to an activation function block whose single output line gives $y$.

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

Roles:

• Weights ($w_i$): scale the importance/strength of each input; a large positive weight makes that input excitatory, a negative weight inhibitory. They are the learnable parameters adjusted during training.
• Bias ($b$): an extra learnable constant that shifts the activation threshold, allowing the neuron to fire even when all inputs are zero; it lets the decision boundary be offset from the origin.
• Activation function ($\varphi$): introduces non-linearity so the network can model complex functions; common choices are the step function (perceptron), sigmoid $\sigma(z)=\frac{1}{1+e^{-z}}$, tanh, and ReLU $\max(0,z)$.

(b) The Backpropagation Algorithm (7 marks)

Backpropagation trains a multilayer feedforward network by gradient descent, propagating the output error backwards to update every weight. It has three phases per training example (or batch):

1. Forward pass. Present the input vector and compute, layer by layer, the activation of every neuron until the output layer produces $\hat{y}$:

$$a_j^{(l)} = \varphi\!\left( \sum_i w_{ji}^{(l)} a_i^{(l-1)} + b_j^{(l)} \right).$$

2. Error computation. Compare the network output $\hat{y}$ with the target $t$ using a loss function, e.g. mean-squared error:

$$E = \tfrac{1}{2}\sum_k (t_k - \hat{y}_k)^2.$$

Compute the error term (delta) for each output neuron:

$$\delta_k = (t_k - \hat{y}_k)\,\varphi'(\text{net}_k),$$

then propagate deltas backwards to each hidden neuron $j$:

$$\delta_j = \varphi'(\text{net}_j)\sum_k \delta_k\, w_{kj}.$$

3. Weight-update phase. Using gradient descent with learning rate $\eta$, adjust every weight (and bias) in the direction that reduces the error:

$$w_{ji} \leftarrow w_{ji} + \eta\,\delta_j\, a_i, \qquad b_j \leftarrow b_j + \eta\,\delta_j.$$

These three phases are repeated over all training examples for many epochs until the error falls below a threshold or stops improving. The key idea is the chain rule, which lets the gradient $\partial E/\partial w$ be computed efficiently by reusing the deltas from the layer above.

Comparison of BFS and DFS (let $b$ = branching factor, $d$ = depth of shallowest goal, $m$ = maximum depth of the tree):

When preferred:

• BFS is preferred when the solution is shallow and we need the shortest (fewest-step) path, and memory is not a constraint.
• DFS is preferred when memory is limited or solutions are deep in the tree, where exploring one branch fully uses far less space.

Knowledge Representation (KR) is the area of AI concerned with how to encode knowledge about the world in a form that a computer can use to solve complex tasks and perform reasoning/inference. A good KR scheme should be representationally adequate, inferentially efficient, easy to acquire, and clear.

Semantic Networks A semantic network represents knowledge as a graph of nodes (concepts/objects) connected by labelled arcs (relationships), typically is-a (class membership/inheritance) and has-part links. Example: Dog —is-a→ Mammal —is-a→ Animal.

• Advantage: Intuitive, visual, and supports inheritance of properties down the is-a hierarchy, reducing redundancy.
• Limitation: Lacks standard semantics for quantifiers and negation; meaning of links can be ambiguous and reasoning is not always sound.

Frames A frame is a record-like data structure representing a stereotyped object or situation as a collection of slots (attributes) and fillers (values), where fillers may be defaults, constraints, or procedures (demons/procedural attachments). Frames are organized in hierarchies with inheritance.

• Advantage: Organizes related knowledge together, supports default values and inheritance, making it natural and efficient for structured/stereotypical knowledge.
• Limitation: Inflexible/rigid for knowledge that does not fit a fixed slot structure, and handling exceptions and reasoning can be cumbersome.

Architecture of an Expert System

An expert system mimics a human expert's decision-making in a narrow domain. Its main components (diagram described):

   User
    |  (queries / answers)
[User Interface]
    |
[Inference Engine] <----> [Knowledge Base (rules + facts)]
    |                              ^
[Explanation Facility]   [Knowledge Acquisition Module]
[Working Memory]                  ^
                          Domain Expert / Knowledge Engineer

• Knowledge Base: stores domain knowledge as facts and IF–THEN production rules.
• Inference Engine: the reasoning component that applies rules to the facts to derive conclusions.
• Working Memory: holds the current facts/intermediate results of a session.
• User Interface: lets the user enter queries and receive advice.
• Explanation Facility: explains how a conclusion was reached and why a question is asked.
• Knowledge Acquisition Module: lets experts/engineers add or update knowledge.

Forward Chaining vs Backward Chaining

Forward chaining matches rule antecedents against facts and fires rules to add consequents; backward chaining takes the goal as a rule consequent and recursively tries to establish its antecedents as sub-goals.

Representation in First-Order Predicate Logic:

(a) Every student who studies passes the exam.

$$\forall x\, \big[ \big(\text{Student}(x) \land \text{Studies}(x)\big) \Rightarrow \text{Passes}(x, \text{Exam}) \big]$$

(b) Some birds cannot fly.

$$\exists x\, \big[ \text{Bird}(x) \land \lnot \text{Fly}(x) \big]$$

(c) All cats are animals.

$$\forall x\, \big[ \text{Cat}(x) \Rightarrow \text{Animal}(x) \big]$$

(d) John loves everyone who loves Mary.

$$\forall x\, \big[ \text{Loves}(x, \text{Mary}) \Rightarrow \text{Loves}(\text{John}, x) \big]$$

Note on the patterns: universal statements ('every/all') use $\forall$ with an implication ($\Rightarrow$); existential statements ('some') use $\exists$ with a conjunction ($\land$).

Hill-Climbing Search

Hill-climbing is a local search (greedy) algorithm. It keeps only the current state and repeatedly moves to the neighbouring state that has the best (highest) value of the objective/heuristic function, stopping when no neighbour is better (a peak).

current <- initial state
loop:
    neighbour <- highest-valued successor of current
    if VALUE(neighbour) <= VALUE(current):
        return current        // local optimum reached
    current <- neighbour

It is fast and memory-cheap but can get stuck because it never looks beyond the immediate neighbours.

Problems and Remedies

A general technique that escapes all three is simulated annealing, which occasionally accepts worse moves with a probability that decreases over time.

Key differences: supervised learning needs labelled data and predicts known outputs; unsupervised learning needs no labels and discovers groupings; reinforcement learning has no fixed dataset—it learns an optimal policy from delayed reward feedback.

Natural Language Processing (NLP) is a branch of AI that enables computers to understand, interpret, generate and manipulate human (natural) language — text or speech. It combines computational linguistics with machine learning. Applications include machine translation, chatbots, sentiment analysis, and information extraction.

Phases of NLP

1. Lexical (morphological) analysis: Breaks text into basic units — tokens/words — and analyses word structure (stems, prefixes, suffixes). It identifies the parts of words. Example: splitting a sentence into words and identifying that 'running' = 'run' + 'ing'.
2. Syntactic analysis (parsing): Checks that words are arranged according to grammar rules and builds a parse tree showing grammatical structure. Example: rejecting 'school the goes boy' as ungrammatical.
3. Semantic analysis: Derives the meaning of the sentence from the meanings of words and their arrangement; resolves word-sense ambiguity. Example: understanding 'hot dog' as a food, not a warm animal.
4. Discourse analysis: Interprets meaning across multiple sentences, handling references such as pronouns. Example: resolving 'it' or 'he' to the entity mentioned in a previous sentence.
5. Pragmatic analysis: Interprets language using real-world knowledge and context/intent to derive the actual intended meaning. Example: understanding 'Can you pass the salt?' as a request, not a question about ability.

(Answer any TWO — all four given for reference.)

(a) Simple Reflex Agent Selects actions based only on the current percept, ignoring percept history. It works on condition–action (IF–THEN) rules, e.g. if dirty then suck. Simple and fast, but works correctly only in fully observable environments and fails when the right action depends on unseen state.

(b) Model-Based Reflex Agent Maintains an internal state (a model of the world) that tracks the part of the environment it cannot currently see, updated using percept history and knowledge of how the world evolves and how its actions affect the world. It can therefore act sensibly in partially observable environments. It still uses condition–action rules but applies them to the maintained internal state.

(c) Goal-Based Agent Extends the model-based agent with explicit goal information describing desirable situations. It chooses actions by reasoning (using search and planning) about which sequence of actions will achieve its goal. More flexible than reflex agents because behaviour can be changed simply by specifying a new goal, but it requires deliberation.

(d) Utility-Based Agent Uses a utility function that maps each state (or sequence of states) to a real number measuring degree of happiness/desirability. When several action sequences reach the goal, or when goals conflict or are uncertain, it chooses the action that maximizes expected utility, giving rational decisions about trade-offs (e.g., a faster vs. safer route).