Final Project

Due Date: Dec. 17 2010

The final project is optional and only applies to students in CSE 5315 (where it is applied instead of homework assignment 6. The final project grade can be used to replace the lowest score equivalent (one homework or an exam fraction of equal value to one homework assignment).

Students are encouraged to select their own final project topics (with approval of the instructor).

Example Projects

• Automatic Camera Calibration: A camera with unknown focal length is put into an environment that has a set of easy to detect targets in known locations. These can be seen by the camera which records their location in terms of pixel coordinates.
  Given that there are 10 targets distributed in the environment, implement a least squares calibration routine that determines the pose of the camera (the location of the focal point and the orientation of the camera) as well as the focal length of the camera.

• Image Compression: Multiple methods can be used to compress image data based on orthogonal transformations. All of these methods basically work by transforming the image data into a set of coefficients for specific basis functions using orthogonal transformations and then transmitting only a subset of these (or to transmit them at a lower precision) and potentially the corresponding basis functions if these are not independent of the image data. In particular we looked at SVD, Discrete Fourier Transform, and Discrete Cosind Transform as three differnt possiblities.
  Apply and compare the three methods in terms of the resulting image quality and the amount of data needed to transmit the compressed image. Evaluate image quality in a subjective as well as an objective (quantitative) manner.

• Robotic Navigation: Robotic path planning is an important aspect where a path is computed as a sequence of locations that a robot has to move through. One way to do this is to uniformly discretize the workspace and compute a harmonic potential over this space which is set to 1 at obstacle locations and is equal to 0 at the goal location. For all intermediate locations the potential is equal to the average of all the neighboring locations, yielding one linear equation per location (either the value at the location is equal to a cosntant or it is equal to the average of its neighbors). Once the solution to this system of equations is computed, the path is generated by using the direction of the gradient of the function as a velocity (or step) command to the robot.
  Build a corresponsing path planner for a robot moving in a 3D environment that is discretized into a 20x20x20 regular grid. Compare at least 3 methods to solve the system of linear equations (e.g. LU factorization, Jacobi Iteration, SOR) in terms of the quality of the solution and in terms of the time required to compute the solution.

• On-Demand Scheduling: In the scheduling of computer jobs, often precedence constraints exist that require certain jobs to be completed before others can be run. Moreover, many processing jobs also have real time constraints, reducing their value if they are completed past a particular deadline. A particular instance of this would the case where all jobs have known runtime t_j and precedence constraints and the utility of the jobs (their value) follows a linear soft real time function where job j has full utility u_j until time t_j,1 which then decreases linearly until it reaches its lowest point (usually negative and corresponding to the penalty to be paid for not completing a job) at time t_j,2. Furthermore, there can be a cost c_j(t) to storing the results of the calculations for a time t after a job is completed and before the followup job is started. The goal of the job scheduler is it to arrange the jobs such that the resulting schedule maximizes the sum of the utilities of all the jobs in the schedule. This utility can be expressed as a non-linear function of the start (and thus comletion) times of the jobs and the scheduling problem as a non-linear constrained optimization problem aimed at finding the optimal starting times for the individual jobs. (Note, however, that as soon as a limit on the number of machines is imposed (i.e. the number of jobs that can run simultaneously is limited), the constraints become dependent on the order in which jobs are executed, making it a non-continuous function.)
  Given the very simplified assumption that there are no limitations on the number of simultaneous jobs, formulate the problem and apply an optimization technique to solve it (and thus determine the start times for all the jobs) for a set of 20 jobs with arbitrary precedence constraints and utility drop function and storage cost factors.

• Multiagent intrusion prevention: A computer system consisting of 3 computers computers has limited resources that can be dedicated to fighting (preventing) attacks on individual computers. In order to prevent intrusions on a particular computer, it has to run a complex prevention programm which uses a large fraction of its resources, incurring a cost of d_m on computer m but guaranteeing that any attack on that computer will fail. On the other hand, if the job is not run and an intrusion happens, a cost of c_m will be incurred on that computer (with c_m usually significantly larger than d_m. Assuming that there is only one attacker on the system and this attacker can only attack one computer at a time, and given that the attacker incurs a cost of c_a for any attack attempt (independent of its success or failure) and receives a benefit of w_m for succeeding to break into machine m, game theory can be used to determine a Nash equilibrium indicating the best strategies for the attacker and the system administrator (expressed in terms of the probability with which the attacker should choose a particular computer to attack and the probabilities with which the system administrator should run the intrusion prevention program on any possible subset of the computers). Game theory here finds a joint solution that simultaneously forms a local maximum for the expected gain (benefit - cost) of the system given that only one of the parties changes the strategy. To find this solution, the expected gain for both parties can be formulated as linear equations and the simultaneous local optimum requirement can be expressed as a set of linear constraints, thus forming a linear program.
  Formulate the above problem as a linear program and use the simplex algorithm to find a solution for different cost and benefit values.