Skip to end of metadata
Go to start of metadata

Task

This week we were tasked with managing an elevator simulation written by a previous Colby professor.  Our goal was to understand the way they organized their code and to meaningfully change the elevator management strategy to try and improve wait times.

Solution

I first implemented the classes required to complete the elevator package simulation:

  1. MyPriorityQueue data structure which acts as a queue but maintains the object with the highest priority at the top
  2. Passenger class which tracks the floor it is on and wishes to reach and its total wait time
  3. PassengerGroup class which extends  MyPriorityQueue and orders passengers by either maximum or minimum target floor 

I then set to work improving the elevator strategy code.  To quantify my changes, I repeatedly ran the simulation on a particular sequence of passenger provided to the class.  With the default strategy, this sequence of 200 passengers resulted in an average wait time of 71.84 time steps.

The elevator strategy was broken into two parts, an empty rule which determines the elevators behavior when it is empty, and a non-empty rule which determines the behavior when it is not.

Originally, the empty rule dictated that elevators would maintain their current direction and check each floor they passed for passengers who were going in the same direction.  If the elevator reached the top or bottom of the building, it would open its doors, even if no passengers were waiting to board, and then change its direction.  The non-empty rule dictated that the elevator would continue in its current direction and drop off passengers as they reached their target floor.

My first change was to the empty rule as it had the most glaring issues.  I had the elevator first attempt to pick up passengers on their current floor, in which case the elevator would begin traveling to the closest target floor of the passengers picked up.  If there were no passengers on the current floor, the elevator would begin to move to the floor with the closest passenger.  Finally, if there were no passengers left in the simulation, the elevator would return to the lobby.

This change immediately improved average wait time for the simulation to 66.66.

Next, I changed the non-empty rule.  Instead of simply passing by passengers waiting to board, I wanted the elevators to stop and pick up passengers traveling in the same direction along the way to their destination.  As I watched the simulation respond to my change, though, I noticed that elevators would often stop every floor to pick up a new passenger and would cause their current passengers to wait longer.  To explore this delay, I changed the number of passengers (going in the same direction) waiting necessary for the elevator to open its doors.  Note an elevator can hold up to 8 passengers.  Here is a table of the effects on wait time:

Minimum Waiters Required

Average Wait Time

1

57.59

2

56.28

3

57.43

4

61.58

5

62.97

6

65.72

7

66.75

8

66.64

I finally tested opening the doors only if the number of passengers waiting to board was greater or equal to the number of passengers already on the elevator. I suspected this might provide a good balance by allowing mostly full elevators to avoid wasting multiple people's time and allowing mostly empty elevators pick up large groups of people waiting.

This gave an average wait time of 54.04.

As I ran more tests, I found average wait time varied pretty significantly between multiple runs of the simulation with the same parameters. With my final improved strategy, average wait time could be anything between 52 to 57 seconds. While I didn't do any statistical analysis on the above strategies, I found the average wait time for each was around the value listed in the above table.

Here is one good time:

Here is a gif of my simulation running with this strategy:

Extensions

For my first and most simple extension, I compared multiple elevator strategies as shown above.

For my second extension, I changed the way elevators and passengers were displayed. Originally, elevators and floors were marked with a circle if they had any passengers. Waiting passengers were represented to the left of the building, and passengers who had reached their destination were represented to the right.

Here is a picture of the original display (stolen from Brian Westerman):

To change the display, I had each passenger draw itself as a rectangle colored by their target floor. A line of rectangles on either side of the building represented passengers waiting or arrived at their floor. When a passenger boarded an elevator, the elevator would take responsibility for drawing the passenger inside of it. Passengers were drawn in the order of the elevators internal queue, so they are drawn in the order they will exit the elevator from left to right.

I used a list of maximally distinct colors from this stackexchange post for each floor so they could be visually differentiated.

Here is a picture of the new display:

One cool result of this display is that the process of elevators picking up passengers and bringing them to their target floor begins to look a lot like sorting:

As I was already very comfortable with swing and user input, I decided to continue implementing interesting data structures for the rest of my extensions.

First I heavily updated my SkipList from two weeks ago to allow indexing. This involved tracking the distance to the next node on every level for a given node. Trying to implement this initially led to many bugs. The logic of figuring out how to update the distance to nodes on each level when a new node is added to the list is not trivial. I did eventually iron out these bugs and added a bit more functionality to my SkipList by also allowing it to order any input using a comparator. Like the priorityQueue, I added a method to change the lists comparator and I also added a method to reverse the lists ordering.

Because insertion into the SkipList is done in log(n) time and it is maintained as a sorted list, I was able to use it to implemented a faster priority queue.

Finally, I implemented a binary search tree. The binary search tree is a binary tree in which the left child of a given node is less than or equal to the node's item and the right child is greater or equal to the node's item.  I got most of my insight on binary trees from Introduction to Algorithms by Cormen.  As a part of my implementation, I added the following methods:

  • insert - inserts an item into the tree in worst time (h) time where h is the height of the tree
  • remove - removes an item from the tree, also in at worst (h) time
  • minimum - finds the entry of the tree with the minimum value in at worst (h) time
  • maximum - as above but with the maximum value also in (h) time
  • search - searches the tree for the given item in at worst (h) time
  • mirror - flips the tree so smaller nodes are right children and larger nodes are left children
  • inOrderWalk - returns a list (or string) of the tree from smallest to largest value, i.e. listing the left child of each node before it and the right child of each node after it.  This is done in (n) time where n is the number of entries in the tree
  • levelOrderWak - returns a string of the tree where each level is printed on a separate line.  This is also done in (n) time
  • getSuccessor - returns the node which appears directly after the given one in an inOrderWalk, done in (h) time
  • getPredcessor - returns the node directly before the given one in an inOrderWalk, also done in (h) time
  • subTree - returns the subtree at a given node as a binary tree in constant time

Note that a BST has height log(n) on average, but the actual height depends on the order in which nodes were added.

Many of these methods used recursion and were fun to implement.  I'm going to work on expanding this implementation to a red-black tree

Conclusions

The biggest challenge this week was the process of sorting through someone else's code.  I enjoyed working on an already designed system, but adding to it was often frustrating because the design was unnatural to me.  One major difficulty was working without all of the source code and having to rely on classes central to the implementation without anyway to change them or understand their internals.  This originally made creating the display I wanted difficult.

If I had more time, I would implement a central elevator controller which could assign waiting passengers to elevators before they are picked up.  One of the biggest problems with my strategy is that multiple elevators may go to pick up the same passenger.  I would also add checks into the requirements to open doors to ensure passengers with higher wait times are served more quickly.

Labels