OBDDs in heuristic search
Identifieur interne : 002291 ( Main/Exploration ); précédent : 002290; suivant : 002292OBDDs in heuristic search
Auteurs : Stefan Edelkamp [Allemagne] ; Frank Reffel [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1998.
Abstract
Abstract: The use of a lower bound estimate in the search has a tremendous impact on the size of the resulting search trees, whereas OBDDs can be used to efficiently describe sets of states based on their binary encoding. This paper combines these two ideas into a new algorithm BDDA *. It challenges both the breadth-first search using OBDDs and the traditional A * algorithm. The problem with A * is that in many application areas the set of states is too huge to be kept in main memory. In contrast, brute-force breadth-first search using OBDDs unnecessarily expands several nodes. Therefore, we exhibit a new trade-off between time and space requirements and tackle the most important problem in heuristic search, the overcoming of space limitations while avoiding a strong penalty in time. We evaluate our approach in the (n 2−1)-Puzzle and within Sokoban.
Url:
DOI: 10.1007/BFb0095430
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001442
- to stream Istex, to step Curation: 001330
- to stream Istex, to step Checkpoint: 000E62
- to stream Main, to step Merge: 002680
- to stream Main, to step Curation: 002291
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">OBDDs in heuristic search</title><author><name sortKey="Edelkamp, Stefan" sort="Edelkamp, Stefan" uniqKey="Edelkamp S" first="Stefan" last="Edelkamp">Stefan Edelkamp</name></author><author><name sortKey="Reffel, Frank" sort="Reffel, Frank" uniqKey="Reffel F" first="Frank" last="Reffel">Frank Reffel</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:1D6E07892F9322EF7C9485DF09E0C3A97F8F4C7C</idno><date when="1998" year="1998">1998</date><idno type="doi">10.1007/BFb0095430</idno><idno type="url">https://api.istex.fr/document/1D6E07892F9322EF7C9485DF09E0C3A97F8F4C7C/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001442</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001442</idno><idno type="wicri:Area/Istex/Curation">001330</idno><idno type="wicri:Area/Istex/Checkpoint">000E62</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000E62</idno><idno type="wicri:doubleKey">0302-9743:1998:Edelkamp S:obdds:in:heuristic</idno><idno type="wicri:Area/Main/Merge">002680</idno><idno type="wicri:Area/Main/Curation">002291</idno><idno type="wicri:Area/Main/Exploration">002291</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">OBDDs in heuristic search</title><author><name sortKey="Edelkamp, Stefan" sort="Edelkamp, Stefan" uniqKey="Edelkamp S" first="Stefan" last="Edelkamp">Stefan Edelkamp</name><affiliation></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Reffel, Frank" sort="Reffel, Frank" uniqKey="Reffel F" first="Frank" last="Reffel">Frank Reffel</name><affiliation wicri:level="3"><country>Allemagne</country><placeName><settlement type="city">Karlsruhe</settlement><region type="land" nuts="1">Bade-Wurtemberg</region><region type="district" nuts="2">District de Karlsruhe</region></placeName><wicri:orgArea>Institut für Logik, Komplexität und Deduktionssysteme, Universität Karlsruhe, Am Fasanengarten 5, D-76128</wicri:orgArea></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><title level="s" type="sub">Lecture Notes in Artificial Intelligence</title><imprint><date>1998</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">1D6E07892F9322EF7C9485DF09E0C3A97F8F4C7C</idno><idno type="DOI">10.1007/BFb0095430</idno><idno type="ChapterID">8</idno><idno type="ChapterID">Chap8</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: The use of a lower bound estimate in the search has a tremendous impact on the size of the resulting search trees, whereas OBDDs can be used to efficiently describe sets of states based on their binary encoding. This paper combines these two ideas into a new algorithm BDDA *. It challenges both the breadth-first search using OBDDs and the traditional A * algorithm. The problem with A * is that in many application areas the set of states is too huge to be kept in main memory. In contrast, brute-force breadth-first search using OBDDs unnecessarily expands several nodes. Therefore, we exhibit a new trade-off between time and space requirements and tackle the most important problem in heuristic search, the overcoming of space limitations while avoiding a strong penalty in time. We evaluate our approach in the (n 2−1)-Puzzle and within Sokoban.</div></front></TEI><affiliations><list><country><li>Allemagne</li></country><region><li>Bade-Wurtemberg</li><li>District de Karlsruhe</li></region><settlement><li>Karlsruhe</li></settlement></list><tree><country name="Allemagne"><noRegion><name sortKey="Edelkamp, Stefan" sort="Edelkamp, Stefan" uniqKey="Edelkamp S" first="Stefan" last="Edelkamp">Stefan Edelkamp</name></noRegion><name sortKey="Reffel, Frank" sort="Reffel, Frank" uniqKey="Reffel F" first="Frank" last="Reffel">Frank Reffel</name><name sortKey="Reffel, Frank" sort="Reffel, Frank" uniqKey="Reffel F" first="Frank" last="Reffel">Frank Reffel</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002291 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002291 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:1D6E07892F9322EF7C9485DF09E0C3A97F8F4C7C
|texte= OBDDs in heuristic search
}}
| This area was generated with Dilib version V0.6.31. |  |