Back to search

Georgia Institute of Technology

Learning-based search algorithm design

Abstract

dc:description.abstract

Classical search algorithms, such as A* search, evolutionary search, and Monte Carlo tree search, play a central role in solving many combinatorial optimization problems, including robotic path planning, molecule optimization, and playing Go. Conventionally, domain experts design these algorithms analytically by hand. However, such an algorithm design process is not data-driven and cannot benefit from the ever-increasing volumes of data. In this dissertation, we introduce a series of learning-to-search methods for different types of search space. We show that both search efficiency and effectiveness can be improved by learning search algorithms from historical data. Specifically, we focus on addressing challenges in a number of continuous and discrete search spaces with applications in robotics and drug design. High-dimensional continuous space. To search for solutions in high-dimensional continuous space, we resort to sampling-based methods to avoid explicitly discretizing the space. We propose a neural path planner that learns from prior experience to solve new path planning problems. Compared to classical methods, our learning-to-search approach achieves higher sample efficiency in high dimensions and can benefit from prior experience in similar environments. Discrete graph space. Finding graph structures with desired properties is a challenging problem. We present a learning-based evolutionary search algorithm to optimize molecules for desired properties. The proposed algorithm leverages a graph explainable model and the REINFORCE algorithm to generate better molecules on a multi-property molecule optimization benchmark. Discrete decomposable combinatorial space. We present a framework to search for solutions to recursively decomposable problems, based on the AND-OR tree representation that efficiently describes the search space. For the retrosynthesis planning problem, we introduce a learning-based A*-like search algorithm that finds high-quality synthetic routes for target molecules efficiently. The proposed algorithm builds on top of the AND-OR search tree and provides theoretical guarantees similar to the A* algorithm. Continuous molecular conformational space. We present a framework to search for molecular conformers with low energy, based on an Equivariant Transformer Forcefield. This strategy begins with an initial set of conformers, which are subsequently refined through structural optimization. We demonstrate that our ETF-based optimization significantly improves the quality of the conformers generated by state-of-the-art methods, achieving a 45\% reduction in the distance to the reference conformers.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Computational Science and Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Chen, Binghong
Advisors dc:contributor.advisor
  • Zhang, Chao
  • Song, Le
Committee members dc:contributor.committeemember
  • Zhang, Xiuwei
  • Luo, Yunan
  • Fung, Victor

Subjects

dc:subject × 10

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/72742

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Chen, Binghong. Learning-based search algorithm design. Doctoral thesis, Georgia Institute of Technology, 2023. https://hdl.handle.net/1853/72742