Grant: Discovery Grants Program - Individual

One expected aspect of any Artificial Intelligent (AI) agent is the ability to solve problems. AI techniques are used to solve a wide variety of problems such as path planning in road networks, for virtual agents, for package delivery in a city, or for individuals or teams of robots moving through a shared space. The problem solving agents used to solve these problems in heuristic search combine exhaustive search techniques with knowledge to solve problems. The better the knowledge, the less search is needed; with less knowledge more search is needed. Thus, knowledge plays an important part in search. The knowledge used for these agents is typically pre-computed in the form of heuristics or constraints. Heuristics guide the search towards the goal by estimating the distance to the goal from a given state, while constraints guide the search away from states that cannot reach the goal. Heuristics and constraints are typically built through an exact computational procedure, so that precise theoretical properties can be guaranteed. For instance, heuristics are usually required to be admissible, meaning they do not overestimate the cost to reach the goal. Although machine learning techniques have had a broad impact on other fields, they have had less of an impact on single-agent heuristic search. One reason for this is that machine learning cannot guarantee the same properties on heuristics (or constraints) that are guaranteed through exact computational procedures. Machine learning approaches may, for instance, produce inadmissible heuristics. However, machine learning has been able to learn very strong heuristics in games such as Go, although nobody currently knows how accurate these heuristics actually are. Given the recent advances in machine learning and success in related domains, along with the lack of use in single-agent search, it is the right time to research the application of machine learning to heuristic search. This research will grow out of the current research by the PI which has produced large data sets that are applicable for learning. It will involve numerous approaches for building heuristics and constraints, as well as building new algorithms that are designed to work with the approximate nature of data from machine learning. This work will allow heuristic techniques to be scaled to larger problems, while maintaining desired theoretical properties on solution quality, such as bounded suboptimality. More broadly, the work will have large impact on single-agent search, bringing new techniques to the field that have the potential to significantly change the approaches currently used.