Title:

Beliefs We Can Believe In: Replacing Assumptions with Data in Real-Time Search

Poster

Preview Converted Images may contain errors

Abstract

Suboptimal heuristic search algorithms can benefit from reasoning about heuristic error, especially in a real-time setting where there is not enough time to search all the way to a goal. However, current reasoning methods implicitly or explicitly incorporate assumptions about the cost-to-go function. We consider a recent real-time search algorithm, called Nancy, that manipulates explicit beliefs about the cost-to-go. The original presentation of Nancy assumed that these beliefs are Gaussian, with parameters following a certain form. In this paper, we explore how to replace these assumptions with actual data. We develop a data-driven variant of Nancy, DDNancy, that bases its beliefs on heuristic performance statistics from the same domain. We extend Nancy and DDNancy with the notion of persistence and prove their completeness.

Authors

First Name Last Name
Marek Petrik
Joerg Hoffmann
Wheeler Ruml
Leonhard Staut
Maximilian Fickert
Tianyi Gu

File Count: 1


Leave a comment

Comments are viewable only by submitter



Submission Details

Conference GRC
Event Graduate Research Conference
Department Computer Science (GRC)
Group Poster Presentation
Added April 10, 2020, 6:35 p.m.
Updated April 10, 2020, 6:35 p.m.
See More Department Presentations Here