Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
From Macro Plans to Automata Plans
View through CrossRef
Macros have a long-standing role in planning as a tool for representing repeating subsequences of operators. Macros are useful both for guiding search towards a solution and for representing plans compactly. In this paper we introduce automata plans which consist of hierarchies of finite state automata. Automata plans can be viewed as an extension of macros that enables parametrization and branching. We provide several examples of the utility of automata plans, and prove that automata plans are strictly more expressive than macro plans. We also prove that automata plans admit polynomialtime sequential access of the operators in the underlying “flat” plan, and identify a subset of automata plans that admit polynomial-time random access. Finally, we compare automata plans with other representations allowing polynomial-time sequential access.
Title: From Macro Plans to Automata Plans
Description:
Macros have a long-standing role in planning as a tool for representing repeating subsequences of operators.
Macros are useful both for guiding search towards a solution and for representing plans compactly.
In this paper we introduce automata plans which consist of hierarchies of finite state automata.
Automata plans can be viewed as an extension of macros that enables parametrization and branching.
We provide several examples of the utility of automata plans, and prove that automata plans are strictly more expressive than macro plans.
We also prove that automata plans admit polynomialtime sequential access of the operators in the underlying “flat” plan, and identify a subset of automata plans that admit polynomial-time random access.
Finally, we compare automata plans with other representations allowing polynomial-time sequential access.
Related Results
Simulations for Event-Clock Automata
Simulations for Event-Clock Automata
Event-clock automata (ECA) are a well-known semantic subclass of timed
automata (TA) which enjoy admirable theoretical properties, e.g.,
determinizability, and are practically usef...
A Unified Model for Real-Time Systems: Symbolic Techniques and Implementation
A Unified Model for Real-Time Systems: Symbolic Techniques and Implementation
AbstractIn this paper, we consider a model of generalized timed automata (GTA) with two kinds of clocks, history and future, that can express many timed features succinctly, includ...
Permutation Groups in Automata Diagrams
Permutation Groups in Automata Diagrams
Automata act as classical models for recognition devices. From the previous researches, the classical models of automata have been used to scan strings and to determine the types o...
FUZZY‐FUZZY AUTOMATA
FUZZY‐FUZZY AUTOMATA
Based on the concept of fuzzy sets of type 2 (or fuzzy‐fuzzy sets) defined by L. A. Zadeh, fuzzy‐fuzzy automata ate newly formulated and some properties of these automata are inves...
Minimisation and Language Inclusion for Separating B\"uchi and Parity Automata
Minimisation and Language Inclusion for Separating B\"uchi and Parity Automata
We provide simple proofs of the NC results for the universality, language inclusion, and equivalence problems of unambiguous finite automata, based on recent advances in model chec...
On Computational Power of Partially Blind Automata
On Computational Power of Partially Blind Automata
On Computational Power of Partially Blind Automata
In this paper we deal with 1-way multihead finite automata, in which the symbol under only one head (called read head) co...
A Robust Class of Data Languages and an Application to Learning
A Robust Class of Data Languages and an Application to Learning
We introduce session automata, an automata model to process data words, i.e.,
words over an infinite alphabet. Session automata support the notion of fresh
data values, which are w...
Freezing, Bounded-Change and Convergent Cellular Automata
Freezing, Bounded-Change and Convergent Cellular Automata
This paper studies three classes of cellular automata from a computational point of view: freezing cellular automata where the state of a cell can only decrease according to some o...