Fundamentals of Artificial Intelligence

(1)

Fundamentals of Artificial Intelligence

Laboratory

Dr. Mauro Dragoni

Department of Information Engineering and Computer Science Academic Year 2020/2021

(2)

Algorithms source code

page 02

 https://github.com/aimacode/aima-java

 Simplified and self-contained version of minimax on the laboratory website.

(3)

Exercise 6.1

page 03

 4-Queen problem

(4)

Exercise 6.1

page 04

 4-Queen problem

(5)

Exercise 6.1

page 05

 4-Queen problem

(6)

Exercise 6.1

page 06

 4-Queen problem

(7)

Exercise 6.1

page 07

 4-Queen problem

(8)

Exercise 6.1

page 08

 4-Queen problem

(9)

Exercise 6.1

page 09

 4-Queen problem

(10)

Exercise 6.1

page 010

 4-Queen problem

(11)

Exercise 6.1

page 011

 4-Queen problem

(12)

Exercise 6.1

page 012

 4-Queen problem

(13)

Exercise 6.2

page 013

 Scheduling activities

• Variables: A, B, C, D, E (starting time of activity)

• Domains: D_i = {1, 2, 3, 4}, for i = A, B, …, E

• Constraints:

o (B ≠ 3) o (C ≠ 2) o (A ≠ B) o (B ≠ C) o (C < D) o (A = D) o (E < A) o (E < B) o (E < C) o (E < D) o (B ≠ D)

 Draw the constraint network and find a solution.

(14)

Exercise 6.2

page 014

 Arc-consistency:

Given binary-constraint C_X,Y: D_X, D_Y are arc consistent (or 2-consistent) if ∀x ∈ D_X∃y ∈ D_Y s.t. 〈x,y〉 ∈ C_X,Y

 E.g.: D_A = {1, 2, 3, 4}, D_B = {1, 2, 3, 4}, and C_A,B = B < A

is NOT arc consistent as A = 1 is not consistent with C_A,B

⇒ use D’_A = { -, 2, 3, 4} and D’_B = {1, 2, 3, -}

(15)

Exercise 6.2 - Solution

page 015

 Constraints network

(16)

Exercise 6.2 - Solution

page 016

(17)

Exercise 6.2 - Solution

page 017

(18)

Exercise 6.2 - Solution

page 018

(19)

Exercise 6.3

page 019

 Consider the following binary constraint network:

• There are 4 variables: X1, X2, X3, X4

• Domains: D1={1,2,3,4}, D2={3,4,5,8,9}, D3={2,3,5,6,7,9}, D4={3,5,7,8,9}

• The constraints are o X1≥X2

o X2>X3 or X3-X2=2 o X3≠X4.

 Tasks:

a. Is the network arc-consistent? If not, compute the arc-consistent network.

(show the whole process of enforcing arc-consistency and not just the final network)

b. Is the network consistent? If yes, give a solution.

(20)

Exercise 6.3 - Solution

page 020

 Task (a)

No, it is not arc-consistent.

Enforce arc-consistency between X₁ and X₂: D₁ = {3, 4} D₂ = {3, 4}

X₂ and X₃ : D₂ = {3, 4} D₃ = {2, 3, 5, 6}

X₃ and X₄ : D₃ = {2, 3, 5, 6} D₄ = {3, 5, 7, 8, 9}

So the arc-consistent domains are

D₁ = {3, 4} D₂ = {3, 4} D₃ = {2, 3, 5, 6} D₄ = {3, 5, 7, 8, 9}

 Task (b)

X₁ = 4, X₂ = 4, X₃ = 3, X₄ = 9

(21)

Exercise 6.4

page 021

 Download “Problem 6.4 Text” from the laboratory website.

(22)

Exercise 6.4 - Solution

page 022

 Question 1

5 variables: AR-1, AR-2, MLR, CR, IWR 4 constraints:

1. IAR says ≤ 1 of 15-381, 15-681, and 19-601 can be assigned to the 5 variables.

2. BAR says ≤ 1 of 15-211 and 70-122 can be assigned to the 5 variables 3. OR says ≤ 1 of 21-484 and 70-311 can be assigned to the 5 variables

4. No double counting says if a variable is assigned to one variable it can’t be assigned to another variable

Initial domains:

AR-1: 15-211, 15-212, 15-381, 15-681, 21-484 AR-2: 15-211, 15-212, 15-381, 15-681, 21-484 MLR: 15-381, 15-681, 80-310

CR: 21-484, 70-122, 70-311 IWR: 15-381, 19-601

(23)

Exercise 6.4 - Solution

page 023

 Question 2

AR-1 = 15-211

AR-2 = 15-212

MLR = 15-381

CR = 21-484 CR = 70-122

VIOLATES BAR

CR = 70-311

IWR = 15-381 VIOLATES NO DOUBLE

COUNTING

IWR = 19-601 VIOLATES IAR

IWR = 15-381 VIOLATES NO DOUBLE

COUNTING

(24)

Exercise 6.4 - Solution

page 024

 Question 2

AR-1 = 15-211

AR-2 = 15-212

MLR = 15-681

CR = 21-484 CR = 70-122 VIOLATES BAR

CR = 70-311

IWR = 19-601 VIOLATES IAR MLR = 15-381

(25)

Exercise 6.4 - Solution

page 025

 Question 2

AR-1 = 15-211

AR-2 = 15-212

MLR = 15-681

CR = 21-484

IWR = 15-381 SOLUTION MLR = 15-381

MLR = 80-310

(26)

Exercise 6.5 - Homework

page 026

 Consider the 8 squares positioned as follows:

The task is to label the boxes above with the numbers 1-8 such that the labels of

any pair of adjacent squares (i.e. horizontal, vertical or diagonal) differ by at least 2 (i.e. 2 or more).

a. Write all constraints and draw the constraint graph.

b. Is the network arc-consistent? If not, compute the arc-consistent network.

(show the whole process of enforcing arc-consistency and not just the final arc-consistent network)

c. Is the network consistent? If yes, give a solution.