Staff View
Model-based refinement of search heuristics

Descriptive

Language
LanguageTerm (authority = ISO 639-3:2007); (type = text)
English
Genre (authority = RULIB-FS)
Other
Genre (authority = marcgt)
technical report
PhysicalDescription
InternetMediaType
application/pdf
Extent
1 online resource (168 pages) : illustrations
Note (type = special display note)
Technical report lcsr-tr-267
Name (type = corporate); (authority = RutgersOrg-School)
NamePart
School of Arts and Sciences (SAS) (New Brunswick)
Name (type = corporate); (authority = RutgersOrg-Department)
NamePart
Computer Science (New Brunswick)
TypeOfResource
Text
Name (type = personal)
NamePart (type = family)
Barley
NamePart (type = given)
Michael W.
Affiliation
Computer Science (New Brunswick)
Role
RoleTerm (type = text); (authority = marcrt)
author
TitleInfo
Title
Model-based refinement of search heuristics
Abstract (type = abstract)
Search is one of the central problem-solving paradigms in Artificial Intelligence. Unfortunately, search can be quite expensive. Problem-solvers frequently use rejection heuristics to lower the cost of their searches. Unfortunately, these rejection heuristics can also prevent a problem-solver from solving a problem. I describe a new learning algorithm, SHAPeS, that enables the learner to modify both rejection heuristics implemented explicitly as search control rules and those implemented implicitly by either being embedded within the program code or by being incorporated into the search space generators. The SHAPeS learning algorithm only requires a solution to be supplied rather than needing that solution's problem-solving trace. This frees the system from having to find the solution itself. The SHAPeS algorithm is generally applicable to search-based problem-solvers. I discuss both the conditions for the algorithm's correctness and its computational complexity. I implemented a restricted version of SHAPeS, called Bacall, and in this thesis report on the results of experiments conducted to assess the utility of the Bacall learned modifications. The experiments show that not only can Bacall learned modifications extend a problem-solver coverage but can also enable it to run faster. The experiments also compare the utility of the Bacall learned modifications with the utility of current approaches to modifying rejection heuristics. The experiments show that Bacall learned modifications can improve the problem-solver's performance more than comparable modifications learned by the alternative approaches. Lastly, I identify three types of search control knowledge interactions that complicate the analysis of rejection heuristics' effects upon a problem-solver's coverage. These interactions cause modifications to a problem-solver's search control knowledge to have counter-intuitive effects upon the problem-solver's coverage. For example, removing rejection rules or specializing their preconditions can cause the problem-solver to become unable solve some problems. I also identify conditions that are sufficient to eliminate these types of interactions and that simplify the analysis of the effect of modifying a problem-solver's search control logic upon its coverage.
OriginInfo
DateCreated (encoding = w3cdtf); (qualifier = exact); (keyDate = yes)
1996-05
RelatedItem (type = host)
TitleInfo
Title
Computer Science (New Brunswick)
Identifier (type = local)
rucore21032500001
Location
PhysicalLocation (authority = marcorg); (displayLabel = Rutgers, The State University of New Jersey)
NjNbRU
Identifier (type = doi)
doi:10.7282/t3-2ese-ce74
Back to the top

Rights

RightsDeclaration (AUTHORITY = rightsstatements.org); (TYPE = IN COPYRIGHT); (ID = http://rightsstatements.org/vocab/InC/1.0/)
This Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).
Copyright
Status
Copyright protected
Availability
Status
Open
Reason
Permission or license
Back to the top

Technical

RULTechMD (ID = TECHNICAL1)
ContentModel
Document
CreatingApplication
Version
1.4
ApplicationName
GPL Ghostscript 9.07
DateCreated (point = start); (encoding = w3cdtf); (qualifier = exact)
2018-06-06T12:37:46
DateCreated (point = start); (encoding = w3cdtf); (qualifier = exact)
2018-06-06T12:37:46
Back to the top
Version 8.3.10
Rutgers University Libraries - Copyright ©2019