Wednesday, 28 March 2018

Internet of Things and Autonomous Driving – Centralized or Decentralized?


By Dirk Helbing (ETH Zurich/TU Delft/Complexity Science Hub Vienna)

Digital technologies – from cloud computing to Big Data, from Artificial Intelligence to cognitive computing, from robotics to 3D printing, from the Internet of Things to Virtual Reality, from blockchain technology to quantum computing – have opened up amazing opportunities for our future. The development of autonomous vehicles, for example, promises the next level of comfort and safety in mobility systems. At the same time, transport as a service allows for a new level of sustainability, as much less cars, parking lots and garages (and much less materials and energy required to build them) will be needed to offer the mobility we need. Nevertheless, the discussion, for example, about privacy, cybercrime, autonomous weapons, and “trolley problems” illustrates that, besides great opportunities, there are also major challenges and risks. Recently, not only in connection with Cambridge Analytica and Facebook, the public media have started to write about a “techlash” (i.e. a technological backlash), and engineering organizations such as the IEEE have started to work on frameworks such as “ethically aligned design”[1] and “value-sensitive design” or “design for values”.[2] For example, experts discuss about solutions such as “privacy by design” or “democracy by design”[3] (see Fig. 1). 
 

Figure 1: Core issues to consider in digital democracy platforms
One of the question raised in this connection is: should we organize the data-rich society of the future in a centralized or decentralized way? This also concerns the deployment of the 5G network in Europe. An increasing number of experts recommends the development and use of decentralized information technologies[4] due to increasing dangers of misuse and vulnerabilities (e.g. by means of hacking), drawbacks on democracy, and matters of resilience. In the following, I will shortly discuss economic, political, technological and health issues to consider.
  1. A uniform, Europe-wide 5G network would not be economic. Making autonomous driving dependent on it could considerably delay autonomous driving. Today, many areas in Europe do not have a 3G or a 4G net, yet. This also includes many railway connections and many major roads, even in economically leading countries such as Germany. Besides, there are many regions lacking a mobile phone signal at all. It would be very expensive and take many years to deploy a 5G network all over Europe, which could offer standardized and reliable services as they would be needed to operate all traffic. By the time the deployment would be completed, we would probably have the next generations of wireless technology already, and perhaps new mobility concepts, too.   
  2. A Europe-wide control grid implies dangers to democracy. The developments in countries such as Turkey shows that powerful technologies can also be turned against people. A similar argument has recently been made about Facebook and various other IT companies, which have engaged in what is sometimes referred to as “surveillance capitalism” as well as in the manipulation of the opinions, emotions, decisions and behaviours of their users. It could be a political concern that technologies such as big nudging and neuromarketing aimed at manipulating peoples’ minds can be traced back to fascist projects and ideology. Moreover, it may raise concerns that some of the biggest companies harvesting Big Data across Europe have grown powerful during the Nazi regime or are linked to the military-industrial complex. Given that technologies originally developed for autocratic states and secret services are being applied to entire populations also in Western democracies,[5] concerns are certainly not pointless. Decentralized data control could counter related risks. 
  3. If 5G would be deployed all over Europe as planned, this could imply health risks for hundreds of millions of people. Currently, we do not know enough what are the implications for health, if today’s radiation thresholds are exceeded or raised. In principle, as 5G is in the microwave spectrum, significant interaction of 5G radiation with biological matter, also the brain, cannot be sufficiently excluded. Hence, there may be undesirable side effects. 
  4. Autonomous driving as well as the Internet of Things can be operated in a decentralized way such that the local organization or self-organization of systems is enabled via real-time feedback. This includes traffic assistant systems based on “mechanism design” to reduce congestion on freeways, which is done by changing interactions between cars, based on local measurements. Novel self-organizing traffic light control systems are also able to considerably improve traffic flows in cities based on local measurements and interactions. Both can even be operated without a control centre. The traffic situation around the corner is more difficult to handle, but solutions using relay stations or laser-based systems are being developed.[6]
In summary, given the above concerns, the current “techlash”, and the fact that a decentralized realization of autonomous driving and IoT applications is possible, Europe would be wise to engage into the “digitization 2.0”, oriented primarily at local empowerment and coordination. This calls, in particular, for technical solutions supporting informational self-determination (see Fig. 2). Data- and AI-based personal digital assistants could support people in taking better decision, in being more creative and innovative, and in coordinating each other and cooperating more successfully. They could also help us manage our personal data, namely who would have access to that what kinds of data and for what purposes. As trusted companies would get access to more data, the competition for data and trust would be expected to promote a trustable digital society. This would not only benefit autonomous driving.


Figure 2: Core issues to achieve informational self-determination.
Appendix:
Digitally Assisted Self-Organization
(excerpt from my book “The Automation of Society Is Next”)

Avoiding traffic jams

Since the early days of computers, traffic engineers always sought ways to improve the flow of traffic. The traditional "telematics" approach to reduce congestion was based on the concept of a traffic control center that collects information from a lot of traffic sensors. This control center would then centrally determine the best strategy and implement it in a top-down way, by introducing variable speed limits on motorways or using traffic lights at junctions, for example. Recently, however, researchers and engineers have started to explore a different and more efficient approach, which is based on distributed control.

In the following, I will show that local interactions may lead to a favorable kind of self-organization of a complex dynamical system, if the components of the system (in the above example, the vehicles) interact with each other in a suitable way. Moreover, I will demonstrate that only a slight modification of these interactions can turn bad outcomes (such as congestion) into good outcomes (such as free traffic flow). Therefore, in complex dynamical systems, "interaction design", also known as "mechanism design", is the secret of success.

Assisting traffic flow

Some years ago, Martin Treiber, Arne Kesting, Martin Schönhof, and I had the pleasure of being involved in the development of a new traffic assistance system together with a research team of Volkswagen. The system we invented is based on the observation that, in order to prevent (or delay) the traffic flow from breaking down and to use the full capacity of the freeway, it is important to reduce disruptions to the flow of vehicles. With this in mind, we created a special kind of adaptive cruise control (ACC) system, where adjustments are made by a certain proportion of self-driving cars that are equipped with the ACC system. A traffic control center is not needed for this. The ACC system includes a radar sensor, which measures the distance to the car in front and the relative velocity. The measurement data are then used in real time to accelerate and decelerate the ACC car automatically. Such radar-based ACC systems already existed before. In contrast to conventional ACC systems, however, the one developed by us did not merely aim to reduce the burden of driving. It also increased the stability of the traffic flow and capacity of the road. Our ACC system did this by taking into account what nearby vehicles were doing, thereby stimulating a favorable form of self-organization in the overall traffic flow. This is why we call it a "traffic assistance system" rather than a "driver assistance system".

The distributed control approach adopted by the underlying ACC system was inspired by the way fluids flow. When a garden hose is narrowed, the water simply flows faster through the bottleneck. Similarly, in order to keep the traffic flow constant, either the traffic needs to become denser or the vehicles need to drive faster, or both. The ACC system, which we developed with Volkswagen many years before people started to talk about Google cars, imitates the natural interactions and acceleration of driver-controlled vehicles most of the time. But whenever the traffic flow needs to be increased, the time gap between successive vehicles is slightly reduced. In addition, our ACC system increases the acceleration of vehicles exiting a traffic jam in order to reach a high traffic flow and stabilize it.

Creating favorable collective effects

Most other driver assistance systems today operate in a "selfish" way. They are focused on individual driver comfort rather than on creating better flow conditions for everyone. Our approach, in contrast, seeks to obtain system-wide benefits through a self-organized collective effect based on "other-regarding" local interactions. This is a central feature of what I call "Social Technologies". Interestingly, even if only a small proportion of cars (say, 20 percent) are equipped with our ACC system, this is expected to support a favorable self-organization of the traffic flow.[7] By reducing the reaction and response times, the real-time measurement of distances and relative velocities using radar sensors allows the ACC vehicles to adjust their speeds better than human drivers can do it. In other words, the ACC system manages to increase the traffic flow and its stability by improving the way vehicles accelerate and interact with each other.

Figure 3: Snapshot of a computer simulation of stop-and-go traffic on a freeway.[8]

A simulation video we created illustrates how effective this approach can be.[9] As long as the ACC system is turned off, traffic flow develops the familiar and annoying stop-and-go pattern of congestion. When seen from a bird's-eye view, it is evident that the congestion originates from small disruptions caused by vehicles joining the freeway from an entry lane. But once the ACC system is turned on, the stop-and-go pattern vanishes and the vehicles flow freely.

In summary, driver assistance systems modify the interaction of vehicles based on real-time measurements. Importantly, they can do this in such a way that they produce a coordinated, efficient and stable traffic flow in a self-organized way. Our traffic assistance system was also successfully tested in real-world traffic conditions. In fact, it was very impressive to see how natural our ACC system drove already a decade ago. Since then, experimental cars have become smarter every year.

Cars with collective intelligence

A key issue for the operation of the ACC system is to discover where and when it needs to alter the way a vehicle is being driven. The right moments of intervention can be determined by connecting the cars in a communication network. Many cars today contain a lot of sensors that can be used to give them "collective intelligence". They can perceive the driving state of the vehicle (e.g. free or congested flow) and determine the features of the local environment to discern what nearby cars are doing. By communicating with neighboring cars through wireless car-to-car communication,[10] the vehicles can assess the situation they are in (such as the surrounding traffic state), take autonomous decisions (e.g. adjust driving parameters such as speed), and give advice to drivers (e.g. warn of a traffic jam behind the next curve). One could say, such vehicles acquire "social" abilities in that they can autonomously coordinate their movements with other vehicles.

Self-organizing traffic lights

Let's have a look at another interesting example: the coordination of traffic lights. In comparison to the flow of traffic on freeways, urban traffic poses additional challenges. Roads are connected into complex networks with many junctions, and the main problem is how to coordinate the traffic at all these intersections. When I began to study this difficult problem, my goal was to find an approach that would work not only when conditions are ideal, but also when they are complicated or problematic. Irregular road networks, accidents or building sites are examples of the types of problems, which are often encountered. Given that the flow of traffic in urban areas greatly varies over the course of days and seasons, I argue that the best approach is one that flexibly adapts to the prevailing local travel demand, rather than one which is pre-planned for "typical" traffic situations at a certain time and weekday. Rather than controlling vehicle flows by switching traffic lights in a top-down way, as it is done by traffic control centers today, I propose that it would be better if the actual local traffic conditions determined the traffic lights in a bottom-up way.

But how can self-organizing traffic lights, based on the principle of distributed control, perform better than the top-down control of a traffic center? Is this possible at all? Yes, indeed. Let us explore this now. Our decentralized approach to traffic light control was inspired by the discovery of oscillatory pedestrian flows. Specifically, Peter Molnar and I observed alternating pedestrian flows at bottlenecks such as doors.[11] There, the crowd surges through the constriction in one direction. After some time, however, the flow direction turns. As a consequence, pedestrians surge through the bottleneck in the opposite direction, and so on. While one might think that such oscillatory flows are caused by a pedestrian traffic light, the turning of the flow direction rather results from the build-up and relief of "pressure" in the crowd.

Could one use this pressure principle underlying such oscillatory flows to define a self-organizing traffic light control?[12] In fact, a road intersection can be understood as a bottleneck too, but one with flows in several directions. Based on this principle, could traffic flows control the traffic lights in a bottom-up way rather than letting the traffic lights control the vehicle flows in a top-down way, as we have it today? Just when I was asking myself this question, a student named Stefan Lämmer knocked at my door and wanted to write a PhD thesis.[13] This is where our investigations began.

How to outsmart centralized control

Let us first discuss how traffic lights are controlled today. Typically, there is a traffic control center that collects information about the traffic situation all over the city. Based on this information, (super)computers try to identify the optimal traffic light control, which is then implemented as if the traffic center were a "benevolent dictator". However, when trying to find a traffic light control that optimizes the vehicle flows, there are many parameters that can be varied: the order in which green lights are given to the different vehicle flows, the green time periods, and the time delays between the green lights at neighboring intersections (the so-called "phase shift"). If one would systematically vary all these parameters for all traffic lights in the city, there would be so many parameter combinations to assess that the optimization could not be done in real time. The optimization problem is just too demanding.

Therefore, a typical approach is to operate each intersection in a periodic way and to synchronize these cycles as much as possible, in order to create a "green wave". This approach significantly constrains the search space of considered solutions, but the optimization task may still not be solvable in real time. Due to these computational constraints, traffic-light control schemes are usually optimized offline for "typical" traffic flows, and subsequently applied during the corresponding time periods (for example, on Monday mornings between 10am and 11am, or on Friday afternoons between 3pm and 4pm, or after a soccer game). In the best case, these schemes are subsequently adapted to match the actual traffic situation at any given time, by extending or shortening the green phases. But the order in which the roads at any intersection get a green light (i.e. the switching sequence) usually remains the same.

Unfortunately, the efficiency of even the most sophisticated top-down optimization schemes is limited. This is because real-world traffic conditions vary to such a large extent that the typical (i.e. average) traffic flow at a particular weekday, hour, and place is not representative of the actual traffic situation at any particular place and time. For example, if we look at the number of cars behind a red light, or the proportion of vehicles turning right, the degree to which these factors vary in space and time is approximately as large as their average value.

So how close to optimal is the pre-planned traffic light control scheme really? Traditional top-down optimization attempts based on a traffic control center produce an average vehicle queue, which increases almost linearly with the "capacity utilization" of the intersection, i.e. with the traffic volume. Let us compare this approach with two alternative ways of controlling traffic lights based on the concept of self-organization (see Fig. 4).[14] In the first approach, termed "selfish self-organization", the switching sequence of the traffic lights at each separate intersection is organized such that it strictly minimizes the travel times of the cars on the incoming road sections. In the second approach, termed "other-regarding self-organization", the local travel time minimization may be interrupted in order to clear long vehicle queues first. This may slow down some of the vehicles. But how does it affect the overall traffic flow? If there exists a faster-is-slower effect, could there be a "slower-is-faster effect", too?[15]

Figure 4: Illustration of three different kinds of traffic light control.[16]

How successful are the two self-organizing schemes compared to the centralized control approach? To evaluate this, besides locally measuring the outflows from the road sections, we assume that the inflows are measured as well (see Fig. 5). This flow information is exchanged between the neighboring intersections in order to make short-term predictions about the arrival times of vehicles. Based on this information, the traffic lights self-organize by adapting their operation to these predictions.
Figure 5: Illustration of the measurement of traffic flows arriving at a road section of interest (left) and departing from it (center).[17]

When the capacity utilization of the intersection is low, both of the self-organizing traffic light schemes described above work extremely well. They produce a traffic flow which is well-coordinated and much more efficient than top-down control. This is reflected by the shorter vehicle queues at traffic lights (compare the dotted violet line and the solid blue line with the dashed red line in Fig. 6). However, long before the maximum capacity of the intersection is reached, the average queue length gets out of hand because some road sections with low traffic volumes are not given enough green times. That's one of the reasons why we still use traffic control centers.
Figure 6: Illustration of the performance of a road intersection (quantified by the overall queue length), as a function of the utilization of its capacity (i.e. traffic volume).[18]
Interestingly, by changing the way in which intersections respond to local information about arriving traffic streams, it is possible to outperform top-down optimization attempts also at high capacity utilizations (see the solid blue line in Fig. 6.6). To achieve this, the objective of minimizing the travel time at each intersection must be combined with a second rule, which stipulates that any queue of vehicles above a certain critical length must be cleared immediately.[19] The second rule avoids excessive queues which may cause spill-over effects and obstruct neighboring intersections. Thus, this form of self-organization can be viewed as "other-regarding". Nevertheless, it produces not only shorter vehicle queues than "selfish self-organization", but shorter travel times on average, too.[20]

The above graph shows a further noteworthy effect: the combination of two bad strategies can be the best one! In fact, clearing the longest queue (see the grey dash-dotted line in Fig. 6.6) always performs worse than top-down optimization (dashed red line). When the capacity utilization of the intersection is high, strict travel time minimization also produces longer queues (see the dotted violet line). Therefore, if the two strategies (clearing long queues and minimizing travel times) are applied in isolation, they are not performing well at all. However, contrary to what one might expect, the combination of these two under-performing strategies, as it is applied in the other-regarding kind of self-organization, produces the best results (see the solid blue curve).

This is, because the other-regarding self-organization of traffic lights flexibly takes advantage of gaps that randomly appear in the traffic flow to ease congestion elsewhere. In this way, non-periodic sequences of green lights may result, which outperform the conventional periodic service of traffic lights. Furthermore, the other-regarding self-organization creates a flow-based coordination of traffic lights among neighboring intersections. This coordination spreads over large parts of the city in a self-organized way through a favorable cascade effect.

A pilot study

After our promising simulation study, Stefan Lämmer approached the public transport authority in Dresden, Germany, to collaborate with them on traffic light control. So far, the traffic center applied a state-of-the-art adaptive control scheme producing "green waves". But although it was the best system on the market, they weren't entirely happy with it. Around a busy railway station in the city center they could either produce "green waves" of motorized traffic on the main arterials or prioritize public transport, but not both. The particular challenge was to prioritize public transport while so many different tram tracks and bus lanes cut through Dresden's highly irregular road network. However, if public transport (buses and trams) would be given a green light whenever they approached an intersection, this would destroy the green wave system needed to keep the motorized traffic flowing. Inevitably, the resulting congestion would spread quickly, causing massive disruption over a huge area of the city.

When we simulated the expected outcomes of the other-regarding self-organization of traffic lights and compared it with the state-of-the art control they used, we got amazing results.[21] The waiting times were reduced for all modes of transport, dramatically for public transport and pedestrians, but also somewhat for motorized traffic. Overall, the roads were less congested, trams and buses could be prioritized, and travel times became more predictable, too. In other words, the new approach can benefit everybody (see Fig. 7) – including the environment. Thus, it is just consequential that the other-regarding self-organization approach was recently implemented at some traffic intersections in Dresden with amazing success (a 40 percent reduction in travel times). "Finally, a dream is becoming true", said one of the observing traffic engineers, and a bus driver inquired in the traffic center: "Where have all the traffic jams gone?"[22]

Figure 7: Improvement of intersection performance for different modes of transport achieved by other-regarding self-organization. The graph displays cumulative waiting times. Public transport has to wait 56 percent less, motorized traffic 9 percent less, and pedestrians 36 percent less.[23]

Lessons learned

The example of self-organized traffic control allows us to draw some interesting conclusions. Firstly, in a complex dynamical system, which varies a lot in a hardly predictable way and can't be optimized in real time, the principle of bottom-up self-organization can outperform centralized top-down control. This is true even if the central authority has comprehensive and reliable data. Secondly, if a selfish local optimization is applied, the system may perform well in certain circumstances. However, if the interactions between the system's components are strong (if the traffic volume is too high), local optimization may not lead to large-scale coordination (here: of neighboring intersections). Thirdly, an "other-regarding" distributed control approach, which adapts to local needs and additionally takes into account external effects ("externalities"), can coordinate the behavior of neighboring components within the system such that it produces favorable and efficient outcomes.

In conclusion, a centralized authority may not be able to manage a complex dynamical system well because even supercomputers may not have enough processing power to identify the most appropriate course of action in real time. Compared to this, selfish local optimization will fail due to a breakdown of coordination when interactions in the system become too strong. However, an other-regarding local self-organization approach can overcome both of these problems by considering externalities (such as spillover effects). This results in a system, which is both efficient and resilient to unforeseen circumstances.
[2] http://designforvalues.tudelft.nl
[3] https://www.ams-institute.org/solution/democracy-by-design/
[4] https://www.scientificamerican.com/article/will-democracy-survive-big-data-and-artificial-intelligence/, https://techcrunch.com/2016/10/09/a-decentralized-web-would-give-power-back-to-the-people-online/
[5] see e.g. the Snowden and Wikileaks “Vault 7” revelations or the TED talk by Tristan Harris: https://www.youtube.com/watch?v=C74amJRp730
[6] M. O’Toole, D.B. Lindell, and G. Wetzstein, Nature 555, 338-341 (2018); Autonome Autos: Laser-System und Algorithmen helfen verdeckte Objekte zu erkennen, https://www.heise.de/newsticker/meldung/Autonome-Autos-Laser-System-und-Algorithmen-helfen-verdeckte-Objekte-zu-erkennen-3987149.html
[7] A. Kesting, M. Treiber, M. Schönhof, and D. Helbing (2008) Adaptive cruise control design for active congestion avoidance. Transportation Research C 16(6), 668-683 ; A. Kesting, M. Treiber, and D. Helbing (2010) Enhanced intelligent driver model to access the impact of driving strategies on traffic capacity. Phil. Trans. R. Soc. A 368(1928), 4585-4605
[8] I would like to thank Martin Treiber for providing this graphic.
[10] A. Kesting, M. Treiber, and D. Helbing (2010) Connectivity statistics of store-and-forward intervehicle communication. IEEE Transactions on Intelligent Transportation Systems 11(1), 172-181.
[11] D. Helbing and P. Molnár (1995) Social force model for pedestrian dynamics. Physical Review E 51, 4282-4286
[12] D. Helbing, S. Lämmer, and J.-P. Lebacque (2005) Self-organized control of irregular or perturbed network traffic. Pages 239-274 in: C. Deissenberg and R. F. Hartl (eds.) Optimal Control and Dynamic Games (Springer, Dordrecht)
[13] S. Lämmer (2007) Reglerentwurf zur dezentralen Online-Steuerung von Lichtsignalanlagen in Straßennetzwerken (PhD thesis, TU Dresden)
[14] S. Lämmer and D. Helbing (2008) Self-control of traffic lights and vehicle flows in urban road networks. Journal of Statistical Mechanics: Theory and Experiment, P04019, see http://iopscience.iop.org/1742-5468/2008/04/P04019; S. Lämmer, R. Donner, and D. Helbing (2007) Anticipative control of switched queueing systems, The European Physical Journal B 63(3) 341-347; D. Helbing, J. Siegmeier, and S. Lämmer (2007) Self-organized network flows. Networks and Heterogeneous Media 2(2), 193-210; D. Helbing and S. Lämmer (2006) Method for coordination of concurrent processes for control of the transport of mobile units within a network, Patent WO/2006/122528
[15] C. Gershenson and D. Helbing, When slower is faster, see http://arxiv.org/abs/1506.06796; D. Helbing and A. Mazloumian (2009) Operation regimes and slower-is-faster effect in the control of traffic intersections. European Physical Journal B 70(2), 257–274
[16] Reproduced from D. Helbing (2013) Economics 2.0: The natural step towards a self-regulating, participatory market society. Evol. Inst. Econ. Rev. 10, 3-41, with kind permission of Springer Publishers
[17] Reproduction from S. Lämmer (2007) Reglerentwurf zur dezentralen Online-Steuerung von Lichtsignalanlagen in Straßennetzwerken (Dissertation, TU Dresden) with kind permission of Stefan Lämmer, accessible at
[18] Reproduced from D. Helbing (2013) Economics 2.0: The natural step towards a self-regulating, participatory market society. Evol. Inst. Econ. Rev. 10, 3-41, with kind permission of Springer Publishers
[19] This critical length can be expressed as a certain percentage of the road section.
[20] Due to spill-over effects and a lack of coordination between neighboring intersections, selfish self-organization may cause a quick spreading of congestion over large parts of the city analogous to a cascading failure. This outcome can be viewed as a traffic-related "tragedy of the commons", as the overall capacity of the intersections is not used in an efficient way.
[21] S. Lämmer and D. Helbing (2010) Self-stabilizing decentralized signal control of realistic, saturated network traffic, Santa Fe Working Paper No. 10-09-019, see http://www.santafe.edu/media/workingpapers/10-09-019.pdf ; S. Lämmer, J. Krimmling, A. Hoppe (2009) Selbst-Steuerung von Lichtsignalanlagen - Regelungstechnischer Ansatz und Simulation. Straßenverkehrstechnik 11, 714-721
[22] Latest results from a real-life test can be found here: S. Lämmer (2015) Die Selbst-Steuerung im Praxistest, see http://stefanlaemmer.de/Publikationen/Laemmer2015.pdf
[23] Adapted reproduction from S. Lämmer and D. Helbing (2010) Self-stabilizing decentralized signal control of realistic, saturated network traffic, Santa Fe Working Paper No. 10-09-019, see

No comments:

Post a comment

Note: only a member of this blog may post a comment.