Skolem Constant, Skolemization, and FOPL Representation

1. Skolem Constant

A Skolem constant is a special constant introduced during the process of Skolemization to eliminate existential quantifiers from a First Order Predicate Logic (FOPL) formula. When an existential quantifier appears in a formula without any enclosing universal quantifier, the existentially quantified variable is replaced by a unique new constant (called a Skolem constant) that represents the specific (but unnamed) individual whose existence is asserted.

Example:

• Formula: ∃x P(x)
• After Skolemization: P(a) where a is a Skolem constant.

If the existential quantifier is within the scope of a universal quantifier, the existential variable is replaced by a Skolem function (not a constant) of the universally quantified variables.

Example:

• Formula: ∀x ∃y Loves(x, y)
• After Skolemization: ∀x Loves(x, f(x)) where f(x) is a Skolem function.

2. Skolemization During Resolution

Skolemization is the process of removing existential quantifiers from a FOPL formula to prepare it for resolution. Resolution works on clausal form (CNF), and existential quantifiers must be eliminated before conversion to clause form.

Steps of Skolemization (as part of full conversion to clause form):

Rules of Skolemization:

• Case 1: If ∃x appears outside the scope of any universal quantifier, replace x with a Skolem constant (e.g., a, b, c).

  ∃x Movie(x) becomes Movie(SK1) where SK1 is a Skolem constant.

• Case 2: If ∃x appears within the scope of universal quantifiers ∀y1, ∀y2, ..., replace x with a Skolem function of those variables.

  ∀x ∃y HasScript(x, y) becomes ∀x HasScript(x, f(x)) where f(x) is a Skolem function.

3. Representation of Statements into FOPL

Predicates Used:

• Movie(x) : x is a movie
• Hit(x) : x is a hit
• GoodScript(x) : x has a good script
• Sentimental(x) : x is sentimental
• Comedy(x) : x is a comedy

Statement 1: "All movies are not hit."

Every x, if x is a movie, then x is not a hit.

$$\forall x ; Movie(x) \Rightarrow \neg Hit(x)$$

Statement 2: "Sarangi is a movie."

Sarangi is a specific individual (constant).

$$Movie(Sarangi)$$

Statement 3: "All movies which have good script are hit."

Every x, if x is a movie AND x has a good script, then x is a hit.

$$\forall x ; [Movie(x) \wedge GoodScript(x)] \Rightarrow Hit(x)$$

Statement 4: "Sarangi has a good script but Sarangi is sentimental."

Conjunction of two facts about the constant Sarangi.

$$GoodScript(Sarangi) \wedge Sentimental(Sarangi)$$

Statement 5: "There is a movie which is comedy."

There exists some x such that x is a movie and x is a comedy.

$$\exists x ; [Movie(x) \wedge Comedy(x)]$$

After Skolemization (since ∃x has no enclosing universal quantifier, replace x with Skolem constant SK1):

$$Movie(SK1) \wedge Comedy(SK1)$$

Summary Table

Note: Statements 1 and 3 appear contradictory (all movies are not hit vs. movies with good script are hit). This is intentional in the problem, likely to test resolution-based contradiction detection. In resolution, we would derive a contradiction from Movie(Sarangi), GoodScript(Sarangi), Statement 1, and Statement 3.

Natural Language Generation vs. Natural Language Understanding, and Morphological Analysis

Part 1: NLG vs. NLU (Differences)

According to the notes, NLP is composed of two parts: NLU and NLG.

Part 2: Morphological Analysis in NLP

Definition

Morphological analysis is one of the levels of analysis required in NLU. It is the study and analysis of the internal structure of words -- how words are formed from smaller meaningful units called morphemes.

What is a Morpheme?

A morpheme is the smallest unit of meaning in a language.

• Free morpheme: Can stand alone as a word. Example: play, book
• Bound morpheme: Cannot stand alone; must be attached to another morpheme. Example: -ing, -ed, -s, un-

How Morphological Analysis is Done

Morphological analysis involves breaking a word into its constituent morphemes and identifying their roles. The steps are:

Step 1: Tokenization The input sentence is split into individual words (tokens).

Example: "The boys are playing" --> ["The", "boys", "are", "playing"]

Step 2: Stemming / Lemmatization Each word is reduced to its base or root form.

Example:

• playing --> root: play + suffix: -ing (present participle)
• boys --> root: boy + suffix: -s (plural)
• played --> root: play + suffix: -ed (past tense)

Step 3: Identifying Morphological Categories The morphemes are tagged with their grammatical roles:

Step 4: Applying Morphological Rules Rules such as inflectional morphology (tense, number, gender) and derivational morphology (forming new words) are applied to understand the word's role in the sentence.

Importance in NLP

Morphological analysis is the first and foundational level of NLU. It helps the NLP system:

• Understand word forms and their base meanings
• Reduce vocabulary size for further processing
• Prepare input for syntactic and semantic analysis in subsequent stages

Summary: NLU converts language to meaning (harder), while NLG converts meaning to language (easier). Morphological analysis, the first step in NLU, breaks words into morphemes to understand their structure and grammatical roles.

Artificial Neural Networks: Biological Analogy and Backpropagation

STEP 1 - EXTRACT (Given / Assumed Data)

The question requires us to assume inputs and weights, so the worked example below uses these values:

Inputs: $x_1 = 0.5$, $x_2 = 0.3$ Target: $t = 1.0$

Learning rate: $\alpha = 0.5$ Activation: Sigmoid $g(x) = \dfrac{1}{1+e^{-x}}$, derivative $g'(x) = g(x)(1-g(x))$ Biases: $0$

Initial weights:

Part 1: Biological vs Artificial Neural Network Mapping

Summary: dendrites $\to$ inputs, synapses $\to$ weights, soma $\to$ summation + activation, axon $\to$ output. Learning in ANN = adjusting synaptic weights.

Part 2: Network Architecture

A 2-2-1 multilayer network:

 x1 ─w13─┐        ┌─w35─┐
         ├──> h1 ─┤     │
 x2 ─w23─┘        │     ├──> o1 ──> y
                  │     │
 x1 ─w14─┐        │     │
         ├──> h2 ─┴─w45─┘
 x2 ─w24─┘

Part 3: Single Iteration of Backpropagation

Step 1: Forward pass - hidden layer

$$net_{h1} = 0.4(0.5) + 0.2(0.3) = 0.20 + 0.06 = 0.26$$ $$h_1 = g(0.26) = \frac{1}{1+e^{-0.26}} = \frac{1}{1.7711} = 0.5646$$

$$net_{h2} = 0.3(0.5) + 0.5(0.3) = 0.15 + 0.15 = 0.30$$ $$h_2 = g(0.30) = \frac{1}{1+e^{-0.30}} = \frac{1}{1.7408} = 0.5744$$

Step 2: Forward pass - output layer

$$net_{o1} = 0.6(0.5646) + 0.7(0.5744) = 0.3388 + 0.4021 = 0.7409$$ $$y = g(0.7409) = \frac{1}{1+e^{-0.7409}} = \frac{1}{1.4767} = 0.6772$$

Step 3: Output error and delta

$$\delta_{o1} = (t - y)\cdot y(1-y) = (1.0 - 0.6772)(0.6772)(1-0.6772)$$ $$= 0.3228 \times 0.6772 \times 0.3228 = 0.07057$$

Step 4: Hidden layer deltas

$$\delta_{h1} = h_1(1-h_1),(w_{35},\delta_{o1})$$ $$= 0.5646(0.4354)(0.6 \times 0.07057) = 0.2458 \times 0.04234 = 0.01041$$

$$\delta_{h2} = h_2(1-h_2),(w_{45},\delta_{o1})$$ $$= 0.5744(0.4256)(0.7 \times 0.07057) = 0.2445 \times 0.04940 = 0.01208$$

Step 5: Weight updates $;w^{new} = w^{old} + \alpha,\delta,(\text{input to that weight})$

Output layer: $$w_{35}^{new} = 0.6 + 0.5(0.07057)(0.5646) = 0.6 + 0.01992 = 0.6199$$ $$w_{45}^{new} = 0.7 + 0.5(0.07057)(0.5744) = 0.7 + 0.02027 = 0.7203$$

Hidden layer: $$w_{13}^{new} = 0.4 + 0.5(0.01041)(0.5) = 0.4 + 0.00260 = 0.4026$$ $$w_{23}^{new} = 0.2 + 0.5(0.01041)(0.3) = 0.2 + 0.00156 = 0.2016$$ $$w_{14}^{new} = 0.3 + 0.5(0.01208)(0.5) = 0.3 + 0.00302 = 0.3030$$ $$w_{24}^{new} = 0.5 + 0.5(0.01208)(0.3) = 0.5 + 0.00181 = 0.5018$$

Result of one iteration

Output moved from $y = 0.6772$ toward target $t = 1.0$; repeating iterations reduces error.

Common mistake: treating $\delta = t - y = 0.3229$ as the output delta. The sigmoid derivative must be included, giving $\delta_{o1} = (t-y),y(1-y) = 0.0706$, and that is the value used in the weight updates. The forward pass gives $h_1 \approx 0.565$, $h_2 \approx 0.574$ and $y \approx 0.677$.

Informed vs Uninformed Search, Hill Climbing, and Incompleteness

STEP 1 - EXTRACT: Given Data

This is a conceptual and design question. There are no fixed numeric inputs provided; the student must construct a state space with heuristics. The state space used below is:

Working state space (Part 3):

Modified state space (Part 4):

No data is missing since the values are self-created and internally consistent.

STEP 2 - SOLVE

Part 1: Informed vs Uninformed Search

The heuristic function is: $$h(n) = \text{estimated cost of the cheapest path from node } n \text{ to a goal}$$

Informed search leverages $h(n)$ to prioritize promising nodes, which uninformed search cannot do.

Part 2: Hill Climbing Concept

Hill climbing is a local, informed search that:

• keeps only the current state (no frontier, no memory),
• always moves to the best neighbor (here, lowest $h$ toward goal),
• halts when no neighbor improves on the current node.

Part 3: State Space Where Hill Climbing Succeeds

        A (10)
       /   \
    B(7)    C(8)
    /  \      \
  D(4) E(5)   F(6)
   |
  G(0)  <-- GOAL

Execution (choose neighbor with lowest $h$):

Solution path: $A \to B \to D \to G$

Hill climbing succeeds because the heuristic decreases monotonically along the correct path.

Part 4: Modified State Space Where Hill Climbing Fails

We change $D$'s value to $5$ and add a misleading branch $E \to X$ with $h(E)=3$, $h(X)=4$, so the greedy choice leads into a local minimum.

        A (10)
       /   \
    B(7)    C(8)
    /  \      \
  D(5) E(3)   F(6)
   |     \
  G(0)   X(4)  <-- dead-end trap

Execution:

Path followed: $A \to B \to E$ → stuck at $E$ (local minimum).

The actual goal lies on $A \to B \to D \to G$, but at step 2 the greedy heuristic picked $E$ (h=3) over $D$ (h=5). At $E$, the only neighbor $X$ (h=4) is worse, so hill climbing terminates without reaching $G$.

Why incomplete: Hill climbing has no backtracking and no memory, so once it commits to a locally attractive but misleading node it cannot recover. This illustrates the classic failure modes:

1. Local minimum/maximum (shown above),
2. Plateau (all neighbors equal),
3. Ridge (progress only via non-improving sideways moves).

Hence hill climbing is not complete: it can fail to find an existing goal.

Conclusion: Informed search uses $h(n)$ to guide exploration (unlike blind uninformed search). Hill climbing exploits $h(n)$ greedily and works when the heuristic slopes toward the goal, but because it lacks backtracking it becomes incomplete at local minima, plateaus, and ridges.

AI can be defined from four dimensions based on thinking/acting and humanly/rationally. The behavioural (process) dimension focuses on how a system acts rather than what it thinks internally. The two behavioural approaches are: "A comput...

Skolem Constant, Skolemization, and FOPL Representation

1. Skolem Constant

A Skolem constant is a special constant introduced during the process of Skolemization to eliminate existential quantifiers from a First Order Predicate Logic (FOPL) formula. When an existential quantifier appears in a formula without any enclosing universal quantifier, the existentially quantified variable is replaced by a unique new constant (called a Skolem constant) that represents the specific (but unnamed) individual whose existence is asserted.

Example:

• Formula: ∃x P(x)
• After Skolemization: P(a) where a is a Skolem constant.

If the existential quantifier is within the scope of a universal quantifier, the existential variable is replaced by a Skolem function (not a constant) of the universally quantified variables.

Example:

• Formula: ∀x ∃y Loves(x, y)
• After Skolemization: ∀x Loves(x, f(x)) where f(x) is a Skolem function.

2. Skolemization During Resolution

Skolemization is the process of removing existential quantifiers from a FOPL formula to prepare it for resolution. Resolution works on clausal form (CNF), and existential quantifiers must be eliminated before conversion to clause form.

Steps of Skolemization (as part of full conversion to clause form):

Rules of Skolemization:

• Case 1: If ∃x appears outside the scope of any universal quantifier, replace x with a Skolem constant (e.g., a, b, c).

  ∃x Movie(x) becomes Movie(SK1) where SK1 is a Skolem constant.

• Case 2: If ∃x appears within the scope of universal quantifiers ∀y1, ∀y2, ..., replace x with a Skolem function of those variables.

  ∀x ∃y HasScript(x, y) becomes ∀x HasScript(x, f(x)) where f(x) is a Skolem function.

3. Representation of Statements into FOPL

Predicates Used:

• Movie(x) : x is a movie
• Hit(x) : x is a hit
• GoodScript(x) : x has a good script
• Sentimental(x) : x is sentimental
• Comedy(x) : x is a comedy

Statement 1: "All movies are not hit."

Every x, if x is a movie, then x is not a hit.

$$\forall x ; Movie(x) \Rightarrow \neg Hit(x)$$

Statement 2: "Sarangi is a movie."

Sarangi is a specific individual (constant).

$$Movie(Sarangi)$$

Statement 3: "All movies which have good script are hit."

Every x, if x is a movie AND x has a good script, then x is a hit.

$$\forall x ; [Movie(x) \wedge GoodScript(x)] \Rightarrow Hit(x)$$

Statement 4: "Sarangi has a good script but Sarangi is sentimental."

Conjunction of two facts about the constant Sarangi.

$$GoodScript(Sarangi) \wedge Sentimental(Sarangi)$$

Statement 5: "There is a movie which is comedy."

There exists some x such that x is a movie and x is a comedy.

$$\exists x ; [Movie(x) \wedge Comedy(x)]$$

After Skolemization (since ∃x has no enclosing universal quantifier, replace x with Skolem constant SK1):

$$Movie(SK1) \wedge Comedy(SK1)$$

Summary Table

Note: Statements 1 and 3 appear contradictory (all movies are not hit vs. movies with good script are hit). This is intentional in the problem, likely to test resolution-based contradiction detection. In resolution, we would derive a contradiction from Movie(Sarangi), GoodScript(Sarangi), Statement 1, and Statement 3.

Artificial Neural Networks: Biological Analogy and Backpropagation

STEP 1 - EXTRACT (Given / Assumed Data)

The question requires us to assume inputs and weights, so the worked example below uses these values:

Inputs: $x_1 = 0.5$, $x_2 = 0.3$ Target: $t = 1.0$

Learning rate: $\alpha = 0.5$ Activation: Sigmoid $g(x) = \dfrac{1}{1+e^{-x}}$, derivative $g'(x) = g(x)(1-g(x))$ Biases: $0$

Initial weights:

Part 1: Biological vs Artificial Neural Network Mapping

Summary: dendrites $\to$ inputs, synapses $\to$ weights, soma $\to$ summation + activation, axon $\to$ output. Learning in ANN = adjusting synaptic weights.

Part 2: Network Architecture

A 2-2-1 multilayer network:

 x1 ─w13─┐        ┌─w35─┐
         ├──> h1 ─┤     │
 x2 ─w23─┘        │     ├──> o1 ──> y
                  │     │
 x1 ─w14─┐        │     │
         ├──> h2 ─┴─w45─┘
 x2 ─w24─┘

Part 3: Single Iteration of Backpropagation

Step 1: Forward pass - hidden layer

$$net_{h1} = 0.4(0.5) + 0.2(0.3) = 0.20 + 0.06 = 0.26$$ $$h_1 = g(0.26) = \frac{1}{1+e^{-0.26}} = \frac{1}{1.7711} = 0.5646$$

$$net_{h2} = 0.3(0.5) + 0.5(0.3) = 0.15 + 0.15 = 0.30$$ $$h_2 = g(0.30) = \frac{1}{1+e^{-0.30}} = \frac{1}{1.7408} = 0.5744$$

Step 2: Forward pass - output layer

$$net_{o1} = 0.6(0.5646) + 0.7(0.5744) = 0.3388 + 0.4021 = 0.7409$$ $$y = g(0.7409) = \frac{1}{1+e^{-0.7409}} = \frac{1}{1.4767} = 0.6772$$

Step 3: Output error and delta

$$\delta_{o1} = (t - y)\cdot y(1-y) = (1.0 - 0.6772)(0.6772)(1-0.6772)$$ $$= 0.3228 \times 0.6772 \times 0.3228 = 0.07057$$

Step 4: Hidden layer deltas

$$\delta_{h1} = h_1(1-h_1),(w_{35},\delta_{o1})$$ $$= 0.5646(0.4354)(0.6 \times 0.07057) = 0.2458 \times 0.04234 = 0.01041$$

$$\delta_{h2} = h_2(1-h_2),(w_{45},\delta_{o1})$$ $$= 0.5744(0.4256)(0.7 \times 0.07057) = 0.2445 \times 0.04940 = 0.01208$$

Step 5: Weight updates $;w^{new} = w^{old} + \alpha,\delta,(\text{input to that weight})$

Output layer: $$w_{35}^{new} = 0.6 + 0.5(0.07057)(0.5646) = 0.6 + 0.01992 = 0.6199$$ $$w_{45}^{new} = 0.7 + 0.5(0.07057)(0.5744) = 0.7 + 0.02027 = 0.7203$$

Hidden layer: $$w_{13}^{new} = 0.4 + 0.5(0.01041)(0.5) = 0.4 + 0.00260 = 0.4026$$ $$w_{23}^{new} = 0.2 + 0.5(0.01041)(0.3) = 0.2 + 0.00156 = 0.2016$$ $$w_{14}^{new} = 0.3 + 0.5(0.01208)(0.5) = 0.3 + 0.00302 = 0.3030$$ $$w_{24}^{new} = 0.5 + 0.5(0.01208)(0.3) = 0.5 + 0.00181 = 0.5018$$

Result of one iteration

Output moved from $y = 0.6772$ toward target $t = 1.0$; repeating iterations reduces error.

Common mistake: treating $\delta = t - y = 0.3229$ as the output delta. The sigmoid derivative must be included, giving $\delta_{o1} = (t-y),y(1-y) = 0.0706$, and that is the value used in the weight updates. The forward pass gives $h_1 \approx 0.565$, $h_2 \approx 0.574$ and $y \approx 0.677$.

Natural Language Generation vs. Natural Language Understanding, and Morphological Analysis

Part 1: NLG vs. NLU (Differences)

According to the notes, NLP is composed of two parts: NLU and NLG.

Part 2: Morphological Analysis in NLP

Definition

Morphological analysis is one of the levels of analysis required in NLU. It is the study and analysis of the internal structure of words -- how words are formed from smaller meaningful units called morphemes.

What is a Morpheme?

A morpheme is the smallest unit of meaning in a language.

• Free morpheme: Can stand alone as a word. Example: play, book
• Bound morpheme: Cannot stand alone; must be attached to another morpheme. Example: -ing, -ed, -s, un-

How Morphological Analysis is Done

Morphological analysis involves breaking a word into its constituent morphemes and identifying their roles. The steps are:

Step 1: Tokenization The input sentence is split into individual words (tokens).

Example: "The boys are playing" --> ["The", "boys", "are", "playing"]

Step 2: Stemming / Lemmatization Each word is reduced to its base or root form.

Example:

• playing --> root: play + suffix: -ing (present participle)
• boys --> root: boy + suffix: -s (plural)
• played --> root: play + suffix: -ed (past tense)

Step 3: Identifying Morphological Categories The morphemes are tagged with their grammatical roles:

Step 4: Applying Morphological Rules Rules such as inflectional morphology (tense, number, gender) and derivational morphology (forming new words) are applied to understand the word's role in the sentence.

Importance in NLP

Morphological analysis is the first and foundational level of NLU. It helps the NLP system:

• Understand word forms and their base meanings
• Reduce vocabulary size for further processing
• Prepare input for syntactic and semantic analysis in subsequent stages

Summary: NLU converts language to meaning (harder), while NLG converts meaning to language (easier). Morphological analysis, the first step in NLU, breaks words into morphemes to understand their structure and grammatical roles.

Informed vs Uninformed Search, Hill Climbing, and Incompleteness

STEP 1 - EXTRACT: Given Data

This is a conceptual and design question. There are no fixed numeric inputs provided; the student must construct a state space with heuristics. The state space used below is:

Working state space (Part 3):

Modified state space (Part 4):

No data is missing since the values are self-created and internally consistent.

STEP 2 - SOLVE

Part 1: Informed vs Uninformed Search

The heuristic function is: $$h(n) = \text{estimated cost of the cheapest path from node } n \text{ to a goal}$$

Informed search leverages $h(n)$ to prioritize promising nodes, which uninformed search cannot do.

Part 2: Hill Climbing Concept

Hill climbing is a local, informed search that:

• keeps only the current state (no frontier, no memory),
• always moves to the best neighbor (here, lowest $h$ toward goal),
• halts when no neighbor improves on the current node.

Part 3: State Space Where Hill Climbing Succeeds

        A (10)
       /   \
    B(7)    C(8)
    /  \      \
  D(4) E(5)   F(6)
   |
  G(0)  <-- GOAL

Execution (choose neighbor with lowest $h$):

Solution path: $A \to B \to D \to G$

Hill climbing succeeds because the heuristic decreases monotonically along the correct path.

Part 4: Modified State Space Where Hill Climbing Fails

We change $D$'s value to $5$ and add a misleading branch $E \to X$ with $h(E)=3$, $h(X)=4$, so the greedy choice leads into a local minimum.

        A (10)
       /   \
    B(7)    C(8)
    /  \      \
  D(5) E(3)   F(6)
   |     \
  G(0)   X(4)  <-- dead-end trap

Execution:

Path followed: $A \to B \to E$ → stuck at $E$ (local minimum).

The actual goal lies on $A \to B \to D \to G$, but at step 2 the greedy heuristic picked $E$ (h=3) over $D$ (h=5). At $E$, the only neighbor $X$ (h=4) is worse, so hill climbing terminates without reaching $G$.

Why incomplete: Hill climbing has no backtracking and no memory, so once it commits to a locally attractive but misleading node it cannot recover. This illustrates the classic failure modes:

1. Local minimum/maximum (shown above),
2. Plateau (all neighbors equal),
3. Ridge (progress only via non-improving sideways moves).

Hence hill climbing is not complete: it can fail to find an existing goal.

Conclusion: Informed search uses $h(n)$ to guide exploration (unlike blind uninformed search). Hill climbing exploits $h(n)$ greedily and works when the heuristic slopes toward the goal, but because it lacks backtracking it becomes incomplete at local minima, plateaus, and ridges.

Uniform Cost Search (UCS) in State Space

Given Data

This is a conceptual/descriptive question. No numeric matrices, burst times, or reference strings are provided. The example graph and edge costs are constructed for illustration (as the question requires "an example").

Definition

Uniform Cost Search (UCS) is an uninformed (blind) search strategy that expands the node with the lowest cumulative path cost $g(n)$ from the start node. It is a special case of Best-First Search using the evaluation function:

$$f(n) = g(n)$$

where $g(n)$ = total cost of the path from the start state to node $n$. When all step costs are equal, UCS reduces to Breadth-First Search.

How UCS Searches the Goal

1. Insert the start node into a priority queue ordered by path cost (minimum first), with cost $0$.
2. Remove the node with the least path cost.
3. Goal test at expansion (when popped, not when generated) to guarantee optimality.
4. Generate successors; for each, compute $g(\text{child}) = g(\text{parent}) + \text{step cost}$ and insert into the priority queue.
5. If a cheaper path to an already-seen node is found, update it.
6. Repeat until the goal is popped or the queue is empty.

Illustrated Example

Consider a weighted graph with start $S$ and goal $G$:

Edge costs:

• $S \to A = 1$
• $S \to B = 4$
• $A \to B = 2$
• $A \to G = 5$
• $B \to G = 2$

Step-by-Step Trace

Optimal Path: $S \to A \to B \to G$ with total cost $= 1 + 2 + 2 = \mathbf{5}$

The alternative $S \to A \to G$ costs $6$, so UCS correctly returns the cheaper path.

Check the path, not just the cost: with $S \to A = 1$ and $A \to B = 2$, node $B$ is reached at cost $3$, so the optimal path is $S \to A \to B \to G$ rather than $S \to B \to G$. The final cost (5) is identical either way.

Performance Measures

where $C^{*}$ = cost of optimal solution, $\varepsilon$ = minimum step cost, $b$ = branching factor.

Key Points

• Uses a priority queue ordered by $g(n)$.
• Optimal and complete for positive step costs.
• Uninformed counterpart of A* (A* adds heuristic: $f(n)=g(n)+h(n)$).
• Goal tested at expansion, ensuring no cheaper path is missed.

A script is a structured knowledge representation technique used in AI to represent stereotyped sequences of events in a particular context. It was introduced by Roger Schank and Robert Abelson (1977). A script describes a typical sequen...

AI can be defined from four dimensions based on thinking/acting and humanly/rationally. The behavioural (process) dimension focuses on how a system acts rather than what it thinks internally. The two behavioural approaches are: "A comput...

Genetic Algorithms (GAs) are adaptive heuristic search algorithms that belong to the larger part of evolutionary algorithms. They are based on the idea of natural selection and genetics. Historical data are provided to find better soluti...

To design a rational agent, we must specify its task environment using the PEAS framework: - P - Performance Measure - E - Environment - A - Actuators - S - Sensors --- Assumptions: The drone operates in an urban area, picks up medicines...

Fuzzy logic is a form of multi-valued logic derived from fuzzy set theory that deals with approximate reasoning rather than precise (crisp) reasoning. Unlike classical binary logic where variables take only values of 0 (false) or 1 (true...

In a standard Minimax game tree, every node must be evaluated, which leads to exponential time complexity of O(b^m) where b is the branching factor and m is the maximum depth. This becomes computationally infeasible for games like chess ...

An expert system is a computer program designed to solve complex problems and provide decision-making ability like a human expert. It extracts knowledge from its knowledge base using reasoning and inference rules according to user querie...

What is an Agent? Utility Agent and Example

What is an Agent? (1 mark)

An agent is anything that can perceive its environment through sensors and act upon that environment through actuators. An agent operates in a continuous cycle:

Environment --> Sensors --> Agent --> Actuators --> Environment

An agent takes a percept sequence as input and produces an action as output. The goal of an agent is to act rationally, meaning it selects actions that maximize its expected performance measure based on available knowledge.

How a Utility-Based Agent Works (2 marks)

A utility-based agent is an advanced type of agent that goes beyond simply achieving goals. It uses a utility function to measure how desirable a particular state is, allowing the agent to choose the best possible action among many alternatives.

Working Mechanism:

Percepts --> [State Representation] --> [Utility Function] --> Best Action

Step-by-step working:

1. Perceive the current state of the environment through sensors.
2. Maintain an internal model of the world (current state).
3. Evaluate possible next states using a utility function, which assigns a numerical value (happiness/desirability score) to each state.
4. Select the action that leads to the state with the maximum expected utility.
5. Execute the chosen action through actuators.

Key Features:

• It handles situations where multiple goals conflict with each other.
• It handles uncertainty by computing expected utility (probability-weighted utility).
• It does not just ask "Did I achieve the goal?" but rather "How well did I achieve it?"

Formula:

View full

Best Action = argmax [ Σ P(outcome | action) × Utility(outcome) ]

Example of a Utility-Based Agent (2 marks)

Example: Self-Driving Taxi (Automated Taxi)

Consider an automated taxi agent navigating from point A to point B.

How it works:

• The taxi perceives road conditions, traffic, distance, and fuel level.
• It evaluates each possible route using a utility function that considers:
  • Travel time (less time = higher utility)
  • Passenger comfort (smooth road = higher utility)
  • Fuel cost (less cost = higher utility)
  • Safety (safer route = higher utility)
• It selects the route with the maximum utility score (longer route with no traffic = 75).
• This is better than a simple goal-based agent that would just pick the shortest route without considering comfort or traffic.

Why Utility Agent is Better:

• A goal-based agent only checks: "Did I reach destination? Yes/No"
• A utility-based agent checks: "Which path gives the best overall experience?"

This makes utility-based agents ideal for stochastic and partially observable environments (like driving) where uncertainty must be handled rationally through probability and utility calculations.

Machine vision is the ability of a computer to "see". A machine vision system employs one or more video cameras, analog-to-digital conversion (ADC), and digital signal processing (DSP). The resulting data goes to a computer or robot cont...

Symbol Meaning Value ------------------------ $P(L)$ Probability a patient has liver disease $0.15$ $P(A)$ Probability a patient is alcoholic $0.05$ $P(A\mid L)$ Probability a patient is alcoholic given they have liver disease $0.07$ Req...