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>

www.000webhost.com