Uploaded April 2016 | Updated September 2026, 30 minutes ago
This talk was given by undergraduate Bradley Davis during the 10th Annual Computer Science Undergraduate Research Symposium in 2016. Bradley‘s research was supervised by Dr. Diane Pozefsky.
“Congestion Avoidance on Road Networks through Adaptive Routing on Contracted Graphs”
We have developed a method of integrating live traffic information into preprocessed graphs of large road networks in order to adaptively route autonomous vehicles. Our intent is to reduce congestion caused by fleets of centrally-routed vehicles being assigned overlapping routes and to help those vehicles avoid already congested areas. Recent developments in shortest-path routing, namely Contraction Hierarchies, are used in conjunction with a modified bidirectional Dijkstra search algorithm to ensure fast route computations despite frequent graph updates. We introduce a novel heuristic for graph reprocessing that enables quick updates alongside a simple approach to computing appropriate edge weights based on substantial amounts of feedback received from vehicles on the road. Our approach is tested on a developed simulation platform using real road data and a Nagel–Schreckenberg traffic model. Early results show that vehicles experience an overall speedup in travel time and adeptly react to unforeseen conditions by using alternative routes to avoid further congestion.
Bradley Davis is a senior majoring in computer science. During his time at Carolina, he has been actively involved on campus, studied abroad at University College London, and participated in many programming contests, hackathons, and case competitions. He has most recently joined a local startup, LineLeader, as a principal engineer. After graduation, Bradley will move to San Francisco to work for the popular business chat application Slack as a software engineer. Bradley hopes to pursue a master’s degree in computer science through Georgia Tech’s OMSCS program in the near future.
This talk was given by undergraduate Bradley Davis during the 10th Annual Computer Science Undergraduate Research Symposium in 2016. Bradley‘s research was supervised by Dr. Diane Pozefsky.
“Congestion Avoidance on Road Networks through Adaptive Routing on Contracted Graphs”
We have developed a method of integrating live traffic information into preprocessed graphs of large road networks in order to adaptively route autonomous vehicles. Our intent is to reduce congestion caused by fleets of centrally-routed vehicles being assigned overlapping routes and to help those vehicles avoid already congested areas. Recent developments in shortest-path routing, namely Contraction Hierarchies, are used in conjunction with a modified bidirectional Dijkstra search algorithm to ensure fast route computations despite frequent graph updates. We introduce a novel heuristic for graph reprocessing that enables quick updates alongside a simple approach to computing appropriate edge weights based on substantial amounts of feedback received from vehicles on the road. Our approach is tested on a developed simulation platform using real road data and a Nagel–Schreckenberg traffic model. Early results show that vehicles experience an overall speedup in travel time and adeptly react to unforeseen conditions by using alternative routes to avoid further congestion.
Bradley Davis is a senior majoring in computer science. During his time at Carolina, he has been actively involved on campus, studied abroad at University College London, and participated in many programming contests, hackathons, and case competitions. He has most recently joined a local startup, LineLeader, as a principal engineer. After graduation, Bradley will move to San Francisco to work for the popular business chat application Slack as a software engineer. Bradley hopes to pursue a master’s degree in computer science through Georgia Tech’s OMSCS program in the near future.
