ERA

Download the full-sized PDF of Adding Exploration to Greedy Best-First SearchDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3QR4NR7K

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

Adding Exploration to Greedy Best-First Search Open Access

Descriptions

Author or creator
Valenzano, Richard
Sturtevant, Nathan R.
Schaeffer, Jonathan
Additional contributors
Subject/Keyword
Greedy best-first search
Artificial Intelligence
Diversity
Heuristic search
Planning
Exploration
Type of item
Computing Science Technical Report
Computing science technical report ID
TR13-06
Language
English
Place
Time
Description
While greedy best-first search (GBFS) is a popular algorithm for solving automated planning tasks, it can exhibit poor performance if the heuristic in use mistakenly identifies a region of the search space as promising. In such cases, the way the algorithm greedily trusts the heuristic can cause the algorithm to get stuck performing a lot of unnecessary work. In this report, we consider simple techniques that help GBFS to avoid overly trusting the heuristic. The first technique, heuristic perturbation, will be shown to lead to large increases in coverage in some domains, and large decreases in others. Over all problems tested, this technique does increase the average coverage by up to 9.5% over standard GBFS when it is parameterized effectively. The second technique, epsilon-greedy node selection, will be shown to lead to smaller improvements than heuristic perturbation in many domains, though it does so without hurting the algorithm's performance in any other domains. Over all tested problems, this technique will be shown to increase coverage even when used with a wide range of parameter values, with the best setting leading to a 11.0% increase in coverage when compared to standard GBFS. We will also show that these techniques can be paired together effectively in an algorithm portfolio due to the complementary way they introduce exploration into the search, with our best portfolio having an expected coverage that is 22.5% higher than standard GBFS.
Date created
2013
DOI
doi:10.7939/R3QR4NR7K
License information
Creative Commons Attribution 3.0 Unported
Rights

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-04-24T23:35:20.276+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 244043
Last modified: 2015:10:12 16:45:40-06:00
Filename: TR13-06.pdf
Original checksum: d994b23a10f33d53619ff3633ede50da
Well formed: false
Valid: false
Status message: Lexical error offset=241567
Page count: 16
Activity of users you follow
User Activity Date