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

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

Cars going straight or turning right can go significant faster in reservation intersection.