BSc CSIT (TU) Science BIT Artificial Intelligence (BIT252) – 4th Semester (Model) Question Paper 2079 Nepal

PEAS description of an autonomous taxi driving system

PEAS stands for Performance measure, Environment, Actuators and Sensors. For an automated taxi driver:

Types of task environments

1. Fully observable vs. Partially observable — If the agent's sensors give it access to the complete state of the environment at each point in time, it is fully observable (e.g. chess). If parts are hidden or sensors are noisy/missing, it is partially observable (e.g. an automated taxi cannot see what other drivers are thinking).
2. Single-agent vs. Multi-agent — A single agent acts alone (e.g. crossword puzzle), whereas in a multi-agent environment other agents affect the performance measure (e.g. taxi driving, chess).
3. Deterministic vs. Stochastic — In a deterministic environment the next state is completely determined by the current state and the agent's action (e.g. 8-puzzle). If there is randomness/uncertainty it is stochastic (e.g. taxi driving, where other vehicles behave unpredictably).
4. Episodic vs. Sequential — In an episodic environment each action is independent of previous ones (e.g. classifying parts on an assembly line). In a sequential environment current decisions affect future ones (e.g. chess, taxi driving).
5. Static vs. Dynamic — A static environment does not change while the agent deliberates (e.g. crossword). A dynamic environment changes with time (e.g. taxi driving). If the environment is static but the score changes with time it is semi-dynamic.
6. Discrete vs. Continuous — A discrete environment has a finite number of distinct states/actions (e.g. chess), whereas a continuous one varies smoothly over a range (e.g. taxi driving with continuous speed and location).
7. Known vs. Unknown — In a known environment the outcomes (or probabilities of outcomes) for all actions are given; in an unknown environment the agent must learn how it works.

AO* search

The AO* algorithm is a heuristic, best-first search used on an AND-OR graph, where a problem is decomposed into sub-problems.

• OR nodes: alternative ways to solve a problem — choose any one successor.
• AND nodes: a problem is solved only if all of its successor sub-problems are solved (linked by an arc).

It uses the evaluation function $f(n) = g(n) + h(n)$ but, unlike A*, it works on a graph that yields a solution sub-graph rather than a single path, and it propagates revised cost estimates back up the graph.

Example

Suppose the goal A can be achieved either by B (an OR branch) or by solving both C AND D (an AND branch).

            A
          /   \
       (OR)   (AND)
        B      C---D

• Cost via B = edge(A,B) + h(B)
• Cost via (C AND D) = edge(A,C) + h(C) + edge(A,D) + h(D)

AO* expands the most promising node, computes the costs of the two options, marks the cheaper option, and back-propagates the updated cost to A. The process repeats until a complete, cheapest solution sub-graph (with all AND children solved) is found.

Search for multiple-goal environments

A bidirectional / multi-goal best-first search, and more specifically the AND-OR graph search (AO*), works in environments with multiple goals because problem decomposition lets several sub-goals (AND nodes) be satisfied simultaneously. (Greedy/best-first and breadth-first style multi-goal searches can also handle several goal states.)

Four evaluation factors of a search algorithm

1. Completeness — Is the algorithm guaranteed to find a solution when one exists?
2. Optimality — Does it find the least-cost (best) solution?
3. Time complexity — How long does it take to find a solution (number of nodes generated)?
4. Space complexity — How much memory is needed to perform the search (maximum nodes stored)?

Why do we need Recurrent Neural Networks (RNN)?

Feed-forward networks treat every input independently and have no memory of previous inputs. We need RNNs because:

• Many problems involve sequential / time-series data (text, speech, video, stock prices) where the order and context of previous inputs matters.
• RNNs have recurrent (feedback) connections, so the output of a step is fed back as part of the input to the next step, giving the network a form of memory of past information.
• They can handle variable-length sequences and share parameters across time steps, making them ideal for language modelling, machine translation, speech recognition and sequence prediction.

How back-propagation minimizes the error

Back-propagation is a supervised gradient-descent learning algorithm that adjusts network weights to reduce the error between the predicted output and the target output.

1. Forward pass. Inputs are propagated through the network. Each neuron computes a weighted sum and applies an activation function:

2. Compute the error. Using a loss function such as mean-squared error:

where $t_k$ is the target and $o_k$ the actual output.

3. Backward pass. The error is propagated backward and the gradient of the error with respect to each weight is computed using the chain rule:

For an output neuron the error term is

and for a hidden neuron

4. Update the weights. Each weight is adjusted in the direction that decreases the error, scaled by the learning rate $\eta$:

5. Iterate. Steps 1–4 repeat over many epochs until the error converges to a minimum (or an acceptable threshold).

In an RNN this is extended to Back-Propagation Through Time (BPTT), where the network is unrolled across time steps and gradients are summed over all steps before updating the shared weights.

Natural Language Processing suffers from several kinds of ambiguity, where a word, phrase or sentence has more than one possible interpretation:

1. Lexical (word-level) ambiguity — a single word has multiple meanings or parts of speech. Example: "bank" (river bank vs. financial bank); "book" (noun vs. verb).
2. Syntactic (structural / grammatical) ambiguity — a sentence can be parsed in more than one way. Example: "I saw a man with a telescope" (who has the telescope?).
3. Semantic ambiguity — even with a fixed structure the meaning is unclear. Example: "The car hit the pole while it was moving" (what was moving?).
4. Anaphoric (referential) ambiguity — a pronoun or reference can point to more than one entity. Example: "Ram told Shyam that he passed" (who passed?).
5. Pragmatic ambiguity — meaning depends on context/speaker intention. Example: "Can you open the door?" (a question about ability or a polite request?).

An expert system is an AI program that mimics the decision-making ability of a human expert in a specific domain. Its development follows these phases:

1. Problem identification & feasibility — define the domain, scope and objectives, and verify that an expert system is appropriate and a human expert is available.
2. Knowledge acquisition — the knowledge engineer gathers domain knowledge (facts and heuristics/rules) from human experts, books and databases.
3. Knowledge representation — represent the acquired knowledge in a formal form such as IF-THEN production rules, semantic networks, frames or logic, and store it in the knowledge base.
4. Design of the inference engine — build the reasoning component that applies the rules to facts (using forward or backward chaining) to draw conclusions; add an explanation facility and user interface.
5. Prototype development — implement an initial working system using a shell or AI language (e.g. CLIPS, Prolog).
6. Testing, validation & verification — test the system against real cases and expert judgement; refine the knowledge base to correct errors.
7. Implementation & maintenance — deploy the system for end users and continuously update the knowledge base as the domain evolves.

The core components produced are the knowledge base, inference engine, user interface, explanation facility and knowledge-acquisition module.

A Genetic Algorithm (GA) is a search/optimization technique inspired by natural evolution. It evolves a population of candidate solutions (chromosomes) using three main genetic operators:

1. Selection (Reproduction) — chooses the fitter chromosomes from the current population to act as parents for the next generation. Common schemes: roulette-wheel selection, tournament selection and rank selection. Fitter individuals have a higher chance of being selected.

2. Crossover (Recombination) — combines genetic material of two parents to produce offspring, exchanging sub-strings of the parents. Types include single-point, two-point and uniform crossover. Example (single point):

   Parent1: 1011 | 010      Child1: 1011 | 101
   Parent2: 1100 | 101      Child2: 1100 | 010
   

3. Mutation — randomly flips one or more bits (genes) of a chromosome with a small probability. It maintains genetic diversity and prevents premature convergence to a local optimum. Example: 10110 → 10010.

Some GAs also use an Elitism operator, which carries the best individual(s) unchanged into the next generation, and an encoding/fitness-evaluation step. Together these operators iteratively improve the population toward an optimal solution.

Representation in predicate logic

Let the predicates be: $Living(x)$, $Animal(x)$, $Plant(x)$, $Bark(x)$, $Dog(x)$.

1. $\forall x\,[\,Living(x) \Rightarrow (Animal(x) \lor Plant(x))\,]$ — all living things are animal or plant
2. $\forall x\,[\,(Animal(x) \land Bark(x)) \Rightarrow Dog(x)\,]$ — all animals who can bark are dogs
3. $Living(Puppy)$ — Puppy is a living thing
4. $\lnot Plant(Puppy)$ — Puppy is not a plant

Goal: show $Bark(Puppy)$.

Note: The premises as stated let us prove that Puppy is an animal. To conclude that Puppy can bark we also use the implicit fact that a dog can bark / Puppy is a dog, i.e. $\forall x\,[\,Dog(x) \Rightarrow Bark(x)\,]$ (or that Puppy, being a young dog, barks). The derivation below shows Puppy is an animal and then uses this to reach $Bark(Puppy)$.

Derivation using rules of inference

Hence, by Universal Instantiation, Modus Ponens and Disjunctive Syllogism, it is proved that Puppy can bark.

Depth-First Search (DFS) and Breadth-First Search (BFS) are uninformed graph/tree traversal strategies.

Here $b$ = branching factor, $d$ = depth of the shallowest solution, $m$ = maximum depth of the tree.

The Turing Test

The Turing Test, proposed by Alan Turing (1950), states that a machine is considered intelligent if a human interrogator, communicating through text only, cannot reliably distinguish the machine's responses from those of a human.

Is it sufficient? — Justification

In my opinion, the Turing Test is not fully sufficient to test true machine intelligence:

1. Tests imitation, not understanding — it only checks whether a machine can mimic human conversation, not whether it actually understands meaning (Searle's Chinese Room argument shows symbol manipulation ≠ understanding).
2. Behaviour-only / limited scope — it judges only linguistic behaviour and ignores other facets of intelligence such as perception, physical interaction, creativity and learning.
3. Can be fooled (deception) — chatbots have "passed" by using tricks, evasion and small talk rather than genuine reasoning, so passing it does not prove intelligence.
4. Anthropocentric — it measures human-likeness rather than intelligence itself; a highly intelligent machine that behaves non-humanly would fail.

However, it remains a useful and historic benchmark for conversational AI. Therefore, while the Turing Test is a valuable indicator, it is not a complete or sufficient measure of machine intelligence; richer tests (perception, reasoning, learning, embodiment) are also needed.

Definition of an Agent

An agent is anything that perceives its environment through sensors and acts upon that environment through actuators. A rational agent selects actions that maximize its expected performance measure. The mapping from percept sequences to actions is its agent function. Examples: a human (eyes/ears = sensors, hands/legs = actuators), a robot, a software bot.

Heuristic function of A* search

A* is an informed (best-first) search algorithm that finds the least-cost path from a start node to a goal. It selects the node with the lowest value of the evaluation function:

where

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

Properties of the heuristic $h(n)$

• Admissible — $h(n)$ never overestimates the true cost to the goal ($h(n) \le h^*(n)$). Admissibility guarantees A* finds the optimal solution.
• Consistent (monotonic) — for every node $n$ and successor $n'$: $h(n) \le c(n,n') + h(n')$. Consistency guarantees A* is optimal even with graph search.

Example: in route finding, $h(n)$ can be the straight-line (Euclidean) distance from a city to the destination, which never overestimates the actual road distance, so it is admissible.

Semantic Network

A semantic network is a graphical (network) form of knowledge representation that represents knowledge as a set of nodes connected by labelled directed edges (arcs).

• Nodes represent objects, concepts, events or entities.
• Arcs (links) represent the relationships between them.

Common relations are:

• IS-A (subclass) — class/sub-class hierarchy, supports inheritance.
• AKO / INSTANCE-OF — an object is a member of a class.
• HAS-A / property links — attributes of an object.

Knowledge is expressed by drawing these nodes and relations; inheritance lets sub-classes/instances automatically acquire the properties of their parent classes.

Example

Representing "Tweety is a bird, a bird is an animal, and a bird can fly":

   Animal
     ^
     | IS-A
   Bird ----can----> Fly
     ^
     | INSTANCE-OF
   Tweety

From this network we can infer (by inheritance) that Tweety is an animal and Tweety can fly, even though these facts were not stated directly. This makes semantic networks an efficient, easy-to-visualize way to store and reason about related knowledge.

Alpha and Beta in the Min-Max algorithm

In alpha-beta pruning (an optimization of the Min-Max algorithm for two-player games), two bounds are maintained while traversing the game tree:

• Alpha (α) — the best (highest) value that the MAX player is guaranteed so far along the path to the root. It is the lower bound of possible solutions; α starts at $-\infty$ and only increases.
• Beta (β) — the best (lowest) value that the MIN player is guaranteed so far. It is the upper bound; β starts at $+\infty$ and only decreases.

Whenever α ≥ β, the remaining branches at that node are pruned (cut off), because they cannot influence the final decision. This reduces the number of nodes evaluated without changing the result.

Script for "shopping at a department store"

A script (Schank & Abelson) is a structured knowledge representation of a stereotyped sequence of events.

• Script: SHOPPING (at a department store)
• Roles (actors): Customer (C), Salesperson/Cashier (S)
• Props (objects): Goods/items, money/card, shopping cart/basket, bill/receipt
• Entry conditions: Customer needs goods; customer has money; store is open
• Results: Customer has the goods; customer has less money; store has more money

Scenes (sequence of events):

1. Entering — Customer enters the department store and takes a basket/cart.
2. Browsing/Selecting — Customer walks through aisles and selects the required items.
3. Billing — Customer goes to the counter; the cashier scans the items and prepares the bill.
4. Paying — Customer pays in cash or by card; the cashier hands over the receipt.
5. Leaving — Customer collects the goods and exits the store.