21st Century Science Initiative Grant: Studying Complex Systems
A car waits for a traffic signal to turn green when no other vehicles are at the crossroad. A vehicle traveling at the speed limit is forced to brake every half mile for a traffic light. A car arriving at a crossroad seconds earlier triggers a traffic signal stopping a large group of vehicles traveling on the main road. Commuters face such frustrations each day. Urban traffic is controlled by traffic lights which have inherent inefficiencies that cause needless delays at traffic intersections. Such inefficiencies not only frustrate drivers, but also result in unnecessary engine idling at traffic lights, which has been linked to increased greenhouse gas emissions. In 2007, traffic congestion wasted 2.8 billion gallons of fuel, 4.2 billion hours, and $87.2 billion in delay and fuel costs.
The first four-way three-color traffic light was installed in 1920 and since then, research on traffic optimization has brought steady improvements to efficiency. However, we may be at the limit on how far we can go with the current class of optimization techniques; a paradigm shift is necessary for significant additional gains. The traffic system is inherently a complex system - large numbers of intelligent components (i.e., signals, vehicles, sensors and pedestrians) communicate with one another at the local level and exhibit sophisticated, emergent collective behaviors at the global level. Instead of trying to leverage the innate self-organization in such systems, most past "intelligent" traffic systems have attempted to use centralized control.
Such schemes are not ideal since they typically streamline traffic flow in only one direction and become increasingly inefficient and complex as the number of intersections increases. Our initial work on understanding the behavior of the traffic grid has shown promising results. We examined different conventional and unconventional approaches for signal optimization. Surprisingly, we found that randomly timed signals worked better than using fixed-time signals. More importantly, the rudimentary self-organization algorithm developed was more effective than either random or fixedtiming algorithms. We believe that there is greater potential for improving traffic controls with selforganization. A deeper understanding of the theoretical underpinnings of self-organization in the context of traffic control is required to realize that potential.
In the past, available technology might have limited a complex systems approach. However, recent advances in sensors and communications technologies (i.e., increased network connectivity between traffic lights and accuracy in sensors) enable more effective implementation of self-organization within traffic systems, since information can now be shared among traffic lights to coordinate their actions at the local level. The proposed project will set the stage for development of models, simulations, algorithms and rules for self-organization of traffic networks. The goal of this project is to minimize traffic congestion and delays by developing models of traffic signal self-organization, with local decisions made by each traffic signal based on traffic sensor data (e.g., vehicle speed and count). Each signal will only communicate with its immediate neighbors rather than with all the signals in the entire grid. Signals will react to changing conditions without external intervention and automatically recover from unpredictable traffic disturbances, such as disabled vehicles and dangerous weather conditions. Instead of all traffic signals feeding and receiving information from a central controller, each signal analyzes information locally, distributing the computational load and decreasing latency. As each signal shares information with its neighbors, global synchronization occurs over time - with expected effects of reducing vehicle delay, idling, emissions, fuel consumption and driver frustration. We will not only create models for traffic self-organization, but also examine the impact of using current sensor technology to gather information to support the system. We will also estimate the benefits of using data from more recently designed sensors (e.g., vehicular sensors).
In nature, many complex systems operate very efficiently through self-organization. Ants, for example, are social insects that self-organize and exhibit sophisticated collective behavior without the directing influence of external control. An ant has limited access to information and its behavioral repertoire is limited to 10-40 elementary behaviors. However, in groups, ants exhibit sophisticated collective behavior and demonstrate a clear division of labor, contributing to the entire colony's success. Some collect food; others take care of eggs, repair the nest, or protect the ant hill against threats. The secret lies in self-organization: Each organism follows simple rules and makes decisions based on local information from its neighbors. Yet collectively, the entire swarm accomplishes complex tasks. The advantage of such a system is its simplicity - where a few basic rules applied locally affect global order resulting in sophisticated behavior. The key to this outcome is finding the proper rules. Analogous to the behavior of social insects, a self-organized traffic system can be designed to optimize flow through the entire traffic grid by using simple rules based on local neighbor information to adjust a single signal's behavior while enabling global synchronization.
Complex systems devised by humans differ from those in nature. While natural systems have precise, preordained and predictable global outcomes, most man-made systems exhibit imprecise, unpredictable and chaotic behavior. Precisely controlled communication at the local level leads to desired behavior outcomes at the global level in natural systems. The desire to institute central control in man-made complex systems is inhibitive. A notable exception is the Internet, which uses selforganization by coordinating millions of relatively simple components to collectively create a virtual world exhibiting sophisticated behavior. Internet-based social networking applications - i.e., Facebook, MySpace and LinkedIn - also exhibit such behavior.
Stuart Kauffman said: "If biologists have ignored self-organization, it is not because self-ordering is not pervasive and profound. It is because biologists have yet to understand how to think about systems governed simultaneously by two sources of order. We will have to see that we are the natural expressions of a deeper order." In our efforts to control man-made complex systems, we need to embrace their inherent qualities and behaviors in order to align them with their natural states, instead of forcing them under centralized control. Such an understanding of natural systems will help us to resolve some of the difficulties we face in managing complex systems.
Associating complex systems with traffic control and developing the proper rules for interaction and behavior can be a difficult undertaking. Rules of self-organization can not only be applied to traffic control, but also for managing other complex systems such as social networks, nanosenor networks for biomedicine, free-market economies and engineering systems. This research will leverage our previous work in engineering optimization3,4 and communication5.
Our preliminary work using rudimentary algorithms on a small traffic grid shows promise in applying self-organization techniques to optimize traffic signals. The work proposed will not only investigate how to develop rules for individual traffic signals, but compare different self-organization strategies to manage and organize behavior at a global level. In addition to decreased traffic congestion, we will also explore improved resilience and robustness to failure or unpredictable events. Organisms that self-organize successfully use a limited number of attributes in decision-making. Our goal is also to understand the limits of self-organization. As the number of attributes increase, will self-organization still be feasible? For instance, the free-market economy is a self-organizing system with a basic set of rules that all participants must follow. It generally works efficiently; however, its rules occasionally need to be tweaked as participants capitalize on its inefficiencies and disrupt its natural harmony. Such possible flaws in the rules of self-organization for traffic control can lead to dangerous traffic conditions and need to be identified.
Metropolitan areas are engines for economic growth where oftentimes public transportation is available, congestion is moderate, and varied settings exist (i.e. downtown, suburbs and rural areas) in close proximity. These areas offer fertile ground for testing and studying a self-organized traffic system. They will also be able to withstand the minor disruptions associated with deployment and testing of the developed algorithms. Our objective is to study the City of Albany, New York and the surrounding metropolitan area. We are currently working with the Department of Transportation as a testbed for studying this approach.
Self-organizing traffic signals promise to revolutionize current traffic-control mechanisms and have the potential for results beyond our expectations. For instance, as they evolve, we might find the need to adapt - we may install speed controllers in cars that will adjust speed based on traffic congestion and signal timing such that it gets a green light when it reaches the intersection. There are broader implications to this work - urban planning may need to be reviewed and traffic rules modified. There is no question that communication and sensors have advanced sufficiently to allow us not only to conceive such a system, but to actually make it a reality. There are several unanswered questions on design of such systems that we will attempt to address in this proposal. We will endeavor to not only study the system conceptually, but to observe its performance in a real-life scenario that may manifest revelations elusive in theoretical experiments.