02/02/2021

Necessary and Sufficient Conditions for Avoiding Reopenings in Best First Suboptimal Search with General Bounding Functions

Jingwei Chen, Nathan R. Sturtevant

Keywords:

Abstract Paper Similar Papers

Abstract: Recent work introduced XDP and XUP priority functions for best-first bounded-suboptimal search that do not need to perform state re-expansions as long as the search heuristic is consistent. However, that work had several limitations that are rectified here. This paper analyzes the sufficiency and necessity of the conditions used to formulate XDP and XUP. The analysis presents a simpler proof and generalizes the result in three aspects: (1) the priority function no longer has to be differentiable everywhere, (2) the quality of the solution does not have to be bounded by a constant factor, and (3) directed graphs are handled correctly. These results allow the introduction of more priority functions, such as piecewise linear functions, and more variants of bounded-suboptimal search, such as constant suboptimality. Several new priority functions are presented in this paper that, according to empirical results, can significantly outperform existing approaches including XDP.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38949038
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 12:11 
 0
 0
 0
 0
 4:40 
 0
 0
 0
 0
 21:49 
 0
 0
 0
 0
 3:23 
 0
 0
 0
 0
 16:46 
 0
 0
 0
 0
 25:50 
 0
 0
 0
 0
 14:36 
 0
 0
 0
 0
 7:35 
 0
 0
 0
 0
 14:26 
 0
 0
 0
 0
 1:00 
 0
 0
 0
 0
 11:06 
 0
 0
 1
 1
 16:17 
 0
 0
 0
 0
 7:27 
 0
 0
 0
 0
 9:50 
 0
 0
 0
 1
 15:49 
 0
 0
 0
 0
 18:25 
 0
 0
 0
 0
 17:35 
 0
 0
 0
 0
 15:26 
 0
 0
 0
 0
 5:15 
 0
 0
 0
 0
 20:56 
 0
 0
 0
 0
 14:35 
 0
 0
 0
 0
 32:08 
 0
 0
 0
 0
 6:58 
 0
 0
 0
 0
 12:32 
 0
 0
 0
 0
 3:21 
 0
 0
 0
 0
 7:46 
 0
 0
 0
 0
 3:09 
 0
 0
 0
 0
 2:53 
 0
 0
 0
 0
 14:47 
 0
 0
 0
 0
 14:56 
 0
 0
 0
 0
 3:11 
 0
 0
 0
 0
 1:01 
 0
 0
 0
 0
 10:04 
 0
 0
 0
 0
 15:08 
 0
 0
 0
 0
 7:39 
 0
 0
 0
 0
 10:14 
 0
 0
 0
 0
 8:05 
 0
 0
 0
 0
 15:01 
 0
 0
 0
 0
 5:13 
 0
 0
 0
 0
 8:58