AF: Small: New Directions in Geometric Shortest Paths

University Of California-Santa Barbara, Santa Barbara CA

Investigators

Abstract

Shortest paths and reachability are fundamental problems with a long and distinguished history in computer science and mathematics. Due to growing integration of cyber and physical worlds through the Internet-of-Things (IoT), an increasing amount of data processing entails geometric models, and an ever growing set of smart mobile devices can interact with, and affect, the environment in which they operate - from self-driving cars to autonomous robots. Addressing the needs of these applications, this project explores new directions for shortest paths in geometric domains, organized around the following two broad themes: (1) improving shortest paths by removal of some path-blocking obstacles, and (2) searching for a randomized prize. The specific research topics of the project are novel, yet the general theme touches on many classical problems in geometry, combinatorial optimization, probability theory, decision science and search. The project significantly broadens the scope, applicability and relevance of geometric algorithms to search and planning in continuous spaces, by incorporating strategic intervention and planning under uncertainty. The fundamental nature of topics addressed in this project is likely to appeal to a broad set of students with diverse backgrounds, both graduate and undergraduate. The material generated from this project will be integrated into multiple courses on algorithms and computational geometry, including the investigator's newly launched Foundations of Data Science course. The project is centered around two research topics. The first topic deals with the following question of reachability: can one reach a target position from an initial position. When this is possible, the goal is to compute a feasible path, or perhaps the shortest one. The focus of the project is the "if not" side of this question, which is often left unattended. Specifically, if no feasible path exists, or the shortest path is unacceptably long, how many and which obstacles should be removed? This form of reachability augmentation in geometric domains is both fundamental and intellectually exciting, with many surprising twists and turns. The solution quality and the algorithmic efficiency critically depend on the geometry of the workspace and model assumptions: are obstacles convex or non-convex? Are obstacles disjoint or overlapping? Is the removal cost the same for all obstacles or different? The second topic proposes a novel framework for problems in which one tries a sequence of alternatives in search for a prize (favorable outcome), where each outcome is determined by a random trial. Computing combinatorial structures, such as shortest paths, in the presence of such random events poses significant intellectual challenges, and the project research contributes to an important body of knowledge. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.