Blocks World revisited
Identifieur interne : 002765 ( Istex/Curation ); précédent : 002764; suivant : 002766Blocks World revisited
Auteurs : John Slaney [Australie, France] ; Sylvie Thiébaux [Australie, France]Source :
- Artificial Intelligence [ 0004-3702 ] ; 2001.
English descriptors
- KwdEn :
- Additional actions, Additional variables, Algorithm, Approximation algorithms, Average case, Average length, Average number, Average performance, Average performance ratios, Average plan length, Average plan quality, Average problem, Average runtimes, Backtracking search, Benchmark, Benchmark instances, Block, Blocks World, Blocks world, Blocks world planning, Chaining planner, Clear block, Clear blocks, Complexity results, Concierge, Consequent failure, Constant number, Constant time, Constructive move, Constructive moves, Current state, Deadlock, Decision procedure, Easy instances, Elsevier science, Empty table, Equal probability, Experimental results, Extra block, Goal state, Goal states, Goal tower, Gure, Hard instances, Hard problems, Hard region, Hardness, Initial state, Laguerre polynomial, Last block, Last move, Limited capacity, Linear time, Little difference, Many blocks, Meaningful distributions, Median hardness, Minimal size, More variables, Nding, Optimal algorithm, Optimal plan, Optimal plan length, Optimal plan lengths, Optimal planning, Optimal plans, Optimal solver, Optimally, Optimisation problems, Other hand, Other towers, Other ungrounded towers, Performance ratio, Plan length, Plan quality, Planner, Planner performance, Planning algorithms, Planning benchmarks, Planning methods, Planning problem, Planning problems, Planning systems, Possible extensions, Present paper, Problem instances, Proc, Quadratic time, Random instances, Random problems, Random states, Random/hard problems, Reasoning project, Reference point, Same experiment, Search control rules, Selman, Short plans, Shorter plan, Simple expression, Single block, Singleton, Singleton deadlocks, Slaney, Solution quality, Suitable testbed, Systematic experimentation, Systematic experiments, Technical report, Temporal logic, Time complexity, Time performances, Tower, Tractable, Transitive closure, Ungrounded, Ungrounded ones, Ungrounded tower, Ungrounded towers, Uniform distribution, Worst case.
- Teeft :
- Additional actions, Additional variables, Algorithm, Average case, Average length, Average number, Average performance, Average performance ratios, Average plan length, Average plan quality, Average problem, Average runtimes, Backtracking search, Benchmark, Benchmark instances, Block, Blocks world, Blocks world planning, Chaining planner, Clear block, Clear blocks, Complexity results, Concierge, Consequent failure, Constant number, Constant time, Constructive move, Constructive moves, Current state, Deadlock, Decision procedure, Easy instances, Elsevier science, Empty table, Equal probability, Experimental results, Extra block, Goal state, Goal states, Goal tower, Gure, Hard instances, Hard problems, Hard region, Hardness, Initial state, Laguerre polynomial, Last block, Last move, Limited capacity, Linear time, Little difference, Many blocks, Meaningful distributions, Median hardness, Minimal size, More variables, Nding, Optimal algorithm, Optimal plan, Optimal plan length, Optimal plan lengths, Optimal planning, Optimal plans, Optimal solver, Optimally, Optimisation problems, Other hand, Other towers, Other ungrounded towers, Performance ratio, Plan length, Plan quality, Planner, Planner performance, Planning algorithms, Planning methods, Planning problem, Planning problems, Planning systems, Possible extensions, Present paper, Problem instances, Proc, Quadratic time, Random instances, Random problems, Random states, Reasoning project, Reference point, Same experiment, Search control rules, Selman, Short plans, Shorter plan, Simple expression, Single block, Singleton, Singleton deadlocks, Slaney, Solution quality, Suitable testbed, Systematic experimentation, Systematic experiments, Technical report, Temporal logic, Time complexity, Time performances, Tower, Tractable, Transitive closure, Ungrounded, Ungrounded ones, Ungrounded tower, Ungrounded towers, Uniform distribution, Worst case.
Abstract
Abstract: Contemporary AI shows a healthy trend away from artificial problems towards real-world applications. Less healthy, however, is the fashionable disparagement of “toy” domains: when properly approached, these domains can at the very least support meaningful systematic experiments, and allow features relevant to many kinds of reasoning to be abstracted and studied. A major reason why they have fallen into disrepute is that superficial understanding of them has resulted in poor experimental methodology and consequent failure to extract useful information. This paper presents a sustained investigation of one such toy: the (in)famous Blocks World planning problem, and provides the level of understanding required for its effective use as a benchmark. Our results include methods for generating random problems for systematic experimentation, the best domain-specific planning algorithms against which AI planners can be compared, and observations establishing the average plan quality of near-optimal methods. We also study the distribution of hard/easy instances, and identify the structure that AI planners must be able to exploit in order to approach Blocks World successfully.
Url:
DOI: 10.1016/S0004-3702(00)00079-5
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :002765
Links to Exploration step
ISTEX:D4400B8835AF3B3EA44CC7BBFE20F4BF2EDD8CA4Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Blocks World revisited</title>
<author><name sortKey="Slaney, John" sort="Slaney, John" uniqKey="Slaney J" first="John" last="Slaney">John Slaney</name>
<affiliation wicri:level="1"><mods:affiliation>Computer Sciences Lab, Australian National University, Canberra, Australia</mods:affiliation>
<country xml:lang="fr">Australie</country>
<wicri:regionArea>Computer Sciences Lab, Australian National University, Canberra</wicri:regionArea>
</affiliation>
<affiliation><mods:affiliation>Corresponding author.</mods:affiliation>
<wicri:noCountry code="no comma">Corresponding author.</wicri:noCountry>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>1Some of this work was done while the author was visiting IMAG (Grenoble, France).</mods:affiliation>
<country xml:lang="fr" wicri:curation="lc">France</country>
<wicri:regionArea>1Some of this work was done while the author was visiting IMAG (Grenoble</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: John.Slaney@arp.anu.edu.au</mods:affiliation>
<country wicri:rule="url">Australie</country>
</affiliation>
</author>
<author><name sortKey="Thiebaux, Sylvie" sort="Thiebaux, Sylvie" uniqKey="Thiebaux S" first="Sylvie" last="Thiébaux">Sylvie Thiébaux</name>
<affiliation wicri:level="1"><mods:affiliation>CSIRO Mathematical & Information Sciences, PO Box 664, Canberra, Australia</mods:affiliation>
<country xml:lang="fr">Australie</country>
<wicri:regionArea>CSIRO Mathematical & Information Sciences, PO Box 664, Canberra</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>2This work was partly done while the author was at IRISA (Rennes, France).</mods:affiliation>
<country xml:lang="fr" wicri:curation="lc">France</country>
<wicri:regionArea>2This work was partly done while the author was at IRISA (Rennes</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: Sylvie.Thiebaux@cmis.csiro.au</mods:affiliation>
<country wicri:rule="url">Australie</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:D4400B8835AF3B3EA44CC7BBFE20F4BF2EDD8CA4</idno>
<date when="2001" year="2001">2001</date>
<idno type="doi">10.1016/S0004-3702(00)00079-5</idno>
<idno type="url">https://api.istex.fr/document/D4400B8835AF3B3EA44CC7BBFE20F4BF2EDD8CA4/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">002765</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002765</idno>
<idno type="wicri:Area/Istex/Curation">002765</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Blocks World revisited</title>
<author><name sortKey="Slaney, John" sort="Slaney, John" uniqKey="Slaney J" first="John" last="Slaney">John Slaney</name>
<affiliation wicri:level="1"><mods:affiliation>Computer Sciences Lab, Australian National University, Canberra, Australia</mods:affiliation>
<country xml:lang="fr">Australie</country>
<wicri:regionArea>Computer Sciences Lab, Australian National University, Canberra</wicri:regionArea>
</affiliation>
<affiliation><mods:affiliation>Corresponding author.</mods:affiliation>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>1Some of this work was done while the author was visiting IMAG (Grenoble, France).</mods:affiliation>
<country xml:lang="fr" wicri:curation="lc">France</country>
<wicri:regionArea>1Some of this work was done while the author was visiting IMAG (Grenoble</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: John.Slaney@arp.anu.edu.au</mods:affiliation>
<country wicri:rule="url">Australie</country>
</affiliation>
</author>
<author><name sortKey="Thiebaux, Sylvie" sort="Thiebaux, Sylvie" uniqKey="Thiebaux S" first="Sylvie" last="Thiébaux">Sylvie Thiébaux</name>
<affiliation wicri:level="1"><mods:affiliation>CSIRO Mathematical & Information Sciences, PO Box 664, Canberra, Australia</mods:affiliation>
<country xml:lang="fr">Australie</country>
<wicri:regionArea>CSIRO Mathematical & Information Sciences, PO Box 664, Canberra</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>2This work was partly done while the author was at IRISA (Rennes, France).</mods:affiliation>
<country xml:lang="fr" wicri:curation="lc">France</country>
<wicri:regionArea>2This work was partly done while the author was at IRISA (Rennes</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: Sylvie.Thiebaux@cmis.csiro.au</mods:affiliation>
<country wicri:rule="url">Australie</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="j">Artificial Intelligence</title>
<title level="j" type="abbrev">ARTINT</title>
<idno type="ISSN">0004-3702</idno>
<imprint><publisher>ELSEVIER</publisher>
<date type="published" when="2001">2001</date>
<biblScope unit="volume">125</biblScope>
<biblScope unit="issue">1–2</biblScope>
<biblScope unit="page" from="119">119</biblScope>
<biblScope unit="page" to="153">153</biblScope>
</imprint>
<idno type="ISSN">0004-3702</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0004-3702</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Additional actions</term>
<term>Additional variables</term>
<term>Algorithm</term>
<term>Approximation algorithms</term>
<term>Average case</term>
<term>Average length</term>
<term>Average number</term>
<term>Average performance</term>
<term>Average performance ratios</term>
<term>Average plan length</term>
<term>Average plan quality</term>
<term>Average problem</term>
<term>Average runtimes</term>
<term>Backtracking search</term>
<term>Benchmark</term>
<term>Benchmark instances</term>
<term>Block</term>
<term>Blocks World</term>
<term>Blocks world</term>
<term>Blocks world planning</term>
<term>Chaining planner</term>
<term>Clear block</term>
<term>Clear blocks</term>
<term>Complexity results</term>
<term>Concierge</term>
<term>Consequent failure</term>
<term>Constant number</term>
<term>Constant time</term>
<term>Constructive move</term>
<term>Constructive moves</term>
<term>Current state</term>
<term>Deadlock</term>
<term>Decision procedure</term>
<term>Easy instances</term>
<term>Elsevier science</term>
<term>Empty table</term>
<term>Equal probability</term>
<term>Experimental results</term>
<term>Extra block</term>
<term>Goal state</term>
<term>Goal states</term>
<term>Goal tower</term>
<term>Gure</term>
<term>Hard instances</term>
<term>Hard problems</term>
<term>Hard region</term>
<term>Hardness</term>
<term>Initial state</term>
<term>Laguerre polynomial</term>
<term>Last block</term>
<term>Last move</term>
<term>Limited capacity</term>
<term>Linear time</term>
<term>Little difference</term>
<term>Many blocks</term>
<term>Meaningful distributions</term>
<term>Median hardness</term>
<term>Minimal size</term>
<term>More variables</term>
<term>Nding</term>
<term>Optimal algorithm</term>
<term>Optimal plan</term>
<term>Optimal plan length</term>
<term>Optimal plan lengths</term>
<term>Optimal planning</term>
<term>Optimal plans</term>
<term>Optimal solver</term>
<term>Optimally</term>
<term>Optimisation problems</term>
<term>Other hand</term>
<term>Other towers</term>
<term>Other ungrounded towers</term>
<term>Performance ratio</term>
<term>Plan length</term>
<term>Plan quality</term>
<term>Planner</term>
<term>Planner performance</term>
<term>Planning algorithms</term>
<term>Planning benchmarks</term>
<term>Planning methods</term>
<term>Planning problem</term>
<term>Planning problems</term>
<term>Planning systems</term>
<term>Possible extensions</term>
<term>Present paper</term>
<term>Problem instances</term>
<term>Proc</term>
<term>Quadratic time</term>
<term>Random instances</term>
<term>Random problems</term>
<term>Random states</term>
<term>Random/hard problems</term>
<term>Reasoning project</term>
<term>Reference point</term>
<term>Same experiment</term>
<term>Search control rules</term>
<term>Selman</term>
<term>Short plans</term>
<term>Shorter plan</term>
<term>Simple expression</term>
<term>Single block</term>
<term>Singleton</term>
<term>Singleton deadlocks</term>
<term>Slaney</term>
<term>Solution quality</term>
<term>Suitable testbed</term>
<term>Systematic experimentation</term>
<term>Systematic experiments</term>
<term>Technical report</term>
<term>Temporal logic</term>
<term>Time complexity</term>
<term>Time performances</term>
<term>Tower</term>
<term>Tractable</term>
<term>Transitive closure</term>
<term>Ungrounded</term>
<term>Ungrounded ones</term>
<term>Ungrounded tower</term>
<term>Ungrounded towers</term>
<term>Uniform distribution</term>
<term>Worst case</term>
</keywords>
<keywords scheme="Teeft" xml:lang="en"><term>Additional actions</term>
<term>Additional variables</term>
<term>Algorithm</term>
<term>Average case</term>
<term>Average length</term>
<term>Average number</term>
<term>Average performance</term>
<term>Average performance ratios</term>
<term>Average plan length</term>
<term>Average plan quality</term>
<term>Average problem</term>
<term>Average runtimes</term>
<term>Backtracking search</term>
<term>Benchmark</term>
<term>Benchmark instances</term>
<term>Block</term>
<term>Blocks world</term>
<term>Blocks world planning</term>
<term>Chaining planner</term>
<term>Clear block</term>
<term>Clear blocks</term>
<term>Complexity results</term>
<term>Concierge</term>
<term>Consequent failure</term>
<term>Constant number</term>
<term>Constant time</term>
<term>Constructive move</term>
<term>Constructive moves</term>
<term>Current state</term>
<term>Deadlock</term>
<term>Decision procedure</term>
<term>Easy instances</term>
<term>Elsevier science</term>
<term>Empty table</term>
<term>Equal probability</term>
<term>Experimental results</term>
<term>Extra block</term>
<term>Goal state</term>
<term>Goal states</term>
<term>Goal tower</term>
<term>Gure</term>
<term>Hard instances</term>
<term>Hard problems</term>
<term>Hard region</term>
<term>Hardness</term>
<term>Initial state</term>
<term>Laguerre polynomial</term>
<term>Last block</term>
<term>Last move</term>
<term>Limited capacity</term>
<term>Linear time</term>
<term>Little difference</term>
<term>Many blocks</term>
<term>Meaningful distributions</term>
<term>Median hardness</term>
<term>Minimal size</term>
<term>More variables</term>
<term>Nding</term>
<term>Optimal algorithm</term>
<term>Optimal plan</term>
<term>Optimal plan length</term>
<term>Optimal plan lengths</term>
<term>Optimal planning</term>
<term>Optimal plans</term>
<term>Optimal solver</term>
<term>Optimally</term>
<term>Optimisation problems</term>
<term>Other hand</term>
<term>Other towers</term>
<term>Other ungrounded towers</term>
<term>Performance ratio</term>
<term>Plan length</term>
<term>Plan quality</term>
<term>Planner</term>
<term>Planner performance</term>
<term>Planning algorithms</term>
<term>Planning methods</term>
<term>Planning problem</term>
<term>Planning problems</term>
<term>Planning systems</term>
<term>Possible extensions</term>
<term>Present paper</term>
<term>Problem instances</term>
<term>Proc</term>
<term>Quadratic time</term>
<term>Random instances</term>
<term>Random problems</term>
<term>Random states</term>
<term>Reasoning project</term>
<term>Reference point</term>
<term>Same experiment</term>
<term>Search control rules</term>
<term>Selman</term>
<term>Short plans</term>
<term>Shorter plan</term>
<term>Simple expression</term>
<term>Single block</term>
<term>Singleton</term>
<term>Singleton deadlocks</term>
<term>Slaney</term>
<term>Solution quality</term>
<term>Suitable testbed</term>
<term>Systematic experimentation</term>
<term>Systematic experiments</term>
<term>Technical report</term>
<term>Temporal logic</term>
<term>Time complexity</term>
<term>Time performances</term>
<term>Tower</term>
<term>Tractable</term>
<term>Transitive closure</term>
<term>Ungrounded</term>
<term>Ungrounded ones</term>
<term>Ungrounded tower</term>
<term>Ungrounded towers</term>
<term>Uniform distribution</term>
<term>Worst case</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: Contemporary AI shows a healthy trend away from artificial problems towards real-world applications. Less healthy, however, is the fashionable disparagement of “toy” domains: when properly approached, these domains can at the very least support meaningful systematic experiments, and allow features relevant to many kinds of reasoning to be abstracted and studied. A major reason why they have fallen into disrepute is that superficial understanding of them has resulted in poor experimental methodology and consequent failure to extract useful information. This paper presents a sustained investigation of one such toy: the (in)famous Blocks World planning problem, and provides the level of understanding required for its effective use as a benchmark. Our results include methods for generating random problems for systematic experimentation, the best domain-specific planning algorithms against which AI planners can be compared, and observations establishing the average plan quality of near-optimal methods. We also study the distribution of hard/easy instances, and identify the structure that AI planners must be able to exploit in order to approach Blocks World successfully.</div>
</front>
</TEI>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002765 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 002765 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Asie |area= AustralieFrV1 |flux= Istex |étape= Curation |type= RBID |clé= ISTEX:D4400B8835AF3B3EA44CC7BBFE20F4BF2EDD8CA4 |texte= Blocks World revisited }}
This area was generated with Dilib version V0.6.33. |