Artifial intellignece Note that all edges in this state space go in both directi

Question

Artifial intellignece

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 (, ) = 1 /1+(,) . Define also the heuristic for the problem to be () = Number of cannibals that need to move from start side to the goal side.

a. 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

1. Given the state space of Missionaries and Cannibals problem below: 3rm ac boat boat 3c

Explanation / Answer

First of all, I hope you are aware of Missionaries & Cannibals problem of AI. Still, we can go through it once before actually understanding the actions to solve the problem.

Hence the action sequence to solve the problem needs to be determined. There can be multiple solutions but we need to find the solution with minimum states.

The image uploaded for state space is not quite clear, still I will try to explain the solution using that.

State At any given point of time, defines the value of variables involved in a problem statement.

Here, three variables are present, Missionaries, Cannibals and Boat.

Constraints The constraints must be satisfied by each action w.r.t the values that it assigns to variables.

For this problem constraints are

Domain of variables The values that can be assigned to variables. Here, missionaries and cannibals can take values from {0,1,2} after applying the constraints.

Solution of the problem

** C-> Cannibals, M-> Missionaries, B-> Boat

Hence the Goal state is achieved.

Number of cannibals moved from start side to goal side :-

h(s) = 8

Bank A Bank B Initial State (3M,3C,1B) (0M,0C,0B) Step 1: (3M,1C,0B) send 2 cannibals (0M,2C,1B) Step 2 : (3M,2C,1B) (0M,1C,0B) Send one cannibal back Step 3 : (3M,0C,0B) send 2 cannibals (0M,3C,1B) Step 4 : (3M,1C,1B) (0M,2C,0B) Send one cannibal back Step 5 : (1M,1C,0B) send 2 missionaries (2M,2C,1B) Step 6 : (2M,2C,1B) (1M,1C,0B) send 1 missionary and 1 cannibal back Step 7 : (0M,2C,0B) send 2 missionaries (3M,1C,1B) Step 7 : (0M,3B,1B) (3M,0C,0B) send 1 cannibal back Step 8 : (0M,1C,0B) send 2 cannibals (3M,2C,1B) Step 9 : (0M,2C,1B) (3M,1C,0B) send 1 cannibal back Step 10 : (0M,0C,0B) send 2 cannibals (3M,3C,1B) Goal State

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.