This post is written by UI grad student Keith Drew
The team at University of Idaho currently consists of four people, Dr. Robert B. Heckendorn, Keith Drew, Homaja Marisetty, and Madhav Pandey. Our team also includes researchers at the Michigan State University, led by Dr. Kalyan Deb. Our work is focused on evacuation planning and emergency management, using evolution strategies to evolve traffic assignments, or probability-based instructions, for intersections in urban areas. The problem we want to solve regarding evacuation is the issue of traffic congestion, while also being able to adapt to changes in the environment. Our goal is to evolve real-time traffic distributions in the face of disasters and other evacuation events, however, the group at Michigan State University is seeking to solve the same problem using a different approach. So far, we at the University of Idaho have created an implementation of our model and began running experiments.
I am a graduate student in Computer Science at the University of Idaho and I also completed my undergraduate here as well. I was introduced to the project by Dr. Heckendorn, and have found it to be engaging work so far. Personally, I am interested in this work because I feel it is important. A real-world application, leveraging evolution strategies, appeals to me in two significant ways. First, the work could lead to a life-saving evacuation management system, which appeals to my practical side and second, working with evolution heuristics is always compelling for the sake of watching solutions to difficult problems form.
Our research goal is to find a way to provide real-time solutions to evacuation problems, which are constrained by congestion, time, and dynamic events. In the past, evacuations have led to large congestion problems in the traffic systems being evacuated. Our work seeks to provide traffic distributions that tell vehicles which way to go at intersections, adapt to changes in the environment, and optimize routing for the safety of the population being evacuated. So far, our specific approach is untested and looks promising. Our current approach is to evolve probability distributions for each intersection throughout the area being evacuated. These probabilities serve to route traffic by breaking the traffic assignment up and sending the appropriate amount each way at an intersection. We judge each set of such probabilities based on how safe every member in the population is at a given time. For example, if a hurricane will move over the evacuation area in one hour, we simulate one hour and evaluate safety at that point. Evacuation plans vary by the type of event calling for an evacuation, such as a flood or a hurricane. In some cases, elevation is a key component of safety, in other cases distance is the key focus; by evaluating the safety of the population we hope to find non-intuitive solutions for any type of evacuation event.
Another aspect driving our research is the dynamic nature of real disaster and evacuation events. Our model focuses on these changes as constraints. For example, we want to be able to handle a change in the availability of certain routes, during a disaster. Such a change might be a bridge washing out or collapsing, or perhaps a road becoming partially or fully blocked due to a traffic accident. Another type of change involves the way that people behave while driving. If people are told to evacuate a certain way, yet they choose to follow their own instincts, issues of congestion can arise, and our model needs to be able to handle those types of changes. Another more obvious type of change is the disaster or danger that people are evacuating from. Consider a hurricane, which moves along. Over time, safe areas become unsafe, and unsafe areas become safe once again. In the face of such changes evacuation plans can be undone, and we want to provide a solution that can adapt to any such change.
Once an algorithm or model is created that works well and can create robust traffic assignments for large areas, communicating that information to the evacuees becomes a new challenge. Methods for communicating such information include possibilities such as vehicle-to-vehicle communications, self-driving cars, and more. Self-driving cars are of particular interest, as studies have shown that automation can improve traffic conditions significantly, and some work has shown that self-driving cars can work together to navigate intersections without stopping. They simply speed up or slow down on approach to the intersection. With such technology, our model might be able to provide the directions needed to such cars.
My contribution to the project so far has been helping to develop the model we are using, as well as implementing it, using a combination of a lexical analyzer, parser, and C++. Currently our system includes a simulation, for running traffic through a graph that represents the area being evacuated, an evolution strategy algorithm, which evolves the traffic distributions, and a grammar which is used to specify evacuation areas and tests for our model. Another key component created by Homaja, is a visualization tool, written in Processing. The tool takes output from our model and creates visualizations of traffic moving through the grid, as well as creating graphs that allow us to ensure the model is working as intended. It’s very nice to be able to watch vehicles traverse our little city, and escape some unseen danger.
In the end, we are leveraging knowledge and experience from the realms of evolutionary computation, emergency management, civil engineering, and traffic analysis and behavior, all to create a system which can, ideally, minimize any loss of life during large emergency events. So far, preliminary results look very promising, and I am definitely enjoying this work.