Utilizing automatically inferred invariants in graph construction and search

Maria Fox, Derek Long

Research output: Contribution to conferencePaper

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.

Conference

Conference5th International Conference on Artificial Intelligence Planning Systems
Abbreviated titleAIPS 2000
CountryUnited States
CityBreckenridge, CO
Period14/04/0017/04/00

Fingerprint

Planning
Processing

Keywords

  • graph construction
  • mutex relations
  • graphplan
  • STAN

Cite this

Fox, M., & Long, D. (2000). Utilizing automatically inferred invariants in graph construction and search. 102-111. Paper presented at 5th International Conference on Artificial Intelligence Planning Systems, Breckenridge, CO, United States.
Fox, Maria ; Long, Derek. / Utilizing automatically inferred invariants in graph construction and search. Paper presented at 5th International Conference on Artificial Intelligence Planning Systems, Breckenridge, CO, United States.9 p.
@conference{117bfc979e8f41f5b0182c5fcec099e6,
title = "Utilizing automatically inferred invariants in graph construction and search",
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.",
keywords = "graph construction, mutex relations, graphplan, STAN",
author = "Maria Fox and Derek Long",
year = "2000",
month = "4",
language = "English",
pages = "102--111",
note = "5th International Conference on Artificial Intelligence Planning Systems, AIPS 2000 ; Conference date: 14-04-2000 Through 17-04-2000",

}

Fox, M & Long, D 2000, 'Utilizing automatically inferred invariants in graph construction and search' Paper presented at 5th International Conference on Artificial Intelligence Planning Systems, Breckenridge, CO, United States, 14/04/00 - 17/04/00, pp. 102-111.

Utilizing automatically inferred invariants in graph construction and search. / Fox, Maria; Long, Derek.

2000. 102-111 Paper presented at 5th International Conference on Artificial Intelligence Planning Systems, Breckenridge, CO, United States.

Research output: Contribution to conferencePaper

TY - CONF

T1 - Utilizing automatically inferred invariants in graph construction and search

AU - Fox, Maria

AU - Long, Derek

PY - 2000/4

Y1 - 2000/4

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

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

KW - graph construction

KW - mutex relations

KW - graphplan

KW - STAN

UR - http://www.aaai.org/Library/AIPS/2000/aips00-011.php

M3 - Paper

SP - 102

EP - 111

ER -

Fox M, Long D. Utilizing automatically inferred invariants in graph construction and search. 2000. Paper presented at 5th International Conference on Artificial Intelligence Planning Systems, Breckenridge, CO, United States.