From EECS492_W11
Jump to: navigation, search

Problem Set 4 (55 points)[edit]

EECS492 problem sets are a collaborative activity amongst your staff-assigned team. You may also discuss the problem sets and problem solving approach with other teams, but the work you submit must be wholly that of your team. In particular, you may not derive your solutions from previous years' solutions, nor may you derive your solutions from code snippets found elsewhere (including online). Examples: studying pseudo-code as found on Wikipedia is acceptable; adapting code from an open source project is not.

Your submission will include a written portion (which must be typeset, including any equations, figures, or graphs, and must be in PDF format), and a programming portion. Your writeup should include a terse restatement of each question (copy/paste is fine) in a font face that clearly separates the question from your answer, and should be formatted in an easy-to-navigate fashion (i.e., with large headings for task, and smaller headings for each problem). Make sure that the uniqnames of each member are listed at the top of every page as a running header. Deviations from this format will be penalized.

For the programming portions, you must include all of your code in a ready-to-compile state, along with a README that gives invocation instructions. Your PDF and programming files must then be zipped and submitted by email. Your email must have the following form, where the challenge score is computed based on the scoring rules described in the problem set.

SUBJECT: PS4: <uniqname1>, <uniqname2>, <uniqname3>. challenge=<challenge score> 
CC: <all of your team members>

You may receive a "moderation pending" message; this is harmless.

Task 1. Planning [15 points] [moved from PS3][edit]

1.1. Consider the cleaning agent in the vacuum world again. Given definitions of the following actions:

Preconditions: ¬At(Room1) 
Effects: At(Room1) ^ ¬At(Room2)
Preconditions: ¬At(Room2)
Effects: At(Room2) ^ ¬At(Room1)
Preconditions: At(Room1) ∧ Dirty(Room1)
Effects: ¬Dirty(Room1)
Preconditions: At(Room2) ∧ Dirty(Room2)
Effects: ¬Dirty(Room2)

Now we have initial state

At(Room1) ∧ ¬At(Room2) ^ Dirty(Room1) ∧ Dirty(Room2). 

The goal state is

At(Room2) ∧ ¬Dirty(Room1) ∧ ¬Dirty(Room2).

Draw planning graph up to level 3 (S0, S1, S2) for this problem. For each step, state action you can take, show preconditions, mutex links and effects.

Task 2. Probability [10 points][edit]

2.1 You have been experiencing tooth pain (P) recently and are afraid you have a cavity (C). You know that at any given time, one out of every 1,000 people have a cavity. You also did some wikipedia research and discovered that if a person has a cavity, the probability of having tooth pain is 0.90. The probability of having tooth pain, given no cavities, is 0.30. What is the probability that you have a cavity (given all the evidence you have)? [5]

2.2. Extending the problem described in 2.1, suppose that the other major cause of tooth pain is an exposed root (R). Poor brushing habits (B) tend to lead to both cavities and tooth pain. Draw a Bayes net corresponding to the causal links described. [2 points]

Draw a Bayes net which captures the same dependencies, but in which the variables are introduced in the order C, R, B, P. [3 points]

Task 3. Bayesian Inference [15 points][edit]

Consider the Bayesian network with four nodes as shown below.


  1. What information about random variables are encoded in a Bayes network? Why is this information useful? [2 points]
  2. Write expressions for Pr(A, B, C, D), Pr(A | D) and Pr(A, B, D) in terms of the conditional probabilities shown above. (You do not need to provide a table). [7 points]
  3. Compute the marginal probability Pr(A, B, D) (i.e., give us a table). [6 points]

Task 4. SimElevator (Challenge problem) [15 points][edit]

You've been tasked with designing a control system for 492-Corp's new elevator system. Marketing has promised that it will significantly reduce passenger travel time by making better use of the available elevators. As their plucky newest employee, it's your job to make the claim true!


In order to formulate better plans for the elevator, each floor is equipped with a new button panel: instead of the traditional up/down buttons, there is a button for each floor. Consequently, the system knows which floor every passenger is travelling to. In addition, the elevator recognizes passengers and announces which passengers should board which elevator (and when they should do so).

492-Corp's clients span from traditional buildings (with a single bank of identical elevators) to sky scrapers which have multiple banks of elevators that service only subsets of the floors. For example, a building might have an elevator that services floors 1-20 and another that services floors 20-40. The elevator system must be able to instruct passengers when to change elevators and should plan accordingly. Some buildings were designed by Frank Gehry, and thus their elevators make no sense at all!

Your job is to compute where to send the elevators given the current set of passenger requests. In contrast to our earlier problem sets, this is a "real world" planning problem: you'll need to continuously replan due to the fact that you don't know where or when passengers will appear. It's also a problem with a very large search space, so you'll probably need to forgo optimality in the sake of making it work.

To simplify the problem somewhat, time is divided into a number of discrete "steps". At each step, each elevator can move one floor. New passengers arrive, and your agent is called with the complete state of the world (minus passengers that will arrive in the future). Your agent then sets the destination of each elevator. Note that passengers load and unload from elevators "automatically": whenever an elevator is headed in the right direction, they'll board and unboard appropriately. In other words, you don't need to tell the passengers what to do: you just control the elevators.

Your goal is to minimize the average *squared* passenger travel time. This reflects the idea that passengers' irritation grows much faster than linearly. You'll implement your agent in Java (see provided code below) and test your code on a number of different buildings over 50000 time steps. The long run time is intended to coerce you into implementing reasonably fast methods. Your score is the sum of the squared passenger travel time across all four buildings; low scores are better.

The code is available here: Media:eecs492_ps4.tgz

You can invoke it as follows:

java -cp simel.jar simel.Simulator building1.txt --agent=simel.DumbAgent

We've provided a simple agent that sends the elevators up and down, without regard to where passengers actually are. Note that you can speed up the simulation by using the -d flag.

Problem set credit

For full problem set credit, you must implement a planner that performs some sort of optimization over the elevator plans in order to minimize the average travel time. Your method should be able to look more than one step ahead, in order to improve times for passengers that need to take multiple elevators in order to reach their destination. Naturally, your score should be noticeably better than the "DumbAgent" we've provided.

There are a number of ways of approaching the problem. You can formulate the problem as a forward search using Tree Search. But like Borealis, you'll find that the search space explodes rapidly. This might force you to use a beam search instead. This is the least interesting way of approaching the problem, since it's similar to what we've done before.

Another option is to use local search. Write a simple module that, given a "plan" and a set of passengers, computes the cost. Once you've done this, you can use methods like hill climbing to improve the plans for the elevators. Genetic algorithms would also be possible.

A third approach is based on sequential planning. Do a forward search considering just one elevator-- compute a plan for it that moves passengers closer to their destinations as fast as possible. Next, do a forward search for another elevator, given that the first elevator will execute the plan you found earlier. Repeat this for each additional elevator, computing new plans for the Nth elevator, taking into account the actions of the previous N-1 elevators.

Note that passengers do not appear uniformly on all floors: some floors are more "popular" than others. Using only the information you get from the arrival of passengers, you can estimate the popularity of floors. If you're able to reasonably incorporate this sort of knowledge into your plan, you'll earn up to 5 bonus points depending on the sophistication of your approach. (Make sure you explain how you did it!)

In any case, describe your approach. Specifically describe how your approach "thinks ahead" in order to minimize travel time.

You must also submit your score to the leaderboard, showing that your code was able to finish the test cases..


Create your submission file by running:

java -cp simel.jar simel.Simulator building?.txt -d 0 --agent=simel.MyAgent | tee submission.txt

Upload the submission.txt file to the leaderboard. The top three teams on the leaderboard will have their code run on a different set of buildings (which are similar to those you've been provided), and the winning team will be announced in lecture. Teams whose code runs for more than 20 minutes will be disqualified from the final round... we have places to be!

Task 5. Certification and Peer Evaluation [required for credit, 0 points][edit]

Print or write the following on a sheet of paper:

"I participated and contributed to team discussions on each problem, and I attest to the integrity of each solution. Our team met as a group on [DATE(S)]."

Each team member should sign the paper (physically, not digitally), and a photo of the paper should be included with your problem set. By doing so, you are asserting that you were materially involved in each answer, and that you certify that every solution complies with the collaboration policy of this course. In the event of a violation of the course's guidelines, your certification will be forwarded to the honor council.

If the statement requires qualification (i.e., it's not quite true), please describe the issue and the steps you took to mitigate it. If a team member did not materially contribute to a particular solution, then their score on that problem will generally be reduced. The staff will use their discretion based on the specific circumstances you identify, and we are happy to discuss potential problems prior to the problem set due date.

If your team works together, as required, this will be painless! :)

Each member of your team must also complete a peer evaluation, accessible from the apps page.

Your evaluations of your teammates will remain private. If problems develop with your team, it is up to your team to resolve them: we will not intercede except in the most extreme situations.