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

Artificial Intelligence

Definition: Artificial Intelligence (AI) is the branch of computer science concerned with building machines and software that can perform tasks that normally require human intelligence — such as perceiving, reasoning, learning, planning, problem-solving, understanding language, and decision-making. A common definition (Russell & Norvig) is that AI is the study of rational agents — agents that act so as to achieve the best (expected) outcome given their knowledge.

Intelligent Agents

An agent is anything that perceives its environment through sensors and acts upon that environment through actuators. An intelligent (rational) agent selects actions that are expected to maximize its performance measure, given the percept sequence and built-in knowledge.

The agent function maps percept sequences to actions:

Main types of agents (increasing sophistication):

1. Simple reflex agents — act only on the current percept using condition–action rules.
2. Model-based reflex agents — maintain internal state to handle partial observability.
3. Goal-based agents — use goal information plus search/planning to choose actions.
4. Utility-based agents — use a utility function to choose among many ways of reaching a goal.
5. Learning agents — improve performance over time from experience (learning element, performance element, critic, problem generator).

Types of Agent (Task) Environments

Example: Chess is fully observable, deterministic (without clock), sequential, static, discrete and multi-agent; an automated taxi is partially observable, stochastic, sequential, dynamic, continuous and multi-agent.

PEAS Framework

To design a rational agent we first specify the task environment using PEAS:

• P – Performance measure: the criteria used to judge success.
• E – Environment: the surroundings in which the agent operates.
• A – Actuators: the means by which the agent acts.
• S – Sensors: the means by which the agent perceives.

Example – Automated taxi driver:

Thus AI builds rational agents, and PEAS together with the environment properties gives a systematic way to characterise and design them.

Uninformed (Blind) Search Strategies

Uninformed search strategies have no additional information about the goal beyond the problem definition; they can only generate successors and check whether a state is a goal. They explore the search tree systematically without any domain heuristic. The main uninformed strategies are Breadth-First Search (BFS), Depth-First Search (DFS), Uniform-Cost Search, Depth-Limited Search, and Iterative-Deepening Search.

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

Breadth-First Search (BFS)

BFS expands the shallowest unexpanded node first, using a FIFO queue. It explores all nodes at depth $k$ before any at depth $k+1$.

• Completeness: Complete (if $b$ is finite).
• Optimality: Optimal if all step costs are equal (or unit cost).
• Time complexity: $O(b^d)$.
• Space complexity: $O(b^d)$ — must store the whole frontier (its main drawback).

Depth-First Search (DFS)

DFS expands the deepest unexpanded node first, using a LIFO stack. It goes as deep as possible along one branch before backtracking.

• Completeness: Not complete (can loop forever in infinite-depth or cyclic spaces; complete in finite spaces with cycle checking).
• Optimality: Not optimal — may return a deep, costly solution.
• Time complexity: $O(b^m)$.
• Space complexity: $O(b\,m)$ — needs to store only a single path plus siblings, which is its key advantage.

Comparison

Example

Consider a tree with root A, children B, C; B has children D, E; C has children F, G, with goal = G.

• BFS order: A, B, C, D, E, F, G — finds G level by level and guarantees the shortest path.
• DFS order: A, B, D, E, C, F, G — dives down the left branch (B→D→E) first, backtracks, then finds G.

Summary: BFS is complete and optimal but memory-hungry ($O(b^d)$ space); DFS is memory-efficient ($O(bm)$ space) but neither complete nor optimal. Iterative deepening combines the advantages of both.

Heuristic Search

Heuristic search (informed search) uses problem-specific knowledge, encoded in a heuristic function $h(n)$, to estimate the cost of the cheapest path from node $n$ to a goal. This guidance lets the search reach the goal faster than blind search by expanding the most promising nodes first. Examples include Greedy Best-First Search and A* search.

A heuristic $h(n)$ is an estimate of the remaining cost to the goal; e.g., straight-line (Euclidean) distance in route finding, or the number of misplaced tiles in the 8-puzzle.

A* Search Algorithm

A* combines the cost already incurred and the estimated cost to go, evaluating each node by:

where

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

A* uses a priority queue ordered by $f(n)$, always expanding the node with the lowest $f$ value.

A*(start, goal):
  OPEN = priority queue ordered by f = g + h, containing start
  CLOSED = empty set
  g(start) = 0
  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 s in CLOSED and tentative_g >= g(s): continue
        if s not in OPEN or tentative_g < g(s):
           g(s) = tentative_g
           f(s) = g(s) + h(s)
           parent(s) = n
           add/update s in OPEN
  return failure

Example

Find a route from S to G. Suppose:

• $g$ costs: S→A = 1, A→G = 5, S→B = 2, B→G = 3.
• Heuristic $h$: $h(A)=5$, $h(B)=3$, $h(G)=0$.

Evaluate frontier:

• Through A: $f(A) = g(A)+h(A) = 1+5 = 6$, and path S–A–G costs $1+5 = 6$.
• Through B: $f(B) = g(B)+h(B) = 2+3 = 5$, and path S–B–G costs $2+3 = 5$.

A* expands B first (lower $f$) and returns S → B → G with total cost 5, the optimal path.

Admissibility and Consistency

Admissibility: A heuristic $h(n)$ is admissible if it never overestimates the true cost to the goal:

where $h^*(n)$ is the actual optimal cost from $n$ to the goal. With an admissible heuristic, tree-search A* is optimal.

Consistency (monotonicity): $h$ is consistent if for every node $n$ and every successor $n'$ generated by action $a$ with step cost $c(n,a,n')$:

and $h(goal)=0$. This is a form of the triangle inequality. Consistency implies admissibility and guarantees that $f$ values are non-decreasing along any path, so graph-search A* is optimal without re-expanding closed nodes.

Conclusion: A* is complete and optimal (and optimally efficient) provided the heuristic is admissible (for tree search) and consistent (for graph search).

Strong AI vs. Weak AI

• Weak AI holds that machines can be made to act as if they are intelligent for a particular task, without claiming they truly think.
• Strong AI holds that a suitably programmed machine is a mind, with genuine cognitive states and understanding.

Turing Test

Proposed by Alan Turing (1950) as the Imitation Game, the Turing Test is an operational test for machine intelligence. A human interrogator communicates through a text-only channel with two hidden parties — one human and one machine — and asks questions. If the interrogator cannot reliably tell which respondent is the machine, the machine is said to have passed the test and to exhibit intelligent (human-like) behaviour.

To pass, a machine typically needs: natural language processing (to communicate), knowledge representation (to store information), automated reasoning (to answer and draw conclusions) and machine learning (to adapt and handle new situations).

Significance:

• It provides a concrete, behaviour-based criterion for intelligence, avoiding hard philosophical questions of consciousness.
• It defined a long-standing goal and benchmark for AI research.
• It highlights the core capabilities (language, reasoning, learning) an intelligent system must have.
• Its limitation: it tests only the appearance of intelligence (behaviour), not genuine understanding — a critique formalised by Searle's Chinese Room argument.

Rational Agent

A rational agent is one that, for each possible percept sequence, selects the action expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has. Rationality depends on (i) the performance measure, (ii) the agent's prior knowledge, (iii) the available actions, and (iv) the percept sequence to date. It is about doing the right thing (expected best outcome), not about being omniscient or always perfect.

Properties of a Task Environment (PEAS-described environment dimensions):

1. Fully observable vs. Partially observable
2. Single-agent vs. Multi-agent
3. Deterministic vs. Stochastic (and strategic)
4. Episodic vs. Sequential
5. Static vs. Dynamic (and semi-dynamic)
6. Discrete vs. Continuous
7. Known vs. Unknown

These properties determine the appropriate agent design for the task.

Informed vs. Uninformed Search

In short, uninformed search has no clue about how far the goal is, whereas informed search uses an estimate of the remaining distance to reach the goal more efficiently.

Hill-Climbing Search

Hill climbing is a local search / optimization technique. It starts from an initial state and repeatedly moves to the neighbouring state with the highest value (best heuristic/objective value), continuing until no neighbour is better. It is a greedy loop that keeps only the current state, using no memory of the path.

Hill-Climbing(problem):
  current = initial state
  loop:
     neighbor = highest-valued successor of current
     if value(neighbor) <= value(current):
         return current        // a peak (local maximum)
     current = neighbor

Problems (drawbacks):

1. Local maximum: A peak lower than the global maximum; all neighbours are worse, so the search stops at a suboptimal solution.
2. Plateau: A flat region where neighbours have the same value, giving no direction to move; the search may wander.
3. Ridge: A sequence of local maxima where moves in available directions all go downhill, though a better state lies along the ridge — hard to navigate with single-step moves.

Remedies: random-restart hill climbing, simulated annealing, stochastic/first-choice hill climbing, and allowing sideways moves.

Heuristic Function

A heuristic function $h(n)$ is a function that maps a state $n$ to a non-negative number estimating the cost of the cheapest path from $n$ to a goal state. It encodes problem-specific knowledge to guide an informed search toward the goal, where $h(goal)=0$. A good heuristic is one that is admissible (never overestimates the true cost) and close to the real cost.

Examples:

• Route finding: the straight-line (Euclidean) distance from the current city to the destination, e.g. $h(n)=\sqrt{(x_g-x_n)^2+(y_g-y_n)^2}$.
• 8-puzzle: the number of misplaced tiles ($h_1$), or the Manhattan distance of each tile from its goal position ($h_2 = \sum |x_i - x_i^*| + |y_i - y_i^*|$).

For instance, in a map search, choosing the next city by smallest straight-line distance to the goal uses this heuristic.

Forward and Backward Chaining

These are two inference methods used in rule-based (production) systems and Horn-clause knowledge bases to derive conclusions.

Forward Chaining (data-driven):

• Starts from the known facts in the knowledge base.
• Repeatedly applies rules whose premises (antecedents) are satisfied (modus ponens), adding their conclusions as new facts.
• Continues until the goal is derived or no new facts can be added.
• It is bottom-up and well suited when many conclusions follow from a few facts (e.g. expert/monitoring systems).

Backward Chaining (goal-driven):

• Starts from the goal (query) to be proved.
• Finds rules whose conclusion matches the goal, then recursively tries to prove their premises as sub-goals.
• Continues until sub-goals are matched against known facts (or the proof fails).
• It is top-down and well suited for proving a specific query (e.g. Prolog, diagnosis).

Example: Given rule If A and B then C, facts A, B. Forward chaining fires the rule to infer C. To prove goal C, backward chaining finds the rule with conclusion C and tries to prove sub-goals A and B, which are facts — so C holds.

Propositional Logic vs. Predicate (First-Order) Logic

Illustration: The statement "All men are mortal" cannot be captured by a single proposition in propositional logic, but in predicate logic it is written compactly as:

Thus predicate logic generalises propositional logic by adding objects, predicates, functions and quantifiers, giving far greater expressive power.

Semantic Network

A semantic network is a graphical (network-based) knowledge-representation scheme in which knowledge is represented as a graph of nodes connected by labelled directed edges (links):

• Nodes represent objects, concepts, or events.
• Links (arcs) represent the relationships between them — most commonly IS-A (subclass/instance/inheritance) and HAS-A / part-of / property relations.

It supports inheritance: properties of a general class are automatically inherited by its members, allowing efficient and intuitive reasoning. It is essentially a way to depict an associative network of meanings.

Example (described in words):

        Animal
          ^  (IS-A)            has --> covering: skin
          |
         Bird  -- has --> can: fly
          ^  (IS-A)
          |
        Sparrow --(instance-of)--> Tweety

• Bird --IS-A--> Animal
• Sparrow --IS-A--> Bird
• Tweety --is-an-instance-of--> Sparrow
• Bird --can--> Fly

From this network we infer by inheritance that Tweety is a Sparrow, which is a Bird, which is an Animal, and therefore Tweety can fly and is an animal — even though those facts were not stored directly on the Tweety node.