J
M Backus
GWCSSMC08 HW1: The Elevator Problem.
This is a spatial model of how arrivals sort, shuffle, and pack themselves into an elevator, and subsequently push, shove, and claw their way out when the elevator reaches their desired floor.
The elevator is a 3 by 3 grid, with a door that opens to the middle column of the front row. Agents have heuristic strategies; for every possible destination, they either prefer to stand in the front of the elevator, the middle, or the back. We measure inconvenience, which is the time it takes to shuffle, in steps through the 3 by 3 grid. Diagonal steps are allowed.
Stage 1: Entry
Agents walk down the aisle of the elevator until they either reach their desired row or they are blocked. Once they settle on a row they move to the side columns if possible; if not, they block the row for subsequent arrivals. If the front row is blocked, then every agent in the elevator is pushed back one square, if possible. It is easy to see that this always makes room for entry so long as we have no more than 9 arrivals.
The Confusion Parameter: One of the things we noticed in the optimal heuristics experiment was that agents were taking advantage of the pushback step in order to move everyone efficiently, in just one tick. So we added a penalty parameter in order to avoid this. Too large a confusion parameter, however, means that agents will be more concerned about avoiding the pushback stage than about tailoring their optimal row to their destination!
Note: The following animations only run on IE.
Stage 2: Exit
The elevator goes up, stopping at each floor. Agents leave the elevator if they are not blocked in (if nobody is blocking the middle aisle). If the middle aisle is blocked, either the person in the way moves into one of the front corners – if they are in the middle row – or, if this is impossible, they step out of the elevator to make way – if they are in the front row or if the front corners are blocked. Once the former agent has left the elevator, those who made way enter again according to the procedure described in Stage 1.
Note: The following animations only run on IE.
Optimal Heuristics: In this experiment we ask what the optimal heuristics are for getting a random set of agents off of the elevator with as little inconvenience as possible. We do not, but in principle one could, weight the inconvenience by the number of agents who are still on the elevator to suffer it.
Here we supposed that n random agents arrive with destinations that are randomly and uniformly drawn from the building’s k floors. They arrive in a random order. We ran the simulation for a grid that allowed the confusion parameter and the number of arrivals to vary.
We found that the optimal strategy is generally monotone for reasonable values of p, the confusion parameter. For higher values, agents focus on avoiding the pushback effect, creating pathologies. For instance, for n=6 and p=100, the optimal heuristic strategy is for all agents to prefer the second row, which guarantees no pushback. This is impossible for n=7 (and analogously for n=4), and it is these cases where we observed nonmonotonic strategies.
Files for the optimal heuristics experiment are located here.
- Mastermaster.m: runs the experiment, generates a datafile titled “result.mat”.
- Master.m: this is the function that is a single “run” for some n,k,p.
- Entry.m: this is the entry routine
- Settle.m: this is the clearing of the aisle when an agent finds the appropriate row.
- Fullfront.m: generates the “pushback” when the first row is full.
- Exit.m: this is the exit routine.
- Aisle.m: This routine clears the aisle after an agent has gotten off of the elevator.
The file result.mat contains information about the minimum number of ticks, the number of floor-types who prefer the first row, the number of floor-types who prefer the second row, and a dummy for whether the optimal heuristic strategy is monotonic in the desired destination.
Adaptive Agents: In this experiment we ask what strategies adaptive agents will choose over time. Here, n agents enter the elevator on the ground floor every day. Each is headed for a different floor (1 – n). An initial strategy set is specified. In each period one agent is selected randomly choose a new strategy. If their elevator ride is shorter than the previous ride, they accept the new strategy. Each simulation allows 1,000 time periods, and we ran 100 simulations for several parameter values suggested from the experiment above.
The initial guess on which the strategy is initialized seem to matter, suggesting a rugged landscape, and only for some initial guesses did the process converge. Overall, the results from this are unclear.
|
Number of
Agents |
Moving
Penalty |
Mean
Number 1's for final adaptive strategy |
Variance
number 1's |
Mean
Number 2's for final adaptive strategy |
Variance
number 2's |
Mean of
the average time to exit in final run |
Variance
in the final time to exit in the final run. |
Mean of
the total time to exit in final run |
Variance
of the total time to exit in final run |
|
|
5 |
3 |
1.18 |
1.3612 |
2.8 |
0.48485 |
15.438 |
5.2571 |
19.08 |
6.9834 |
|
|
5 |
9 |
1.33 |
1.6173 |
2.82 |
0.49253 |
15.92 |
8.2901 |
19.71 |
10.955 |
|
|
5 |
16 |
1.27 |
1.5324 |
2.84 |
0.43879 |
16.374 |
20.227 |
20.12 |
23.824 |
|
|
7 |
3 |
2.57 |
2.389 |
2.62 |
1.2885 |
22.524 |
5.5572 |
28.74 |
7.4267 |
|
|
7 |
9 |
1.51 |
0.55545 |
3.47 |
0.53444 |
24.051 |
12.285 |
30.15 |
14.29 |
|
|
7 |
16 |
1.55 |
0.55303 |
3.59 |
0.50697 |
24.646 |
37.515 |
30.73 |
42.785 |
|
|
8 |
3 |
4.01 |
0.65646 |
2.63 |
0.41727 |
25.75 |
5.9908 |
32.96 |
6.5438 |
|
|
8 |
9 |
2.57 |
0.38899 |
3.19 |
0.43828 |
29.011 |
23.2 |
36.6 |
24.202 |
|
|
8 |
16 |
2.55 |
0.33081 |
3.23 |
0.17889 |
35.6 |
74.164 |
43.4 |
75.98 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Files for the adaptive agent experiment are located here.
Manifest:
- Masteradaptive.m: this is the function that runs the adaptive algorithm for 1,000 periods.
- A_explorer.m: this is the function that runs 100 simulations and provides summaries of the resulting data.
- Submaster.m: this is a necessary process that collects data slightly differently and actually runs each run of the elevator..
- In order to run this you must use the Entry, Settle, Fullfront, Exit, and Aisle files above.