Transportation Network Games

“Have you ever heard of ‘game theory’?” Dr. Nicholas Lownes (Civil & Environmental Engineering) asks as he starts to explain his current Department of Homeland Security (DHS) sponsored research grant with Dr. Reda Ammar, Department Head of Computer Science & Engineering, and Dr. Sanguthevar Rajasekaran, UTC Professor of Computer Science & Engineering. He is referring to the theory that attempts to mathematically capture behavior in strategic situations, in which an individual’s success in making choices depends on the choices of others. Drs. Lownes, Ammar and Rajasekaran are applying game theory to identify critical risks in our nation’s transportation networks.

In 2008, UConn was named one of DHS’s National Transportation Centers of Excellence (NTSCOE) and was given the task of researching and developing new technologies that will protect the nation’s multi-modal surface transportation infrastructure. This multidisciplinary effort fit the DHS mission perfectly. “The idea of our project is to use mathematical models to help us identify pieces of the transportation network, like roads, bridges, rail and even pipelines, which are more vulnerable because of the number of people that travel over them or because of a geographic location, for example,” Dr. Lownes explained. He continued on, “Our system looks at the way the entire network is built to try to identify pieces that a terrorist might try to disable or destroy.” In essence, the researchers are taking DHS’ mission of protection and making it a little bit easier. “What we are trying to do is prevent such incidents from ever happening,” Dr. Lownes explained.

Applying game theory, the researchers have created a computer program that plays a game between a benevolent character, who wants to help people travel safely, and an evil character, who is trying to disrupt the network as much as possible. In this computer program, the benevolent character and the evil character are able to make decisions based on real city maps and networks much like a game of chess. First the benevolent character makes a move based on safety; this is followed by the evil character’s response. This volley goes on until there are no moves left to make. This activity can then be graphed and an output is created detailing the most vulnerable links in the network.

“From a practical standpoint, we have used this game to try to identify vulnerable links and to provide the graphic outputs to a state Department of Transportation or a transportation engineer or planner. This provides valuable insight into the most critical points in the network that warrant monitoring or strengthening,” said Dr. Lownes. The intent of this research is to allow the recipients of this information to make better decisions in deploying security technology, whether it is sensors or improving the infrastructure by making it stronger. “This is designed as a decision support tool,” clarifies Dr. Lownes.

The breadth of this research requires a multidisciplinary approach. For example, Dr. Lownes’ background is in transportation network modeling; Drs. Ammar and Rajasekaran both have a computer science background and specialize in software, theory, and efficient algorithms.

In terms of the project timeline, the researchers have laid the foundation for both game theory and graph theory, “the meat behind the interface,” as Dr. Lownes called it, and are beginning to develop the software tool. “The tool itself is in development, and now we are at a point where we can start to integrate additional factors including broader network structures and some safety modeling aspects; essentially, a more robust definition of vulnerability,” said Dr. Lownes. As a final step the team will create a software tool that allows users to upload their own networks and be able to identify where they need to focus their security efforts.

Categories: algorithm, Civil & Environmental Engineering, Civil Engineering, Headline