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

Speaker: Prof. Craig Gotsman, 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.

Biography: Craig Gotsman is a Distinguished Professor of Computer Science at the New Jersey Institute of Technology (NJIT) and the former 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 MIT, Harvard University, ETH Zurich, INRIA Sophia Antipolis and the University of Miami. Gotsman is a Fellow of the ACM, the US National Academy of Inventors, Academia Europaea and the Academy of Science, Engineering and Medicine of Florida. An active entrepreneur, Gotsman holds thirteen U.S. patents, and founded three startup companies. The last one, Perceptiko, founded in 2014 and acquired by Apple 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.

Host: Prof. Kai Hormann