---
title: "Distributional Metareasoning for Heuristic Search"
authors:
  - "Tianyi Gu"
doi: "10.24963/ijcai.2021/673"
url: "https://ijcai.org/proceedings/2021/673"
pdf: "https://ijcai.org/proceedings/2021/0673.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "4883-4884"
track: "Doctoral Consortium"
keywords:
  - "Heuristic Search and Game Playing: Heuristic Search"
  - "Heuristic Search and Game Playing: Heuristic Search and Machine Learning"
  - "Heuristic Search and Game Playing: Meta-Reasoning and Meta-Heuristics"
---

# Distributional Metareasoning for Heuristic Search

Tianyi Gu

*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 4883-4884. DOI: [10.24963/ijcai.2021/673](https://doi.org/10.24963/ijcai.2021/673)

## Abstract

Heuristic search methods are widely used in many real-world autonomous systems. Yet, people always want to solve search problems that are larger than time allows. To address these challenging problems, even suboptimally, a planning agent should be smart enough to intelligently allocate its computational resources, to think carefully about where in the state space it should spend time searching. For finding optimal solutions, we must examine every node that is not provably too expensive. In contrast, to find suboptimal solutions when under time pressure, we need to be very selective about which nodes to examine. In this work, we will demonstrate that estimates of uncertainty, represented as belief distributions, can be used to drive search effectively.  This type of algorithmic approach is known as metareasoning, which refers to reasoning about which reasoning to do. We will provide examples of improved algorithms for real-time search, bounded-cost search, and situated planning.