Welcome! Log In Create A New Profile


State Spaces

Posted by dve83 
Announcements Last Post
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
State Spaces
February 12, 2011 03:21PM

struglling with state spaces here.

Take for example the vacuum word. The state space includes all possible states that can be reached from an initial state. WIth the vacuum word this is fairly easy: We have to take into account the location of the vacuum cleaner and the status of the LEFT / RIGHT location (dirty / clean. We have two actions namely move(direction) (left or rigth) and CLEAN / SUCK.

Now take the example from our assignment - and Id really like any input from other people here.

The Cannibal and Missionary story: We have inital state of 3C (3 Cannibals) and 3M (missionaries) on one side. We have actions Move(aPerson, aPerson) and Move (aPerson). Hence two actions, one which allows travelling of 1 person and one that allows travelling of 2 persons at once. We also have to take into account which side we are on (Iniital side of the river OR other side). And we have to take into account how many people are on either side. If we dont take into account which side we are on now, it makes thigns very easy - sop I am assuming we must take into account which side we are on. smile


Initial State
Side1 | Side 2

Side1 | Side 2

Option 2

Side1 | Side 2

Option 3
Side1 | Side 2

Option 4
Side1 | Side 2

Option 5

Side1 | Side 2

Ok this is the first 5 options from the initial state, Of which Option 2 and 5 must fail immediately because we have C > M.

Now my first question is: when drawing our tree like structure for the states -> do we simply stop at this point for option2 and 5 (and only continue with the rest?)
Second Question is: What happens when one of your steps involves for eg. moving from option 3 to a new state where we have

Side1 | Side 2

which is, in fact equal to option 4? Can we just indicate it with circular reference? (arrow towards option4)? or do you down further in the tree structure and redraw a similar state? Seems we dont have to follow perfect tree structure when drawing state diagrams here.. just so long as you indicate all things

Question 3: How do we keep track of what side the boat is on (ie. you have just moved from side 1 of the river to side2. Now you have to go back...Any specific way of doing this? Or do we just draw the next state keeping this in mind...?

sorry for typing a lot and asking possibly stupid questions... just thought id get some insight from other people as well.

Danie van Eeden
Anonymous User
Re: State Spaces
February 15, 2011 01:04PM
I did COS351D last year - the above question was asked in the final exam...

Hint - something like CCCMMM introduces postional information which means CCMMCM is actual another state to CCCMMM, but conveys the same information

State spaces are all the valid states - you can simply enumerate them all, against the M >= C rule

The transitions between states is what I think you are after, like the vacuum world, RIGHT, LEFT, SUCK changes from current to another state (or same state), you need to define your own RIGHT. LEFT, etc equivalent othe C & M problem....
Re: State Spaces
February 21, 2011 11:29AM
If I understand your questions correctly ....

My advice :-
Option 4 and option 5 don't make sense because the only thing that can happen is the single person crosses and single person comes back. I left those out. The only options you have is to take two persons across and bring one back.
As soon as you get a fail you stop that branch.
As for keeping track - you just have to do that yourself and assume that and draw the states after each single crossing. It is obvious which way you are going because there will be either one person or two persons in the boat. So on your arrow you can put CM or C say, to show who is crossing. Remember, when the boat is on one side, it doesn't matter how many there are. It's only after the boat leaves do you see what your state is and whether it is valid or a fail.
Hope this helps.

Why are there so many views but no contributions? Come on people, this is a discussion FORUM not a monologue. It's a way for people to exchange ideas and pick other people's brains. It doesn't matter if what you write is wrong. That's how we can learn from each other. Rant over.
Anonymous User
Re: State Spaces
February 22, 2011 08:34PM
On page 65 in the textbook it states for the Bucharest problem:
"Courses of action that don't reach Bucharest on time can be rejected without further consideration and the agent's decision problem is greatly simplified." Which answers your first question.

Why not just find a solution with your tree structure and only give that? There are more than one solution and I don't think we are required to give all of them.

"It is obvious which way you are going because there will be either one person or two persons in the boat." - There can be two people on the boat either way, so this will not necessarily give you an indication on what side the boat is on, but as Jo says you just have to keep track yourself.

Re: State Spaces
February 23, 2011 06:34AM
Thanks gerrit. But I think that if you take two people back on the boat, it is going to take a lot longer to get to the goal. It's like going back to the town you just came. if you don't get an extra person across on each out journey then you are not really making progress and the tree could become infinite.
Sorry, only registered users may post in this forum.

Click here to login