Automatically assigned DDC number: 006333
Manually assigned DDC number: 006333

Number of references: 8

Title: Domain-Dependent Single-Agent Search Enhancements

Author:

Author:

Subject: Andreas Junghanns,Jonathan Schaeffer Domain-Dependent Single-Agent Search Enhancements

Description: AI research has developed an extensive collection of methods to solve state-space problems. Using the challenging domain of Sokoban, this paper studies the effect of search enhancements on program performance. We show that the current state of the art in AI generally requires a large programming and research effort into domain-dependent methods to solve even moderately complex problems in such difficult domains. The application of domain-specific knowledge to exploit properties of the search space can result in large reductions in the size of the search tree, often several orders of magnitude per search enhancement. Understanding the effect of these enhancements on the search leads to a new classification of search enhancements, and a new framework for developing single-agent search applications. This is used to illustrate the large gap between what is portrayed in the literature versus what is needed in practice.

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1999-02-27

Pubyear: 1999

Format: ps

Identifier: http://citeseer.ist.psu.edu/161985.html

Source: http://www.cs.ualberta.ca/~andreas/Papers/soko_ijcai99.ps

Language: en

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml version="1.0" encoding="UTF-8"?>

<references_metadata>

<rec ID="/33917.html" Type="inproceedings" CiteSeer_Book="Canadian Conference on AI" CiteSeer_Volume="" Title="Searching with Pattern Databases,">

<identifier Org="ISBN:0262510952" Paper_ID="/33917.html" Extracted="0262510952" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:0262510987" Paper_ID="/33917.html" Extracted="0262510987" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:1558604804" Paper_ID="/33917.html" Extracted="1558604804" />

<identifier Org="ISBN:157735236X" Paper_ID="/33917.html" Extracted="157735236X" />

<identifier Org="ISBN:1586034529" Paper_ID="/33917.html" Extracted="1586034529" />

<identifier Org="ISBN:1586038915" Paper_ID="/33917.html" Extracted="1586038915" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:354021299X" Paper_ID="/33917.html" Extracted="354021299X" DDC="005.1/2" Normalized_DDC="00512" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540214453" Paper_ID="/33917.html" Extracted="3540214453" DDC="658.4034" Normalized_DDC="6584034" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540222189" Paper_ID="/33917.html" Extracted="3540222189" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:354029189X" Paper_ID="/33917.html" Extracted="354029189X" DDC="004.6/2" Normalized_DDC="00462" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540413855" Paper_ID="/33917.html" Extracted="3540413855" DDC="510 s" Normalized_DDC="51" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540426124" Paper_ID="/33917.html" Extracted="3540426124" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540645756" Paper_ID="/33917.html" Extracted="3540645756" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540650806" Paper_ID="/33917.html" Extracted="3540650806" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540678395" Paper_ID="/33917.html" Extracted="3540678395" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540678662" Paper_ID="/33917.html" Extracted="3540678662" DDC="006.3/33" Normalized_DDC="006333" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540735798" Paper_ID="/33917.html" Extracted="3540735798" DDC="004" Normalized_DDC="004" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540741275" Paper_ID="/33917.html" Extracted="3540741275" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:364200430X" Paper_ID="/33917.html" Extracted="364200430X" />

</rec>

<rec ID="/43156.html" Type="inproceedings" CiteSeer_Book="" CiteSeer_Volume="" Title="Sokoban is {PSPACE}-complete,">

<identifier Org="ISBN:0444509496" Paper_ID="/43156.html" Extracted="0444509496" DDC="794.8/1526" Normalized_DDC="79481526" Normalized_Weight="0.0625" />

<identifier Org="ISBN:0521808324" Paper_ID="/43156.html" Extracted="0521808324" DDC="519.3" Normalized_DDC="5193" Normalized_Weight="0.0625" />

<identifier Org="ISBN:0521862051" Paper_ID="/43156.html" Extracted="0521862051" DDC="629.8/932" Normalized_DDC="6298932" Normalized_Weight="0.0625" />

<identifier Org="ISBN:1402075243" Paper_ID="/43156.html" Extracted="1402075243" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />

<identifier Org="ISBN:1568811306" Paper_ID="/43156.html" Extracted="1568811306" DDC="793.7/4" Normalized_DDC="79374" Normalized_Weight="0.0625" />

<identifier Org="ISBN:1586037587" Paper_ID="/43156.html" Extracted="1586037587" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540205454" Paper_ID="/43156.html" Extracted="3540205454" DDC="794.8/1416" Normalized_DDC="79481416" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540424962" Paper_ID="/43156.html" Extracted="3540424962" DDC="004/.01/51" Normalized_DDC="0040151" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540426124" Paper_ID="/43156.html" Extracted="3540426124" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540430806" Paper_ID="/43156.html" Extracted="3540430806" DDC="794.81" Normalized_DDC="79481" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540438645" Paper_ID="/43156.html" Extracted="3540438645" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540645756" Paper_ID="/43156.html" Extracted="3540645756" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540684042" Paper_ID="/43156.html" Extracted="3540684042" DDC="629.892" Normalized_DDC="629892" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540729135" Paper_ID="/43156.html" Extracted="3540729135" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540752536" Paper_ID="/43156.html" Extracted="3540752536" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />

<identifier Org="ISBN:9810248458" Paper_ID="/43156.html" Extracted="9810248458" DDC="004.0151" Normalized_DDC="0040151" Normalized_Weight="0.0625" />

</rec>

<rec ID="/87349.html" Type="article" CiteSeer_Book="Lecture Notes in Computer Science" CiteSeer_Volume="1558" Title="Relevance Cuts: Localizing the Search,">

<identifier Org="ISBN:0444509496" Paper_ID="/87349.html" Extracted="0444509496" DDC="794.8/1526" Normalized_DDC="79481526" Normalized_Weight="1.0" />

</rec>

<rec ID="/190862.html" Type="inproceedings" CiteSeer_Book="Proceedings of the Fifteenth National Conference on Artificial Intelligence AAAI98" CiteSeer_Volume="" Title="Single-Agent Search in the Presence of Deadlocks,">

<identifier Org="ISBN:0262510987" Paper_ID="/190862.html" Extracted="0262510987" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.25" />

<identifier Org="ISBN:3540650806" Paper_ID="/190862.html" Extracted="3540650806" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.25" />

<identifier Org="ISBN:3540678662" Paper_ID="/190862.html" Extracted="3540678662" DDC="006.3/33" Normalized_DDC="006333" Normalized_Weight="0.25" />

<identifier Org="ISBN:3790815233" Paper_ID="/190862.html" Extracted="3790815233" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.25" />

</rec>

<rec ID="/25305.html" Type="inproceedings" CiteSeer_Book="Canadian Conference on AI" CiteSeer_Volume="" Title="Sokoban: Evaluating Standard Single-Agent Search Techniques in the Presence of Deadlock,">

<identifier Org="ISBN:0262510987" Paper_ID="/25305.html" Extracted="0262510987" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.25" />

<identifier Org="ISBN:0444509496" Paper_ID="/25305.html" Extracted="0444509496" DDC="794.8/1526" Normalized_DDC="79481526" Normalized_Weight="0.25" />

<identifier Org="ISBN:3540645756" Paper_ID="/25305.html" Extracted="3540645756" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.25" />

<identifier Org="ISBN:3540650806" Paper_ID="/25305.html" Extracted="3540650806" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.25" />

</rec>

<rec ID="/2111.html" Type="inproceedings" CiteSeer_Book="Proceedings of the Thirteenth National Conference on Artificial Intelligence and the Eighth Innovative Applications of Artificial Intelligence Conference" CiteSeer_Volume="" Title="Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search,">

<identifier Org="ISBN:1558604804" Paper_ID="/2111.html" Extracted="1558604804" />

<identifier Org="ISBN:1586030132" Paper_ID="/2111.html" Extracted="1586030132" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.05263157894736842" />

<identifier Org="ISBN:1586030612" Paper_ID="/2111.html" Extracted="1586030612" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.05263157894736842" />

<identifier Org="ISBN:1591404517" Paper_ID="/2111.html" Extracted="1591404517" DDC="006.3/3" Normalized_DDC="00633" Normalized_Weight="0.05263157894736842" />

<identifier Org="ISBN:3540202021" Paper_ID="/2111.html" Extracted="3540202021" DDC="005.1/1" Normalized_DDC="00511" Normalized_Weight="0.05263157894736842" />

<identifier Org="ISBN:354027829X" Paper_ID="/2111.html" Extracted="354027829X" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.05263157894736842" />

<identifier Org="ISBN:3540410945" Paper_ID="/2111.html" Extracted="3540410945" DDC="006.3/3" Normalized_DDC="00633" Normalized_Weight="0.05263157894736842" />

<identifier Org="ISBN:3540411313" Paper_ID="/2111.html" Extracted="3540411313" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.05263157894736842" />

<identifier Org="ISBN:3540425543" Paper_ID="/2111.html" Extracted="3540425543" DDC="005.1/01/5113" Normalized_DDC="0051015113" Normalized_Weight="0.05263157894736842" />

<identifier Org="ISBN:3540428984" Paper_ID="/2111.html" Extracted="3540428984" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.05263157894736842" />

<identifier Org="ISBN:3540439293" Paper_ID="/2111.html" Extracted="3540439293" DDC="006.3/33" Normalized_DDC="006333" Normalized_Weight="0.05263157894736842" />

<identifier Org="ISBN:3540657037" Paper_ID="/2111.html" Extracted="3540657037" DDC="004.2/1" Normalized_DDC="00421" Normalized_Weight="0.05263157894736842" />

<identifier Org="ISBN:3540664289" Paper_ID="/2111.html" Extracted="3540664289" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.05263157894736842" />

<identifier Org="ISBN:3540664920" Paper_ID="/2111.html" Extracted="3540664920" DDC="005.1/15" Normalized_DDC="005115" Normalized_Weight="0.05263157894736842" />

<identifier Org="ISBN:354066548X" Paper_ID="/2111.html" Extracted="354066548X" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.05263157894736842" />

<identifier Org="ISBN:3540667490" Paper_ID="/2111.html" Extracted="3540667490" DDC="005.1/15" Normalized_DDC="005115" Normalized_Weight="0.05263157894736842" />

<identifier Org="ISBN:3540677976" Paper_ID="/2111.html" Extracted="3540677976" DDC="004/.01/5113" Normalized_DDC="004015113" Normalized_Weight="0.05263157894736842" />

<identifier Org="ISBN:3540678662" Paper_ID="/2111.html" Extracted="3540678662" DDC="006.3/33" Normalized_DDC="006333" Normalized_Weight="0.05263157894736842" />

<identifier Org="ISBN:3540741275" Paper_ID="/2111.html" Extracted="3540741275" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.05263157894736842" />

<identifier Org="ISBN:3540754075" Paper_ID="/2111.html" Extracted="3540754075" DDC="003/.54" Normalized_DDC="00354" Normalized_Weight="0.05263157894736842" />

</rec>

<rec ID="/157215.html" Type="inproceedings" CiteSeer_Book="Proceedings of the Workshop on Computer Games W31 at IJCAI97" CiteSeer_Volume="" Title="Finding Optimal Solutions to Rubik's Cube Using Pattern Databases,">

<identifier Org="ISBN:0262510952" Paper_ID="/157215.html" Extracted="0262510952" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:0262510987" Paper_ID="/157215.html" Extracted="0262510987" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:0262560976" Paper_ID="/157215.html" Extracted="0262560976" DDC="001.4/225/028563" Normalized_DDC="0014225028563" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:0444509496" Paper_ID="/157215.html" Extracted="0444509496" DDC="794.8/1526" Normalized_DDC="79481526" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:0792372247" Paper_ID="/157215.html" Extracted="0792372247" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:089871558X" Paper_ID="/157215.html" Extracted="089871558X" />

<identifier Org="ISBN:1586034529" Paper_ID="/157215.html" Extracted="1586034529" />

<identifier Org="ISBN:3540214453" Paper_ID="/157215.html" Extracted="3540214453" DDC="658.4034" Normalized_DDC="6584034" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540426124" Paper_ID="/157215.html" Extracted="3540426124" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540645756" Paper_ID="/157215.html" Extracted="3540645756" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540650806" Paper_ID="/157215.html" Extracted="3540650806" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540678395" Paper_ID="/157215.html" Extracted="3540678395" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540678662" Paper_ID="/157215.html" Extracted="3540678662" DDC="006.3/33" Normalized_DDC="006333" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540678808" Paper_ID="/157215.html" Extracted="3540678808" />

<identifier Org="ISBN:3540735798" Paper_ID="/157215.html" Extracted="3540735798" DDC="004" Normalized_DDC="004" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540741275" Paper_ID="/157215.html" Extracted="3540741275" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540879862" Paper_ID="/157215.html" Extracted="3540879862" />

<identifier Org="ISBN:364200430X" Paper_ID="/157215.html" Extracted="364200430X" />

<identifier Org="ISBN:3790813486" Paper_ID="/157215.html" Extracted="3790813486" DDC="794.8/151" Normalized_DDC="7948151" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:902724992X" Paper_ID="/157215.html" Extracted="902724992X" DDC="006.3/5" Normalized_DDC="00635" Normalized_Weight="0.06666666666666667" />

</rec>

<rec ID="/10179.html" Type="article" CiteSeer_Book="Artificial Intelligence" CiteSeer_Volume="109" Title="Using Regression-Match Graphs to Control Search in Planning,">

<identifier Org="ISBN:1577351878" Paper_ID="/10179.html" Extracted="1577351878" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:157735236X" Paper_ID="/10179.html" Extracted="157735236X" />

<identifier Org="ISBN:1586036424" Paper_ID="/10179.html" Extracted="1586036424" />

<identifier Org="ISBN:3540205454" Paper_ID="/10179.html" Extracted="3540205454" DDC="794.8/1416" Normalized_DDC="79481416" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:3540428984" Paper_ID="/10179.html" Extracted="3540428984" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:354043321X" Paper_ID="/10179.html" Extracted="354043321X" DDC="004.1/9" Normalized_DDC="00419" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:3540749691" Paper_ID="/10179.html" Extracted="3540749691" DDC="005.1/16" Normalized_DDC="005116" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:3540777229" Paper_ID="/10179.html" Extracted="3540777229" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:3540892869" Paper_ID="/10179.html" Extracted="3540892869" />

</rec>

<rec ID="SELF" Type="SELF" CiteSeer_Book="SELF" CiteSeer_Volume="SELF" Title="Domain-Dependent Single-Agent Search Enhancements">

<identifier Org="ISBN:0262511290" Paper_ID="SELF" Extracted="0262511290" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:0262560976" Paper_ID="SELF" Extracted="0262560976" DDC="001.4/225/028563" Normalized_DDC="0014225028563" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:0444509496" Paper_ID="SELF" Extracted="0444509496" DDC="794.8/1526" Normalized_DDC="79481526" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:1577351878" Paper_ID="SELF" Extracted="1577351878" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:3540205454" Paper_ID="SELF" Extracted="3540205454" DDC="794.8/1416" Normalized_DDC="79481416" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:3540430806" Paper_ID="SELF" Extracted="3540430806" DDC="794.81" Normalized_DDC="79481" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:3540675574" Paper_ID="SELF" Extracted="3540675574" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:3540678662" Paper_ID="SELF" Extracted="3540678662" DDC="006.3/33" Normalized_DDC="006333" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:3790815233" Paper_ID="SELF" Extracted="3790815233" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1111111111111111" />

</rec>

</references_metadata>