Scalable Next-Generation Software Infrastructure for High-Dimensional Search

Search is a universal problem-solving mechanism in Artificial Intelligence, enabling great leaps in the field. A variety of search methods have been used to solve diverse problems, such as playing games, planning the routes of autonomous vehicles, finding patterns in biological sequences, and many others. This project develops ultra-fast algorithms and software cyberinfrastructure appropriate for searching high-dimensional spaces induced by problems in the physical world. The paradigm investigated is that of state space search. State space search is a widely used AI search method that finds a solution to a problem by searching through the set of possible states of the problem. This paradigm entails randomization schemes that exploit local geometric properties both for state selection and local exploration. Its performance has been characterized and linked to the properties of the underlying search spaces, establishing the relevance of these methods for search in spaces arising from problems in the physical world. Our work systematizes and implements key insights that significantly improve the performance of sampling-based search methods without compromising their generality. The first part of our work has focused on fine-grained parallelism (SIMD parallelism) for validity checking. We showcase our results in the context of an open source software infrastructure for manipulation planning and underwater vehicle navigation.