BSc CSIT (TU) Science Artificial Intelligence (BSc CSIT, CSC261) Question Paper 2080 Nepal

Uninformed (Blind) Search Strategies

Uninformed search strategies have no additional information about the goal beyond what is given in the problem definition. They can only generate successors and distinguish a goal state from a non-goal state. They explore the search tree systematically without using any domain-specific knowledge (no heuristic). Common uninformed strategies are:

• Breadth-First Search (BFS) – expands the shallowest unexpanded node (FIFO queue).
• Depth-First Search (DFS) – expands the deepest unexpanded node (LIFO stack).
• Uniform-Cost Search – expands the node with the lowest path cost $g(n)$.
• Depth-Limited Search – DFS with a depth bound $\ell$.
• Iterative Deepening DFS – repeated depth-limited search with increasing limits.

BFS vs DFS

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

Example

Consider the tree with root A, children B, C; B’s children D, E; C’s children F, G; goal = G.

• BFS order: A → B → C → D → E → F → G (explores level by level; guarantees the shallowest goal).
• DFS order: A → B → D → E → C → F → G (dives deep down the leftmost branch before backtracking).

Summary

BFS is complete and optimal for equal step costs but needs exponential memory, which is its main drawback. DFS is memory-efficient ($O(bm)$) but is neither complete nor optimal in general. Iterative Deepening combines DFS’s low memory with BFS’s completeness/optimality.

Heuristic Search

A heuristic search (informed search) uses problem-specific knowledge in the form of a heuristic function $h(n)$, which estimates the cost of the cheapest path from node $n$ to a goal. By guiding expansion toward promising nodes, heuristic search reaches the goal far more efficiently than blind search. Examples: Greedy Best-First Search and A* Search.

A* Search Algorithm

A* selects the node with the lowest evaluation function:

where $g(n)$ = actual cost from the start node to $n$, and $h(n)$ = estimated cost from $n$ to the goal. It thus balances the cost already paid against the estimated cost remaining.

A*(start, goal):
    OPEN  = {start};  CLOSED = {}
    g(start) = 0;  f(start) = h(start)
    while OPEN not empty:
        n = node in OPEN with smallest f(n)
        if n == goal: return reconstructed path
        move n from OPEN to CLOSED
        for each successor s of n:
            tentative_g = g(n) + cost(n, s)
            if tentative_g < g(s):
                g(s) = tentative_g
                f(s) = g(s) + h(s)
                parent(s) = n
                add s to OPEN
    return failure

Example

Find a path S → G. Edge costs: S–A = 1, S–B = 4, A–G = 6, B–G = 2. Heuristics: $h(S)=5, h(A)=4, h(B)=2, h(G)=0$.

• Expand S: $f(A)=g(A)+h(A)=1+4=5$, $f(B)=4+2=6$.
• Pick A ($f=5$): $f(G)=1+6+0=7$.
• Pick B ($f=6$): path S–B–G gives $g(G)=4+2=6$, $f(G)=6$.
• Pick G via B ($f=6$): goal reached. Optimal path = S → B → G, cost 6.

Admissibility and Consistency

• Admissibility: $h(n)$ is admissible if it never overestimates the true cost to the goal: $h(n) \le h^{*}(n)$ for all $n$. An admissible heuristic makes tree-search A optimal*.
• Consistency (monotonicity): $h$ is consistent if for every node $n$ and successor $n'$ via action with cost $c(n,n')$:

Consistency implies admissibility and makes graph-search A optimal* (the $f$-value never decreases along any path).

Knowledge Representation using Predicate Logic

Predicate (First-Order) Logic represents knowledge using objects, predicates (relations), functions, quantifiers ($\forall, \exists$), connectives ($\neg, \wedge, \vee, \rightarrow, \leftrightarrow$) and variables. Unlike propositional logic, it can express general statements about classes of objects, which makes it expressive enough for AI knowledge bases (e.g., Loves(x, y), Cat(Tom)).

Translating English to First-Order Predicate Logic

Resolution Method

Resolution is a sound and complete proof by refutation inference rule. To prove a goal $G$ from a knowledge base $KB$, we add $\neg G$ and show $KB \wedge \neg G$ derives a contradiction (empty clause $\square$).

Steps: (1) Convert all sentences to CNF (clause form) – eliminate $\rightarrow$, move $\neg$ inward, standardize variables, Skolemize $\exists$, drop $\forall$, distribute $\vee$ over $\wedge$. (2) Negate the goal and add to clause set. (3) Repeatedly apply resolution + unification until the empty clause is derived.

Resolution rule: from $(A \vee P)$ and $(\neg P \vee B)$ infer $(A \vee B)$.

Example

KB: “All humans are mortal” and “Socrates is a human.” Prove Mortal(Socrates).

Clauses:

1. $\neg Human(x) \vee Mortal(x)$
2. $Human(Socrates)$
3. $\neg Mortal(Socrates)$ (negated goal)

• Resolve 1 & 3 with $\{x/Socrates\}$ → $\neg Human(Socrates)$.
• Resolve that with 2 → empty clause $\square$.

A contradiction is reached, so Mortal(Socrates) is proved.

Wumpus World Problem

The Wumpus World is a classic AI environment used to illustrate knowledge-based agents and logical reasoning under uncertainty. It is a $4\times4$ grid of rooms containing:

• A Wumpus – a monster that eats any agent entering its room.
• Pits – falling into one kills the agent.
• A heap of gold – the goal is to grab it and exit.

Percepts (sensors):

• Stench – in squares adjacent to the Wumpus.
• Breeze – in squares adjacent to a pit.
• Glitter – in the square containing gold.
• Bump – when walking into a wall.
• Scream – when the Wumpus is killed by the agent’s single arrow.

PEAS / behaviour: The agent starts at $[1,1]$ facing right, has one arrow, and must use logical inference on its percepts to deduce safe squares (e.g., “no breeze ⇒ neighbours are pit-free”), find the gold, and climb out. The performance measure rewards getting the gold and penalizes death, each move, and arrow use.

It demonstrates how an agent represents knowledge in propositional/first-order logic and uses inference to act safely in a partially observable, deterministic environment.

Depth-First Search vs Best-First Search

Summary: DFS blindly dives along the deepest branch using a stack, whereas Best-First Search uses a heuristic to expand the most promising node first, generally reaching the goal faster but at higher memory cost.

Goal of Unification

Unification is the process of finding a substitution (a set of variable–term bindings) that makes two logical expressions (literals/terms) identical. The resulting substitution is called the unifier; the simplest such substitution is the Most General Unifier (MGU).

Goal / purpose:

• To make two predicate expressions syntactically equal so that inference rules such as resolution and modus ponens can be applied to first-order clauses.
• It is the core matching mechanism that lets a reasoning engine bind variables consistently while combining clauses.

Example: Unifying $P(x, f(a))$ with $P(b, y)$ gives the MGU $\{x/b,\; y/f(a)\}$, after which both become $P(b, f(a))$.

Note: Unification fails when terms cannot be matched, e.g., $P(a)$ and $P(b)$ with two different constants, or when the occurs-check is violated (a variable unifying with a term that contains it).

Components of an Expert System

An expert system is an AI program that emulates the decision-making ability of a human expert in a specific domain. Its main components are:

1. Knowledge Base – Stores domain knowledge as facts and IF–THEN rules acquired from human experts. It is the heart of the system.
2. Inference Engine – The reasoning component that applies logical rules to the knowledge base to deduce new facts and conclusions, using forward chaining (data-driven) or backward chaining (goal-driven).
3. Knowledge Acquisition Module – Helps the knowledge engineer/expert add, update and refine knowledge in the knowledge base.
4. User Interface – Allows a non-expert user to interact with the system (input queries, receive advice) in a convenient way.
5. Explanation Facility – Justifies the system’s reasoning, explaining how a conclusion was reached and why a question is asked, building user trust.
6. Working Memory (Blackboard) – Temporary storage holding the current facts/inputs about the problem being solved.

Examples: MYCIN (medical diagnosis), DENDRAL (chemical analysis).

Strong AI vs Weak AI

Summary: Weak AI performs specific tasks by simulating intelligence and is what all current systems are, whereas Strong AI refers to a hypothetical machine with human-level general intelligence and actual cognitive understanding.

Turing Test

The Turing Test, proposed by Alan Turing (1950) in his paper “Computing Machinery and Intelligence”, is an operational test to decide whether a machine can be considered intelligent.

Setup (the Imitation Game): A human interrogator communicates via text (to hide voice/appearance) with two unseen participants – one human and one machine. The interrogator asks questions and tries to identify which is which. If the machine can converse so convincingly that the interrogator cannot reliably distinguish it from the human, the machine is said to have passed the Turing Test and to exhibit intelligent behaviour.

Significance

• Provides an objective, behaviour-based definition of machine intelligence, avoiding the philosophical debate about what “thinking” means.
• Sets a benchmark goal for AI in natural language processing, knowledge representation, automated reasoning and learning – the capabilities a machine needs to pass it.
• Inspired research directions and variants such as the Total Turing Test (adding vision and robotics).

Limitation: Passing the test shows the appearance of intelligence, not genuine understanding (cf. Searle’s Chinese Room argument).

Rational Agent

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 any built-in knowledge it has. In short, a rational agent does the right thing — the action expected to yield the best outcome.

Its rationality depends on four things: the performance measure, the agent’s prior knowledge of the environment, the actions available, and the percept sequence to date (the PEAS view).

Properties (Dimensions) of a Task Environment

1. Fully observable vs. Partially observable – whether sensors give access to the complete state.
2. Deterministic vs. Stochastic – whether the next state is fully determined by the current state and action.
3. Episodic vs. Sequential – whether each action is independent or affects future decisions.
4. Static vs. Dynamic – whether the environment can change while the agent deliberates.
5. Discrete vs. Continuous – whether states/percepts/actions are finite-discrete or continuous.
6. Single-agent vs. Multi-agent – whether one or several agents act in the environment.
7. Known vs. Unknown – whether the rules/outcomes of the environment are known to the agent.

Informed vs Uninformed Search

Summary: Uninformed search has no clue about goal distance and searches systematically, whereas informed search uses a heuristic to estimate which paths are most promising, making it usually faster and more memory-efficient.

Hill-Climbing Search

Hill Climbing is a local search / optimization technique. It starts from an arbitrary state and iteratively moves to the neighbouring state with the best (highest) value of an objective/heuristic function, stopping when no neighbour is better. It keeps only the current state (no search tree), so it uses very little memory.

HillClimbing(problem):
    current = initial_state
    loop:
        neighbor = highest-valued successor of current
        if value(neighbor) <= value(current):
            return current        // local peak reached
        current = neighbor

It is like “climbing a hill in fog” — always stepping upward toward higher value.

Problems of Hill Climbing

1. Local Maximum – a peak lower than the global maximum; all neighbours are worse, so the search stops without reaching the best solution.
2. Plateau (flat region) – a flat area where neighbouring states have equal value, giving no direction to move and causing the search to wander or halt.
3. Ridge – a sequence of local maxima that is hard to navigate because moves are restricted to single directions, so progress along the ridge is slow or stalls.

Remedies: random-restart hill climbing, simulated annealing, and stochastic/first-choice variants help escape these traps.