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. The objective of this work is to 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 such as modern AI-enabled laboratories for the synthesis of chemical compounds; infrastructure inspection with aerial vehicles; and analysis of protein shape changes. 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 (e.g., the variables describing the x,y,z position of a drone). 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. We will systematize and implement key insights that can drastically improve 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.
This work has been supported by grant NSF 2411219.