PRE2016 1 Groep2

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

---

Group members

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

Introduction

On day 1 our idea for a project was to build a small robot that could teach itself to walk by using self learning AI. This idea was quickly abandoned when it was brought to our attention that these already exist. We were also unable to combine lots of USE aspects with the idea.

The next idea was investigate algorithms of intersections with only autonomous vehicles and to build a simulation of it. We could compare different algorithms and decide in which was best in certain situations. The problem was that it didn't contribute to real world scenarios because lots of algorithms used unrealistic assumptions, including: all traffic must be autonomous and there is no packet-loss in communication between car and intersection,

After receiving feedback on our second idea, we had a long discussion with Mr. Borghuis. To address all the points in the criticism received: unrealistic assumptions, no contribution, little USE, why 100% autonomous cars. We came up with an idea to update current intersection systems to encorporate autonomous vehicles. The project idea allows a realistic intermediate solution in the process only allowing autonomous cars in traffic.

Focus

Our main focus area concerns: Automated traffic regulation (ATR).

Narrow that down is our specific focus: Updating the Current Intersection System to be Compatible with Autonomous Vehicles (Vehicle Intersection Control).

Restrictions on the focus area:

• Crossing has 4 directions.
• Traffic is randomly generated, the ratio between autonomous and normal cars will be changeable.

A multitude of traffic accidents happen at intersections^{citation needed}. 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 intersection 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 can be greatly reduced, which benefits the environment. Enterprises will also be positively influenced, since people will be able to get to work quicker instead of being stuck at an intersection.

Objectives

Main objective:

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

Objectives:

• Using sensor data from autonomous cars to make traffic light algorithms more aware of current traffic
• Choose a suitable communication protocol between autonomous cars and the intersection.
• Find existing efficient algorithms for autonomous cars at intersection in a literary review.
• Combine said algorithm with current traffic light algorithms to optimize traffic flow of both normal and autonomous cars.
• Make sure the traffic flow is optimal, which results in less waiting time and less emission.
• Create a transition solution that can combine the use of autonomous cars with human drivers by using the current intersection system.
• Keep in mind the perception of safety and the actual safety of passengers inside the autonomous cars.
• Decrease the number of traffic accidents involving cars on crossings.

Approach

The approach that is chosen is research and 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 tested, after which an evaluation will follow.

Literature review

Intersection algorithms now

article needs more references

There are multiple technologies possible for detecting cars; lasers, rubber hoses filled with air, but most commonly inductive loops. These loops work by detecting a change of inductance; the metal body of a waiting car changes the inductance. Around the world different algorithms are used in traffic light timings.

Fixed time control

The most basic model. There are 3 groups of traffic; three different modes, being:

1. The main road
2. The road that crosses it
3. Pedestrians

Without checking anything, the lights just cycle through these possibilities. There aren’t any sensors required, only the actuators. It is possible to allocate different time periods to the three cycles, for instance keeping the light on a busy source road green for a longer period of time. Usually the intervals are about 30 seconds, but this depends on the region.

By making use of the sensors in pedestrian traffic lights, a small optimization can be used.

if (pedestrian_button == pushed) {
	cycle through three modes }
else {
	cycle through mode #1 and #2 }

These methods can be of use in populated areas, where there (most likely) are cars waiting anyway to detection does not offer any benefit. Not using sensors for the cars makes these intersections cheaper and more fault-proof.

Vehicle Actuation

Only useful when one road has way more traffic than the road crossing it. Basically it’s green for the main road, until a car is detected on the side road.

while (!car detected from side road) {
	green light on main road }
else {
	green light on side road }

Urban Traffic Control

A quite sophisticated system that is centrally controlled. The intervals can be altered in real-time. This is useful if there happens to be for example a concert ending, causing a sudden influx of traffic from one way. Or, during peak hours, increase the time intervals of all directions, to reduce the lost time during transitions. Additionally it is possible to create a “groene golf” by linking sites together. This system is used in, among others, London, New York (7660 intersections out of 12460) and 83% of Toronto intersections (15% using SCOOT).

Split Cycle Offset Optimisation Technique

This technique uses detectors away from the intersection, say 50 to 200 meter, which makes it possible to know what traffic is approaching the intersection before it is actually waiting. Apparently the alterations to the UTC are rather small timewise, but efficiency-wise they can make a big difference.

Interesting find: Ingolstadt, German city (audi) which uses intelligent traffic light system. Via special equipment the vehicles communicate with the traffic lights. These lights send, for instance, the time until the next color change, allowing the vehicle to adjust their speed, even automatically when adaptive cruise control is present. Or, when already waiting for a red light, the traffic light can communicate the waiting time. As far as I can tell, it does not affect the time intervals on the traffic lights themselves.

Sensor and communicationsystems of autonomous cars

article needs more text and communications part

Following is a list of sensors and their properties, advantages and disadvantages.

Sensors

Sensor goals:

1. Know where you are going
2. See where you are going
3. Get where you are going

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

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 (~570 ft) updated every 50ms and handling object speeds from -100 m/s to +25 m/s (~220mph closure to ~55 mph separation,) medium range is a 90 degree arc out to 60m (~200ft) updated every 50 ms and handling object speeds from -100 m/s to +25 m/s.

Camera:

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

GPS:

• Only send information about location
• Cheap
• Needs a clear view of the sky

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 shaft encoders/gps
• Steering angle from wheels angle sensors

Questions regarding the project

A few important questions arise that are in need of answering for the project.

1. Different cars will have different sensors, how will it be made compatible?
2. Which sensordata is important for the intersection to acquire?
3. Where will the interpretation of data be done? (Lidar is a lot of data!)
4. The communication-module needs to compatible between the autonomous cars, how will be dealt with different updates and versions?
5. How will packetloss be processed in the simulation and how can a protocol be made to minimize its effect.

Existing communication systems in traffic

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.

USE Aspects

Initially, some choices have to be made regarding the consideration of the USE-aspects in order to start designing the algorithm and communication protocol. Here, the aspects regarding the initial choices 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.

In the design and the simulation the influence of this USE-aspect will be shown by a graph of the throughput of the crossing versus the percentage of autonomous cars on the crossing. The throughput is measured by the mean time that the cars spend on the crossing.'

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.

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, it might be a more distant future image than is aimed for with this research. As previously mentioned, the full potential of this service might be reachable when the market-share of autonomous vehicles is increasing. Realizing a perfect solution for this aspect of autonomous driving when utilizing existing technology might therefore be outside the scope of this research.

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.

In 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.

Maximising 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 tradeoff 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 however, is 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.

Conclusion

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.

Focus is kept on the begin phase of the introduction of autonomous cars, which means that considering fully operational autonomous taxi services is outside the scope of this research.

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.

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.

Algorithm

Type of Algorithm

Explicit 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.

Proposed algorithm

Algorithm for controlling the lights

This algorithm tries to achieve two main goals:

• 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.

More components can be added.

All possible combinations of light states

There are 18 possible combination of states:

• 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.

The concept of the algorithm

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.

Including the user

The algorithm should not let any individual wait to 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 to green after the next state transition.

Cost function

The three elements, traffic, wait time, and wait limit have to be combined into one cost function: The cost of having a light remain red.

• [math]\displaystyle{ Cost_{Lane} = Cost_{traffic} + Cost_{wait time} + Cost_{wait limit} }[/math]
• [math]\displaystyle{ Cost_{Lane} = N + R + C \times t + P \times (t \gt T) }[/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), 'C' an arbitrary constant that defines the importance of wait time, 't' the time since the first car started waiting in this lane, 'P' the cost penalty for having a lane wait too long (value should be arbitrarily large), 'T' the maximum time a vehicle can be expected to wait at a intersection. Note that due to the way this cost function works 't' can slightly overshoot 'T' before the lane light goes on green, 'T' therefor need to be adjusted accordingly.

The formula for pedestrian lanes is similar:

• [math]\displaystyle{ Cost_{Lane} = Cost_{wait time} + Cost_{wait limit} }[/math]
• [math]\displaystyle{ Cost_{Lane} = C \times t + P \times (t\gt T) }[/math]

With its own values for C, T 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.

RPCs

Requirements

The design has to satisfy any requirement you formulate. This means that a requirement needs to be specific/measurable!

• 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:
  • Current position: Current speed and distance from intersection, entry direction and which lane. (Odometer/GPS/Camera/Compass)
  • 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 it's distance is within 5 60 meters. (Sonar)
  • Knows speed and distance of a car in front if it's distance is within 60 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. (not simulated)
  • 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. (not simulated)
• 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 % packetloss 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. (done 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 multiple reasons. Some requirements appeared redundant in the later stages of the project.

• Speed

A great example is the speed, it was thought of to be vital information to be send 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 feature was decided to be implemented.

• Normal intersection

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

• Simulation of communication

Our first idea was to actually simulate the communication (TCP style) within Java. This seemed a lot of extra work when the same output can be achieved via randomly (amount can be adjusted within program) skipping information readouts, temporarily transforming blue cars into red cars but with 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 we are only simulating the intersection and there is no room for normal roads. 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.

• Maximal allowed waiting time implementation

Our algorithm is a cost function so a maximal waiting time is in fact technically not possible. Even when cost constants are close to infinity (which are not feasible), it is mathematically possible that the maximal 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.

Packetloss in the simulation

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 a autonomous car can not contact the intersection, default to simple intersection behaviour.
• If an intersection can not contact a autonomous car, then it can not even know that it exists, so it will threat it like a normal human driven one.
• If communication fails halfway through, switch to the default behaviour.

This can be simulated by replacing the autonomous car with a human driven one, which means that simulating this scenario is pointless. However this 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 we have 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 can not 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 skipping then communication code. This is best described by an example: Lets say we have 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 therefor 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 acknowledgment responses. This way there is a significant chance the packet loss is detected and corrected by re-sending the message. However, remember that this acknowledgment 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, or simply put: 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 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.

Green Wave design choice

The “Groene golf” 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. However there are several issues that makes modifying the “Groene golf” system to use automatic cars both unpractical and unnecessary.

It is important to remember that the intersections need to be able to communicate with the vehicle. This requires communication systems to be placed along the roads between intersections. The point of our project is to not overhaul the road network, but to make minor hardware modifications to improve an intersection. Our project is focused on intersections. A multiple-intersection arrangement has its own complexities and its own goals, problems, and USE aspects. On top of that it important to remember that autonomous cars will follow the speed limit perfectly anyway, meaning that they will by default use the system the way its intended. It is therefore questionable that rather expensive communication upgrades will result in any significant benefit at all.

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

The idea of the “green wave” for autonomous scars 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 behaviour 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 behaviour 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.

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 behaviour 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

We cannot simulate everything. In this chapter we elaborate on some situations on why they are not in the simulation and how it would affect our intersection. In some situations our intersection cannot add something to that of a normal one, there are also situations where it does not matter if it's a normal or an autonomous car. In these specific cases, the answer is always the same: it will not be implemented. So before each situation we ask ourselves:

1. What are the actions for the intersection?
2. Does it matter if it's a normal or an autonomous car?

• Emergency traffic, ambulances

When emergency traffic needs to pass through the intersection at high speed, several lives are at the line. The intersection helps these vehicles and reduces the change of an accident by setting all lights to red. This is already implemented in the KAR-system - which we are improving - so it does not need to put 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 is 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.

• Pedestrians crossing at red light

When a pedestrian decide to cross at a red light, presumably because they are waiting too long, there is not much the intersection itself can do. Questions number is already no. It is up to cars themselves to react to the pedestrian if given green light, question two is also no. Hence, there is no point of including them in the simulation. However, we do need to prevent long waiting times. If a predestinarian is waiting too long, the program logs the situation for further analysis.

• 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 will often drive past the accident after most of the debris is cleared. It is a bad solution to set all light to red until the emergency services arrive, since people will get 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 a 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 to 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. How accurate are these speed measurements and why not put a speed camera at the intersection?

• 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 difference between the behavior of a platoon and an elongated vehicle. At first, it might look a little strange but we think 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 completely 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 maximal speed, it might also be very annoying. In some cities traffic signs display the best speed to drive for a green wave. Our intersection sends this information to the autonomous cars, giving them to ability to act like buffers for traffic behind them. It is build in our simulation but because there are no long roads it's very difficult to see. The effectiveness is highest when there are multiple intersection and roads involved (which are not simulated but very interesting for followup 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 followup study).

Spawning and Gauging

Spawning

We decided not to acquire real traffic data and inserting that into our simulation. In real life vehicles have different length (vans, trucks, etc.) these are not included in the data. And we have to find an intersection with the exact same layout. This could be done, but it is also possible (and a lot easier given the time) 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 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.

Comparison Algorithm

Article from Boon

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. 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 Situatins Wiki chapter.

Simulation

Here details and progress of the simulation will be kept up-to-date.

Executable and Source Code

Here is the latest version of the simulation.

Source code is available here in .zip: sourcecode.

The exact implementation of the cost function in code:

Junction Explanation

A common four way intersection with 2 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.

Code Explanation

Current frontend view

The simulation is created in Java using NetBeans IDE.

Renderer: To display things on the screen Java's Swing. This is a relatively simple graphics library, however it has many limitations. One such limitation is its timer function, which had a hard time to trigger 60 times per second even at low computational loads. As such the generic Java Utility class Timer was used to reach the targeted 60 FPS. In reality since the timer uses a target 16 ms delay between frames, the real amount of a frames is slightly higher than that.

The Renderer class is used to obscure the inner workings of the graphical part from the algorithm. The advantage here is that the functioning of the algorithm is independent to the functioning of the graphical code. This means that changes to the graphical section will not change the behaviour of the algorithm and vice versa.

The Renderer class contains a JFrame, which is the window displayed on screen, and the JPanel. This JPanel is actually the RenderWorld class, which extends the JPanel with the features needed for this simulation, like the sliders. The RenderWorld class also implements key and mouse listeners, allowing for user input.

The Main class: Normally in java one would not define a main class, but in order to allowing for the separation of graphics and algorithm two classes are needed, one for the graphical side (Renderer) and one for the algorithm (Main).

The main class has three important functions: The constructor, this is where the simulation must be setup. The draw function, where the simulation tells the graphical section what has to be displayed. And the loop function, where all cars and pedestrians take one step and the algorithm does its calculations.

Draw and loop are explicitly separate. Although for most draws there is also one loop. Loops can be skipped if the simulation is paused, and draws can be skipped if the frame rate is too high for Swing to handle.

Note that a draw and loop counter exists. The loop counter is used as a in simulation time unit. This means that the vehicles in the simulation will report their time spent in the intersection in terms of computation steps rather than seconds. The latter method would make the results of the simulation frame rate dependent. With the former method the simulation can be done at any speed.

Pedestrians: The pedestrian simulation relies on different walking speed and drawing offset to make the crowds look like crowds. The difference in walking speed disperses the crowds once the traffic lights go on green. The drawing offset makes it so if multiple pedestrians are on one spot, they instead are drawn as a bunch of circles close together.

In the pedestrian simulation each pedestrian is a finite state machine: They have a state to walk towards the intersection, one to wait at the light, and one to walk away once the light is green. Since each pedestrians only want to go one of the four cardinal directions, each pedestrians need to cross at most one road. The effect pf pedestrians crossing multiple parts of the intersection is the same as simply increasing the number of pedestrians.

Cars: Although the fundamentals are ready, for a large part these are not implemented yet. However, the following is already set: A percentage of cars spawned is autonomous. Since autonomous cars is rather lengthy, it is shortened to “auto” in the code while normal cars are called “car”. An auto is just an different kind of car, where the difference is defined by a Boolean (true or false value).

Evaluation

Output measurements

Efficientie.

• Graphs 1

Y-axis: Average Delay (total time through intersection - traveltime) X-axis: %autonomous, 20 steps: 5 to 100. ped at 35%. measurement is 1 minute. packetloss off.

• • Graph 1_1

4 mid. Line 1: Boon Algorithm 30%, Our Algorithm 30%, Boon Algoritm #a 90%, Our Algorithm 90%

• • Graph 1_2

1 heavy 2 mid 1 light. 4 mid. Boon Algorithm 30%, Our Algorithm 30%, Boon Algoritm #a 90%, Our Algorithm 90%

• • Graph 1_3

1 heavy 1 mid 2 light. 4 mid. Boon Algorithm 30%, Our Algorithm 30%, Boon Algoritm #a 90%, Our Algorithm 90%

• • Graph 1_4

2 heavy 2 light. 4 mid. Boon Algorithm 30%, Our Algorithm 30%, Boon Algoritm #a 90%, Our Algorithm 90%

Packetloss performance

• Graphs 2

Y-axis: Average Delay (total time through intersection - traveltime) X-axis: #packetloss, 21 steps: 0 to 100. ped at 35%. measurement is 1 minute. #cars = 50

• • Graph 2_2

4 mid. Line 1: %A=20. Line 2: %A=40;Line 3: %A=60; Line 4:%A=80; Line 5 %A=100 Line 6 %A=0% (To check for convergence)

• CO2 Emissions: integration of all total acceleration * factor + averageTOI * factor * totalcars

• • Comfort:
    • car comfort (Integration of all total acceleration + deceleration)*factor + factor * tailgaiting+amount of cars near * factor
    • pedestrian comfort

Sources and References

Sources

• A Multiagent Approach to Autonomous Intersection Management.
• Decoupled Cooperative Trajectory Optimization for Connected Highly Automated Vehicles at Urban Intersections.
• A review on agent-based technology for traffic and transportation.
• Microsimulation analysis of automated vehicles on multiple merge junction highways
• A Review of the Applications of Agent Technology in Traffic and Transportation Systems
• Tesla specifications and sensors
• The analysis and optimization of methods for determining traffic signal settings, M. Schutte. http://cstwiki.wtb.tue.nl/images/MasterThesis_-_Mattijn_Schutte_2.pdf

Collaboration

Milestones

• Literature review
  • Current intersection systems;
  • Sensor and communication abilities of current autonomous vehicles;
  • Communication systems that are already present in current intersections (busses and ambulances have the ability to control the traffic lights to a limited extent)

• Coupling between intersection and the autonomous car

• Simulation
  • Algorithm (backend)
  • Visualisation (frontend)
  • Test

• USE aspects (to be considered with every decision that will be made). The considerations of the USE will be discussed throughout the report and delivered in an evaluation chapter at the end of the report.

• Evaluation of Simulation
  • Wiki
  • Presentation
  • Final simulation

Planning

The planning has been divided in three phases that categorize the main elements of the project. During the startup phase, the goal is to create a good basis for the project by doing a literature review and make a (global) plan that can be a guideline for finalizing the project.

In the chart, the specific activities that belong to each phase have been listed. The green cells indicate when these activities will take place.

The USE aspects have not been mentioned specifically, since this is an integral element of the research and will have to be considered and reviewed every step of the way.

Update week 4

Our goals for this week were:

• Finalize the algorithm;
• Make the communication protocol;
• Start on backend of the algorithm;
• Make RPC’s explicit.

Our main accomplishments:

• Progress on the simulation;
• A list of RPC's has been built on which we can further base the algorithm;
• The communication protocol can be based on the KAR system, which is already implemented in many intersections. Only some minor details have to be looked at;
• The algorithm was partially constructed, which puts us behind on one of our important goals.

The fact that we did not completely reach our goals, is worrying. The main cause of this problem is to compensate for this by working less chaotic and more as a team. Last week this was already a problem and we tried to resolve it this week. However, this turned out badly again since we did not have a concrete plan for this. For the next week we are going to compensate for this by having more structured meetings with a chairman and an agenda, so that we can clearly define goals and milestones and everyone in the group has to make sure their tasks are finished and of good quality so that we can move on. A lot of work has been done this week, but not clearly communicated, which has to change immediately.

Task division

The tasks divided per week are an indication of the work that needs to be done by all the group members. The reserved hours for each task are mentioned in the schedule below.

Sjoerd

• Week 2:
  • Brainstorming on subject an milestones. (5 hours)
  • Work on simulation (8 hours)
  • Researching: sensors and communicationsystems of autonomous cars. (7 hours).
• Week 3:
  • Brainstorming on subject an milestones. (5 hours)
  • Continue startup work on the simulation. (6 hours)
  • Start on algorithm (the whole group is involved in this weeks decisions on the algorithm). (10 hours)
• Week 4:
  • Finalize frontend of simulation. (6 hours)
  • Start working on backend of simulation. (6 hours)
  • Write part about why we are choosing not to simulate the "green wave" and investigate and write a piece about packet loss. (4 hours)
• Week 5:
  • Work on backend of simulation (15 hours)
• Week 6:
  • Finalize backend of simulation (15 hours)
  • Visualize results of simulation. (3 hours)
• Week 7:
  • Tweaking and evaluation backend algorithm. (10 hours)

Johan

• Week 2:
  • Brainstorming on subject an milestones. (7 hours)
  • Researching: Existing communication systems in traffic.(9 hours)
• Week 3:
  • Final literature review (if still necessary after the work in week 2). (5 hours)
  • Start on algorithm (the whole group is involved in this weeks decisions on the algorithm). (7 hours)
  • Reporting on Existing communication systems in trafic. (6 hours)
• Week 4:
  • Adjust the architecture of the code. (7 hours)
  • Program collision detection. (7 hours)
  • Research and write a text about our use of Poission distributions to generate traffic flow. (2 hours)
  • Adjust planning and make a Gantt-chart. (2 hours)

Jeroen

• Week 2:
  • Brainstorming on subject an milestones. (5 hours)
  • Managing wiki. (2 hours)
  • Work on planning. (4 hours)
  • Evaluation of Simulation. (9 hours)
• Week 3:
  • Finalize literature review (if still necessary after the work in week 2). (6 hours)
  • Start on algorithm (the whole group is involved in this weeks decisions on the algorithm). (4 hours)
  • Keep Wiki page updated. (4 hours)
• Week 4:
  • Keep Wiki page updated. (4 hours)
  • Finish the RPC's of the algorithm. (2 hours)
  • Write text about real traffic data and gauging. (2 hours)
• Week 5:
  • Keep Wiki page updated. (4 hours)
  • Help tweaking simulation. (8 hours)
• Week 6:
  • Keep Wiki page updated. (4 hours)
  • Evaluate USE aspects of the algorithm and simulation. (4 hours)
• Week 7:
  • Final editing on Wiki page. (15 hours)
  • Evaluate results simulation (3 hours)

Rodger

• Week 2:
  • Brainstorming on subject an milestones. (5 hours)
  • Researching: Intersection algorithms now. (10 hours)
• Week 3:
  • Final literature review (if still necessary after the work in week 2) (4 hours)
  • Start on algorithm (the whole group is involved in this weeks decisions on the algorithm). (4 hours)
  • Evaluate USE aspects of the algorithm. (4 hours)
• Week 4:
  • Report on Intersection algorithms now. (8 hours)
  • Mail Boon
  • Finish pseudo-code of algorithm with human drivers. (6 hours)
• Week 5:
  • Evaluate frontend of simulation, adjust GUI. (8 hours)
• Week 6:
  • Evaluate USE aspects of the algorithm and simulation. (4 hours)
• Week 7:
  • Review the results of simulation and write report on it. (10 hours)

Lisanne

• Week 2:
  • Brainstorming on subject an milestones. (5 hours)
  • Work on presentation and planning. (8 hours)
• Week 3:
  • Giving presentation. (1 hour)
  • Final literature review (if still necessary after the work in week 2) (4 hours)
  • Start on algorithm (the whole group is involved in this weeks decisions on the algorithm). (4 hours)
  • Evaluate USE aspects of the algorithm. (4 hours)
• Week 4:
  • Combine all the literary review results in a comprehending summary. (12 hours)
  • Literature study of communication systems in intersections. (4 hours)
  • Write text about explicit algorithm choice and its effect. (4 hours)
  • Update Wiki and manage collaboration. (4 hours)
• Week 5:
  • Evaluate frontend of simulation, adjust GUI. (8 hours)
  • Help with managing wiki. (3 hours)
• Week 6:
  • Preview the results of simulation and write report on it. (10 hours)
  • Help with managing wiki. (3 hours)
• Week 7:
  • Evaluate USE aspects of the algorithm and simulation. (4 hours)
  • Help with final editing of Wiki page. (8 hours)

Meetings and weekly planning

A record of all held meetings can be found here.

Report setup

A setup of the final structure of the report.