Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CST 381/411 Intelligent Systems

Fall 2022

HW 2

1. Missionaries and Cannibals (5 pts). 3 missionaries and 3 cannibals are on one side of a river, along with a boat that can hold at most 2 people.  As soon as there are more cannibals than missionaries in one place (including the boat) cannibals start to eat missionaries. We need to find a way to get everyone to the other side without ever leaving a group of missionaries in one place outnumbered by the cannibals in that place.  

For this problem the state space including transition between states is given below:

Note that all edges in this state space go in both directions. For a transition from ���_��� to ���_��� let

���(���_���, ���_���) = max {0, Change in the number of missionaries on the ‘start’ side of the river} 

Notice that change can be positive (number of missionaries on start size decrease) or negative (it increases). So for example change of the number of missionaries from state A to H is 3-2=1 and from H to A is 2-3=-1. Therefore ���(���, ���) = 1 while ���(���, ���) = max(0, −1) = 0. Define a cost of a transition (an edge in the state space) to be ���(���, ���) = .  Define also the heuristic for the problem to be  ℎ(���) = Number of cannibals that need to move from start side to the goal side.

a. (3pts) Describe the state space with Missionaries and Cannibals problem as a set of assignments that satisfy a set of constraints over variables: you need to give number of variables, domain of each variable  and the set of constraints that must be satisfied. Note ���_��� and it take valethat  constraints should be given as conditions on values of variables  (equalities, inequalities or combinations of both).

Hint: for example, number of missionaries on left bank can be describes by a variable ���_��� and it can take values 0,1,2,3m  

b. (1 pt) Is this an admissible heuristic? Prove or give counterexample

c. (1 pt) Is this a consistent heuristic? Prove or give counterexample  

2. (2 pts – 0.5 each) Give the name of the algorithm that results from each of the following special cases:

a. Local beam with 1 initial state and no limit on retained state.

b. Simulated annealing with T = 0 at all times (and omitting the termination test).

c. Simulated annealing with T = ∞at all times.

d. Genetic algorithm with population size N = 1.

3. [4pts] ��� missionaries and ��� > 3 cannibals are on one side of a river, along with a boat that can hold at most ��� = 2��� people, where 2 ≤ ��� < [⌉. As soon as there are more cannibals than missionaries in 2one place including the boat) cannibals start to eat missionaries. Find a way to get everyone to the other side without ever leaving a group of missionaries in one place outnumbered by the cannibals in that place. Define the problem formally.

1. (1pt) Give the description of the state space of the problem (not in words, but in formulas)  

2. (1pt) Define initial state and goal

3. (1pt) Describe transitions between states (by giving constraints that relate states at times ��� and ��� + 1 where ��� ∈ {1,2, …    

4. (1pt) Give appropriate admissible heuristic function for the problem. What are ���, ���, ℎ in ���(���) = ���(���) + ℎ(���) for your definition

4. Programming exercise -make-up [2pts] Modify the rewriting system search Jupyter NB program that is in week 2 folder named ‘direct BFS of the generated word by rewriting system’ so that it takes a text file in the following format as input. It contains as separate lines:

• Initial state

• Goal states (possibly more than one separated by space)

• Rewriting rules of the system. Each rule is in the format ‘premise, consequent’. Two rules are separated by a space.

Example of a file contents is given below: E

abbba babba

E,a a,ab a,ba b,bba b,bbba  

The following modifications should be made:  

• The data structure for the goal should now be either a set or a list

• The termination condition in the search routing should be changes as a membership in goal set (list)

• Input file must be parsed so that the rules dictionary for the call to search function should be created from the file

For help with string processing and with file input see in the Intro to Python Jupyter NBs folder