Serveur d'exploration sur les relations entre la France et l'Australie

Attention, ce site est en cours de développement !
Attention, site généré par des moyens informatiques à partir de corpus bruts.
Les informations ne sont donc pas validées.

Blocks World revisited

Identifieur interne : 002765 ( Istex/Curation ); précédent : 002764; suivant : 002766

Blocks World revisited

Auteurs : John Slaney [Australie, France] ; Sylvie Thiébaux [Australie, France]

Source :

RBID : ISTEX:D4400B8835AF3B3EA44CC7BBFE20F4BF2EDD8CA4

English descriptors

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...)


Links to Exploration step

ISTEX:D4400B8835AF3B3EA44CC7BBFE20F4BF2EDD8CA4

Le 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
}}

Wicri

This area was generated with Dilib version V0.6.33.
Data generation: Tue Dec 5 10:43:12 2017. Site generation: Tue Mar 5 14:07:20 2024