Past Event: Oden Institute Seminar

A Scalable Heuristic for Fastest-Path Computation on Very Large Road Maps

Craig Gotsman, Dean, Ying Wu College of Computing and Distinguished Professor, New Jersey Institute of Technology

Abstract

This talk will present a simple but very effective improvement to a variant of the classical shortest-path algorithm, a cornerstone in computer science. The fastest-path (or minimal travel time) query between two points in a very large road map is an increasingly important primitive in modern transportation and navigation systems, thus very efficient computation of these paths on detailed road maps under dynamic traffic conditions is critical for system performance and throughput. We present a method to compute an effective admissible heuristic for the fastest path travel time between two points on a road map, which can be used to significantly accelerate the classical A* algorithm when computing fastest paths in road maps. Our method is based on two hierarchical sets of separators of the map represented by two binary trees. A preprocessing step computes a short vector of values per road junction based on the separator trees, which is then stored with the map and used to efficiently compute the heuristic at the online query stage. We demonstrate experimentally that this method scales well to maps at the continental level, providing a better quality heuristic, thus more efficient A* search, for fastest path queries between points at all distances, relative to other known heuristics. Joint work with Renjie Chen - Max-Planck Institute for Informatics, Saarbrücken, Germany. Bio Craig Gotsman is a Distinguished Professor of Computer Science at the New Jersey Institute of Technology (NJIT) and the Dean of NJIT’s Ying Wu College of Computing since Jan 2017. Prior to that he was a co-founder of the Cornell Tech campus in New York City and Professor and Founding Director of the Jacobs Technion-Cornell Innovation Institute there. Before Cornell Tech, Gotsman held the Hewlett-Packard Chair in Computer Engineering at Technion – Israel Institute of Technology, where he was a faculty member for 20 years. He also served as Deputy Senior Vice President of the Technion. He received his Ph.D. in Computer Science from the Hebrew University of Jerusalem in 1991. Gotsman, who co-founded the Technion Center for Graphics and Geometric Computing, is active in research on 3D computer graphics, geometric modeling, animation and computational geometry. He has been a visiting professor at Harvard University, ETH Zurich and INRIA Sophia Antipolis, and a research scientist at MIT. He has published 160 papers in the professional literature, and served on the editorial boards and on the program committees of the most important publication venues in computer graphics, including ACM SIGGRAPH, ACM TOG and IEEE TVCG. Gotsman is a Fellow of the National Academy of Inventors and a Fellow of the Academy of Europe. An active entrepreneur, Gotsman holds eleven U.S. patents, and founded three startup companies. The most recent one, Perceptiko, founded in 2014 and acquired in 2017, commercialized his academic research and developed real-time video processing technology using the output of a depth camera to enhance the video conferencing experience. Gotsman has also consulted for numerous Fortune 100 companies including Hewlett-Packard, Intel, Nokia, Samsung, Shell Oil and Disney.