I am looking for a good second hand text book for this module. Have registered this module for 2013 first semester. Past tutorial material would be appreciated as well.

sedeya@gmail.com, 0795801661

Thanks]]>

I could not complete-I don't think I will make it on this module, I'll probably have to wait for June next year- there were so many short theory questions that I didn't answer and you can not guess on questions like those ones that costs me a lot of marks. My year mark was quite high, but I don't think it will help me that much, but I do have a bit of hope if I can get 90% of what I wrote, I left a lot of spaces especially on theoretical questions because I didn't want to waist time writing wrong answers because

Would any1 like to do an online study group to come up with the answers to the past exams?]]>

a tut 101 would also be nice

Thanks

cfrauenstein@gmail.com

0826537281]]>

4.1

a) Local Beam search generates all successors of k initial states, then choosed the best K successors over all results and starts again. Until goal is generated.

So if k = 1, we generate the successors of 1 state, choose the best and go again. The question asks which search algorithm results from each of these

Looks like normal Hill Climbing to me (current state has successors both sides of it and we choose the best 1 and go again from there).

Or perhaps UNIFORM COst search _ which is breath first with a priority queue - thus expanding all sucessors and choosing the brest 1 (best node cost). This sounds like the best answer.

b) Local beam search with 1 initial state and no limit on the number of states retained. So we have 1 state and generate all successors, then we choose the best 1 and go again (without worrying about memory usage).

Thus is looks like were looking for a very inefficient algorithm. Cant be Normal Breadth First (it doesnt choose the best path), and cannot be Depth First (it doesnt store a lot of nodes only O(bm)). I woudl once again choose Uniform Cost Search (generates all nodes at each level, and chooses the best 1).

c) If T = 0, we will most likely not easily allow bad moves (we are already within some crevice (global minimum) which we dont really want to get out of). SO all moves are small and precise. I have no clue further.

d) If t = infinity. We allow al sorts of random moves. Sounds very much like stochastic hillclimbing, but allowing downhill moves. I would choose Random Restart Hill CLimbing - why? It generates random initial states (will eventually generates the goal state). Hence jsut as random as Simulated annealing with T = infinity.

e) Genetic Algorithm with population size = 1. The fitness function would result in only 1 item to choose, which would have to reproduce with itself...The crossover point would be chosen and the first and last parts of the string would just be swapped around. Then we would have a random mutation of 1 of the digits. Basically we are just arranging and randomly changing a digit.

What kind of search algorithm? I have no idea.

Your inputs much appreciated.]]>

Robot starts in the middle of a maze and can move N,S,E,W. Initially its facing N. IT can move a distance d forward, but will stop when it hits a wall.

a) Formulate the problem. How Large is the statespace?

I assume a grid like below were X = walls and # = tunnel and E = exit.

States: Each state is (i,j,d) where i and j is the position (where applicable) of the current location (i,j e 1..6) and where D = {N,S,E,W}.

Initial State = (3,3,N)

Actions:

a) Turn(d) where d is the new direction

b) Move(d) where d is the number of cells to traverse. D will always be Max(d, and available cells until we reach a wall)

Goal State = (1,5)

Transition Model: THis is the states, initial state (as defined above) and die successor function.

Successor Function can be 1 of two:

Successor(i,j,d) = Result(In(i,j,d), Turn(d)) = In(i2,j2,d2) where i2, j2 and d2 are the new values

OR Successor(i,j,d) = Result(In(i,j,d), Move(d)) = In(i2,j2,d2)

Path Cost: Cost is value of 1 per move/action

I dont think I should draw the state space unless asked.

E

xxxx#x

x####x

xx#xxx

How large is the state space? Well for each state we can move the direction (4 actions possible). Also for each state we can Move (1 action). Assuming we turn and then move which would be a good choice (because after we move we will have stopped somewhere, so we must turn), we will have a move action and then posisble 4 directions for each state. Also we must consider each possible state, that is Move(1), Move(2) etc in all directions.

Thus for each state we have a Move and Turn of 4 directions. Thus 5 actions for each state. I think Size = 4^n + n where n = number of states. (however on second thought the +n could greatly depend on the number of blocks available for each Mode(d) where d could be {1,2,3,4,5,max avail.}

B) Now we only need to turn at the intersection of 2 or more corridors. Update the above definitions and State space size.

States and Initial state stay the same. Actions are changed to MoveUntilWall in stead of Move(d). We still have Turn(d). There is no way of knowing if we are at an intersection (without trying to move and checking the result). Thus I say, Move until we stop and choose a direction. The size of the statespace will drastically diminish as we dont have each state to account for (but only the number of moves). THus still 4^n + n but here N is the number of MoveUntilWall actions.

C)From each point in maze we can move in any four directions until we hit a turning point. this is the only action we need to take.Reformulate and "How do we keep track of direction / orirentation"?

Now actions are just Move(d) where d is direction. We will move until we hit something (wall). 4^n only? where n is max number of levels in the tree until we reach a goal. Orientation? = The robots orientation will be whatever the last direction was in which we moved. If last action was Move(N), then the orientation will be N. If the move failed (ie. we could not move N) tyhen I assume we orientated N and stayed that way.

d) List three abstractions from the real world: 1) Robot doesn't have to worry about moving its legs, we abstracted the mechanical details, 2) Robot doesn't have to worry about breaking down (abstracted various external factors) 3. Robots doesnt have to worry about the maze changing]]>

c4 c3 c2 c1

S E N D

M O R E

M O N E Y

very time consuming and less easy to solve.

I choose C4 and M = 1.

Then need to choose c3. If We choose wrong here, It takes very long to realize it (for exam purposes this is critical - and I feel I might be missing something here, because in order to select the value that is least constraining, we need to first assign the value and check its results)

suppose I choose c3 = 0,

the S + M = 0 can be completed by S = 9. Thus 9 + 1 = 10 carry 1.

if C3 = 1, then 8 + 1 + C3 = 10 carry 1

there arent other options because we cannot have O = 1 and cannot obtain a value of 12 in any way.

Now which one to choose?

I chose C3 = 0, and now we need to choose c2. I can see this needs to be 1 else E = N (because O = zero)

Now we need to choose C4, but I can find no intelligent way of filling this without still having to then first check all its results. (hoping you might have some advice here)

I have tried just going on by selecting E, but this also leads to numerous iterations. Now in the back of mind is this: If I can find no solution, then I need to backtrack to where I chose C3=0 and rather try C3 = 1 - which then results in the same exercise again.

Based on the algorithm in R&N, the choosing of Variables is quite easy, choosing the value requires us to check how the other variables are constrained as result (how much there domain shrinks). Less us assume such assignment restricts 2 variables x and y to domains (1..5) and (2..6), then we would have to fill these as well until we find a NO solution and then backtrack up the tree.

Any hints?]]>

Quote

The question says that jackals must not outnumber coyotes at any time:

Some scenarios:

Start state: Assume that one jackal crosses. There will be one jackal on the opposite riverbank. A case will exist where jackals outnumber coyotes, so this cannot be correct.

Start State: Assume that one coyote crosses. There will be three jackals and two coyotes on the first riverbank. A case will exist where jackals outnumber coyotes, so this cannot be correct.

Start State: Assume that both a jackal and a coyote cross. All okay in this step. Next step, and a similar problem happens as mentioned above.

I my mind there is no way that this is feasible?

Any thoughts??

Thanks

MIke

(2012-05-23 22:59)

Now see below:

]]>Quote

There is a problem with the way this question is and was worded in the exam which changed the meaning completely!!! "Three jackals and three coyotes come to a river. There is a boat on THEIR side of the river...." This leads me to believe that all the animals are on the same side of the river. But the link below shows that this is not the case!!!

http://answers.yahoo.com/question/index?qid=20100307182303AA3ebpk

(2012-05-23 23:10)

Seem to have misplaced my hard copy and I cant seem to access the download version. Please can someone mail the pdf copy to me.

vncoolness@yahoo.com

I will be more than happy to share any material I have including past papers.

Thanks in advance]]>

I am struggling with the concept of resolution.

I understand that it applies to both propositional logic and fist order logic. I also understand that all first order logic needs to be converted to clause form (ie. remove implications, move Negation inwards (and adjust E to A and A to E), remove Existential qualifiers by using skolem functions. Remove universal quantifiers, and distribute to get () ^ () ^ () form of expression.

Now we are asked to prove G from our EXPRESSION. Hence we assume NOT G and try to see if we get a FALSE / NIL via resolution. For this we need to choose two clauses and resolve the negations inside it.

I have done some extra browsing on the internet - and will have to do some more reading in our book - but it seems linear resolution is the key.

We have from our previous exam paper:

1. Smoke(x) V ~Party(x) V Happy(x)

2. ~Single(y) V Party(Y)

3. Single(john)

4. ~Smoke(John)

5. ~Happy(Z) V Exciting(Z)

6. ~G: ~Exciting(W)

Thus i start with goal

Resolve G with 5 (only thing containing exciting) and we get

7. ~Happy(W) (i'm never sure which way around the substitution should go, but this seems correct to me). Lines 6 and 5

Now I resolve 7 with something from the KB (line 1)

8. Smoke(w) V ~Party(w)

Now I resolve 8 with something from KB (either 4 OR 2). I don't think I can resolve with 4, because I cannot replace JOHN with variable.

if I resolve with 2 I get : 9: ~Single(w) V Smoke(w)

Now I resolve 9 with something. I cannot resolve with 3 or 4 (it contains constants).

Where Am I going wrong?

Many thanks for your reply.

Danie]]>

I get the feeling we only have to choose 1 of the decision trees in the answers. Ie. we pick an order and draw the decision tree -> then simply by consolidating nodes that have the same value in the same branch.

The question does not state to draw possible combinations.

correct?

Danie]]>

Looking at the solutions to Assignment 3 we have roughly 12 pages as an answer to the decision tree question. Worried about the time it takes to do this and the chances of making mistakes through the process.

My summary on the concept (for those who need another perspective / who would like to comment and correct me)

1. Start with the whole example set and define S = [number for each category eg. 5l,3m,6h]

ie. we have a total of 14 values, of which 5 are low, 3 are medium and 6 are high

2. Calculate the Entropy for the Complete set defined as S (log is actually log base 2)

- (4/14 log 5/14) - (3/14 log 3/14) - (6/14 log 6/14) = 1.531

Now we determine the gain of each of the other attributes still left

3. For each attribute (eg here will be Credit History)

a) Define it in terms of the possible values for S where S = [5l,3m,6h] as defined above

Thus we have: 3 possible values for Credit History (bad, good, unknown)

- in terms of S's possible values, for Bad Credit History we will have 0 Low, 1 Medium and 3 High.

Thus for bad: Sb = [0l, 1m, 3h] Notice that it contains only 4 out of the 14 values (4/14)

Also, Sg = [3l,1m,1h] (5/15 values)

Su = [2l,1m,2h] (5/14 values)

We calculate Entropy for each of these - why? cause we want to deduct it from entropy of the set S to get the information GAIN.

Entrypy(Sb) = -(0/4 log 0/4) - (1/4 log 1/4) - (3/4 log 3/4) = 0.811

E(Sg) = 1.371

E(Su) = 1.522

Now Gain = E(S) - 4/14(E(Sb)) - 5/15(E(Sg)) - 5/15(S(Su)) = 0.266

This is the information gain for the first attribute. NOw we do it for the other three and pick the highest valued attribute.This is our first node. (InCOME)

b) Now notice that INcome in turn has three possible values. Each of these will form a branch to the next level in your tree. Thus for each of these

you will have to decide the next node. Thus for each of the 3 possible values, filter out all lines that aren't relevent (ie.start with value <R15k and work with those lines only - there are 4)

Now you again define S. S = [4H]. Because we only have 1 type of value, this will be the result of this branch.

second take the value R15k - R35K

Filter out all irrelevant lines.

We have to value types of our goal node (ie. 2x High and 2x Medium).

Define S = [2m, 2H]

Get Entropy (S) = -(2/4log2/4) - (2/4 log 2/4)

Now for each of the left over attributes (Credit History, Debt, Collateral), find its entropy and information gain. Pick the best 1 and use that as the next node in your tree

eg.

Credit History: For unknown we have 1 High and 1 Medium goal value Su = [1h, 1m] Fraction of total S = 2/4

For Good we only have 1 Medium goal value Sg =[0h, 1m] Fraction 1/4

For Bad we have 1 High goal value Sb = [1h, 0m] Fraction 1/4

Work out eaches entropy eg(unknown = - (1/2 log 1/2) - (1/2 log 1/2))

Then deduct it from entropy of S (with each attribute as a fraction)

Pick the highest gain and insert the node in your tree.

The moment your example list gets filtered and ends up with a single goal value (also not that if you end up with a single line - you will always have 1 goal value), then just insert the goal value as the node in your tree. The moment you have more than 1 optio for a goal value, you need to do the calc above.

Dan]]>

http://www.trueshift.za.net/Files/summaries/Sum_Exam_cos3751_chp3.pdf]]>

Anyone who has the past papers for this module can you please forward them to me at sugerbunny@gmail.com.

thank you.]]>

constraints are

ALLDIFF

the four constratints regarding the carry over digits (if applicable)

and no leading zeros

They ask us to solve the cryptarithmic puzzle in image 6.2.

My thoughts are this:

choose the first variable as the one with the highest degree of constraints (thus variable O)

choose the value to insert into this variable by selecting the variable which is least constraining.

our goal here is to find the first solution, not all solutions.

thus backtracking means that: when I get to a chosen variable that has no legal values, I must backtrack to the previous variable and select a different value for it and then try the next variable again.

forward checking means that: when I fill a variable with value, I remove any illegal values from the next variables. If any of these variables left then have an empty domain, there exists no solution - thus we backtrack again.

Now my question:

Im setting up a grid like on page 218 of R&N. Ive got the six variables, which will all have an initial domain of {0 1 2 3 4 5 6 7 8 9}. Step one needs to select a value- how? -> the only method of obtaining the least constraining value is to set up this table / grid and work out the effects of all 9 assignments of the first variable. Thus a) I take assignment of value1 to variable O. b) I check the constraints and update the domains of the other variables.

Seems like a hell of a job to check everything. PLUS.. how far do you go. I give an example.

I take into account that I am only summing two rows, so the carry over wont be more than 1. (in order to get a carry over of 2, we need to get above 20 - which you cant becuase 9+9+1 = 19 = max;

let take for example: setting O = 2, this results in R being 4 automatically (the only value for the domain of R). This means that T + T must give you 2 one some way. There are two ways - with and without a carry digits. Without the carry digit, you can only get T + T = 2 by having T = 1. With the carry digit you need to find something that adds to 11 first, then we add the carry digit and get to 12. Thus T + T = 2 carry 1. However, I can find no such value (nothing equal to each other, and added to each other will give 11 because 11 mod 2 <> 0).

So okay if O=2, then R = 4 and T = 1 OR t = 6 (6+6=12 ; thus 2 carry 1)

HOWEVER, T cannot be 1. Why? Because if T were 1 then 1+1=2 but we would have no carry digit to the next column, THUS we would have F = 0 which is not allowed (not allowed to have leading zeros).

Are we suppose to go at it in this way? This means that for variable O we check all possible assignments to get the least constraining value. And I'm guessing there might be two values which constrain other equally.. what then (i guess we take the one with the highest degree of constraints as the tie breaker). (keeping in ming that if one of the domains become empty, the solution cannot be found, and we simply skip that assignment)

your thoughts and input appreciated.]]>

Q1: Just wondering about the definition of a Search Node, cant find the formal definition anywhere. However I would assume it is a node within the search tree corresponding to a state in the environment.

Q2:

a) Mathematical notation? Are there good examples of how to formulate this? The state space contains all reachable states (by sequence of actions): How do you define the statespace mathematical notation if you need to include states, actions and the transitional model?

b) Successor function - how much detail should we provide here? The successor returns the next state based on the current state / function. Thus result := GetSuccessor(aCurrentState, aAction);. This seems to trivial... should we be providing the body of the function in pseudo code as well..?

Question 3:

My understanding: In order to spend as little time as possible, we need to handle the people that have a long waiting time as little as possible. Meaning: we need to take them across only once. This means that the optimal solution would be to take someone across together with D. D will serve as the main torch carrier - as we will always wait only 1 minute / unit when returning across the bridge to the LEFT. Hence D takes someone (X) across at the cost of X and returns at a cost of 1. Then he takes someone new across (Y) at the cost of Y, and returns at a minimal cost of 1. We use D as the torch carrier as any other person would cost more on the return trip. This also results in all other people (A,B,C) to make the trip only once and thus their cost being minimal. The optimal path would be D&A go right, D goes Left, D&B go right, D goes left, D and C go right. Thus total minimal cost = 10 + 5 + 2 + (1 + 1) = 19.

Now, when we need to graphically represent the state space, there a a multitide of sequencial states - in actual fact I think 108 distinct states (using nCr x nCr x nCr etc etc). I assume we only need tod rsaw the first 2 -3 levels of this state space diagram. Your thoughts..

Many thanks.

Danie]]>