PRE2016 1 Groep2

Updating the Current Intersection System to be Compatible with Autonomous Vehicles.

---

Group members

---

• Jeroen van Dongen (0889788)
• Rodger van der Heijden (0851985)
• Sjoerd Westendorp (0864518)
• Lisanne van Wincoop (0849855)

Introduction

---

For the project Robots Everywhere the goal is to create a project within the field of robotics while keeping USE-aspects at the center stage. These are used to make informed and user-centered decisions on the design. This led to the topic of Vehicle Intersection Control in combination with autonomous vehicles. The idea is to design an algorithm that will use the benefits of autonomous cars on intersections with mixed traffic. This brings risks as well as benefits. Several user categories play an essential part, such as the autonomous car user, the human driver, pedestrians and cyclists. To accommodate the user as best as possible, while finding an economically viable design, the algorithm will be implemented in current intersection control technology.

In this report, the design of the algorithm will be shown. At first, the focus, objectives and approach of the project are stated explicitly as well as initial user aspects that need to be kept in mind while starting the design process. Secondly, a summary of the most important results from the literature study will be shown. The literature study is used to make the requirements, preferences and constraints that the design has to satisfy. This is stated in the algorithm chapter where the features of the design as well as several design choices are elaborated. Also, a communication protocol was made using current intersection technology, which is the hardware that is used to implement the algorithm. Next, the implementation of the algorithm in a simulation is discussed. Throughout the project, USE-aspects are considered to motivate choices. This is addressed in the USE-aspects chapter. Lastly, the results from the experiments that are conducted using the simulation are presented and discussed and a conclusion is drawn on the algorithm design.

Focus, Objectives and Approach

---

Focus

Our main focus area concerns: Vehicle Intersection Control (VIC).

For this project, the focus area was narrowed down to the more specific focus: Updating the Current Intersection System to be Compatible with Autonomous Vehicles.

Restrictions on the focus area:

• The considered intersection has four directions;
• Traffic is randomly generated by a Gaussian distribution, the ratio between autonomous and normal cars will be changeable.

A multitude of traffic accidents happen at intersections. These are also the bottlenecks in terms of efficiency since human drivers have varying reaction times. Drivers can also get stressed behind the wheel and lose valuable time while commuting. Contemporary intersections could make traffic more efficient by utilizing data from sensors of autonomous cars and controlling autonomous cars passing the intersection. By making the intersections smarter, user comfort can be greatly increased. Also society will benefit from more efficient driving past intersections, since emissions are assumed to be reduced, which benefits the environment. Enterprises will also be positively influenced, since people will be able to arrive at work quicker instead of being stuck at an intersection.

Objectives

The main objective of the project is:

• Optimizing traffic flow at intersections by making them compatible with autonomous vehicles.

Objectives that follow from the main objective:

• Using sensor data from autonomous cars to make traffic light algorithms more aware of current traffic;
• Choosing a suitable communication protocol between autonomous cars and the intersection;
• Finding existing efficient algorithms for autonomous cars at intersections in a literature review;
• Combining said algorithm with current traffic light algorithms to optimize traffic flow of both normal and autonomous cars;
• Making sure the traffic flow is optimal, which results in less waiting time and less emission;
• Creating a transition solution that can combine the use of autonomous cars with human drivers by using the current intersection system;
• Keeping in mind the perception of safety and the actual safety of passengers inside the autonomous cars (level of comfort);
• Decreasing the number of traffic accidents involving cars on crossings.

Changes in Objectives

Later on in the design process, several changes were made to the objectives. It was decided to create a new algorithm instead of optimizing an algorithm from a literature study. For comparison, an algorithm that is currently implemented in intersections without autonomous cars is chosen from the literature. As a result points three and four in the list of objectives are changed to be:

• Find an existing algorithm for intersection control, which is implemented in current intersection systems, so that it can be compared to the new algorithm;
• Create a new algorithm for the current traffic light system so the situation is optimal for both normal and autonomous cars.

Approach

The approach that is chosen is research, but mostly simulation oriented. Most information on existing solutions must come from literature and ongoing research. By identifying the state of the art, we will try to combine traffic light algorithms with algorithms that only work with 100% autonomous cars at the intersection. When such combination has been made, a simulation will be created and with this the algorithm can be tested. Lastly, an evaluation will be done of the acquired results.

Initial USE-aspects

Regarding the focus, objectives and approach, USE-aspects need to be evaluated to see what important goals can be defined with regard to the algorithm and simulation. In this subsection, the most important aspects will be discussed.

Keeping in mind the initial estimated market share of autonomous cars

This is a USE-aspect from a society point of view. The crossing that is to be design should be compatible with the transition period after the introduction of autonomous cars on the market. In the beginning, the market-share of the autonomous cars will be relatively low compared to cars with human drivers. However, when the autonomous vehicles have been on the market for some time, the expectation is that the market-share will increase as society becomes more used to the presence of autonomous cars on the road. This means that the intersection should be usable for a minority as well as a majority of autonomous cars.

As the percentage of autonomous cars on the crossing increase, this will impact the traffic situation. Human drivers might become a minority if the launch of autonomous cars is a success. This gives way for more advanced behavior from the autonomous vehicles. An example of this could be that when there are multiple autonomous cars subsequently nearing the crossing, they could use platooning to cross the intersection more efficiently. However, this is a hypothetical theory about the efficiency of autonomous cars that might be outside the scope of this research.

In the simulation the percentage of autonomous cars will be changeable so the results of the algorithm can be viewed for different market shares.

Viewing autonomous cars as lounge cars that adjust driving behavior to perfect timing and comfort

In the future, a plan for the autonomous cars is that they function as lounge cars for people to order to come and pick them up with the assignment to take them to the right destination at a certain arrival time. This image is envisioned by for example the CEO of Tesla, Elon Musk and the CEO of the taxi service Uber Travis Kalanick.

However, fully implementing the green wave between intersections is outside of the scope of this research as only one intersection is considered. It is possible though to consider estimating the time-to-green-light for one intersection and sending this information to the autonomous vehicle. This creates a green wave like effect.

Safety systems in communication between autonomous cars and the intersection

One of the keys to the customer acceptance of autonomous vehicles is decreasing the risk of hacking. Without means to stop this, customer acceptance will never be optimal. However, the way to stop this lies in complicated software which would be a project alone to construct. It is possible however, to keep in mind the possibility of communication failure between the car and the crossing.

The risk of hacking however, is present in many modern technological applications. Personal computers are very sensitive to hacking and yet the majority of society has accepted the risk. A more recent example is the introduction of drones that are used in the airforce or modern surveillance technology. Although these technologies lead to many controversial debates, there is a large number of people who endorse the use of these systems.

It is argued that modern society itself is a “risk culture”. Society is constantly searching for new energy sources and technological advancement that can drive the earth forward. People are getting used to putting their trust in new systems since new technologies are increasingly being introduced into their lives. Risk nowadays also varies between social groups and cultures. This indicates that some groups will be more risk-taking than others and also that autonomous vehicles have a good chance of being accepted by the group that is most risk-taking and then gradually accepted by other cultures that are more apprehensive, despite the fact that the technology carries with it the risk of hacking. This paints a more nuanced picture of the implementation of new technology into society, which many business and market studies do not consider.

Maximizing the throughput while keeping in mind the safety of the users

When human drivers are passing the intersection, it will not feel safe to them if autonomous cars start planning ideal trajectories around them and overtake them on the right side of the road or cross right in front of their bumper because the autonomous car calculated that this would be possible. This is very risky since human drivers are easily scared and can react unpredictably and cause unavoidable collisions. When this occurs, another problem arises: how to collide as ethically correct as possible. Even if it might not be as efficient, autonomous cars will need to keep a certain distance to human drivers in mind.

However, one of the main advantages of autonomous driving is the predicted increased efficiency as well as safety. This indicates that a trade-off has to be made between the efficiency of the autonomous cars and the safety and the perceived safety of the human drivers, in other words an optimization problem.

In the case of the perceived safety of human drivers, this is influenced by the way in which the autonomous cars plan their trajectory. If they plan their trajectories more aggressively (for example overtaking on the right), this will increase the discomfort of the human drivers. This aggression can be simulated by increasing or decreasing the constraints bound to the freedom of trajectory planning for the autonomous cars. What is less obvious is how to measure the level of discomfort of the human drivers, without the pitfall of resorting to simplified if-then reactions.

Efficiency or throughput are more easy to measure. For this, the mean time cars spend on a normal, autonomous car free crossing can be used. If after implementation of the new crossing this mean time decreases, the efficiency has increased.

The environmental factor

Society is involved in heavy environmental debate in which traffic plays an important role. The implementation of autonomous cars and taxi services, should decrease the CO2 -emission by their increased traffic efficiency. This means that if the throughput of the intersections is increased, society will benefit in environmental terms.

By using the mean carbon footprint of cars, the emission on the crossing can be measured. This will be an additional result to the optimization problem introduced above.

Summary of the initial USE-aspects

The market-share of autonomous cars will change rapidly in the transition period, which is the setting of this research. Therefore, it is important to consider the influence of this change when designing the intersection.

The implementation of safety systems is an important factor in the introduction of autonomous vehicles. Even though the design of such software is subject matter for future work, in this design problem communication failure and the consequences of this can be considered.

An optimization problem is introduced when considering the (perceived) safety of human drivers and the efficiency of the intersection. The latter can be measured and identified, while the human factor of perceived safety leads to reactions that are more complicated to consider, without resorting to unrealistic simplifications.

Literature study

---

In this chapter the state of the art will be identified and summarized.

Current state of the art for autonomous intersection control

There has already been a lot of research on the topic of intersections with autonomous vehicles. For example R. Krajewski, P. Themann and L. Eckstein designed an algorithm for autonomous vehicles at an intersection. They create a decision graph based on choosing the velocities of vehicles and select the best decision based on a cost function. Although it is then proven to work, the system can only work when there are only autonomous vehicles, even though the lack of literature about mixed traffic is mentioned.

Similarly, Tachet R, Santi P created a slot based system which is similar to the reservation system mentioned earlier, except that is uses an simplified intersection. This intersection is the crossing of two traffic flows that go in a straight line. Besides the question whether such simplification is representative of real intersections, the paper simply assumes that there are only autonomous vehicles.

Although rare, more thorough research exists: Kurt Dresner and Peter Stone designed an intersection control system that is based around reservations. Every car would reserve the area of the intersection it needs to use. If the area is already in use, the car has to wait. However the hardware is never discussed. This system assumes that no cars are driven by human drivers. To cope with human drivers it then suggest installing the software and hardware of both the new system and the old traffic light system into the intersection. This means that if a human driver wants to cross the intersection, then a piece of the intersection must become out of bounds for autonomous vehicles. In the simulation results it is obvious that this human driver compatibility was an afterthought: the efficiency difference between 100% and 10% human drivers is insignificant compared to the difference between 1% and 0%. This means that a single human driver massively reduces the throughput of the intersection. The system is then also proven to prefer autonomous drivers over human ones, with a more than 4 times difference in waiting time in worst case scenario.

All the literature mentioned so far in this section have in common that they rely on completely rebuilding the intersection. This could be a costly operation and one could argue that it may not be worth the investment.

To conclude, current literature about intersection control with autonomous vehicles describe the far future situation, which is taken to the extreme: all cars are autonomous and if there are non-autonomous vehicles then the drivers will follow the orders of the intersection without fail. In this far future scenario the costs of completely rebuilding the intersections are ignored and pedestrians often too. Sometimes these facets are mentioned, but just as an afterthought. This results in a gap between two extremes: An algorithm that is optimized for the transitional case where there are still a size-able number of human drivers. And a system that does not require a complete overhaul of the hardware of the intersection.

Intersection algorithm

An overview of the temporary states and the corresponding signal states in Vehicle Actuated Control.

In order to evaluate later results from the simulation, an existing algorithm needs to be researched. Currently implemented in nearly 80% of all intersections in the Netherlands is Vehicle Actuated Control (VAC).

In vehicle actuated control the lengths of green periods are not fixed and depend on the traffic present on the intersection. Signals will only turn if there is traffic present. If a signal turns green it will stay green until the maximum green time is reached or until there is no traffic present anymore. This causes more dynamic and efficient behavior than the simple fixed time control algorithms, which is the second most used in the Netherlands. A schematic of VAC can be found to the right.

There are four traffic light states in total in this algorithm, from one direction the left lane is green, the next direction has a green for the right lane and at the following direction the pedestrians have green. One direction has all red. The algorithm will start to check if a car is present (detected via induction loops) on lanes of this state. If there is no car or pedestrian, the algorithm will go to the next possible state. If there is a car or pedestrian, it will stay green for a minimum amount of time, and will then go to yellow if there are no cars or the maximum green time is reached. The next state is scanned and checked for cars. This is repeated indefinitely.

Sensors in autonomous vehicles

To simulate autonomous cars, it is crucial to know the capabilities of these vehicles. An important point is sensors, which are used to detect vehicles, lanes and traffic signs. There is a large variety in sensors, and each type of car has different sensors. However, the capabilities of the vehicles should be the same. For each sensor, the capabilities, some properties, advantages and disadvantages are presented. This will be used to determine the capabilities of the simulated autonomous cars.

Sensors

Lidar: (Tesla does not have it, only uses camera/radar/sonar)

• Cannot detect lanes;
• Cannot detect Traffic signs/lights;
• Can detect humans;
• Very high cost;
• Lots of data;
• Easier for algorithms to manipulate data;
• 360 view around the car, because it is mounted on top.

Radar:

• Cannot detect lanes;
• Good at detecting motion;
• Cannot detect traffic signs/lights;
• Poor detection of pedestrians;
• Cheap;
• Even less data than camera;
• Cannot detect standing objects;
• Long range: Long range radar is a 20 degree arc out to 174m, medium range is a 90 degree arc out to 60m.

Camera:

• Cheapest
• Lots of data, albeit less than lidar;
• Can detect lanes;
• Can detect traffic signs/lights;
• Can detect humans;
• Needs advanced algorithms to correctly understand images;
• Needs more cameras to get 360 view.

GPS:

• Only sends information about location;
• Cheap;
• Needs a clear view of the sky;
• Sometimes inaccurate.

Ultrasonic/sonar:

• Sensitive to smoke and dirt;
• Very short range (max 5m);
• Very wide range;
• Small devices;
• Needs more devices for 360 view. (12 sensors in Tesla)

Odometer:

• Velocity from wheels and GPS;
• Steering angle from wheels angle sensors.

Current communication systems

As one of the objectives is to incorporate current technology into the design of the intersection that is compatible with autonomous vehicles, research has to be done to determine what communication systems are currently embedded in intersection systems.

VETAG/VECOM

These are systems that can be found in current intersections. VETAG stands for vehicle tagging and uses an induction-loop that is built into the crossing. This loop receives information from buses and ambulances through transponders that are built into the vehicle.

The induction-loop sends out a signal every few time steps and if there is a vehicle with a transponder located above the induction-loop then the intersection will receive information on for example the bus number and bus line in order to know where the bus is going. The correct traffic lights can then become green.

VECOM stands for vehicle communication and is an extension of the VETAG technology. With VECOM, the induction-loop is able not only to receive information, but it can also give information to the vehicle itself; this can be a signal that indicates what crossing the vehicle is nearing.

KAR

The KAR system stands for korte afstands radio in Dutch, which means short distance radio. This system is based on GPS signals, which permanently keeps track of the location of the vehicle by using location determination systems in the vehicle itself. This system eliminates the use of induction-loops, which is beneficial since these can be quite costly. An important feature with this technology is two-way communication. The intersection will likely be sending updates to the car and vice versa. It is unsure what the capacity of this system is, it's more of an overarching term. There is always a possibility of adding more antennas if such a thing occurs.

Algorithm

---

In this chapter the process of creating the algorithm will be explained in more detail. Firstly a bit of context is created; the requirements, preferences and constraints that were set, will be mentioned. The changes in those RPCs will also be noted, giving a better insight in the changes that occurred during the project. The distinction between implicit and explicit algorithms is explained, along with the choice between the two.

After this, the main goals and the bare concept of the algorithm will make an appearance, followed by an explanation of the cost function. Then some design choices that were a result of either the literature study or of keeping track of the USE-aspect will be listed.

To conclude, there is a list of special situations that might occur in traffic, an extensive list of features in the algorithm, a comparison algorithm (Vehicle Actuated Control) and the communication protocol that has been chosen.

Requirements, Preferences and Constraints

In this paragraph requirements, preferences and constraints (RPCs) are listed that the design of the algorithm has to satisfy. The design has to satisfy any requirement that is formulated. This indicates that the requirements need to be specific and measurable.

Requirements

• The algorithm concerns a common four-way intersection with two turn lanes; one for going right, the other one for going left/straight. This limits the combinations of green/red, which is a good thing.
• Without any autonomous cars, the intersection will behave like a normal intersection.
• Autonomous cars know the following data:
  • The current position: Current speed and distance from intersection, entry direction and which lane. (Odometer/GPS/Camera/Compass)
  • It knows if a car is present in a cone of +45 to -45 degrees max 5 meters to either side of the car, no speed measurement. (Sonar)
  • Knows speed and distance of a car behind if its distance is within 5 meters. (Sonar)
  • Knows speed and distance of a car in front if its distance is within 5 meters. (Radar/camera/sonar)
• Autonomous cars will respond to traffic, and will avoid collisions on its own. (Without intersection communication)
• Communication between autonomous cars and intersection contains:
  • Handshake of communication.
  • Intersection can change velocity of autonomous cars.
  • Send locations and possible speeds of cars near the autonomous car and itself to the intersection.
  • Acknowledge data received.
• Using the data of car locations, the algorithm is able to provide more throughput to the directions that has more waiting traffic, to increase efficiency.
• Traffic intensity can be adjusted for all four roads.

Preferences

These are likes and want-to-haves. Measurability is less important.

• The algorithm is able to know when packet loss occurs, and is able to deal with such situations. (Amount of % packet loss can be adjusted)
• When the algorithms notices multiple autonomous cars are together, it will send data for them to become a platoon. However, if there is an significant amount of normal cars, the algorithm will decrease the number of cars in the platoon (communicated vehicle to vehicle).

Constraints

Necessary conditions, design choices are fixed from the start.

• Pedestrians are simulated but no cyclists. (They do not behave significantly different than pedestrians, as the roads can have cycling lanes instead of sidewalks.)
• Pedestrians have a maximal allowed waiting time. This cannot be exceeded. Extremely unlikely to be exceeded.
• Emergency vehicles will not be simulated (will be discussed).
• Cars will be generated according to a Gaussian distribution.
• Autonomous cars behave like human drivers, they do drive in platoons.

Changes in RPCs

Throughout the project, some RPCs have changed as a result of developments in the design process. Some requirements appeared redundant in the later stages of the project and some of the initial decisions in the RPCs were adjusted.

• Speed

An example is the speed of a car. This was thought be vital information to be sent to the intersection. However, cars collision-avoid each other individually and for this they only need differences in distance. Furthermore, location data is enough for the algorithm to work. The intersection does send speed instructions to the cars because a green wave like feature was decided to be implemented, which will be further explained in this chapter.

• Normal intersection

The statement without any autonomous cars, the intersection will behave like a normal intersection was removed. The algorithm is quite different from the most common vehicle actuated control algorithm, so when there are no autonomous cars it will not technically behave like a common intersection. Throughput results (among others) will be compared between vehicle actuated control, the designed algorithm with no autonomous cars and the designed algorithm with autonomous cars.

• Simulation of communication

Initially, the idea was to actually simulate the communication (TCP style) within Java. However, the same output can be achieved by randomly (amount can be adjusted within program) skipping information readouts, temporarily transforming blue cars into red cars but while including platooning.

• Platooning

The original idea was for autonomous cars to switch lanes and group together to form platoons. This proved to be too ambitious due to the fact that only the intersection is simulated and there is no room for normal roads leading up to the intersection. Autonomous cars do platoon when they are randomly spawned behind each other, communication of this type of platooning is done vehicle to vehicle and the intersection is not involved whatsoever.

• Maximum allowed waiting time implementation

The designed algorithm is a cost function. Therefore a maximum on the waiting time is in fact mathematically traversable. Even when cost constants are close to infinity (which are not feasible), it is possible that the maximum waiting time is exceeded. A trade off will occur between the intersection deciding what is the most efficient and pedestrians not having to wait the maximal allowed waiting time.

Type of Algorithm

When creating an algorithm where path-planning is involved, one can choose to use an explicit algorithm, but there is also the option to use a neural network to have the autonomous cars learn for themselves. For this project, the choice was made to use an explicit algorithm. This is because the neural network problem is very complex and not always ethically correct. When these networks become more and more complex, the origin and the strategy of the decisions become untraceable, since these networks can grow more and more complex beyond the level of human comprehension.

Also manipulation is a large problem regarding neural networks, especially in the use of automated vehicles, since ethically there are a lot of stakeholders. Companies might prefer to manipulate the neural network in such a way that the people using their cars are prioritized in dangerous situations.

An explicit network, however, is very transparent. Everything about the algorithm is known and therefore not as easily manipulated. To achieve reasonable results from a neural network, a large knowledge base has to be constructed. For this project however, a good quality result can be achieved without the use of complex neural networks that bring ethical problems. For these reasons the choice was made to use a transparent, explicit algorithm.

Concept of the Algorithm

Two things that the algorithm tries to achieve are:

• Better throughput due to usage of dynamically gathered estimations of traffic;
• Smoother driving experience and less pollution by telling autonomous vehicles when the light will go on green, so it arrives at the light just in time.

The latter point is not a very complex algorithm, but requires the algorithm of the former to know ahead of time what state it is going to be in.

Using estimations of the lane usage, it is possible to determine for all 18 states how many cars would be given a green light by switching to that state. Then the algorithm simply selects the state with the highest number. The algorithm should not let any individual wait too long. As such there is an upper limit for both the cars and the pedestrians on how long they are expected to wait at most. If this threshold is reached, then the algorithm should always turn the associated light green after the next state transition.

Combination of states

There are 18 possible combination of states that the traffic lights can be in. With a state is meant the combination of red and green lights at the intersection at a certain time. The list of states is as follows:

• All pedestrians green, all car lights red;
• 4 rotations of one right turn car lane green, 2 pedestrian routes green;
• 4 rotations of two right turn car lane green, 1 pedestrian route green;
• All right turn car lanes green, all pedestrians red;
• 4 rotations of one left and straight car lane green, one right turn lane green and one pedestrian route green;
• 4 rotations of one left and straight car lane green, two right turn lanes green and all pedestrian routes red.

The number of combinations is very limited due to the fact that left turns block all but one straight car route, the only straight car route it does not block is located on the very same turn lane.

Cost Function

The basis of the algorithm is formed by the cost function. This method was beneficial for the algorithm design since different features could be added, altered and weighed throughout the design process in order to find a good balance in the cost function. The cost function represents the cost of having a light remain red. This cost consists of three elements: traffic, wait time and wait limit, as shown in the equations below.

• [math]\displaystyle{ Cost_{Lane} = Cost_{traffic} + Cost_{wait time} + Cost_{wait limit} }[/math]
• [math]\displaystyle{ Cost_{Lane} = N + R + C_1 \times t + P \times (t \gt T_{1}) }[/math]

Where ‘N’ is the number of autonomous cars in the turn lane, ‘R’ the number of normal cars in the turn lane as reported by the autonomous cars (R is smaller or equal to the total number of normal cars in the turn lane). Together the term N+R forms the traffic cost. In other words, the cost goes up when there is more traffic in a lane. ‘[math]\displaystyle{ C_1 }[/math]’ is an arbitrary constant that defines the importance of wait time and 't' the time since the first car started waiting in this lane. So the longer a car is waiting, the higher the cost becomes. 'P' is the cost penalty for having a lane wait too long (value should be arbitrarily large) and [math]\displaystyle{ T_1 }[/math] the maximum time a vehicle can be expected to wait at a intersection. In this way, no vehicle should ever wait longer than the maximum waiting time defined by [math]\displaystyle{ T_1 }[/math]. Note that due to the way this cost function works 't' can slightly overshoot [math]\displaystyle{ T_1 }[/math] before the lane light goes on green, [math]\displaystyle{ T_1 }[/math] therefor need to be adjusted accordingly.

As pedestrians are also a crucial part of an intersection system, a cost function has also been constructed for the pedestrian lanes. This is quite similar to the cost function for the car lanes, however the traffic quantity element is excluded, since the current intersection system can register that there are pedestrians present at a crossing, but now how many pedestrians there are. The cost function for the pedestrians is as follows:

• [math]\displaystyle{ Cost_{Pedestrian lane} = Cost_{wait time} + Cost_{wait limit} }[/math]
• [math]\displaystyle{ Cost_{Pedestrian lane} = C_2 \times t + P \times (t\gt T_{2}) }[/math]

With its own values for [math]\displaystyle{ C_2 }[/math], [math]\displaystyle{ T_2 }[/math] and P.

The cost for each state is the sum of the costs of all lanes that remain red in that state. However, to reduce computation time, the algorithm will calculate the cost reduction instead: This is defined as the sum of the cost of all lanes that will become green in that state. The algorithm will then select the state that causes the biggest cost reduction.

Several Design Choices

Resulting from the literature study and the USE-aspects, several design choices have been made that influence the algorithm. These will be discussed in this paragraph.

Packet loss

As was shown in the USE-aspects in the Focus, Objectives and Approach chapter, fear of hacking and loss of ability of the car, plays a significant part in the user acceptance of autonomous vehicles. However since the security of the system of the cars and the intersection is outside the scope of this research, this cannot be explored in-depth. Packet loss, i.e loss of communication between the intersection and the car, is however an aspect that can be taken into account in a straightforward way. Since the intersection is filled with regular human driven cars that do not communicate, it is logical to make the default state of both the algorithm and the vehicles to be just like that:

• If an autonomous car cannot contact the intersection, it will default to simple intersection behavior;
• If an intersection cannot contact an autonomous car, then it cannot even know that it exists, so it will treat it like a normal human driven vehicle.
• If communication fails halfway through, the autonomous car will again switch to the default behavior.

This can be simulated by replacing the autonomous car with a human driven one. However, complete packet loss is an extreme case of failure: The communication does not work at all.

Packet loss is a generic way to describe all communication transmissions that fail. If a set of data, called a packet, fails to be in any way or shape received correctly, the packet is considered lost. A 100% packet loss is what has been discussed so far, but realistically a system does not switch between 0% and 100%, but fluctuates somewhere in between. This can have many causes, from interference to hardware failures. It is important not to assume the cause of the losses. Therefore, the algorithm cannot assume anything about why a vehicle has stopped responding for a few seconds. Simulating packet loss can be done by rolling a dice every time the algorithm accesses data of an autonomous car or every time it tills a car something it has to do. In the code this will often result in a random generator being called before each communication, then if the random generator says it fails, it should skip the communication code. This is best explained by an example: Let’s say there is an algorithm that estimates how many cars there are on each lane, it does so by asking each autonomous car where they are. In the simulation code this would involve the algorithm to go over a list of cars and then accessing it coordinates. Packet loss would then be simulated by having the algorithm skip a vehicle. This means for the algorithm that it will underestimate the number of cars in that lane. However, this estimate is still better than the old detection system that could detect at most one car. So here packet loss interferes but does not break the system. Note however that due to the (pseudo)-randomness of packet loss the estimate of number of cars in a lane will fluctuate, therefore the algorithm that uses this data must be able to cope with this.

Packet loss also occurs in the other direction. For example, when the intersection wants a vehicle to not drive through green, it could send it a message telling it not to drive through green. However due to packet loss it might not receive this message and as such it will just continue on its way. The algorithm can therefore not assume the vehicle actually does what it is told. At this point is might be obvious that any message telling a vehicle not to do something is bad design.

For safety purposes it might be necessary for all the communication to require acknowledgement responses. This way there is a significant chance the packet loss is detected and corrected by re-sending the message. However, remember that this acknowledgement message can get lost too. So even in this case it is still important that the algorithm does not make the assumption that communication succeeds.

Packet injection (hacking)

For most part this is a matter of security. The only real way to prevent this is using encryption and other security techniques like obfuscation. For the most part this would be integrated into the communication system. In this project we are going to assume this does not happen. If hacking does happen, then the ship is already lost. Putting our lives at the hands of systems that are hack-able is normal these days. From aviation to the military, the dangers of hacked communication are real, but also very complex. All in all, while relevant, this is far beyond the scope of this project.

Spawning

It was decided not to acquire real traffic data and to insert that into our simulation. In real life vehicles have different length (vans, trucks, etc.); These are not included in the data. And and intersection has to be found with the exact same layout. This could be done, but it is also possible to compare different algorithms under different conditions with the same cars being spawned by using specific random seeds.

The time between vehicle arrivals in the simulation is composed out of three components: a base time that defines the minimum time between vehicles, a slider dependent time that allows the user of the simulation to determine the number of vehicles that arrive at the intersection and a random number, because vehicles arrive at an intersection in an unpredictable manner, or at least one should not assume it is predictable. This random number is a Gaussian distributed random variable.

Random seed and the auto-tester

In order to be able to compare multiple algorithms, they need to be tested in comparable situations. The random spawning of vehicles make causes the results of the simulation to be “noisy”. Sometimes the generator creates more or less favorable traffic. As a result one algorithm could get easier traffic than the other.

This can be avoided using a random seed. This random seed defines the results of the pseudo-random number generators. Using the same seed twice results in the exact same traffic. Allowing for accurate comparisons between algorithms.

These random seeds are automatically handled by the auto-tester. This system build into the simulation will run several consecutive experiments without requiring human input. One simply sets the simulation settings as the user wants it and then presses the A button. Now the auto-tester will expose several algorithms to the exact same traffic as defined by the random seed and settings. The auto-tester will generate a new random seed for each set of tests. It will run these tests at maximum simulation speed and will reset the speed back to normal once it is done. It also displays the results on screen allowing for quick comparisons.

Gauging

Every few years some intersections - especially in the city - need to be gauged and updated to handle changing traffic flow. This is a problem our intersection solves, since live traffic data is present to make efficient decisions. This leads to reduced costs for the municipality and an increases throughput in dynamic situations including holidays, rush hour and local events.

Green Wave like effect

The Green Wave system works by synchronizing several intersections to allow large groups of cars to pass through the region in one go. Using communication with autonomous cars could allow these vehicles to set the pace of other cars behind them in order to improve the effectiveness of the system. It is unpractical to set up a communication network along roads and between several intersections in order to communicate effectively with autonomous vehicles. This is also not the aim of this project. The goal is to create an effective intersection that is compatible with autonomous cars while keeping the current infrastructure and system intact. However, a Green Wave like effect can be used in another way by just the one intersection that the autonomous vehicle is approaching. The car will receive an estimation of what state the intersection will be in when it arrives at the intersection. This information will initially have a large error when the car is quite far away and this error then decreases as the car moves closer to the intersection.

Communicating the green wave cruise speed with autonomous cars to normal cars

As a consequence of receiving the information about the states from the intersection as described above, the autonomous car will adjust its driving speed to the information that it receives. When human drivers encounter a Green Wave, they receive information via an LED-sign that says, if they drive a certain speed that is either equal to or lower than the maximum speed, they will have green light for an indicated number of times. However, not every driver tends to stick to the advised speed that is indicated on the Green Wave sign. Therefore, irritations and aggressive behavior can be provoked when autonomous cars adjust their speed to the information provided by the intersection. In order to maintain the safety of the users of autonomous and human-driven cars, the human drivers need to be provided with information on the behavior of the autonomous cars while they are driving so that they know what to expect when approaching an intersection.

In order to increase acceptance, it is important that drivers know what they can expect when nearing a crossing. Without any knowledge about how autonomous cars work, drivers might become annoyed by autonomous cars that adapt their speed to below the speed limit. A way in which acceptance of for example waiting time is increased among cyclists and pedestrians and that also decreases the aggression and risk of them running a red light is by implementing a traffic light that shows how long it takes before their light turns green. The advantage here is that people know what to expect when waiting at a traffic light. While nearing a crossing without information that autonomous cars are adapting their driving, human drivers may become confused.

For this reason, a method to increase the acceptance and decrease the aggressiveness of some drivers, signs can be put up beside the road that indicate that autonomous cars are adapting their driving to the situation handed by them through the intersection system. It will also help to send the human drivers approximately the same information as the autonomous cars, which might stop human drivers from feeling deprived of advantageous information. They will also know exactly what behavior to expect on the road as they approach the crossing, which should stop some of the aggression and might make some people follow the lead of the autonomous cars. If the information that the autonomous cars genuinely leads to greater efficiency, it is expected that some of the human drivers will realize this and start following the autonomous cars. This could then indirectly lead to platooning with human drivers and autonomous cars if the autonomous are clearly recognizable for the human drivers, however this is still only speculation.

Specific Situations

Not everything can be simulated. In this chapter some situations are explained and elaborated on why they are not in the simulation and how it would affect the intersection if they were. In some situations, the designed intersection cannot add something to that of a normal one. There are also situations where it does not matter if it is a normal or an autonomous car that encounters a situation. In these specific cases, the answer is always the same: it will not be implemented in the simulation. Therefore, before each situations the following questions are asked: What are the actions for the intersection? Does it matter if there is a normal or an autonomous car involved?

• Emergency traffic, ambulances

When emergency traffic needs to pass through the intersection at high speed, several lives are ON the line. The intersection helps these vehicles and reduces the chance of an accident by setting all lights to red. This is already implemented in the KAR-system so it does not need to be included explicitly in the simulation. In real life situations, traffic moves to the sides for the emergency services.

A question that arises is, do autonomous cars move out of the way when an ambulance approaches? As of yet, only Google is actively working on this feature. It works by detecting light patterns. In case of Tesla - which is a semi-autonomous vehicle - the users are responsible for moving out of the way. A feature for the future could be that intersections sends information of the emergency traffic to the autonomous cars for them to react upon, since direct light from the sirens can easily be blocked. This way, traffic is less dependent on their own sensors.

• Traffic accidents

It is even a hard situation for human drivers when an accident happens on the intersection itself. More often than not, traffic regulators or local police helps direct traffic. For the intersection to act when a collision happens, it first needs to detect a collision. If an autonomous car is involved it could be handled fairly easily. However, when two normal cars are involved, it can be quite difficult for the intersection to detect. Human drivers will often drive past the accident after most of the debris is cleared. It is a bad solution to set all light on red until the emergency services arrive, since people will become impatient. Situations including damage and injury, are often best solved by humans themselves. Autonomous technology is not advanced enough to think of the best way for the intersection to react to such a situation.

• Speeding traffic/road rage

An interesting situation is when an autonomous car detects a car speeding when headed to the intersection or driving through red. As in the situation with traffic accident, it is a bad idea to set all the light on red, since it would benefit the offender and is very susceptible to abuse. It is not convenient for autonomous cars to become moving speed cameras since the accuracy of these speed measurements is questionable. Aside from the accuracy, installing speed cameras alongside the road is in this case a less invasive and less expensive option.

• Platoon overtaking normal cars

Normal drivers can be scared when they see an autonomous platoon drive next to them. They have no visible drivers and are extremely close to each other. There is actually not much of a difference between the behavior of a platoon and an elongated vehicle. At first, it might look a little strange but the expectation is that it is very unlikely for drivers to be completely distracted when they see a platoon. Over time (half a year, when all drivers have seen a platoon) a little strange will become normal.

• Platoon braking/accelerating close to each other near normal cars

Normal cars do not participate in a platoon. The platoon itself maintains a safe distance between normal cars and will prevent normal cars from purposefully breaking up such a platoon. Just like the previous point, there is not much of difference between the behavior of a platoon and an elongated vehicle. There is no point for the intersection to prevent platoons from forming in specific situations.

• Autonomous cars acting as buffer (slower driving)

A situation that might be peculiar for drivers is when autonomous cars will drive slower than the maximum speed. This might also be very annoying. In some cities traffic signs display the best speed to drive for a green wave. The designed intersection sends this information to the autonomous cars, giving them the ability to act like buffers for traffic behind them. It is built in the simulation but because there are no long roads it is very difficult to see. The effectiveness is the highest when there are multiple intersections and roads involved (which are not simulated but very interesting for follow-up studies). To prevent annoyed human drivers that are forced to drive slower, having signs alongside the roads or a way for the autonomous cars to communicate back is necessary.

• Algorithm with different types of vehicles

The algorithm should be able to handle different vehicles like vans, buses or trucks. Currently only one type of car is simulated. Cost function variables will be slightly different because for example: more people fit inside a bus and trucks are longer and pollute more. For the intersection to detect and distinguish between these vehicles extra information from the camera sensors of the autonomous cars will be needed. This will make the algorithm progressively more complicated, and for this reason is not implemented in our version (but again, very interesting for a follow-up study).

List of Features

In order to create an overview of the implemented elements of the algorithm, this paragraph provides a list of features that the algorithm contains.

• System states. A list of all possible combinations of green and red lights that are logical for an intersection situation and that are safe (so no crossing vehicle paths). The list is ordered such that the system state that is most favorable for pedestrians is at the beginning of the list and the ones most favorable for the cars at the very end.

• Transition between system states. The transition between system states is done in two steps; In step 1 the relevant lights are set to yellow and in step 2 they are then set to red. Pedestrian lights stay green during step 1 (since they are never yellow). If a light is green in both the original and the new state, it will remain green during the transition.

• Car detection and timers. Modeling the old-fashioned detection system that detects whether there is a car waiting right in front of the traffic light. The time that this one car is waiting and the time that there are no cars waiting are measured.

• Turn lane traffic estimation using autonomous vehicles ability to communicate efficiently and automatically. The algorithm collects from each autonomous vehicle in which turn lane they are located and whether there are cars in front and behind them. This data is then used to estimate the total number of cars in that turn lane. This means that for an accurate estimation it is not necessary for all cars to be autonomous.

• Announcing time till green to autonomous vehicle in order to create a green wave like effect. By telling autonomous vehicle when their light will be green, they will be able to adjust their speed in order to arrive just on time at the light.

• Cost function calculation per lane and then the cost reduction calculation for each system state. The algorithm will first calculate the cost per turn lane/pedestrian crossing and then put the cost reduction for each system state in a list.

• Cost function components:
  • R + N, reported number of vehicles plus the number of autonomous vehicles. This estimates the number of vehicles in a lane. Pedestrian lanes do not have this component.
  • [math]\displaystyle{ C*t }[/math], a constant times the time that a vehicle has been waiting. This makes sure that vehicles waiting longer will be given a green light sooner.
  • [math]\displaystyle{ P*(t\gt T) }[/math], a penalty will be given if a vehicle has been waiting longer than T. This prevents vehicles from waiting too long at the intersection. Contrary to the other two components, this does not improve throughput in any way.

• Selecting the optimal system state based on their cost reduction. The algorithm will select the system state with the highest cost reduction as the next system state. If two system states have the same cost reduction value, then the one earlier in the list is chosen. Due to the order of the list, this results in a preference towards pedestrians.

• Estimating the next system state for the green wave like effect to work better. Whenever the algorithm selects a system state, it will also estimate which system state is going to be selected next. It does this based on the assumption that the lanes associated with the just chosen system state are empty. This estimation will of-course regularly fail.

• Packet loss simulation. Whenever the algorithm receives or sends data to the autonomous vehicles, there is a random chance it fails. In these cases the algorithm either has less data to work with or the autonomous vehicle does not know when its light is going to be green.

Comparison Algorithm

In order to evaluate the results from the simulation a comparison needs to be made between the newly created algorithm and an existing algorithm. The existing algorithm is called Vehicle Actuated Control and is currently implemented in nearly 80% of the intersections. This algorithm was explained in the literary review. However, this algorithm will have to be adjusted to be compatible with autonomous vehicles in order to be comparable to the new algorithm. When this adjustment is done, the functioning of the two algorithms can be compared for different percentages of autonomous cars on the intersection.

It is possible that the existing algorithm is more successful than the new algorithm when there are no autonomous cars present on the intersection. This is due to the fact that the existing algorithm has been created to function optimally for a traffic situation with only human drivers, while the new algorithm is made to function optimally for different percentages of autonomous cars on the intersection. So in case the existing algorithm proves to be more efficient in a situation with only human drivers, this does not disprove the efficiency of the new algorithm.

The algorithms will be compared for different percentages of autonomous cars as well as different traffic situations, like a situation when an ambulance approaches the intersection or a pedestrian who crosses through a red light. For more information on the different situations that will be tested, see the Specific Situations Wiki chapter.

Communication protocol

In order to make the algorithm work, a communication protocol has to be implemented in the intersection system. Following the literature research on current communication systems that exist between intersections and busses and ambulances, the KAR system was identified. This is a system that is already present in current intersections. It is based on a short distance radio.

When implementing it into the situation with autonomous cars, every autonomous car will be able to send information on their position, provided by their navigation system, to the intersection. The intersection is then able to know where every autonomous car is on the intersection. In reverse, the intersection is able to send information to the autonomous cars as well. In that way, the cars can anticipate on the time they will have to wait at the intersection and adjust their speed accordingly so a minimum amount of breaking and quick speed reduction is required, which increases the comfort for the autonomous car users.

It is also possible to implement a reservation system into the KAR system as it is already used for buses. The bus can now send their route information to the intersection so that the intersection knows how high the priority for that bus is. The same system could be used for autonomous cars. However, the question is how fair this is toward human drivers who will not be able to send their level of priority to the intersection. Therefore, it might not be user-friendly to implement this part of the KAR system into the intersections. The system should be used though when an ambulance or police car approaches.

Another aspect of the communication protocol is to make use of the detection loops that are embedded in the roads. These differ from the more expensive communication loops that are used by the VETAG and VECOM systems as described in the literature study, in the sense that they only register when there is a car on top of the loop. This system can register only that there is a car and not how many cars are present. So whenever there is a non-autonomous car present at the intersection on the loop and there are no autonomous cars that can register this car, the vehicle will still be registered.

By using the communication protocol described above, the currently embedded software can be utilized without having to rebuild the entire intersection and changing its systems.

USE aspects

---

In this chapter the USE-aspects of the algorithm will be explained and evaluated. The traffic in the simulation can be divided into two categories: the cars and the pedestrians. Both of these categories are influenced by the behavior of the intersection system. Therefore, both of these have to be evaluated. In the first paragraph, the USE-aspects for the cars will be discussed where a distinction is made between autonomous cars and non-autonomous vehicles. In the second paragraph, the USE-aspects for the pedestrians are discussed.

USE-aspects for cars

Cost function

The algorithm is based on a cost function, which allows for inclusion of different influences that affect the users. As stated in the Algorithm section, the cost-function for the cars is:

[math]\displaystyle{ Cost_{lane} = (N + R) + C_1 \times t + P \times (t\gt T_2) }[/math]

Example of priority issue in the cost function.

The different variables are explained in the Algorithm Chapter. This equation indicates that the cost for the traffic consists of the number of registered autonomous cars and the number of non-autonomous cars that have been registered by the autonomous cars and the detection loops that are present in the intersection. The cost of the wait time is determined by the time that the cars are waiting at the intersection and an arbitrary constant which defines the importance of the waiting time. The last term is the cost of the wait limit. The maximum waiting time is defined by [math]\displaystyle{ T_2 }[/math]. Whenever the actual waiting time exceeds the maximum waiting time, the cost for this lane will increase significantly as P is a constant that is arbitrarily large.

Another noticeable aspect of the cost function for cars is the term N+R, where N is the number of autonomous cars that the intersection has registered and R is the number of reported non-autonomous cars that have been detected by the autonomous cars. This means that the cars that are not at a detection loop or are directly behind or in front of an autonomous car, will not be registered in a lane. This means that in case a lane consists of several autonomous cars and a few non-autonomous cars, this lane will be prioritized over a lane that may consist of a larger total number of non-autonomous cars as sketched in the image below.

In the situation to the right the red dots indicate non-autonomous cars and the blue dots indicate autonomous cars. In the lane with five non-autonomous cars only the first car is registered by the detection loop in the intersection. In the lane with four cars, the two cars that are autonomous register two non-autonomous cars. Should the cost function be built in a way that this problem frequently occurs, this would be unethical. However, there are other factors that even this problem out. In reality, the situation sketched above is extreme as also other factors play a part in determining the priority of the lanes. Autonomous cars will generally be spread over several lanes, especially when the percentage of autonomous cars on the road increases. This indicates that the difference in situations between the lanes will be less than what is sketched in the above situation.

From this analysis can be concluded that in extreme situations (especially when there are still only a few autonomous cars on the road), the cost-function can behave unethically. However, in reality the situation is more nuanced by influences from several lanes and pedestrians.

Influence of green wave like effect on human drivers

The idea of the green wave like effect for autonomous cars is that the intersection sends information about the current states and expected states to autonomous cars that are nearing the intersection. This information has a certain error that decreases as the car comes closer to the intersection. As a consequence, the autonomous car will adjust its driving speed to the information that it receives. This corresponds with the known principle of the “green wave” where drivers are notified via a sign that, if they drive a certain speed that is either equal to or lower than the maximum speed, they will have green light for an indicated number of times. Not every driver tends to stick to the advised speed that is indicated on the “green wave”-sign. Therefore, irritations and aggressive behavior can be provoked when the fact that autonomous cars adjust their speed to the information provided by the intersection. In order to maintain the safety of the users of autonomous and human-driven cars, the human drivers need to be provided with information on the behavior of the autonomous cars while they are driving so that they know what to expect when approaching an intersection.

In order to increase acceptance, it is important that drivers know what they can expect when nearing a crossing. Without any knowledge about how autonomous cars work, drivers might become annoyed by autonomous cars that adapt their speed to below the speed limit. A way in which acceptance of for example waiting time is increased among cyclists and pedestrians and that also decreases the aggression and risk of them running a red light is by implementing a traffic light that shows how long it takes before their light turns to green. The advantage here is that people know what to expect when waiting at a traffic light. While nearing a crossing without information that autonomous cars are adapting their driving, human drivers may become confused.

As the previous shows that drivers need to know what to expect, signs can be put up beside the road that indicate that autonomous cars are adapting their driving to the situation handed by them through the intersection system. It will also help to send the human drivers approximately the same information as the autonomous cars, which might stop human drivers from feeling deprived of advantageous information. They will also know exactly what behavior to expect on the road as they approach the crossing, which should stop some of the aggression and might make some people follow the lead of the autonomous cars. If the information that the autonomous cars genuinely leads to greater efficiency, it is expected that some of the human drivers will realize this and start following the autonomous cars. This could then indirectly lead to platooning with human drivers and autonomous cars if the autonomous are clearly recognizable for the human drivers.

In order to implement the signs for the human-drivers, the currently existing green wave LED-signs may be used. Additionally, a larger sign may be placed along the road that shows an image of the autonomous car situation.

Safety

As mentioned in the Focus, Objectives and Approach chapter, the user might be fearful of malfunctioning of the technology as this could be life-threatening. To this end, the simulation includes the case in which packet loss occurs. When the communication with the intersection fails, the autonomous vehicles will not receive any information on the states of the intersection. This will imply that the autonomous car starts behaving like a human-driven vehicle and react to the situation as it is. This will not endanger any of the passengers in the autonomous car where the packet loss occurs or the surrounding traffic. However, it will take away the advantage of receiving the information from the intersection and therefore the amount of comfort the passengers experience will decrease.

USE-aspects for pedestrians

The cost function for the pedestrians is quite similar, with terms for the wait time and the wait limit as shown in the following equation.

[math]\displaystyle{ Cost_{pedestrian lane} = C_2 \times t + P \times (t\gt T) }[/math]

Noticeable is the exclusion of the N+R term from the pedestrian cost function. This is because the number of pedestrians is not measurable when using the current technology in the intersection. This would indicate that the cost for the pedestrians is generally lower than the cost for the cars, which would prioritize the cars over the pedestrians. This is not user-friendly as pedestrians are often exposed to weather while waiting. If they are always forced to wait the maximum waiting time, this would create a large level of dissatisfaction with the pedestrians and this would discourage people to come by foot, which would indirectly be bad for the environment. The way in which this is solved is by tuning the [math]\displaystyle{ C_1 }[/math] and [math]\displaystyle{ C_2 }[/math] constants so that these bring the cost functions closer together. Also in the case of bad weather, the constant [math]\displaystyle{ C_2 }[/math] may be tuned to have even more impact to ensure the comfort of the pedestrians. Also, in case several intersection states have the same cost, the priority will go to the states that allows for the pedestrians to cross that have waited the longest.

Since waiting longer than maximally tolerable is not user-friendly, the value P is arbitrarily large to ensure that no lane waits more than the maximum allowed time T. This is applied for pedestrians as well as cars.

When the cost of several states are equal, pedestrians are prioritized because of their generally lower level of comfort (due to being exposed to weather and other factors outside at a busy intersection). Also their cost function is brought closer to the cost function of the cars by tuning the [math]\displaystyle{ C_1 }[/math] and [math]\displaystyle{ C_2 }[/math] constants, which results in less prioritizing of cars over pedestrians due to the missing traffic factor in the pedestrian cost function.

The cost function as presented will ensure the dynamic behavior of the intersection, which makes sure to increase efficiency to benefit user, society and enterprise, but which also increases the fairness of an intersection algorithm as for example more vulnerable users like pedestrians are prioritized when the cost of several states is equal.

Simulation

---

Frontend of the simulation.

In this chapter some details on the implementation of the algorithm are discussed. First the junction that is simulated will be explained. Next the features of the simulation will be listed. A link to the source code can be found here as well as a link to the simulation. Here is the latest version of the simulation. Source code is available here in .zip. The exact implementation of the cost function in code.

Intersection explanation

A common four way intersection with two turn lanes at each side, one for going right, one for going left and straight. Originally the intersection had no turn lanes, but this form of intersection is too uncommon to be representative of the general case. Besides this, an intersection with no turn lanes on any side could very easily be improved by allowing right turn on red for autonomous cars in some cases, but this is a trivial improvement to a simple scenario.

The intersection represents a common traffic light crossing between two one-lane roads. Besides this there is also a simulation of pedestrians, however there is no simulation of cyclists. No simulation of cyclist is needed as, from the intersection point of view, they do not behave differently enough from pedestrians to make a difference for our algorithm, as the roads can just have cycling lanes instead of sidewalks.

Simulation features

Here the simulation features are listed.

• Pedestrian simulation. Pedestrians will cross the intersection when given a green light. Pedestrians will be spawned to arrive in any of the four direction with the intend to get to any of the three remaining direction.
• Car simulation (represented by the red cars). Cars will be spawned at one direction with the intend to get to any of the three remaining direction. This means that the turn lane for traffic that want to go left or forwards is about twice as busy. They have a chance of being a autonomous vehicle. Cars have momentum and need time to accelerate and brake. They will stop for red lights and will not drive into the cars right in front of them. If for any reason cars do collide, the car will throw a CollisionException, which is handled elsewhere in the code.
• Autonomous car simulation (represented by the blue cars). Will be spawned just like the normal cars, and will also behave like the normal cars.
• Platooning. Autonomous cars can form platoons with other autonomous vehicles using vehicle to vehicle communication. This feature can be disabled and re-enabled.
• A simulation world with visible traffic lights.
• Pause and simulation speed functionality.
• Automatic pausing on CollisionException. Will also change the title of the window to indicate that a crash has happened. Some debug data will be printed to the console if available.
• Sliders. An simplistic user interface based primarily around sliders. These sliders determine the amount of cars and pedestrians (and for cars also from which direction), percentage of cars that are autonomous, amount of packet loss, and the simulation speed.
• Measurement results displayed on screen. The user interface contain several location were measurements of the simulation are shown. In the top left the measurements of the simulation right now are shown. In the bottom left, when the auto-tester is used, there are also the measurement results per algorithm.
• Auto-tester. Fairly compares multiple algorithms by supplying the exact same traffic to both the algorithms. Outputs the results in the bottom left screen and also to the console if available.

Simulation Controls

The simulations is primarily controlled using sliders. The User Interface of the simulation only supports mouse clicks. Therefore do not attempt to click and drag the sliders, instead click at the location you want the slider to be.

The simulation has the following sliders:

• Total cars. Determines the number of cars the simulation will spawn. This determines the traffic load on the intersection.
• Auto percentage. Determines the percentage of cars that is autonomous. Autonomous cars are shown in blue and normal cars are shown in red.
• Total pedestrians. Determines the number of pedestrians the simulation will spawn.
• Packet Loss. Determines the rate of packet loss. Note that this slider does not affect algorithms that do not use communication or do not support packet loss.
• Simulation Speed. Determines the speed of simulation. Speeding up the simulation does not reduce its accuracy in any way.
• Traffic Bias (Direction). Determines the spawning bias of this direction. The higher the bias the more likely a car will come from that direction. The values of these sliders are relative to each other. If one slider has a value n times as high as an other, that direction will get n times the traffic. These sliders therefor only determine the distribution of cars. How many cars are to be distributed over the four direction is determined by the Total cars slider.

Besides sliders, there are also a few buttons:

• SPACEBAR. Pause/Unpause the simulation.
• P. Turn Platooning between autonomous vehicles on/off.
• R. Resets the simulation. Also stops the auto-tester and auto-tester automatic testing and turns any unit test of.
• A. Starts the auto-tester. This will run both Vehicle Actuated Control (VAC) and the newly created algorithm and gives them the exact same traffic. It will display the results once its done with an algorithm.
• 0. Turns off the current unit test.
• 1. Starts an Unit Test, this will simply run the newly made cost function algorithm. Referred to as COST_AUTO_PL by the simulation.
• 2. Starts an Unit Test, this will simply run Vehicle Actuated Control (VAC).
• 3. Starts an Unit Test, this one will run the newly made cost function algorithm, but with packet loss ignored (The packet loss slider will not affect this). Referred to as COST_AUTO by the simulation.
• 4. Starts the Green Wave Like Effect Unit Test. This will run the newly made cost function algorithm, but gives it a traffic situation that makes the green wave like effect more obvious. This Unit Test is useful to debug the green wave like effect, because autonomous vehicles are colored depending on how much data they have received. Cyan means that the vehicle has an estimate of time till light goes green, and green means they now exactly when the light becomes green.
• 5. Runs the Auto-tester Automatic tester. This will automatically run the auto-tester 10 times and then display the average of the results. This was used to collect large quantities of data for the final results of the project. Warning: Takes a long time to finish (10 to 20 minutes).
• D (Advanced users only). Toggles the displaying of debug data. This includes cost per turn lane, waiting times, light state in text form. The red crosses on the screen are a visualization of how the cars detect other cars so they do not drive into them.

Results

---

Hypotheses

Several aspects of the simulation will be measured, these include: efficiency, packet loss performance, CO2-emissions and comfort. A lot of parameters can be changed, so it is imperative to predetermine all the different settings before any measurements are done. Each measurement is the average of 500 cars passing through the intersection, with the first 500 cars being skipped to get to an equilibrium. Each measurement is automated and done in the programmed autotester.

• Efficiency
  

  Hypothesis of algorithm comparison for efficiency measurements
  • Value to measure (y-axis): Average Delay, total time through intersection minus travel time.
  • Value to change (x-axis): %A Percentage autonomous cars.
  • Four different situations: 4 lanes with medium traffic, 1 lane heavy + 2 medium + 1 light, 1 heavy + 1 mid + light, 2 heavy + 2 light.
  • Four lines each graph: Vehicle Actuated Control #cars 30% and 90%, Our algorithm #cars 30% and 90%.
  • Settings: Pedestrians at 35%, packet loss off.
  • Hypothesis: The worst case comparison scenario is when VAC is already more efficient when there are no autonomous cars, so this scenario is assumed. Platooning occurs in both algorithms so a decrease in delay with increasing autonomous cars should be expected. Additionally, a slightly larger decrease with CF algorithm is expected since car detection is not present in the VAC algorithm. Green wave implementation should have no impact on delay. In the measurements with low car count we suspect a smaller increase in efficiency, mainly due to the fact that there is less room for improvement in these measurements. It will be interesting to see if different situations will have an effect on delay, if they differ a lot, the following measurements will also be need to be done on different situations.

• Packet loss efficiency
  

  Hypothesis of packet loss efficiency measurement. Y-axis: delay, X-axis: %P, Blue line: %A=0, Light blue line: %A=25, Cyan line: %A=50, Light gray line: %A=75, Grey line: %A=100.
  • Value to measure (y-axis): Average Delay.
  • Value to change (x-axis): %P Percentage of packet loss.
  • Five lines each graph: %A=0,25,50,75,100.
  • Settings: 4 medium traffic, pedestrians at 35%, #cars = 50.
  • Hypothesis: Packet loss disables an autonomous car from sending how many cars it has spotted. With these results we can easily check the effect of platooning versus car counting, at %P=0 car counting and platooning will be available but at %P=100 only platooning. Each increase of %A will lead to a lot slower times at lower values of %P but less at higher values. A graph not unlike the one on the right will likely come from the measurements. Note that at %A=0 nothing will change, this is measured to check for convergence and stability.

• (Dis)Comfort
  • Value to measure (y-axis): Comfort, integration of all acceleration and deceleration.
  • Value to change (x-axis): %A Percentage autonomous cars.
  • Four lines each graph: Boon's algorithm #cars 30% and 90%, Our algorithm #cars 30% and 90%.
  • Settings: Pedestrians at 35%, packet loss off.
  • Hypothesis: The only feature that will have an effect on this measurement is the green wave implementation. The integration value is higher when the passengers are rocked, so a steadier speed and more comfortable ride will result in a lower value. The CF algorithm should be lower at low car counts, since it has more road time to adjust for the green wave like effect. Increasing the amount of autonomous cars will also decrease the value of uncomfort since more cars actively participate in the green wave like effect.

• Pedestrian waiting times
  • Value to measure (y-axis): Average pedestrian waiting times.
  • Value to change (x-axis): Number of cars (#cars).
  • Four lines each graph: Boon's algorithm #cars 30% and 90%, Our algorithm #cars 30% and 90%.
  • Settings: Pedestrians at 50%, packet loss off.
  • Hypothesis: In this measurement, the changes in pedestrian waiting times are checked if more cars are spawned. The values should decrease. It will be checked if the chosen cost function variables associated with pedestrians are realistic by looking at how drastically the pedestrian waiting times changes with more cars. The amount of pedestrians spawned is not changed since the intersection can never know how many are waiting.

• CO2-Emissions
  • Value to measure (y-axis): CO2 emissions: unsure, idea was: integration of all total acceleration * factor + average time on intersection * factor * totalcars.
  • Value to change (x-axis): %A Percentage autonomous cars.
  • Four lines each graph: Boon's algorithm #cars 30% and 90%, Our algorithm #cars 30% and 90%.
  • Settings: Pedestrians at 35%, packet loss off.
  • Hypothesis: More cars will naturally lead to more CO2 emissions, the question is: do the average time on intersection and integration of total acceleration have a large enough impact to counteract the amount of cars? It is suspected that the different will be so insurmountably low that random spawning noise will pollute the measurements, making it difficult to see a big different between the VAC and CF algorithm. The CF algorithm should be a bit more environmentally friendly since the average time on intersection is slightly lower and the total acceleration too because of the green wave implementation.

---

There has been some concern over the possibility of strong variability in output results caused by a multitude of parameters. These concerns are unnecessary. There are two major components that have the largest influence on simulation behavior: percentage of autonomous cars %A and total carcount #cars. Other parameters like the number of pedestrians #ped have slim to none influence because of the way pedestrians are detected and implemented in the cost function. Packet loss is quite predictable and studied in the packet loss efficiency measurements, so if any inconsistencies occur, they will be immediately visible. Another parameter with lots of different settings is the traffic distribution. This parameter is also tested in the efficiency measurements, again: if any inconsistencies are present in the simulation they will arise from the measurement data. In the case that inconsistencies occur, bootstrapping - a term coined by statistics - can be used to acquire a value in the inconsistency. It works by random sampling with replacement values, variables will be randomly varied and differences in output will be compared to get a value for bias, variance, confidence intervals, prediction error or some other such measure.

Experimental Results and Evaluation

Here the results of the simulation experiments will be presented. For each experiment an explanation of the graphs is given as well as an evaluation on the meaning and significance of the results.

Efficiency

Algorithm comparison for efficiency measurements

This measurement was done with symmetrical traffic, so a medium amount cars from four directions. The worst case scenario appears not be true, since the CF algorithm is equally good or even better given the same percentage of autonomous cars compared to vehicle actuated control. This makes the comparison easier. Every data point is the average of 10 measurements of several minutes, this was done to decrease random noise in the output. Noticeably, measurements with the vehicle actuated control algorithm exhibit much more noise than the cost function algorithm. This can be explained by the fact that the cost function (CF) algorithm reacts dynamically to random traffic spawns where the VAC algorithm exhibits much more repetitive behavior. The repetitive behavior causes the random fluctuations in traffic density to be more visible.

Furthermore, changes in delay appear to be linear instead of the predicated exponential decrease. The slope of CF is higher than VAC because cars are not detected in VAC making CF more efficient with increasing autonomous cars. One would not expect both slopes of CF to be equal. However, the slopes of VAC are different. The slope of the 90% total cars measurement is higher than the 30% measurement, an explanation can be found when considering the effect of flooding. When at a certain point there are too many cars (flooding the intersection) the type of algorithm used does not matter anymore. This effect would causes the lines of measurements with an greater amount of traffic to converge. In a follow up research, total cars could be increased up to 200% to see if this indeed happens.

To conclude, when the market share of autonomous increases, the CF algorithm becomes better. In the case of low traffic, the difference in delay between algorithms goes from 0 seconds to 7 seconds. With higher traffic the difference goes from 2 seconds to 5 seconds. It appears that the most benefits are obtained with low to medium traffic.

Other measurement configurations are available here: HMML, HMLL and HHLL. Apart from slight changes in slopes and intercept values, the different configurations yield the same results.

Effect of packet loss on efficiency.

Packet loss efficiency

The resulting graph bears a lot of similarities with the hypothesis. Different lines (A%) represent different percentages of autonomous cars. The difference in intercepts appear to first increase significantly and then lower to a steady two seconds. Slopes are equal to the predicated ones but at 100% packet loss something interesting occurs. The intersection at the two highest amount of autonomous cars appears to be more efficient at 100% packet loss than at 60% and 80%. This seemingly anomalous data actually results from how car counting works in the CF algorithm. When packet loss occurs, the autonomous car does not send car count data to the intersection, so at 60% and 80% a lot of car counts for lanes are inaccurate and incomplete. When packet loss is 100%, car counting is skipped entirely, so no errors can be made in the algorithm and it starts acting more like VAC/first-come-first-served. When there are loads of autonomous cars at the intersection, platooning happens very efficiently. That is why delay is lower for higher amounts of autonomous cars and packet loss.

(Dis)Comfort

Change in comfort and autonomous cars results.

The Y-axis shows the integration of the absolute value of the acceleration, it represents the amount of velocity changes throughout the intersection. It is a measurable user comfort aspect; The lower the value, the higher the comfort. The green wave like behavior was implemented only in the CF algorithm, this prevents autonomous cars from changing speeds unnecessarily. One can observe an almost linear increase of comfort with CF. Comfort increases very slightly with VAC, it is suspected that this is because of platooning among autonomous vehicles, which is independent of the algorithm as it is controlled vehicle to vehicle.

The fact that the comfort increases for the user of the autonomous cars is beneficial for the market share of the autonomous cars. With increased comfort the satisfaction of the user increases and more people will want to make use of autonomous cars. As a result the percentage of autonomous cars will increase on the road and the efficiency of the algorithm will show even more as the delay on the intersection decreases as the market share of autonomous cars increases.

Pedestrian waiting times

Pedestrian delay.

When there is heavy traffic, CF prefers cars and lets pedestrians wait 5 seconds more on average. This is due to the cost function, values for traffic lanes are higher when there is more traffic and are then preferred to pedestrians. A possible solution is changing cost parameters when traffic congestion is higher. It is difficult for CF to account efficiently for pedestrians because they are difficult to detect. If autonomous cars would be able to detect pedestrians, CF could be altered to also take this in account. However, this is something that was not able to be done within this project. For future work, the CF can be tuned more to see if the gap between pedestrians and cars can be decreased. Also the CF for pedestrians needs to be submitted to psychological research on waiting time as there are a lot of factors that have influence on the perception of waiting time (for example weather situations) and therefore on what is acceptable for the pedestrian. This was for now outside of the scope of this project as this is enough to form a new project, but it is important to address for future work.

CO2 Emissions

An actual value cannot be calculated of CO2 emissions without extensive research. What can be said is that CO2 emissions are lower when using CF. This is due to two aspects

1. Time on intersection is lower because delay is lower. This means less fuel is consumed.
2. Changes in speed are also lower (see comfort graph). This means less fuel is wasted when shifting gears/increasing RPM.

However, more research needs to be done to see if the difference in the quantity of emissions is low enough to be relevant.

Conclusion

---

The outcomes for the efficiency of the CF algorithm matched the expectations that were stated in the hypotheses; for busy traffic and for non-busy traffic the CF algorithm proved to be more efficient than the VAC algorithm in the simulation. When the percentage of autonomous cars increases, the efficiency grows even more. This means that when the CF algorithm is implemented, the potential of autonomous cars should be able to be used more than when keeping the current VAC algorithms.

Another outcome of the experiments showed that the pedestrians would have to wait approximately five seconds longer with the CF algorithm than with the VAC algorithm. Expected is that the cost functions of the cars and the pedestrians can be brought closer together by tuning parameters so that the five second gap can become smaller. See future work for more discussion on this.

An important USE-aspect was the consideration of comfort for the autonomous car users. Comfort is something that the users expect to increase when using an autonomous car. In the results is shown that by making use of the green wave like effect, the comfort increases or is maintained.

The packet loss results correspond to the hypotheses. When packet loss occurs, the autonomous cars will behave more like human driven cars as they have to rely on their own sensor data without extra information from the intersection. This will not cause increase danger for autonomous car users, pedestrians or human drivers.

Lastly, the initial plan was to include [math]\displaystyle{ CO_2 }[/math]-emission as a societal aspect in the research. However, during the project it became evident that this would require more extensive research than initially expected. Therefore, this became subject for future work, as is explained in the next section.

Future Work

As not all aspects of this topic were able to be covered in this project, some areas remain for future work.

Right now, only one intersection is considered with the CF algorithm. By extending the simulation to include more than one intersection, the potential of the algorithm can be further explored. This is relevant research since in practice, the infrastructure where the autonomous cars will drive through, consists of multiple intersections that may differ from the type of intersection that was considered here. The expectation is that the efficiency will increase when more intersections are considered. Further additions to the simulation may also be adding some more complex infrastructure to accommodate for real world scenario's, like bicycle lanes and different sized vehicles and so on.

An observation that was done while analyzing the results, was that pedestrians are slightly more delayed by the CF than by the VAC algorithm. This is due to insufficient parameter tuning to bring the CF for pedestrians closer to the CF of the cars. In order to tune the parameters for the pedestrians as optimal as possible, research has to be done to the psychological factor of waiting time in traffic. Also, the parameters can implicitly take into account the generally lower comfort of pedestrians with respect to car drivers (due to noise at intersections or possibly bad weather).

Research was done for a communication protocol that made use of current intersection technology. The outcome of this was that the KAR-system could be used as this is implemented in a large amount of the intersections in the Netherlands. However, more research could be done about the capacity of this system. This becomes especially relevant when the simulation is extended to include multiple intersections.

One subject that was mentioned in the initial USE-aspects section was the environment. With traffic comes [math]\displaystyle{ CO_2 }[/math]-emission, and a hypothesis at the beginning of the project was that with higher efficiency would come less emission.This is because higher efficiency would result in a lower time spent on the intersection (or in traffic in general). Additionally, the algorithm managed to decrease de- and acceleration, which also likely has as the effect that emission is reduced. Further research should indicate whether this hypothesis truly holds and if so what the size of the effect is.

Another subject that was mentioned in the initial USE-aspects was the fear of hacking and the feeling of safety of the autonomous car users. In the CF algorithm packet loss has been implemented, but not packet injection or another form of hacking. This is subject for an entirely new project and was therefore excluded from the research in this report. However, the fear of hacking is justified and needs to be addressed in future research.

---

Planning and task division

---

This is an image of the planning as it was set up initially. Initially, another subject was chosen than the current focus. Due to feedback that was received in the first presentation of week 2, the focus was changed to the current subject. Due to the change of focus, the literature study continued on a bit longer than shown in the schedule. This slowed down the start on the design of the algorithm a bit as this was started in week 4 instead of week 3. It did not give us any problems in the long run because the algorithm was designed efficiently and the project was back on schedule quickly.

Initially, the process of the project was quite chaotic. From week 4 a drastic change was made in this regard by starting to work with a chairman and an agenda during meetings and by defining clear goals and task deliverables. After this the process sped up significantly and more overview of the project was created.

Halfway through the project, we had to continue with one less group member. Now, we had to continue the project with four people instead of the anticipated five. However, we did not notice considerable setback due to this and we were able to finish the project as planned. An aspect where one less group member was inconvenient was the programming part of the project. Initially the group had two skilled programmers, but now only one. Sjoerd was very good in picking the implementation up by himself and the rest of the group contributed as much as possible with the content of the algorithm.

In the end the complete algorithm was finished by the end of week 6 and the testing could commence shortly after that. This is approximately one week later than anticipated in the planning. However, we could afford the extra week of working on the algorithm and during this week a lot of details could be improved. This still left enough time for the test phase, since a clear experimentation plan and hypotheses had been set up. As a group we had enough time to in detail analyze and discuss the results.

The final documentation was for the most part finished during week 7, but fully completed during week 8 after the final presentation.

Task division

Here the most important tasks and contributions of the group members are explained. Everyone has participated very well during the project and there was a very pleasant group atmosphere during the entire course. It was a group where everyone was able to look at each others contributions critically so that the results could be as good as possible. The peer review reflects the amount of work that has come from each of the group members relative to each other.

• Jeroen van Dongen

Jeroen set up the testing plan and processed the results. He was responsible for a lot of literature research, like the sensors in the autonomous cars. He also set up the special situations for the algorithm and was one of the two group members who managed the Wiki.

• Rodger van der Heijden

Rodger did a lot of literature review on the comparison algorithm. He also did two of the three presentations including the final presentation. Furthermore he participated in a lot of different tasks every week, where needed, and he was detail oriented.

• Sjoerd Westendorp

Sjoerd has worked on the implementation of the algorithm and was also the one who came up with using a cost function as a basis of the algorithm.

• Lisanne van Wincoop

Lisanne did all the research on the USE-aspects and analyzed the project based on these USE-aspects. She also researched and decided on the use of the communication protocol and the green wave like effect. Furthermore she was the second group member to manage the Wiki page every week. In the end she made a lot of the report.

Link to the project Wiki

This is a link to the old Wiki as it was kept up-to-date throughout the project.

Meetings

A record of all held meetings can be found here.