Computer Science and Engineering Assistant Professor Forest Agostinelli has received a nearly $350,000, three-year National Science Foundation grant to study the use of heuristic (experimental) search and machine learning to solve complex pathfinding problems. Agostinelli’s project is expected to advance artificial intelligence (AI) techniques that solve problems faster or find approximate solutions.
Pathfinding is the search that a computer program makes to find the shortest route between points. Solving pathfinding problems often involves both considerable computation and human intervention. The development of efficient solutions to these problems is crucial for advancement in many fields.
“Pathfinding involves any problem where you want to get from a starting point to a goal point by a sequence of actions. A Rubik’s Cube, molecular synthesis, proving a theorem, robotics and computer science all are examples of pathfinding problems,” Agostinelli explains. “Developing ways to solve these complex problems more efficiently is important because these fields are fundamental to our everyday lives.”
Agostinelli is combining two AI methods, heuristic search and machine learning, to solve complex problems without human assistance. Heuristic search typically requires advanced domain-specific knowledge to construct a heuristic function, a method in AI that helps guide search algorithms in finding the most efficient path to a goal. While other research has explored the use of deep neural networks and reinforcement learning to learn heuristic functions, challenges remain in scaling with increased problem complexity, leading to inefficient solutions or failure in finding a solution.
To address this limitation, Agostinelli is investigating novel ways of applying machine learning to heuristic search to create an approach that learns to adapt to the problem at hand. This involves measuring the scalability of algorithms with increased problem complexity. The desired result is a computational approach that can efficiently solve a wider array of real-world problems.
“Previously, heuristic functions on more complex matters required a lot of human effort. For example, if I wanted to know how to synthesize a chemical, I would need a Ph.D. in chemistry and significant experience to construct a heuristic function,” Agostinelli says. “Through machine learning, our objective is that only a description of the problem is needed to learn further aspects of the problem that we have yet to discover and incorporate that knowledge in the heuristic function.”
Agostinelli says that his work will make a meaningful and lasting impact on the research landscape and society at large. In the research community, improved heuristics have the potential to advance domains such as chemical synthesis and theorem proving. For society, his methods can lead to greater efficiency that significantly reduces the resource consumption required for finding solutions to real-world problems.
Agostinelli’s work is part of a larger collection of research being conducted in the Artificial Intelligence Institute of the University of South Carolina, led by Department of Computer Science and Engineering Chair Homayoun Valafar.