State Space Graph and Comparison of A* Search vs Greedy Best First Search

Part 1: State Space Graph (Definition)

Definition

A state space graph is a directed graph in which:

• Each node represents a state of the problem
• Each arc (edge) represents the application of an operator that transforms one state into its successor state

Formal Representation

A state space is formally defined by the 4-tuple:

(S, S₀, O, G)

Key Components

1. Initial State: The state from which the agent begins
2. State Description (Successor Function): Describes all possible actions available to the agent at any state
3. Goal Test: A function that checks whether a given state is the goal state
4. Path Cost: The sum of the costs of each step along a path to the goal state

Solution

A solution is a path from the initial state to the goal state:

Initial State --> [Operator 1] --> State 1 --> [Operator 2] --> ... --> Goal State

Example Diagram

        S (Start)
       / \
      A   B
     / \   \
    C   D   E
             \
              G (Goal)

Nodes = States
Edges = Operators/Actions
Path S -> B -> E -> G = Solution

Part 2: Difference Between A* Search and Greedy Best First Search

Both A* and Greedy Best First Search are heuristically informed (heuristic) search methods that use an evaluation function to decide which node to expand next. However, they differ significantly in their approach.

Greedy Best First Search

• Uses the evaluation function:

$$f(n) = h(n)$$

where h(n) is the heuristic estimate of the cost from node n to the goal state.

• It selects the node that appears closest to the goal based solely on the heuristic.
• It is greedy because it only looks at the estimated future cost and ignores the cost already paid to reach the current node.

A* Search

• Uses the evaluation function:

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

where:

• g(n) = actual cost from the start node to node n (path cost so far)

• h(n) = heuristic estimate of cost from node n to the goal

• It selects the node with the lowest total estimated cost (past cost + future cost).

Comparison Table

Here: b = branching factor, m = maximum depth, d = depth of shallowest goal

Illustrative Example

Consider a graph where:

Start = S, Goal = G
Path 1: S -> A -> G  (g = 10, h(G) = 0)
Path 2: S -> B -> G  (g = 3,  h(G) = 0)
h(A) = 1, h(B) = 5

• Greedy Best First would expand A first (h=1 is lower) and may find the longer path S->A->G
• A* would compute:
  • f(A) = g(A) + h(A) = 8 + 1 = 9
  • f(B) = g(B) + h(B) = 2 + 5 = 7
  • Expands B first and finds the optimal path S->B->G

This shows that A* finds the optimal solution while Greedy may not.

Summary

Greedy Best First Search is fast but not reliable for finding optimal paths because it only considers the heuristic estimate. A* Search is both complete and optimal because it accounts for the total cost (actual cost traveled + estimated remaining cost), making it the preferred algorithm when an optimal solution is needed.

Unification, Lifting, and Resolution in FOPL

Part 1: Unification and Lifting

Unification

Unification is the process of finding a substitution (a unifier) that makes two or more logical expressions identical.

• A substitution $\theta$ is a set of bindings ${x/term, \dots}$.
• Applying $\theta$ to an expression $P$ gives $\text{SUBST}(\theta, P)$.
• $\theta$ unifies $P$ and $Q$ if $\text{SUBST}(\theta, P) = \text{SUBST}(\theta, Q)$.
• The Most General Unifier (MGU) is the least restrictive such substitution.

Example: $P = Knows(John, x)$, $Q = Knows(John, Jane)$. MGU $\theta = {x/Jane}$, giving $Knows(John, Jane)$.

Lifting

Lifting raises a propositional inference rule to the first-order level using variables and unification. In propositional logic Modus Ponens works only on ground facts; Generalized (Lifted) Modus Ponens extends it to FOPL.

For $P_1', \dots, P_n'$ and $(P_1 \wedge \dots \wedge P_n \Rightarrow Q)$, if there is $\theta$ with $\text{SUBST}(\theta, P_i') = \text{SUBST}(\theta, P_i)$, then conclude $\text{SUBST}(\theta, Q)$.

Example: $King(John)$, $Greedy(y)$ with $King(x)\wedge Greedy(x)\Rightarrow Evil(x)$, $\theta={x/John, y/John}$ gives $Evil(John)$.

Part 2: Converting Sentences to FOPL

Predicates:

• $Likes(x,y)$: x likes y
• $Practical(x)$: x is a practical course
• $Practices(x,y)$: x practices y

Part 3: Resolution to Prove "Sushma likes PHP"

Step 1: Clause Form (CNF)

Step 2: Negate the Goal

Goal: $Likes(Sushma, PHP)$. Negated goal: $$C_7: \neg Likes(Sushma, PHP)$$

Step 3: Apply Resolution

Resolve $C_1$ and $C_7$, $\theta = {x/PHP}$: $$C_8: \neg Practical(PHP)$$

Resolve $C_4$ and $C_5$, $\theta = {u/Ruby,; v/PHP}$: $$C_9: Practical(PHP)$$

Resolve $C_8$ and $C_9$: $$\square \quad (\text{empty clause, contradiction})$$

Resolution Proof Tree

C1: ¬Practical(x) ∨ Likes(Sushma,x)      C7: ¬Likes(Sushma,PHP)
                    \  {x/PHP}            /
                     C8: ¬Practical(PHP)

C4: ¬Practices(u,v) ∨ Practical(v)       C5: Practices(Ruby,PHP)
                    \  {u/Ruby, v/PHP}   /
                     C9: Practical(PHP)

           C8: ¬Practical(PHP)   C9: Practical(PHP)
                        \        /
                         [ NIL ]  ← contradiction

Conclusion

Since resolution derives the empty clause $\square$, the negated goal is unsatisfiable with the KB. Therefore "Sushma likes PHP" is inferred (proved TRUE).

(Note: clauses $C_6$, and facts about $AI$/$DBMS$, are not needed for this particular proof, since PHP is shown to be practical directly from Ruby practicing it.)

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.

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.