Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

Utilizing automatically inferred invariants in graph construction and search

Fox, M. and Long, D. (2000) Utilizing automatically inferred invariants in graph construction and search. In: Proceedings of AIPS 2000, 2000-04-14 - 2000-04-17, Breckenridge, USA.

[img]
Preview
PDF (strathprints001939.pdf)
Download (188Kb) | Preview

    Abstract

    In this paper we explore the relative importance of persistent and non-persistent mutex relations in the performance of Graphplan- based planners. We also show the advantages of pre-compiling persistent mutex relations. Using TIM we are able to generate, during a pre-processing analysis, all of the persistent binary mutex relations that would be inferred by Graphplan during each graph construction. We show how the efficient storgae of, and access to, these pre-processed persistent mutexes yields a modest improvement in graph construction performance. We further demonstrate that the process by which these persistent mutexes are identified can, in certain kinds of domain, allow the exploitation of binary mutex relations which are inaccessible to Graphplan. We present The Island of Sodor, a simple planning domain characterizing a class of domains in which certain persistent mutexes are present but are not detectable by Graphplan during graph construction. We show that the exploitation of these hidden binary mutexes makes problems in this kind of domain trivially solvable by STAN, where they are intractable for other Graphplan-based planners.

    Item type: Conference or Workshop Item (Paper)
    ID code: 1939
    Keywords: graph construction, mutex relations, graphplan, STAN, Electronic computers. Computer science
    Subjects: Science > Mathematics > Electronic computers. Computer science
    Department: Faculty of Science > Computer and Information Sciences
    Related URLs:
      Depositing user: Professor Maria Fox
      Date Deposited: 30 Oct 2006
      Last modified: 06 Oct 2012 07:09
      URI: http://strathprints.strath.ac.uk/id/eprint/1939

      Actions (login required)

      View Item

      Fulltext Downloads: