-We think that run-time models are a minimum necessity for significant self-awareness in Computationally Reflective systems. For us, a Computationally Reflective system is not only “self-aware” (it can collect information about its own behavior and that of its environment), but also “self-adaptive” (it can reason about that behavior and make adjustments that change it). Moreover, when the system is also “self-modeling”, that is, defined by the models it creates and maintains, then it can modify those models to better align its behavior with changes in its operating environment. In this paper, we show that building and managing these models presents some difficulties that are largely independent of the modeling mechanisms used. We also provide some mechanisms for coping with these difficulties, from a kind of “Behavior Mining” and “Model Deficiency Analysis” for current models to “Dynamic Knowledge Management”, of which major components are “Knowledge Refactoring” and “Constructive Forgetting”. None of these methods eliminate the problem, but each alleviates some of the difficult aspects of the problem, which allows bigger and more complex systems to exist in more complex and diverse environment for longer periods of time.
I. INTRODUCTION
We argue that run-time models are a minimum necessity
for significant and effective self-awareness in Computationally
Reflective systems. A Computationally Reflective system [
A Computationally Reflective system can collect information about its own structure and behavior, and it can also examine that information to decide how to modify the behavior, retain and analyze it over extended time periods, adjust its decision processes to “optimize” it towards selected success criteria, and even change the success criteria to respond to changes detected in the environment (which may also include newly imposed purposes or goals).
In this paper, we explore some seemingly far-fetched theoretical notions, show that they are eminently likely in selfmodeling systems, and provide some suggestions for alleviating their effects.
Self-modeling systems [
Because these models are intended to be interpreted by
the system, the common “4+1” view [
The questions then become: how does a system learn about its own structure and behavior? make decisions about its own structure and behavior? decide on changes to its own structure and behavior? record and use the decisions and their consequences over time?
For us, all of these are about models or involve or require models. The corresponding engineering design problems are: how extensive these reflective mechanisms need to be for a given application, how much we want the system itself to construct and modify the models, and how much of the system behavior is to be driven by the models.
Models cost time for development and execution, which makes this set of engineering problems central to the success of self-adaptive systems in complex environments. If we make this extensive use of models, we are brought to the notion of using the models to define the behavior.
These are self-modeling systems.
In our prior work on self-modeling systems, we have identified two fundamental representational issues that must be addressed by any self-aware system of this kind: 1) the need for identifying repeated patterns and inventing new symbols for them, to reduce the computational load; 2) the need for occasionally re-inventing the representational mechanism itself, to avoid the inevitable increase in rigidity in a complex knowledge-intensive system.
These are both issues of Computational Semiotics [
These theorems are not insurmountable, but they do pose a serious design consideration. In addition, it can be seen that they are inevitable in any systems that build increasingly finegrained models. That means that they are not unlikely; they must be addressed.
Helpfully, there are several processes that can be used to alleviate their effects to some extent. We think that these helpful processes are necessary in any case for a self-modeling system to operate in a complex environment for any non-trivial amount of time.
“Behavior Mining” is the process of recording and analyzing the system’s own behavior to make descriptive or prescriptive models.
“Model Deficiency Analysis” is the process of evaluating the effectiveness of a model (not just success and failure, but also performance, resource implications, and interference with other models), and analyzing where improvements can be made.
“Knowledge Refactoring” is the process of rearranging the hierarchical knowledge structures (e.g., ontologies) to reduce dependencies, duplication and unused elements.
“Constructive Forgetting” is the process of simplifying knowledge structures by conflating and even removing some terms and relationships.
Each of these will be discussed in the rest of the paper.
None of these methods entirely avoids the problems presented by the theorems, of course; the theorems are still true. They do, however, push the bounds farther out, which allows bigger and more complex systems to exist in more complex and diverse environments for longer periods of time. perform
actions of make
observations
The rest of this paper is organized as follows. In the next Section II, we describe more of the structure of self-modeling systems.
In Section III, we describe our own approach to constructing self-modeling systems, using activity loops driven by knowledge bases.
In Section IV, we describe some fundamental results from Computational Semiotics that have relevance to model building at run time.
In Section V, we show how some partial approaches can alleviate the problem of getting stuck, and finally, in Section VI, we describe some conclusions and prospects for further development.
Our goal is to design and build systems that are able to operate in hazardous or remote environments that cannot be completely known. The assumption is that they are too far away or too dynamically variable for a human controller, so they will need to operate largely autonomously.
To that end, we want these systems to build models of that environment, so they can reason about it and their potential activities. We expect the models to help them interact with their environment more effectively. Moreover, if we also make the systems build models of their own behavior, external and internal, then they can reason about that behavior and its connection to the environment. This approach to reflective systems therefore expects the system to use processes that build and use models of the system’s external environment and processes, and also its internal environment and processes (see Figure 1). We have argued that this modeling is an eenxtveirrnoanlment of of processes
use models
build
processes
important enabler for the flexibility required to adjust behavior
to external conditions [
During the course of their activities, these systems will build models of common situations and appropriate responses, so they can subsequently recognize a situation to help decide on a response more quickly. Then they can separate effective and ineffective responses, identify environmental or internal characteristics that distinguish these two classes, and extend the relevant situation descriptions to include the newly identified property. Therefore, these systems are in a continual state of making new distinctions, thereby increasing the knowledge base size and interconnectivity.
However, this process cannot continue indefinitely, as we shall show in Section IV.
We have shown [
We start with the interpreter written in the modeling language (which does put constraints on how simple the modeling language can be), and an external program (that will be used exactly once), written in any convenient language, that compiles the modeling language into an executable process. Then any model subsequently produced can be interpreted, including changes to the interpreter (see Figure 2). Changes interpreter model bootstrap compiler interpreter process all models
all processes to the modeling language are more problematic, and are left for further studies. In many applications, the interpreter will not change at run time, simplifying this process somewhat.
III. OUR APPROACH
To manage the large collection of necessary models, we use
the Wrapping integration infrastructure [
The Problem Posing Interpretation is a different way to interpret programs that provides an enormous amount of flexibility consider in the assignment of semantics to syntax.
The basic idea is to separate information service requests, such as function calls, message sends, etc. from information service providers, such as function and method definitions. Compilers and interpreters can always tell the difference, so there is no reason to require them to use the same name (which is what we usually do).
That separation immediately allows (and requires) a mechanism to reconnect requests to providers. This change of interpretation allows many interesting properties:
Code reuse without modification; Delaying language semantics to run-time, Migration to standards;
Run-Time flexibility.
This last property is our interest here.
Our choice for mapping problems to resources in context is to use a Knowledge Base that defines the various uses of each resource in different contexts; it allows different resources to be used for the same problem in different contexts.
This is a kind of implicit invocation.
There are five essential properties of Wrappings:
ALL parts of the system are resources; ALL activities in the system are resource applications; Relevant system state is given by context;
pings; Problem Managers (PMs) interpret the Wrappings to perform all of the infrastructure and application functions.
The processes in the Wrapping approach are as important as the data in the WKBs (it must be remembered that declarative programs do not DO anything without an interpreter). The PMs organize the computations and interpret the Wrappings. Two basic classes of PMs are the Coordination Manager (CM) and the Study Manager (SM). These two PMs separate the control loop at the center of our approach into the looping “heartbeat” that keeps the system moving forward (the Coordination Manager or CM) from the basic planning steps within the loop (the Study Manager or SM).
1) Coordination Manager: The CM is a class of resources that are analogs of a system’s main program. The simplest one consists of the following steps:
Find Context loop :
Pose Problem Study Problem Present Results
Collect initial context.
Select one problem to study.
Find and use one resource for this problem.
Make adjustments to context (and possibly Wrappings).
This is the analog of an extremely simple sequential main program (and also clearly of the classic “read-eval-print” style of basic LISP interpreter). There is a CM corresponding to any “main program” style (parallel, cooperative, etc.). Remember that each of these steps is also a posed problem, using Wrappings to map them to appropriate resources in context. As always, each of these steps is a posed problem, using Wrappings to map them to resources. This is an extremely simple-minded planner. The main power of Wrappings is that any improvement in planning processes can be incorporated as other resources that can address these posed problems. Other SMs apply all relevant resources in turn until one succeeds, or accumulate the results of all successful applications, etc..
The interaction of the two main PMs is shown schematically in Figure 3, which we find to be a useful mnemonic for which steps occur when. The interaction of these two processes is the
Match Resources Resolve Resources Select Resource Adapt Resource Advise Poser Apply Resource Assess Results 2) Study Manager: The Study Manager is a class of resources that are designed to address the problem “Study Problem” (from the CM). It reads and interprets the WKB (which is described in the next subsection). The simplest one consists of the following steps:
The WKB contains entries called Wrappings. An individual Wrapping is a map from a problem specification to a resource application in context. Its main information components are:
The power of Wrappings comes from the notion that each
of the steps is a posed problem [
It should also be clear that any system with such an explicit central activity loop (whether or not it is organized in the way we described) has a ready-made identifier for the events that it performs. The event labels can be considered as the basic representational language for modeling behavior.
The use of Wrappings provides several conceptual unifications in system design:
ALL activity is requested as posed problems.
ALL activity is performed by resources, ALL processing is resource application.
ALL activity can be recorded (Advise Poser in SM).
Wrappings help with some of the organization processes in self-modeling systems. They do not solve all of the hard problems, but they do help organize the solutions.
They allow a system
To manage its collection of models;
To coordinate its activities with other systems.
foundation of our self-modeling systems [
IV. GETTING STUCK
As our self-modeling systems, or indeed any systems that constructs situational models at run time, behave in their operational environment, the natural tendency for us as designers is to assume that they will build more detailed models to make more detailed distinctions among the phenomena they encounter. This clearly could be a problem, and the following results show that it is definitely a problem.
The “Get Stuck” Theorems [
The first theorem is based on the fact that we can count how many structures of a given size can exist, so representing behavior in a sufficiently complex environment will eventually need to use so many expressions that they will become too large for the system to use either effectively or soon enough. The second theorem is based on the fact that each new element in a complex knowledge structure will need to attach to more of the other elements, and that therefore the practical constraints on adding new knowledge become more and more difficult to satisfy.
The first theorem is relatively straightforward to prove. If
the computing system has a fixed finite symbol system (finitely
many basic symbols, finitely many fixed arity combination
rules), then we can count the number of expressions of any
given size, using the well-known mathematical technique of
generating functions [
Similarly, if we are building and extending a knowledge base, with references from entities to other entities, then the interconnection density eventually becomes large enough that the implications of potential changes take too much time to analyze. The important point here is that it will happen even if humans are doing the extensions.
These two theorems have implications for our computing systems: they will have to change their representational mechanisms. In the next Section, we describe some processes that can at least delay the problem.
V. GETTING UNSTUCK
We have shown that if our system is effective at discovering new distinctions and making more refined models, then it will eventually “Get Stuck”. In this Section, we describe some processes that will help alleviate the problem, but not, of course, eliminate it. The processes are:
Model Deficiency Analysis, Dynamic Knowledge Management, and its main component processes – Knowledge Refactoring and – Constructive Forgetting.
These processes help delay the problem, and we believe that more such alleviations are necessary.
We use the term “Behavior Mining” for any analysis of the sequence of events performed by a system (there may of course be multiple parallel analyses at different resolutions and / or scopes). The intention is to identify and encapsulate common sequences, so that they may not need to be computed separately repeatedly. This is akin to encapsulating sequences of operations into “macros” to reduce computation (the target computation is the same, but the decision processes that construct the sequence are eliminated). The system will invent new symbols as event labels for these common event sequences, as well as other recurring structures (repetitions, alternations, etc.), and use them in a continual analysis.
The technical area of interest for this process is grammatical
inference [
Our Wrapping infrastructure allows for both positive and
negative examples [
Once the system has new labels for some collection of
common event structures, it becomes interesting to consider
the possibility that all events can be placed into one of the
identified commonalities (“macros”). When this happens, there
is the possibility of defining the events solely in terms of the
macros. That is, the event succession can be re-expressed in
terms of the new symbols. If the system can actually express
its behavior using these new symbols only, then we write that
the new symbol set is “semiotically closed” [
The processes we collectively call Model Deficiency Analysis are intended to detect problems with the models in use and provide suggestions for reducing the problems and improving the models. The system needs to be able to determine that a model has a problem, isolate the problem to particular sections of the model, and determine potential changes that will improve the model.
There are three key issues:
How to monitor and validate the models, How to decide which model (if any) has failed or (preferably) is about to fail,
How to use the failure to improve the model.
We can view these collected process as one step in a learning mechanism that is intended to improve the effectiveness of the model behavior. However, most learning applications assume a fairly class of parameterized models, and their process is to adjust the parameters to improve the behavior (which can be quite effective in some circumstances). Very few treat the models as explicit objects of study, and attempt to diagnose what is wrong when the models fail (as opposed to performing less well than they could).
A key property to this kind of analysis is that in Wrappingbased systems, there is a ready-made class of symbols that can be used for event names (the problem names), and a ready-made class of events that can be labeled (the resource applications announced in the SM). This property allows the system to construct models of its own actual behavior, which can be compared to the behavior intended by the designers (as specified, inevitably, by another model). Precise point of failure can be identified by incorrect or missing resource applications, and the event context (also reported by the SM in the Advise Poser step) and the WKB can be studied directly for errors and omissions in the context that was used to create the incorrect resource application (or not select the correct one).
Further discussion from a different context can be found in
[
This kind of analysis is helpful for the infrastructure models,
but not quite sufficient for creating and improving the domain
models. For that part of the analysis process, we rely on some
combination of simulation and evolutionary programming
techniques [
Wrappings are one kind of knowledge base in these systems, but there are certain to be many others to represent domain knowledge and other information resources.
We have not specified what form the knowledge bases are to take, since these methods are largely independent of that, and can be applied or adapted to most kinds of declarative knowledge. One of the most powerful time savers in accessing knowledge is context: the use of situational awareness to greatly reduce the search space for any posed problem. We describe two forms of context-based Dynamic Knowledge Management, time-based forgetting and context-based search reduction.
We envision this knowledge base with meta-knowledge on each element that contains a measure of its “popularity”, that is, how often it has been used in recent reasoning processes. These values are adjusted as the system reasons, and the data structures used for the knowledge base should reflect that ordering. This kind of “dynamic rule promotion” keeps commonly used rules near the front of the search system, and is known to reduce search times. Then the system can occasionally discard some of the oldest and least used elements, as another way to do Constructive Forgetting.
Context describes the current and intended state of affairs of the system (taking goals and capabilities into account), and its best guess for the current and expected state of affairs of the environment (taking its predictive models of the environment into account). Then the available knowledge can be searched in an order determined by expected relevance (this ordering involves the indexing mechanisms, and does not need to move the knowledge around). In some cases, this reordering will delay the discovery of unexpected paths to a goal, or even prevent the system from finding a good course of action, but it is helpful on the whole. We clearly need better indexing and ordering mechanisms, relevance computations, and dynamically steerable search algorithms.
Even if the system cannot define away its problems, it might
be able to re-organize its knowledge structures to require much
shorter expressions. Because this is a more complicated
operation than the previous two, we spend more time discussing
it. There are two parts to this kind of re-organization: the
first is a simple change of emphasis for all of the models
and rules, and the second is an actual re-arrangement. This
re-arrangement has come to be known as refactoring, and is
very popular in object-oriented coding circles [
As an example of the latter, we note the property of
“tangleness”, that is, many elements all referring to each other.
One simple measures of tangleness is the size of maximal
cliques in the directed reference graph. Each maximal clique
is a set of elements that all refer to each other, so it seems
that there should be some partition of the set into subclasses,
or even some new element that they are all connected to. For
an n-clique, this changes the n * (n -1) / 2 edges between
every pair of elements to n edges, from each of the elements
to the new one. We have a speculative notion that small world
graphs may be useful for this kind of structure [
The notion of graph cliques brings up an entirely new
speculation that is interesting and may become important. It
is well-known that the collection of cliques in an undirected
graph is a simplicial complex, and therefore many topological
methods, and in particular persistent homology, can be applied
to understand the structure of the knowledge base at all
scales [
Another intriguing possibility is about reconstructing the
symbolic dynamics of a nonlinear system (a computable
definition of what the system does and will do). Mischaikow
et al. [
Each of these possibilities warrants much more study.
We close with some of the refactoring “smells” and corrective actions that may apply to knowledge based systems, whether they are embodied as rules or some other declarative mechanism. We describe such a knowledge base as having several sets of element definitions that define what objects are being considered, how they relate to each other and how they change. The entities and attributes define the objects, and there are relationships among the objects, and activities that change those objects. The key interconnection is the reference from one of these entities to another.
An entity with too many attributes should be separated into a hierarchy of multiple entities that group the attributes in a sensible way. An entity with too few attributes could be too general, needing some new attributes to make appropriate distinctions (of course, the system needs a reason to make those distinctions). Two entities with too many relationships should be better modeled as subordinate to a more general combined entity. Many different entities with the same set of attributes should be better modeled using a common subordinate containing those attributes. These and other changes are relatively easy. The old element references can be adjusted to these new ones (though the system will have to make up some names).
Note that this kind of refactoring is almost entirely experience driven, and has essentially nothing to do with simplifying different aspects of original models, since they usually do not exist.
The more radical restructurings of the knowledge base depend on the semantics of the elements and their connections, to which the system has little or no access, so these are generally left for the designers, for now (though there are certainly claims in the code refactoring world that many of these small changes can add up to a large one). Eventually, we expect to go farther along the path of having the system identify new core concepts, adjust the knowledge base, and translate old expressions into new ones.
There are many other warning signs that the knowledge base structure might be unwieldy, but none as strong as search delays or mistakes, which the system may not be able to detect when they happen, but might be able to diagnose after the fact.
This kind of refactoring is time-consuming, and very likely too static for the “on-line” system, so we expect our runtime systems to rely on the continual rearrangement of rule priorities according to context and situation, and to do more serious refactoring during down times (if there are any).
Since we know that the system will eventually run out of space, the system needs ways to reclaim that space. Our notion of “Constructive Forgetting” is about how to reduce the knowledge base without sacrificing performance. For this purpose, we think that the system can make simplifications by grouping similar clusters or sequences, and simply treating them all the same. If differences are eventually identified, then either the system can recover some of the distinctions, or it can recognize that it does not have the resources to cope.
This is an application of grammatical inference, and identifying classes of structures that have the same or a similar effect, or to which the system responds nearly identically. In those cases, the distinction is irrelevant to the response and it can be discarded. Of course, if subsequent experience shows that the distinction matters, the normal elaboration process will make that refinement.
It is extremely important for managing the balance among these processes that the system record all of the elaborations and collapsings, so they and their preconditions can be studied. For example, when the system operation seems to be getting slow (or the stored knowledge large), the threshold for approximate matching can be lowered, so that more responses are collapsed by this process. When system operation is relatively fast, the elaboration mechanism can be turned up a little bit, so that finer distinctions can be considered.
In this paper, we have described an application of selfmodeling systems to autonomous systems that we expect to operate in hazardous or remote environments, and to adapt their behavior to the external (and internal, e.g., low battery) conditions they encounter. These systems refine designerprovided knowledge bases that describes what they should expect to encounter from the environment, from themselves, and from the complexities of their interactions. We have also described some methods for reducing the size and complexity of the knowledge bases in an attempt to stave off the “Get Stuck” Theorems, which will allow these self-modeling systems to operate autonomously for longer periods of time or in more dynamic environments.
In general, the question of how to balance expansion and contraction, and tune them to the complexity and dynamics of the environment, is the main sustainable system question, but it is our recommendation to keep the system near the higher boundary, to maximize the available size of the semantic space. A more general answer requires experimentation with some engineering applications, and we expect the result to be quite application specific.
The important design question is how much of this variation machinery we actually need for a given application, and how much of the system structure can remain fixed (and unmodeled). This engineering question can only be answered in the context of a particular application.
The important implementation question is how to make the analysis fast enough to be useful, or how much of the model update process the system can afford to do. This question also is dependent on the particular application, because that will determine how much computing power is available for these sustainability functions.
We know that we can build these self-modeling systems. We think that we can learn to tune the balance rules effectively. We expect that they will be useful for difficult applications.