2022 Final Examination (25th Batch)

Question 1

1 (a) Your company builds AI systems for autonomous vehicles. The Dhaka Cars Ltd. has given you a project to design an AI system for its new autonomous truck—DhakaTruck. The AI system should be responsible for making critical decisions on the road, such as avoiding obstacles and determining the best route to a destination. [7]

• i. Why do you think AI safety and ethics are important in the context of autonomous vehicle?
• ii. Identify and describe at least three potential ethical challenges that may arise with the use of AI in autonomous vehicles.
• iii. Propose at least two strategies or approaches that can be implemented to address the identified ethical and safety challenges.

Intelligent Agents and Environments

---

1 (b) The Turing Test, proposed by Alan Turing in 1950, is a test designed to assess a machine's ability to exhibit human-like intelligence. Describe the test and explain its significance in terms of Artificial General Intelligence. [7]

Overview of Artificial Intelligence

---

Question 2

2 (a) State the differences between local beam search and stochastic beam search. [2]

Informed Search and Heuristics

---

2 (b) Apply Hill-Climbing algorithm to the 8-puzzle problem for the initial state given below with your preferred heuristic function up to four iterations. [6]

$\text{Initial State:} \begin{bmatrix} 8 & \text{\_} & 6 \\ 5 & 4 & 7 \\ 2 & 3 & 1 \end{bmatrix} \quad \quad \text{Goal State:} \begin{bmatrix} \text{\_} & 1 & 2 \\ 3 & 4 & 5 \\ 6 & 7 & 8 \end{bmatrix}$

Heuristic Functions and Optimality

---

2 (c) Consider a genetic algorithm in which individuals are represented using a 5-bit string of the form $b_1 b_2 b_3 b_4 b_5$. An example of an individual is 001001 (or 00101) for which $b_1=0, b_2=0, b_3=1, b_4=0, b_5=1$. [6]

The fitness function is defined over these individuals as follows: $f(b_1 b_2 b_3 b_4 b_5) = b_1 + b_2 + b_3 + b_4 + b_5 + \text{AND}(b_1, b_2, b_3, b_4, b_5)$ where $\text{AND}(b_1 b_2 b_3 b_4 b_5) = 1$ if $b_1 = b_2 = b_3 = b_4 = b_5 = 1$; and $\text{AND}(b_1 b_2 b_3 b_4 b_5) = 0$ otherwise.

For the given initial population set $S = \{10101, 10001, 11001, 11100\}$:

• i. Select two entities with the highest fitness as the parent for the next generation.
• ii. Generate the population of the next generation by applying crossover at all locations.
• iii. Explain the importance of mutation in this given scenario to achieve maximum fitness.

Population-Based Approaches & Swarm Intelligence

---

Question 3

3 (a) Define the arc consistency problem in the context of Constraint Satisfaction Problems (CSPs). Suppose you have a relation $v(N, W)$ that is true if there is a vowel (one of: $a, e, i, o, u$) as the $N$-th letter of word $W$. For example, $v(2, \text{cat})$ is true because there is a vowel ("a") as the second letter of the word "cat"; $v(3, \text{cat})$ is false, because the third letter of "cat" is "t", which is not a vowel; and $v(5, \text{cat})$ is also false because there is no fifth letter in "cat". Suppose the domain of $N$ is $\{1, 3, 5\}$ and the domain of $W$ is $\{\text{added}, \text{blue}, \text{fever}, \text{green}, \text{stare}\}$. [7]

• i. Is the arc $(N, v)$ arc consistent? If so, explain why. If not, show what element(s) can be removed from a domain to make it arc consistent.
• ii. Is the arc $(W, v)$ arc consistent? If so, explain why. If not, show what element(s) can be removed from a domain to make it arc consistent.

Constraint Satisfaction Problems

---

3 (b) The graph below is a constraint graph for a CSP that has only binary constraints. Initially, no variables have been assigned. [7]

For each of the following scenarios, mark all variables for which the specified filtering might result in their domain being changed:

• i. A value is assigned to $A$. Which domains might be changed as a result of running forward checking for $A$?
• ii. A value is assigned to $A$, and then forward checking is run for $A$. Then a value is assigned to $B$. Which domains might be changed as a result of running forward checking for $B$?
• iii. A value is assigned to $A$. Which domains might be changed as a result of enforcing arc consistency after this assignment?

You decide to try a new approach to using arc consistency in which you initially enforce arc consistency, and then enforce arc consistency every time you have assigned an even number of variables. You have to backtrack if, after a value has been assigned to a variable, $X$, the recursion returns at $X$ without a solution. Concretely, this means that for a single variable with $d$ values remaining, it is possible to backtrack up to $d$ times. For the following constraint graph, if each variable has a domain of size $d$, how many times would you have to backtrack in the worst case for each of the ordering: $F-D-B-A-C-G-E$?

Backtracking and Local Search for CSPs

---

Question 4

4 (a) You are given the following knowledge base: [4]

• $a \leftarrow b \land c$

• $a \leftarrow e \land f$

• $b \leftarrow d$

• $b \leftarrow f \land h$

• $c \leftarrow e$

• $d \leftarrow h$

• $e$

• $f \leftarrow g$

• $g \leftarrow c$

• i. Give a model of the knowledge base.

• ii. Give an interpretation that is not a model of the knowledge base.

• iii. Give two atoms that are logical consequences of the knowledge base.

• iv. Give two atoms that are not logical consequences of the knowledge base.

Knowledge-Based Agents and Logic

---

4 (b) [5]

• i. Define propositional logic and its key components. Explain how propositional logic represents statements using logical operators and propositional variables. Consider the following propositional logic statements:
  • $P$: The sun is shining.
  • $Q$: It is raining.
  • $R$: The grass is wet.
• ii. Write the logical expressions for the following compound statements:
  1. "If the sun is shining, then the grass is wet."
  2. "It is raining, or the grass is wet, but not both."
  3. "The grass is wet if and only if it is raining."
• iii. Discuss the concept of logical equivalence in propositional logic. Define logical equivalence and explain how it is determined using truth tables or logical laws. Provide an example of two logically equivalent propositions.

Knowledge-Based Agents and Logic

---

4 (c) You are given the knowledge base $KB$ containing the following clauses: [5]

• $a \leftarrow b \land c$
• $b \leftarrow d$
• $b \leftarrow e$
• $c$
• $d \leftarrow h$
• $e$
• $f \leftarrow g \land b$
• $g \leftarrow c \land k$
• $j \leftarrow a \land b$

Show how the top-down proof procedure works for this example. Give all logical consequences of $KB$.

CNF Conversion and Resolution

---

Question 5

5 (a) What is subjective probability? Explain how conditional independence can be used to reduce uncertainty? [4]

Probabilistic Reasoning and Bayes Nets

---

5 (b) The Starfleet academy has decided to create a class of android students. 90% of these android students study hard for their exams. Out of the androids who study hard for an exam, 80% get an A. Out of the androids who do not study, only half get an A. Androids who study hard have a 75% probability of depleting their battery in less than a day. Androids who do not study hard have a longer battery life: only 10% of them deplete their batteries within the next day. [5]

• i. Draw a Bayes net describing the problem statement above.
• ii. You notice that your android has depleted its battery in less than a day. What is the probability that it will get an A on the exam it had yesterday?

Probabilistic Reasoning and Bayes Nets

---

5 (c) Give a description of MIN-MAX algorithm. Can we say that "Alpha-beta pruning" is a modified version of the minmax algorithm? Why? [5]

Minimax and Alpha-Beta Pruning

---

Question 6

6 (a) What is meant by inductive learning hypothesis? Using an example show how use of version space in the candidate elimination algorithm can be deemed as an improvement over the find-s algorithm in terms of concept learning. You may use the following table, where a robot predicts (Enjoy sport) based on the feature variables presented in the first 6 columns, if his master will go for some sport or not for your demonstration: [7]

Overview of Artificial Intelligence

---

6 (b) Your company The Dhaka Cars Ltd. is secretly designing next generation autonomous vehicles. Your chief ethics officer has identified the designed prototypes as either OK or NotOK. You are charged with building a decision tree classifier to predict the OK or NotOK as they are found using four predictive features: body, color, sensors and software version. [7]

• i. What is the initial entropy of the target variable decision?
• ii. Draw the four possibilities of an initial split on each of the four variables.
• iii. Among body, Color, #sensors and version, which variable will ID3 algorithm choose for the initial split? Using your answer in iii, draw the entire decision tree.

Overview of Artificial Intelligence

---

Question 7

7 (a) Consider the single-layer perceptron shown below. If $w_1=2$, $w_2=-4$, $w_3=1$, and $\varphi(v)$ returns $1$ when $v$ is non-negative and $0$ otherwise. [6]

• i. Calculate the output value $y$ of the unit for each of the following input patterns:

• ii. If the true class of pattern $x_1, x_3$ is zero and $x_2$ is one, perform backpropagation on the network with the learning rate $= 0.3$ for SSE as the loss function.

Overview of Artificial Intelligence

---

7 (b) Explain the scenarios where a single-layer perceptron fails to converge with an example. Propose a solution for such cases. [4]

Overview of Artificial Intelligence

---

7 (c) For the dataset given below, if $x$ works as feature and $y$ as output, find the equation of the least square regression line of $y$ on $x$. [4]

Overview of Artificial Intelligence