Elements: Scalable Next-Generation Software Infrastructure for High-Dimensional Search

Search is a universal problem-solving mechanism in Artificial Intelligence (AI), and it has enabled 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 will develop ultra-fast algorithms and software cyberinfrastructure appropriate for searching high-dimensional spaces induced by problems in the physical world.

Examples of such problems include manipulation planning, where robotic arms grasp objects and transfer them to new locations, potentially in the close presence of a human; autonomous underwater vehicle navigation; semi-automated laboratories for the synthesis of chemical compounds; infrastructure inspection with aerial vehicles; and analysis of protein shape changes. Distinguishing features of this work include (a) its generality that will be encapsulated in the design of the API of the cyberinfrastructure, (b) its implementation in commodity hardware, consumer CPUs, which will enable its widespread use, and (c) the training it will provide to postdoctoral, graduate and undergraduate students on a topic that is a building block for modern AI-driven research.

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. A state space is a mathematical representation of a problem that defines all possible states in which the problem can be.

A set of variables encodes each state in the state space. State spaces that arise from problems in the physical world typically have infinitely many states. This is because many, if not all, of the variables that characterize the underlying system, draw values from a continuous interval.

Search in such spaces is demanding. For many problems, however, it is possible to find solutions without examining the whole state space. The paradigm that will be further investigated and implemented in this proposal is sampling of state spaces combined with local exploration.

This paradigm, which has been widely successful in domains such as robotics, 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.

This proposal will systematize and implement key insights that can drastically affect the performance of sampling-based search methods without affecting their generality. These performance enhancements include, among others, exploiting methods for constraint satisfaction, domain-specific compilers, appropriate data structures, and fine-grained parallelism for validity checking.

It will deliver an integrated framework for sampling-based search, complete with a well-designed API for use in different applications. This proposal will train postdoctoral, graduate, and undergraduate students on the topic of search in high-dimensional spaces and diverse applications. Efforts will be undertaken to broadly disseminate the work and engage researchers from different disciplines. Outreach activities will include a workshop at a major conference.

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.