2. Description of the algorithms
In general, we have two algorithms serving different puposes. Reservation manager is designed for autonmous vehicles. Stop sign manager is designed to mimic human driving behvior, so we can compare if the reservation algorithm is more effiecient than what we already have in the real world.
Protocols:
Protocols for reservation: when at certain distance and no cars ahead waiting (use lidar to detect), cars will tell manager their IDs, position, speed, acceleration, and direction. Manager will tell cars if they can enter the intersection and the sped they should drive at.
Protocols for stop sign: Cars wait if there is a car ahead in the same lane. When stoppig before the intersection, cars will sned in direction to manager, manager will tell if the car can go.
2.1 Reservation Intersection
The goal of this algorithm is to create a central manager that can let autonomous vehicles drive through the intersection safely and efficiently.
Step 0: Build a grid
Upon initializing a reservation manager, we build a grid (2D list) that stores time (float). The time stored represents the time a grid spot will be available. Hence, we fill in current time in step 0.
Step 1: Check the grid spots that the car is going to pass through is available
Based on the position, direction, speed, and the acceleration sent in, we can calcualte the time the car is going to arrive.
Step 2: Optimize speed
Based on the reservation time we have, we can find the fastest speed to pass through safely, potentially letting more cars to get in.
Step 3: Reserve the grid based on the result of optimization
Now we reserve the spots for the car so other cars won't hit it.
Now we have a second incoming car
Multi-car Step 1: Check the grid spots that the car is going to pass through is available
Based on the position, direction, speed, and the acceleration sent in, again, we can calcualte the time the car is going to arrive. However, this time, we can see a conflict as the red circle suggests. Hence, the manager will rejet the car's request.
Multi-car Step 1: Check the grid spots that the car is going to pass through is available
This time, the car doesn't have any conflict because it is slower.
Multi-car Step 2: Optimize speed
Same as before, based on the reservation time we have, we can find the fastest speed to pass through safely, potentially letting more cars to get in.
Multi-car Step 3: Reserve the grid based on the result of optimization
Same as before, we reserve the spots for the car.
Technical details
1. Prioritize
It is possible to have deadlock for some certain cars, so we have a prioritize policy. If a car has waited for too long, we reject all newly incoming cars, and let the car pass through.
2. Turning path
To find the length of the turning path, we used the coordinates of grid spots and calculate the tangent value to obtain the angle.
3. buffer
Since cars are not just single spots, the manager will reserve more space for them based on their speeds.
2.2 Stop Sign Intersection
The goal of this algorithm is to simulate human driving behavior with certain policies.
1. At most 2 car can be in the intersection at a time.
2. If a car is turning left, there must not be any car before it, and no car can enter the intersection either. There can be only one car left turning.
3. Based on the first car's request, we block directions and, depending on cases, may allow one more car to come in.
Case 1: if the first car is going straight
Manager block these directions
Case 2: if the first car is turning right
Manager block these directions
Case 3: if the first car is turning left
Manager block all directions
3. Result
To determine how efficient our reservation algorithm is, we compare it with optimized (no traffic) itersection and stop sign intersection. We ran the simulations for wo minutes 10 times and took the average of data.
Cars per minute
Cars per minute is the average cars that can pass through the itersection.
Our algorithm can allow more car to pass through an intersection than the stop sign can. Additionally, it approaches more to the optimized intersection if there are less traffic.
Time per car
Time per car is the average time for a car to go straight, turn left, turn right and reach their estinations in each intersection.
Cars going straight or turning right can go significant faster in reservation intersection.