-
Notifications
You must be signed in to change notification settings - Fork 0
/
car.py
406 lines (326 loc) · 16.2 KB
/
car.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
from time import time
import numpy as np
from intersection import Intersection
from util import generate_id
import network
from topology import dist
"""
Represents a car as a Simpy process.
env: Simpy environment
origin: origin node (Intersection)
destination: destination node (Intersection)
links: links of the road network (Set of Link)
"""
class Car:
id_generator = generate_id()
def __init__(self, env, origin, destination, links, monitor, verbose):
self.env = env
self.origin = origin
self.destination = destination
self.links = links
self.id = next(self.id_generator)
self.monitor = monitor
self.verbose = verbose
self.cell = None # reference to the cell's resource
self.curr_infra = origin # reference to the link OR intersection on which the car currently is
self.total_delay = 0 # incurred delay since the beginning
def get_id(self):
return self.id
def get_origin(self):
return self.origin
def get_destination(self):
return self.destination
def get_total_delay(self):
return self.total_delay
def set_curr_infra(self, infra):
self.curr_infra = infra
def is_at_intersection(self):
return type(self.curr_infra) == Intersection
@staticmethod
def generate_nyc_car(strategy, day, verbose, monitor, env, links, intersections, omega, alpha, beta, perc):
av_v_st = 7 #Ratio of traffic on avenues vs. streets, based on ratios from NYC open data
edge_wtg = 10 #ratio of cars originating on the edges of the grid vs. center
#Create list with orgins weighted by more likely end points
origin_intersections = list(intersections) + \
['v1_1','v2_1','v4_1','v6_1','v1_16','v3_16','v5_16','v7_16'] * edge_wtg * av_v_st \
+ ['v1_3','v1_5','v1_7','v1_9','v1_11','v1_13','v1_15'] * edge_wtg \
+ ['v7_2','v7_4','v7_6','v7_8','v7_10','v7_12','v7_14'] * edge_wtg
dest_intersections_S = list(intersections) + ['v1_1','v3_1','v5_1','v7_1'] \
* edge_wtg * av_v_st + ['v1_2','v1_4','v1_6','v1_8','v7_1','v7_3', \
'v7_5','v7_7',]* edge_wtg
dest_intersections_N = list(intersections) + ['v1_16','v2_16','v4_16','v6_16'] \
* edge_wtg * av_v_st + ['v1_10','v1_12','v1_14','v1_16','v7_9','v7_11', \
'v7_13','v7_15']* edge_wtg
origin_name = np.random.choice(origin_intersections, 1)[0]
is_south = int(origin_name[origin_name.find('_')+1:]) < 9 #determines if origin is in the southern half of grid
destination_name = origin_name
while destination_name == origin_name:
if is_south:
destination_name = np.random.choice(dest_intersections_N, 1)[0] #more heavily weight northern intersections for southern origins
else:
destination_name = np.random.choice(dest_intersections_S, 1)[0] #more heavily weight southern intersections for northern origins
origin, destination = intersections[origin_name], intersections[destination_name]
car = Car(env, origin, destination, links, monitor, verbose)
car.monitor.register_car(car, day)
return car.run_strategy(strategy, intersections, omega, alpha, beta, perc)
@staticmethod
def generate_cambridge_car(strategy, day, verbose, monitor, env, links, intersections, omega, alpha, beta, perc):
av_v_st = 7 #Ratio of traffic on avenues vs. streets, based on ratios from NYC open data
edge_wtg = 10 #ratio of cars originating on the edges of the grid vs. center
#Create list with orgins weighted by more likely end points
origin_intersections = list(intersections) + ['River_Memorial','DeWolf_Memorial']*7 \
+ ['River_Mass','Mass_Mt_Auburn']*5 + ['Western_Mass']*8 \
+ ['River_Memorial']*8 + ['Mt_Auburn_DeWolf']*2 #increases odds of originating from busiest roads' intersections
origin_name = np.random.choice(origin_intersections, 1)[0]
if 'Memorial' in origin_name:
dest_intersections = list(intersections) + ['River_Memorial','DeWolf_Memorial']*80 #Increases likelihood of staying on same road if you started there
elif 'Mass' in origin_name:
dest_intersections = list(intersections) + ['River_Mass','Mass_Mt_Auburn']*80 #Increases likelihood of staying on same road if you started there
elif 'River' in origin_name:
dest_intersections = list(intersections) + ['River_Mass']*80 #Increases likelihood of staying on same road if you started there
elif 'Western' in origin_name:
dest_intersections = list(intersections) + ['Western_Memorial']*80 #Increases likelihood of staying on same road if you started there
else: dest_intersections = list(intersections) #Assumes random destination if starting off the main roads
#print('dest_intersections',dest_intersections)
destination_name = origin_name
while (destination_name == origin_name or
network.shortest_path(intersections[origin_name], intersections[destination_name], links, intersections) == []):
origin_name = np.random.choice(dest_intersections, 1)[0]
destination_name = np.random.choice(dest_intersections, 1)[0]
origin, destination = intersections[origin_name], intersections[destination_name]
car = Car(env, origin, destination, links, monitor, verbose)
car.monitor.register_car(car, day)
return car.run_strategy(strategy, intersections, omega, alpha, beta, perc)
@staticmethod
def generate_car(strategy, origin_name, destination_name, day, verbose, monitor, env, links, intersections, omega, alpha, beta, perc):
origin, destination = intersections[origin_name], intersections[destination_name]
car = Car(env, origin, destination, links, monitor, verbose)
car.monitor.register_car(car, day)
return car.run_strategy(strategy, intersections, omega, alpha, beta, perc)
def run_strategy(self, strat, intersections, omega, alpha, beta, perc):
if strat == "case0":
links_to_visit = network.shortest_path(self.origin, self.destination, self.links, intersections)
return self.run_blind_shortest(links_to_visit)
if strat == "case1":
links_to_visit = network.shortest_path(self.origin, self.destination, self.links, intersections, network.case1_weight_query)
return self.run_blind_shortest(links_to_visit)
if strat == "case2":
update_path = Car.__update_path_case2(self.destination, self.links, intersections, omega)
links_to_visit = update_path(self.origin, False)
return self.run_dynamic(links_to_visit, update_path, Car.__allocate_anticip_never())
update_path = Car.__update_path_allocated_case(self.destination, self.links, intersections, omega, alpha, beta)
links_to_visit = update_path(self.origin, False)
if strat == "case3":
return self.run_dynamic(links_to_visit, update_path, Car.__allocate_anticip_random())
if strat == "case4":
return self.run_dynamic(links_to_visit, update_path, Car.__allocate_anticip_by_distance(perc, self.verbose))
if strat == "case5":
return self.run_dynamic(links_to_visit, update_path, Car.__allocate_anticip_by_delay(perc, self.verbose))
raise ValueError("Strategy {} does not exist".format(strat))
"""
Allocation rules
"""
@staticmethod
def __allocate_anticip_never():
def allocate_anticip(car, link):
return False
return allocate_anticip
@staticmethod
def __allocate_anticip_always():
def allocate_anticip(car, link):
return True
return allocate_anticip
@staticmethod
def __allocate_anticip_random():
def allocate_anticip(car, link):
if not link.has_stigmergy:
return True
return np.random.uniform() < 0.5
return allocate_anticip
@staticmethod
def __allocate_anticip_by_distance(perc, verbose):
def allocate_anticip(car, link):
if not link.has_stigmergy:
return True
own_distance = dist(car.curr_infra.get_pos(), car.destination.get_pos())
shorter = 0
longer = 0
other_cars = link.get_cache().get_anticip_buffer()
for id in other_cars:
buf = other_cars[id]
for other in buf:
other_distance = dist(car.curr_infra.get_pos(), other.destination.get_pos())
if own_distance > other_distance:
shorter += 1
else:
longer += 1
anticip = shorter > perc * (longer + shorter + 1)
if verbose:
print(car, "to", car.curr_infra, ": shorter =", shorter, ", longer =", longer, ", anticip =", anticip)
return anticip
return allocate_anticip
@staticmethod
def __allocate_anticip_by_delay(perc, verbose):
def allocate_anticip(car, link):
if not link.has_stigmergy:
return True
own_delay = car.get_total_delay()
less_delay = 0
more_delay = 0
other_cars = link.get_cache().get_anticip_buffer()
for id in other_cars:
buf = other_cars[id]
for other in buf:
if own_delay > other.get_total_delay():
less_delay += 1
else:
more_delay += 1
anticip = less_delay > perc * (more_delay + less_delay + 1)
if verbose:
print(car, "to", car.curr_infra, ": less_delay =", less_delay, ", more_delay =", more_delay, ", anticip =", anticip)
return anticip
return allocate_anticip
@staticmethod
def __update_path_case2(destination, links, intersections, omega):
def update_path(origin, _):
return network.shortest_path(origin, destination, links, intersections, network.case2_weight_query(origin, omega))
return update_path
@staticmethod
def __update_path_allocated_case(destination, links, intersections, omega, alpha, beta):
def update_path(origin, allocated):
if allocated:
return network.shortest_path(origin, destination, links, intersections,
network.anticipatory_weight_query(origin, alpha, beta))
return network.shortest_path(origin, destination, links, intersections,
network.case2_weight_query(origin, omega))
return update_path
def __update_link_intentions(self, links):
cap_time = 10
future_time = 0
# We go in reversed order because the links are visited in reversed order.
for link in reversed(links):
time_to_traverse_link = link.get_weight()
future_time += time_to_traverse_link
# update time when the car should be on the link.
# cap_time is 10, because we only look 10 minutes in the future.
# if future_time >= cap_time, we update the stigmergy for 10 minutes in the future, and stop.
if future_time < cap_time:
link.get_cache().increment_anticip_stigmergy(self, future_time)
else:
link.get_cache().increment_anticip_stigmergy(self, cap_time)
break
def run_dynamic(self, path, update_path, allocate_anticip):
if self.verbose:
print(self, "is running the dynamic strategy from", self.origin, "to", self.destination)
print("Its path will be (in reversed order):", path, "\n")
intersec_cell = None
t = 0
# update intentions in next 10 mins (stigmergy caches)
self.__update_link_intentions(path)
while len(path) > 0:
ongoing_link = path.pop()
cell, pos = ongoing_link.request_entry()
cell_req = cell.request(self.get_id())
link_delay = 0
delay = yield from cell_req # wait to have access to the cell
if intersec_cell:
intersec_cell.release(self.id)
t += delay
link_delay += delay
if self.verbose:
print(self, "has accessed the link toward", ongoing_link.get_out_intersection(), "(delay:", link_delay, ") [", self.destination, "]")
# keep moving on the link
while True:
# now we have access to the cell
yield self.env.timeout(1)
t += 1
# TODO: update monitor with travel movement
# update path every 5 minutes
if t >= 5:
t = 0
allocated = allocate_anticip(self, ongoing_link)
path = update_path(ongoing_link.get_out_intersection(), allocated)
# update intentions in next 10 mins (stigmergy caches)
self.__update_link_intentions(path)
# we have reached the end of the link, we need to update stigmergy information about the visited link.
# Notice, that we first need to request access to the intersection before.
# Initially, we didn't put a capacity for intersections, and so technically it could have been possible
# to have an infinity of cars at an intersection. This was especially bad when updating stigmergy caches,
# because the time spent in the intersection was not accounted. Now, we have a special cell (resource), one
# per outgoing lane to that intersection.
if ongoing_link.is_next_to_intersection(pos):
intersec_cell = ongoing_link.get_intersection_cell(pos)
intersec_cell_req = intersec_cell.request(self.get_id())
delay = yield from intersec_cell_req
t += delay
link_delay += delay
cell.release(self.get_id())
ongoing_link.store_stigmergy_data(link_delay)
break
next_cell, next_pos = ongoing_link.get_next_cell(pos)
next_cell_req = next_cell.request(self.get_id())
delay = yield from next_cell_req
t += delay
link_delay += delay
cell.release(self.get_id())
cell, pos, cell_req = next_cell, next_pos, next_cell_req
# car is now at a new intersection
self.total_delay += link_delay # should be useful for case 5
self.curr_infra = ongoing_link.access_intersection()
if self.verbose:
print(self, "is at intersection", self.curr_infra)
if intersec_cell:
intersec_cell.release(self.id)
self.monitor.update_car_finished(self.id)
"""
Run the car process through the shortest path.
The shortest path in this process is blind to stigmergy.
Right now, the logic of this run is very similar to `run_basic`, except the links are popped
from the path list computed via Dijkstra (rather than a random walk).
"""
def run_blind_shortest(self, path):
if self.verbose:
print(self, "is running the blind-shortest strategy from", self.origin, "to", self.destination)
print("Its path will be (in reversed order):", path, "\n")
intersec_cell = None
while len(path) > 0:
ongoing_link = path.pop()
cell, pos = ongoing_link.request_entry()
cell_req = cell.request(self.get_id())
link_delay = 0
link_delay += yield from cell_req # wait to have access to the cell
if intersec_cell:
intersec_cell.release(self.id)
if self.verbose:
print(self, "has accessed the link toward", ongoing_link.get_out_intersection(), "(delay:", link_delay, ") [", self.destination, "]")
# keep moving on the link
while True:
# now we have access to the cell
yield self.env.timeout(1)
# we have reached the end of the link, we need to update stigmergy information about the visited link.
# Notice, that we first need to request access to the intersection before.
# Initially, we didn't put a capacity for intersections, and so technically it could have been possible
# to have an infinity of cars at an intersection. This was especially bad when updating stigmergy caches,
# because the time spent in the intersection was not accounted. Now, we have a special cell (resource), one
# per outgoing lane to that intersection.
if ongoing_link.is_next_to_intersection(pos):
intersec_cell = ongoing_link.get_intersection_cell(pos)
intersec_cell_req = intersec_cell.request(self.get_id())
link_delay += yield from intersec_cell_req
cell.release(self.get_id())
ongoing_link.store_stigmergy_data(link_delay)
break
next_cell, next_pos = ongoing_link.get_next_cell(pos)
next_cell_req = next_cell.request(self.get_id())
link_delay += yield from next_cell_req
cell.release(self.get_id())
cell, pos, cell_req = next_cell, next_pos, next_cell_req
# car is now at a new intersection
self.curr_infra = ongoing_link.access_intersection()
if self.verbose:
print(self, "is at intersection", self.curr_infra)
if intersec_cell:
intersec_cell.release(self.id)
self.monitor.update_car_finished(self.id)
def __str__(self):
return "Car {}".format(self.id)