CSS 455 Scientific Programming

CSS 455 Scientific Programming

Machine Problem #2 MP2

Problem Solving using Gauss Seidel Method for Systems of Linear Equations

Rats in a Maze[i]

Deadline: for full credit - 11:45 PM, Sunday, February 12.
for 75% credit - up to 24 hrs late

for 50% credit – up to 48 hrs late

Changes made since original posting are in blue.

Specification. The overall problem here is to provide a Matlab program for a psychologist is testing whether or not rats can learn. A psychological experiment which is used to test whether rats can learn consists of (repeatedly) putting a rat in a maze of interconnecting passages. At each intersection the rat chooses a direction and proceeds to the next intersection. Food is placed at one or more of the exits from the maze. If the rat learns, then it should get food more

frequently than would result from random decisions. The computer program provides the random probability from each cell that the rat will find food. The “simple case” for this problem is essentially the one you ran in a HW3 assignment:

Consider a small 4 rows x 5cols demo problem of the rat maze. The maze is given below with a set of probabilities of finding food on the perimeter:

XX	0	0	0	XX
1	P₂₂	P₂₃	P₂₄	0
1	P₃₂	P₃₃	P₃₄	0
XX	0	0	0	XX

The corner cells are inaccessible and irrelevant. The exits with “1” have food in them, and the ones with “0” do not. The edge cells are all exits from the maze. The probability of success for any interior cell is given as the average of its four neighbors:

There is one equation like this for each internal cell (6 equations here). This system of equations for the probabilities for a system of linear equations that can be solved in various ways.

Base Case. Because this is a sparse system and we intend to run large cases, you are to use the Gauss Seidel iterative method. This is covered in ch 7 of Turner and has been the subject of the HW3a problem. The detailed specification of the first-phase of the program is as follows:

Write a Matlab program that asks the user for the dimensions of the maze (# of rows and # of columns) and the positions (all on the perimeter) of exits with food and those without.
For each interior cell, the program is to calculate using Gauss Seidel iteration the a-priori probability of a rat starting there and ultimately finding food. P=1 for 100% probability and P=0 for zero probability.
The program is to be explicitly coded (not reliant on a library method for Gauss Seidel) and should have one equation in the system for each interior cell in the maze. The equation is given above.
Initial guesses do not need to be elaborate for this problem, but should be under the control of the user (setting them in some way through input). Uniform guesses may work fine.
The user should be asked for a absolute tolerance of convergence for the set of probabilities.
In addition to the definition of the problem, the output should report the number of iterations required, the tolerance achieved, and the time required for solution..
On output, the user should be presented with a table of probabilities that is similar to the sketch I have above. Its layout is to mimic the maze being modeled, so as to make it easier to interpret.

Runs to be Reported

Base case.

1. Provide properly labeled output for the case of 8 rows and 7 columns using the pattern of food shown in the diagram above.

Refinements and Extensions. After you have the base case running and tested, you are to extend it . In each of the following cases, the program should add these features without subtracting the ones you introduced in the base case. Each number below is an additional case to be reported:

2. Run the basic rectangular grid for a wide range of maze sizes (n x m) to determine experimentally how the time to convergence and the number of iterations varies with grid dimension. You should achieve dimensions of at least 130 rows and columns in this process. This analysis should indicate experimentally how the time of calculation varies with dimension of the system of equations. #2 does not involve modifying the eqns of #1.

3. Add diagonal passages, so that the rat can go diagonally with the same probability as to the four directions above. For example , the rat could go from cell (3,3) to cell (2,4) in addition to the four in the simple problem: (2,3), (4,3), (3,2), and (3,4). This rat could also go to (2,2), (4,4) and (4,2) . The probability of cell (3,3) is now the average of the probabilities for 8 neighboring cells. The corner cells of the maze can now be reached, but they are to be set to “no food.” This involves modifying the equations..

4. Now working from the simple rectangular grid (no diagonal moves), make a model in which all moves are not equally probable. The probability of a certain move will depend upon the direction of the rat at that time and will be different for the four available directions.

a. For example, if a northbound rat is in cell (2,3), then there are different probabilities that the rat will move forward to cell (1,3), turning to the right to cell (2,4), turning to the left to cell (2,2), or reversing direction to cell (3,3). Instead of each direction being weighted equally (25%) as in the base case, each of the directions has a different weight.

b. The probabilities for neighboring cells would be weighted differently for different orientations of the rat. An eastbound rat in cell (2,3) would have forward probability to cell (2,4), right turn to cell (3,3), left turn to cell (1,3), and reverse to cell (2,2). That means there are four different probabilities for each cell, depending on the orientation with which the rat is dropped into it.

c. The user will provide this model with a set of four probabilities for the rat to: move ahead, turn right, turn left, or turn around in reverse. These can be different, must add up to unity, and can be individually zero. For example, if rats cannot turn around, then the reverse probability becomes zero, and the other three must sum to unity. Note as a test for this model, setting all probabilities equal to 25% should duplicate the base case.

d. Produce a nicely labeled output for the (8 x 7) case with the following probabilities: reverse (0), and all other directions equally probable.

e. Produce a nicely labeled output for the (8 x 7) case with the following probabilities: reverse (0), forward 50%, turn right or left 25%.

5. Working with the base rectangular grid, add the possibility of a “trap door” in one cell, in which the rat falls out of the maze upon entering that cell. The user should be able to select the cell. Run this for the (8x 7) case and turn in a nicely labeled output.

6. Finally (do this last!) parallelize the code and distribute it over Matlab workers in a matlab pool. Unlike MP1, this is not so easy or efficient here. The Jacobi method described in the book is closely related to Gauss Seidel, in general slower to converge, but more readily made parallel. I would base my distributed strategy on the Jacobi method. The key question is whether the slower Jacobi convergence more than overwhelms the computational advantage of parallel computing. You will need to do an analysis as a function of problem size to determine this. This should be done last – the other steps are of greater importance in the final grade here. The code may need some redesign at this point.

Programming comments.

Diagonal path option could be controlled by an input parameter

Should probably separate the initialization step from the iteration step.
Convergence is not assured for Gauss Seidel– be sure your code traps diverging cases.
Consider using 2D arrays for this problem input/output – they seem well suited to the physical nature of the maze. The linear equations are also logically represented as 2D arrays.
Output should be nicely labeled and contain the conditions of the run as well as the final result.
The directional refinements (4 a-e above) are trickier. One way to conceptualize this is that each cell now has four probabilities, labeled with the orientation of the rat. From a particular cell, the rat goes to the neighbors in a particular direction and you have to average the probabilities for that direction. Suppose a probability P_ij^N is the probability of a northbound rat in cell (i,j) arriving finding food. To be specific if the rat is in cell (3,3) heading north (i.e. came from the south), the P₃₃^N is the average of P₃₄^E,, P₃₂^W,, P₂₃^N,, and P₄₃^S. The problem now has four times as many probabilities for the same size grid, and four times as many equations, but each equation has the same number of terms. You might envision a 3D array with a 2D layer for each of the four rat orientations. Or, you might just envision separate 2D arrays, identified by variable name for the four orientations.
In the example if rats cannot turn around, have 50% probability of going forward, and 25% probability turning either right or left, the equation for cell (3,3) described above would be given by the equation for P₃₃:
Use tic and toc to measure elapsed (wall clock) time for execution.
Good coding practices are to be followed:

Adequate and informative commenting throughout, including the use of and purpose of each function.
Appropriate indentation in code and use of white space to clearly delineate logic elements.
Comments should explain each function
Use of white space around operators to make the lines of code more readable
Sensible variable and function names that make code easy to understand
Efficiency: especially regarding vector operations
Appropriate modularization based on task components
Sparing use of global variables – in most cases only as constants
Numbers should generally not appear in code if variables or constants would be appropriate. (Is their origin obvious, and are they likely to be ever changed?)

Preliminary submission. By 11:59 PM, Friday, February 3, you are to turn in a deliverable to the “MP2PreliminarySubmission” drop box. This file is to report on the design (including modularization), author responsibilities for different components and phases of code development. It should also include rough drafts ( not yet debugged) of any modules that have been started.

Report. Report should include:

Output for the cases specified above
Code m-file or directory of m-files for this problem.
Discussion about strategy for solving the problem and testing strategy you employed to debug the program. This could involve running some simple trial cases with variable food positions and starting probabilities to see if the results look ‘reasonable’.
Discussion of the dependence of convergence behavior and time to completion (complexity) on the dimensions of the problem. Be sure to conclude whether the Gauss Seidel solution goes as n, n², n³, or higher, based on your results. Does this result seem reasonable. Note that the equations become more and more sparse as the problem grows.
Discussion of the effectiveness of parallelization of this code. Does it become more or less favorable as the problem size grows. Be sure to consider both the time per iteration and the number of iterations to convergence.