Artificial Intelligence Assignment

By Neetu

Roll no. – 24CS3932

Sem – 3rd

Bsc Computer Science (H)

 2

1. Give the Performance Measure, Environment, Actuators, and Sensors (PEAS) description for the

Automated Taxi Driver environment. Differentiate between the following:

• Fully observable vs. partially observable

• Deterministic vs. stochastic

• Episodic vs. sequential

• Static vs. dynamic

• Model-based agent and Goal-based agent

• Goal-based agent and Utility-based agent

Ans.

1) P = performance measure -

• Safety (no accidents)

• Follow traffic rules

• Minimize travel time

• Maximize passenger comfort

• Minimize fuel cost and maximize profit

E = environment –

• Roads, lanes, traffic signals

• Other vehicles & pedestrians

• Weather and road conditions

• Pickup & drop-off locations

A = Actuators –

• Steering, accelerator, brakes

• Gear control, indicator, horn

• Doors for passengers

 3

S= Sensor –

• Cameras, radar/LiDAR, GPS

• Speedometer

• Proximity sensors

• Microphone (passenger commands)

2) Difference between them

❖ Fully observable = Limited perception of surroundings

❖ Partially observable = Limited perception of surroundings

❖ Deterministic =predictable result

❖ Stochastic = Includes uncertainty

❖ Episodic = Each action independent

❖ Sequential= Future depends on previous actions

❖ Static = Environment does not change while reasoning

❖ Dynamic = Environment changes continuously

❖ Model-based agent = Maintains internal model

❖ Goal-based agent = Acts to achieve specific goal

❖ Utility-based agent = Chooses best among many goals

2. What are the differences between Recursive Transition Network (RTN) and Augmented Transition

Network (ATN)? Draw the RTN to implement the grammar given below. Show the derivation of the

sentence "Mary slept on the sofa" and also develop a parse tree using the following grammar:

S → NP VP

NP→N|DET N

VP→V|V PP
 4

PP→PREP NP

N → Mary |sofa

V →slept

DET →the

PREP →on

Ans. Recursive Transition Network (RTN)

• A graph-based representation of a context-free grammar.

• Each nonterminal is represented as a small finite-state network (a subgraph). Edges are labelled

with terminals (tokens) or calls to other nonterminal networks.

• No built-in mechanism for semantic tests or actions — purely syntactic.

• Useful for describing and implementing CFG parsing with recursion/calls.

Augmented Transition Network (ATN)

• Extends RTN by augmenting transitions or nodes with actions, tests, registers/variables, and

conditions.

• Can perform semantic actions (e.g., build parse tree nodes), check predicates, manipulate state

(attributes), or choose alternative paths based on context.

• Therefore more powerful — practical for natural language processing where context or

semantic checks are needed.

• ATNs can implement some context-sensitive behaviours via conditions/actions .

Derivation of the sentance

We show a leftmost derivation:

❖ S

❖ → NP VP (use S → NP VP)
 5

❖ → N VP (choose NP → N)

❖ → Mary VP (use N → Mary)

❖ → Mary V PP (choose VP → V PP)

❖ → Mary slept PP(use V → slept)

❖ → Mary slept PREP NP (use PP → PREP NP)

❖ → Mary slept on NP (use PREP → on)

❖ → Mary slept on DET N (use NP → DET N)

❖ → Mary slept on the N (use DET → the)

❖ → Mary slept on the sofa (use N → sofa)

3. Using the constraint satisfaction algorithm, solve the following cryptarithmetic problem:

BASE

+BALL

=GAMES

Based on the solution of the above cryptarithmetic problem, find the value of B+L+A+M+E.

Ans. Mapping of letters → digits

• G=1

• B=7

• A=4

• S=8

• E=3

• L=5

• M=9

B+L+A+M+E

Compute: 7 + 5 + 4 + 9 + 3 = 28
 6

4. Consider the following axioms:

A1: Rajesh likes all kind of food.

A2: Banana and Orange are food.

A3: Anything anyone eats and not killed is food.

A4: Madhav eats cashews and is still alive.

A5: Anyone who is killed, is not alive.

A6: Pankaj eats everything Madhav eats.

Express the above axioms into First Order Predicate Logic (FOPL) statements and convert them into
clausal form. Using resolution principle, prove that the statement "Rajesh likes cashews" is true.

Ans. Use constants rajesh, madhav, pankaj, cashews, banana, orange. Predicates: Food(x),

Likes(p, x), Eats(p, x), Killed(x), Alive(x).

1. A1: Rajesh likes all kinds of food.

∀y (Food(y)→Likes(rajesh,y))

2. A2: Banana and Orange are food.

Food(banana).Food(orange).

3. A3: Anything anyone eats and (that is) not killed is food.

∀x∀y (Eats(x,y)∧¬Killed(y)→Food(y))

4. A4: Madhav eats cashews and (cashews) is still alive.

Eats(madhav,cashews)∧Alive(cashews).

5. A5: Anyone who is killed is not alive.

∀z (Killed(z)→¬Alive(z))

6. A6: Pankaj eats everything Madhav eats.

∀y (Eats(madhav,y)→Eats(pankaj,y))
 7

We show a sequence of resolutions deriving the empty clause (contradiction) from the clauses

above together with the negated goal.

1. Use C4 with x := madhav, y := cashews and C5 (Eats(madhav,cashews)):

• C4: ¬Eats(x,y) ∨ Killed(y) ∨ Food(y)

• C5: Eats(madhav,cashews)

2. Use C7 (¬Killed(z) ∨ ¬Alive(z)) with C6 (Alive(cashews)):

• C7: ¬Killed(z) ∨ ¬Alive(z)

• C6: Alive(cashews)

3. Resolve R1 (Killed(c) ∨ Food(c)) with R2 (¬Killed(c)):

4. Resolve C1 (¬Food(y) ∨ Likes(rajesh,y)) with R3 (Food(cashews)), instantiating y := cashews:

5. Finally resolve R4 (Likes(rajesh,cashews)) with the negated goal C9 (¬Likes(rajesh,cashews)):

• Resolving on Likes(rajesh,cashews) yields the empty clause ⊥.

5. Differentiate between the monotonic reasoning and nonmonotonic reasoning. Give one example

each of the monotonic and nonmonotonic reasoning.

From experiments, it has been determined that P( B |A)=0.84, P(A) = 0.2 and P(B) = 0.34 Find the

probability P( A |B) of the event A when it is known that some event B has already occurred. Describe

how will you compute P(A| - B ) given only P(A) P( B |A), and P(B) ?

Draw the bayesian belief network for the given joint probability:

P(x 1 ,x 2 ,...,x 7 )=P(x 7 |x 5 ,x 6 )P(x 6 |x 3 ,x 4 )P(x 5 |x 4 )P(x 4 |x 2 )P(x 3 |x 2 )P(x 2 |x 1 ) P(x_{1})

Ans. (a) Compute P(A|B)

We use Bayes’ Theorem:

P(A∣B)=P(B∣A)⋅P(A)/P(B)

Given:

• P(B∣A)=0.84P
 8

• P(A)=0.2

• P(B)=0.34

P(A∣B)=0.84⋅0.2/0.34=0.168/0.34≈0.494

(b)Compute P(A|¬B)

Formula:

P(A∣¬B)=P(A)−P(A∩B)/1−P(B)

Where:

P(A∩B)=P(B∣A)⋅P(A)=0.84⋅0.2=0.168

Now:

P(A∣¬B)=0.2−0.168/1−0.34=0.032/0.66≈0.0485

(c) Bayesian Belief Network for Joint Probability

Given joint probability factorization:

P(x1,x2,…,x7)=P(x7∣x5,x6)P(x6∣x3,x4)P(x5∣x4)P(x4∣x2)P(x3∣x2)P(x2∣x1)P(x1)

From the structure:

• x1x_1x1 is the root

• x2x_2x2 depends on x1x_1x1

• x3x_3x3 and x4x_4x4 depend on x2x_2x2

• x5x_5x5 depends on x4x_4x4

• x6x_6x6 depends on x3x_3x3 and x4x_4x4

• x7x_7x7 depends on x5x_5x5 and x6x_6x6

9