PSVN: A Vector Representation for Production Systems
- Istvan Hernadvolgyi, School of Information Technology and Engineering, University of Ottawa
- Robert Holte, Department of Computing Science, University of Alberta
In this paper we present a production system
which acts on fixed length vectors of labels. Our
goal is to automatically generate heuristics to
search the state space for shortest paths between
states efficiently. The heuristic values which guide
search in the state space are obtained by searching
for the shortest path in an abstract space derived
from the definition of the original space. In PSVN, a
state is a fixed length vector of labels and abstrac
tions are generated by simply mapping the set
of labels to another smaller set of labels (domain
abstraction). A domain abstraction on labels in
duces a state space abstraction and this abstract
space preserves important properties of the origi
nal space while usually being significantly smaller
in size. It is guaranteed that the shortest path
between two states in the original space is at least
as long as the shortest path between their images
in the abstract space. Hence, such abstractions
provide admissible heuristics for search algorithms
such as A* and IDA*. The mapping of states and
operators can be efficiently obtained by applying
the domain map on the labels. We explore im
portant properties of state spaces defined in PSVN
and abstractions generated by domain maps. De
spite its simplicity, PSVN is capable to define all
finitely generated permutation groups and such
benchmark problems as Rubik's Cube, the sliding
tile puzzles and the Blocks World.
Citation
I. Hernadvolgyi,
R. Holte.
"PSVN: A Vector Representation for Production Systems". Technical Report, May 2004.
| Keywords: |
PSVN |
| Category: |
Technical Report |
BibTeX
@manual{Hernadvolgyi+Holte:04,
author = {Istvan Hernadvolgyi and Robert Holte},
title = {PSVN: A Vector Representation for Production Systems},
year = 2004,
}Last Updated: March 14, 2007
Submitted by AICML Admin Assistant 
