Reflective Systems Need Models at Run Time Christopher Landauer Kirstie L. Bellman Topcy House Consulting, Thousand Oaks, California Topcy House Consulting, Thousand Oaks, California Email: topcycal@gmail.com Email: bellmanhome@yahoo.com Abstract—We think that run-time models are a minimum modeling systems, and provide some suggestions for alleviat- necessity for significant self-awareness in Computationally Re- ing their effects. flective systems. For us, a Computationally Reflective system is not only “self-aware” (it can collect information about its own A. Self-Modeling Systems behavior and that of its environment), but also “self-adaptive” (it can reason about that behavior and make adjustments that Self-modeling systems [24] are self-aware systems that change it). Moreover, when the system is also “self-modeling”, have the capability to build and analyze models of their own that is, defined by the models it creates and maintains, then it behavior, and use those models to produce as much of that can modify those models to better align its behavior with changes in its operating environment. behavior as the designers intend. We have already shown In this paper, we show that building and managing these [20] [22] that we can build systems for which all of the models presents some difficulties that are largely independent system’s components are models, including the model inter- of the modeling mechanisms used. We also provide some mecha- preter. While these Computationally Reflective systems are nisms for coping with these difficulties, from a kind of “Behavior usually originally deployed with an initial set of models and Mining” and “Model Deficiency Analysis” for current models to “Dynamic Knowledge Management”, of which major components model construction guidelines, their main self-modeling work are “Knowledge Refactoring” and “Constructive Forgetting”. is to adjust those models according to their observations of None of these methods eliminate the problem, but each alleviates their operational external environment and their own internal some of the difficult aspects of the problem, which allows bigger environment, and produce their behavior by interpreting the and more complex systems to exist in more complex and diverse models that they create. An engineering decision to be made environment for longer periods of time. by the developers is to decide how much of these behavior Keywords: Self-Aware Systems, Self-Adaptive Systems, Self- Modeling Systems, Computational Reflection, Computational generating models are fixed and which ones can be variable Semiotics, Run-Time Model-Building, Wrapping Integration In- (and the boundary can often usefully be changed at run time, frastructure, Problem Posing Interpretation depending on the situation). Because these models are intended to be interpreted by I. I NTRODUCTION the system, the common “4+1” view [16] is not entirely We argue that run-time models are a minimum necessity appropriate: we must mainly be concerned with process and for significant and effective self-awareness in Computationally interconnection models (behavior and interaction), and not Reflective systems. A Computationally Reflective system [28] much with developmental or use case views. Moreover, the [29] [4] must not only be“self-aware” (it can collect and system needs to build and maintain models of its operational organize information about its own behavior and that of its environment also, not just its own structure. environment), but also “self-adaptive” (it can reason about that The questions then become: how does a system behavior and make adjustments that change it). We are primar- • learn about its own structure and behavior? ily interested in systems that are also “self-modeling”, which • make decisions about its own structure and behavior? extends the notion to systems that construct and maintain their • decide on changes to its own structure and behavior? own models, and use those to generate their behavior. We think • record and use the decisions and their consequences over that such systems must be able to change not only the models time? but also the modeling mechanisms they use at run-time, not just adapt parameters or switch between operating modes. For us, all of these are about models or involve or require models. The corresponding engineering design problems are: A Computationally Reflective system can collect informa- tion about its own structure and behavior, and it can also ex- • how extensive these reflective mechanisms need to be for amine that information to decide how to modify the behavior, a given application, retain and analyze it over extended time periods, adjust its • how much we want the system itself to construct and decision processes to “optimize” it towards selected success modify the models, and criteria, and even change the success criteria to respond to • how much of the system behavior is to be driven by the changes detected in the environment (which may also include models. newly imposed purposes or goals). Models cost time for development and execution, which In this paper, we explore some seemingly far-fetched the- makes this set of engineering problems central to the success oretical notions, show that they are eminently likely in self- of self-adaptive systems in complex environments. If we make this extensive use of models, we are brought to the notion of C. Structure of Paper using the models to define the behavior. The rest of this paper is organized as follows. In the next These are self-modeling systems. Section II, we describe more of the structure of self-modeling B. Representational Issues systems. In our prior work on self-modeling systems, we have In Section III, we describe our own approach to constructing identified two fundamental representational issues that must self-modeling systems, using activity loops driven by knowl- be addressed by any self-aware system of this kind: edge bases. In Section IV, we describe some fundamental results from 1) the need for identifying repeated patterns and inventing Computational Semiotics that have relevance to model build- new symbols for them, to reduce the computational load; ing at run time. 2) the need for occasionally re-inventing the representa- In Section V, we show how some partial approaches can tional mechanism itself, to avoid the inevitable increase alleviate the problem of getting stuck, and finally, in Sec- in rigidity in a complex knowledge-intensive system. tion VI, we describe some conclusions and prospects for These are both issues of Computational Semiotics [18] further development. [21], since they involve the use and meaning of symbols in computing systems. The first issue is a generalization II. S ELF -M ODELING S YSTEMS of some well-known optimization techniques, analogous to training, that replace the computation of appropriate responses Our goal is to design and build systems that are able to to recognition of the appropriate situations (which is usually operate in hazardous or remote environments that cannot be much faster). The second issue follows from our “Get Stuck” completely known. The assumption is that they are too far Theorems [18] [21], which essentially show that any increas- away or too dynamically variable for a human controller, so ing knowledge structure will eventually become unwieldy and they will need to operate largely autonomously. extremely difficult to extend (even if humans are putting in To that end, we want these systems to build models of that the new knowledge, so it is not a computability problem). The environment, so they can reason about it and their potential theorems are formalizations of the long experience of failure activities. We expect the models to help them interact with in building extensible languages, systems, and programs. their environment more effectively. Moreover, if we also make These theorems are not insurmountable, but they do pose a the systems build models of their own behavior, external and serious design consideration. In addition, it can be seen that internal, then they can reason about that behavior and its they are inevitable in any systems that build increasingly fine- connection to the environment. This approach to reflective grained models. That means that they are not unlikely; they systems therefore expects the system to use processes that must be addressed. build and use models of the system’s external environment Helpfully, there are several processes that can be used to and processes, and also its internal environment and processes alleviate their effects to some extent. We think that these (see Figure 1). We have argued that this modeling is an helpful processes are necessary in any case for a self-modeling system to operate in a complex environment for any non-trivial perform processes actions amount of time. “Behavior Mining” is the process of recording and an- use external of environment alyzing the system’s own behavior to make descriptive or of prescriptive models. models “Model Deficiency Analysis” is the process of evaluating the effectiveness of a model (not just success and failure, of build but also performance, resource implications, and interference make processes observations with other models), and analyzing where improvements can be made. “Knowledge Refactoring” is the process of rearranging the Fig. 1. Reflective System in Environment hierarchical knowledge structures (e.g., ontologies) to reduce dependencies, duplication and unused elements. important enabler for the flexibility required to adjust behavior “Constructive Forgetting” is the process of simplifying to external conditions [20] [22]. knowledge structures by conflating and even removing some During the course of their activities, these systems will build terms and relationships. models of common situations and appropriate responses, so Each of these will be discussed in the rest of the paper. they can subsequently recognize a situation to help decide None of these methods entirely avoids the problems pre- on a response more quickly. Then they can separate effective sented by the theorems, of course; the theorems are still true. and ineffective responses, identify environmental or internal They do, however, push the bounds farther out, which allows characteristics that distinguish these two classes, and extend bigger and more complex systems to exist in more complex the relevant situation descriptions to include the newly identi- and diverse environments for longer periods of time. fied property. Therefore, these systems are in a continual state of making new distinctions, thereby increasing the knowledge Compilers and interpreters can always tell the difference, so base size and interconnectivity. there is no reason to require them to use the same name (which However, this process cannot continue indefinitely, as we is what we usually do). shall show in Section IV. That separation immediately allows (and requires) a mech- We have shown [24] how to build systems that consist anism to reconnect requests to providers. This change of entirely of models, including the model interpreter. These interpretation allows many interesting properties: systems build models of system behavior (or are provided them • Code reuse without modification; by the designers), and use the model interpreter to execute • Delaying language semantics to run-time, them. The “Moby Hack” [33] [20] shows how to make this • Migration to standards; circular process well-defined. Because it seems unusual, we • Run-Time flexibility. have a short explanation here. This last property is our interest here. We start with the interpreter written in the modeling lan- guage (which does put constraints on how simple the modeling B. Wrapping Properties language can be), and an external program (that will be Our choice for mapping problems to resources in context is used exactly once), written in any convenient language, that to use a Knowledge Base that defines the various uses of each compiles the modeling language into an executable process. resource in different contexts; it allows different resources to Then any model subsequently produced can be interpreted, be used for the same problem in different contexts. including changes to the interpreter (see Figure 2). Changes This is a kind of implicit invocation. There are five essential properties of Wrappings: bootstrap • ALL parts of the system are resources; compiler • ALL activities in the system are resource applications; • Relevant system state is given by context; • Wrapping Knowledge Bases (WKBs) contain the map- pings; • Problem Managers (PMs) interpret the Wrappings to interpreter interpreter perform all of the infrastructure and application functions. model process C. Wrapping Processes 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 all models all processes 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 Fig. 2. Interpreter Bootstrap loop at the center of our approach into the looping “heartbeat” to the modeling language are more problematic, and are left that keeps the system moving forward (the Coordination for further studies. In many applications, the interpreter will Manager or CM) from the basic planning steps within the not change at run time, simplifying this process somewhat. loop (the Study Manager or SM). 1) Coordination Manager: The CM is a class of resources III. O UR A PPROACH that are analogs of a system’s main program. The simplest one consists of the following steps: To manage the large collection of necessary models, we use the Wrapping integration infrastructure [17] [23], which allows Find Context Collect initial context. us enormous flexibility in selecting and employing models. It loop : was first designed to help study infrastructure decisions. What Pose Problem Select one problem to study. follows in this section is a short description of Wrappings, Study Problem Find and use one resource with its focus on resource management. More details can be for this problem. found in the cited references. Present Results Make adjustments to context (and possibly Wrappings). A. Problem Posing Interpretation The Problem Posing Interpretation is a different way to This is the analog of an extremely simple sequential main interpret programs that provides an enormous amount of program (and also clearly of the classic “read-eval-print” style flexibility consider in the assignment of semantics to syntax. of basic LISP interpreter). There is a CM corresponding to any The basic idea is to separate information service requests, “main program” style (parallel, cooperative, etc.). Remember such as function calls, message sends, etc. from information that each of these steps is also a posed problem, using service providers, such as function and method definitions. Wrappings to map them to appropriate resources in context. 2) Study Manager: The Study Manager is a class of D. Wrapping Knowledge Bases resources that are designed to address the problem “Study The WKB contains entries called Wrappings. An individual Problem” (from the CM). It reads and interprets the WKB Wrapping is a map from a problem specification to a resource (which is described in the next subsection). The simplest one application in context. Its main information components are: consists of the following steps: PROB problem name Match Resources Match resources to problem in context COND context condition (may be repeated) (simple WKB filter). RES resource name Resolve Resources Resolve resources via negotiation SYM symbol name between problem and Wrappings FILE file name to produce candidate resources. Select Resource Choose one of the remaining candidate resources. The problem specification consists of a problem name and a Adapt Resource Adapt resource to problem and context list of actual parameters. This is the form in which problems (finish instantiating all necessary are posed. When we write about a problem, we are usually invocation parameters). referring to a class of problems identified by the problem name Advise Poser Record (announce) resource application (e.g., integrate, optimize, infer, etc.). The context condition is (what is about to be done), together with relevant context a sequence of boolean conditions (assumed conjunctive) on (that was used for its construction). the problem parameters and the context variables (this allows Apply Resource Use the resource for the problem the same problem to map to different resources if there are (invoke the resource application). different problem parameters). The resource application is the Assess Results Evaluate success or failure. fully bound invocation of the resource (all required parameters have values assigned). The symbol and file names are used As always, each of these steps is a posed problem, using to find the executable code for the resource. Most of our Wrappings to map them to resources. This is an extremely implementations use dynamic loading and unloading to reduce simple-minded planner. The main power of Wrappings is that the size of the executable and retain the flexibility to add new any improvement in planning processes can be incorporated as or different resources for the same or different problems at other resources that can address these posed problems. Other run time. SMs apply all relevant resources in turn until one succeeds, The actual format of a WKB can vary (even heteroge- or accumulate the results of all successful applications, etc.. neously); it is constrained only by the fact that it is read only The interaction of the two main PMs is shown schematically by a few of the SM steps (minimally Match, Resolve, Apply), in Figure 3, which we find to be a useful mnemonic for which and as the resources for those steps can be selected differently steps occur when. The interaction of these two processes is the at run time, so can the WKB have different syntax at run time. E. Wrapping Summary Find Context The power of Wrappings comes from the notion that each of the steps is a posed problem [19], for which the entire Assimilate Results Wrapping infrastructure is available to identify an appropriate resource to apply. CM It should also be clear that any system with such an explicit central activity loop (whether or not it is organized in the way Pose Problem Study Problem we described) has a ready-made identifier for the events that Match Resources it performs. The event labels can be considered as the basic representational language for modeling behavior. Resolve Resources F. Use of Wrappings SM Select Resource The use of Wrappings provides several conceptual unifica- tions in system design: Adapt Resource • ALL activity is requested as posed problems. • ALL activity is performed by resources, ALL processing Advise Poser is resource application. • ALL activity can be recorded (Advise Poser in SM). This step invokes Apply Resource the resource to do Wrappings help with some of the organization processes whatever it does Assess Results in self-modeling systems. They do not solve all of the hard problems, but they do help organize the solutions. Fig. 3. CM and SM Steps They allow a system • To manage its collection of models; foundation of our self-modeling systems [22] [17]. • To coordinate its activities with other systems. IV. G ETTING S TUCK eventually “Get Stuck”. In this Section, we describe some As our self-modeling systems, or indeed any systems that processes that will help alleviate the problem, but not, of constructs situational models at run time, behave in their oper- course, eliminate it. The processes are: ational environment, the natural tendency for us as designers • Behavior Mining, is to assume that they will build more detailed models to • Model Deficiency Analysis, make more detailed distinctions among the phenomena they • Dynamic Knowledge Management, and its main compo- encounter. This clearly could be a problem, and the following nent processes results show that it is definitely a problem. – Knowledge Refactoring and The “Get Stuck” Theorems [18] [21] show some fundamen- – Constructive Forgetting. tal limits on representing knowledge in symbolic structures in These processes help delay the problem, and we believe that computing systems, in particular, that systems operating in more such alleviations are necessary. complex environments will eventually need to change their own internal representations. These theorems formalize the A. Behavior Mining decades of observations that have the common theme that extending existing systems becomes more difficult and error- We use the term “Behavior Mining” for any analysis of prone over time (e.g., Lehman’s laws of software evolution the sequence of events performed by a system (there may of [26] [27] [12] for programs that operate in the real world, course be multiple parallel analyses at different resolutions among other informal notes), and in many cases has simply and / or scopes). The intention is to identify and encapsulate precluded anything but minor maintenance. common sequences, so that they may not need to be computed The first theorem is based on the fact that we can count separately repeatedly. This is akin to encapsulating sequences how many structures of a given size can exist, so representing of operations into “macros” to reduce computation (the target behavior in a sufficiently complex environment will eventually computation is the same, but the decision processes that con- need to use so many expressions that they will become too struct the sequence are eliminated). The system will invent new large for the system to use either effectively or soon enough. symbols as event labels for these common event sequences, The second theorem is based on the fact that each new element as well as other recurring structures (repetitions, alternations, in a complex knowledge structure will need to attach to etc.), and use them in a continual analysis. more of the other elements, and that therefore the practical The technical area of interest for this process is grammatical constraints on adding new knowledge become more and more inference [7] [9] [3] [5] [13], which is about discovering difficult to satisfy. higher-level structure among sequences of relatively low-level The first theorem is relatively straightforward to prove. If events. For different sets of assumptions about the high-level the computing system has a fixed finite symbol system (finitely structure of these common sequences, different algorithms many basic symbols, finitely many fixed arity combination can be used to infer the higher-level organization of those rules), then we can count the number of expressions of any structures. This is an enormous field, and we have included given size, using the well-known mathematical technique of some references to illustrate some of the different approaches generating functions [36]. The point is not that the values and theoretical results. One of the theorems is that most are large or small, it is that there are only finitely many interesting classes of structures cannot be effectively inferred expressions of any given size. That means, as the system without having both positive and negative examples [10] [1] tries to represent more and more complex phenomena or [2] (see [25] for a summary of these results). relationships, or make more detailed distinctions, it will need Our Wrapping infrastructure allows for both positive and more and more expressions, so they will get larger and larger. negative examples [22], since it makes available not only the The system will eventually run out of expressions small context and reasons for choosing a particular resource to per- enough to process effectively. form a computing step, but also the conditions that eliminated Similarly, if we are building and extending a knowledge other possible resources. It therefore seems possible that these base, with references from entities to other entities, then the systems can infer more complex behavioral structures than interconnection density eventually becomes large enough that other mechanisms can provide. the implications of potential changes take too much time to Once the system has new labels for some collection of analyze. The important point here is that it will happen even common event structures, it becomes interesting to consider if humans are doing the extensions. the possibility that all events can be placed into one of the These two theorems have implications for our computing identified commonalities (“macros”). When this happens, there systems: they will have to change their representational mech- is the possibility of defining the events solely in terms of the anisms. In the next Section, we describe some processes that macros. That is, the event succession can be re-expressed in can at least delay the problem. terms of the new symbols. If the system can actually express its behavior using these new symbols only, then we write that V. G ETTING U NSTUCK the new symbol set is “semiotically closed” [18] [21], which We have shown that if our system is effective at discovering we believe is an essential component of emergence. This line new distinctions and making more refined models, then it will of reasoning is important, but beyond the scope of this paper. B. Model Deficiency Analysis Management, time-based forgetting and context-based search The processes we collectively call Model Deficiency Analy- reduction. sis are intended to detect problems with the models in use and We envision this knowledge base with meta-knowledge on provide suggestions for reducing the problems and improving each element that contains a measure of its “popularity”, that the models. The system needs to be able to determine that is, how often it has been used in recent reasoning processes. a model has a problem, isolate the problem to particular These values are adjusted as the system reasons, and the sections of the model, and determine potential changes that data structures used for the knowledge base should reflect will improve the model. that ordering. This kind of “dynamic rule promotion” keeps There are three key issues: commonly used rules near the front of the search system, and is known to reduce search times. Then the system can occa- • How to monitor and validate the models, sionally discard some of the oldest and least used elements, • How to decide which model (if any) has failed or (prefer- as another way to do Constructive Forgetting. ably) is about to fail, Context describes the current and intended state of affairs • How to use the failure to improve the model. of the system (taking goals and capabilities into account), We can view these collected process as one step in a learning and its best guess for the current and expected state of mechanism that is intended to improve the effectiveness of the affairs of the environment (taking its predictive models of model behavior. However, most learning applications assume the environment into account). Then the available knowledge a fairly class of parameterized models, and their process is can be searched in an order determined by expected relevance to adjust the parameters to improve the behavior (which can (this ordering involves the indexing mechanisms, and does not be quite effective in some circumstances). Very few treat the need to move the knowledge around). In some cases, this re- models as explicit objects of study, and attempt to diagnose ordering will delay the discovery of unexpected paths to a what is wrong when the models fail (as opposed to performing goal, or even prevent the system from finding a good course less well than they could). of action, but it is helpful on the whole. We clearly need better A key property to this kind of analysis is that in Wrapping- indexing and ordering mechanisms, relevance computations, based systems, there is a ready-made class of symbols that and dynamically steerable search algorithms. can be used for event names (the problem names), and a ready-made class of events that can be labeled (the resource D. Knowledge Refactoring applications announced in the SM). This property allows the Even if the system cannot define away its problems, it might system to construct models of its own actual behavior, which be able to re-organize its knowledge structures to require much can be compared to the behavior intended by the designers shorter expressions. Because this is a more complicated oper- (as specified, inevitably, by another model). Precise point ation than the previous two, we spend more time discussing of failure can be identified by incorrect or missing resource it. There are two parts to this kind of re-organization: the applications, and the event context (also reported by the SM in first is a simple change of emphasis for all of the models the Advise Poser step) and the WKB can be studied directly and rules, and the second is an actual re-arrangement. This for errors and omissions in the context that was used to create re-arrangement has come to be known as refactoring, and is the incorrect resource application (or not select the correct very popular in object-oriented coding circles [8] [15] [30]. one). There are many different kinds of refactoring operations, and Further discussion from a different context can be found in which one to use first depends on some characteristics of the [23]. interconnection graph that have come to be called “smells” This kind of analysis is helpful for the infrastructure models, in the object-oriented coding world. For our application, we but not quite sufficient for creating and improving the domain need “smell” analogs for knowledge bases, which are relatively models. For that part of the analysis process, we rely on some easily adapted from [8], in addition to those that can be derived combination of simulation and evolutionary programming from first principles. techniques [6] [11] This area is under active investigation. As an example of the latter, we note the property of “tangleness”, that is, many elements all referring to each other. C. Dynamic Knowledge Management One simple measures of tangleness is the size of maximal Wrappings are one kind of knowledge base in these systems, cliques in the directed reference graph. Each maximal clique but there are certain to be many others to represent domain is a set of elements that all refer to each other, so it seems knowledge and other information resources. that there should be some partition of the set into subclasses, We have not specified what form the knowledge bases are or even some new element that they are all connected to. For to take, since these methods are largely independent of that, an n-clique, this changes the n * (n -1) / 2 edges between and can be applied or adapted to most kinds of declarative every pair of elements to n edges, from each of the elements knowledge. One of the most powerful time savers in accessing to the new one. We have a speculative notion that small world knowledge is context: the use of situational awareness to graphs may be useful for this kind of structure [34] [35]. greatly reduce the search space for any posed problem. We The notion of graph cliques brings up an entirely new describe two forms of context-based Dynamic Knowledge speculation that is interesting and may become important. It is well-known that the collection of cliques in an undirected translate old expressions into new ones. graph is a simplicial complex, and therefore many topological There are many other warning signs that the knowledge methods, and in particular persistent homology, can be applied base structure might be unwieldy, but none as strong as search to understand the structure of the knowledge base at all delays or mistakes, which the system may not be able to detect scales [14] [32]. Our interest is in the recent improvements in when they happen, but might be able to diagnose after the fact. computational speed [37] [38], which may allow these result This kind of refactoring is time-consuming, and very likely to be computed on the fly. The question is which of these too static for the “on-line” system, so we expect our run- methods provides useful information. time systems to rely on the continual rearrangement of rule Another intriguing possibility is about reconstructing the priorities according to context and situation, and to do more symbolic dynamics of a nonlinear system (a computable def- serious refactoring during down times (if there are any). inition of what the system does and will do). Mischaikow et al. [31] show that, given a sequence of measurements E. Constructive Forgetting of the system, a symbolic model with a finite number of Since we know that the system will eventually run out states can be computed, and that model used for predictions of space, the system needs ways to reclaim that space. Our and other analyses. Its utility is in proving that a certain notion of “Constructive Forgetting” is about how to reduce dynamical system is chaotic (which is largely of theoretical the knowledge base without sacrificing performance. For this interest), in separating noise from essentials (which is of great purpose, we think that the system can make simplifications practical interest), and in determining invariant sets (sets that by grouping similar clusters or sequences, and simply treating the dynamics preserves, which include all attractors, and gives them all the same. If differences are eventually identified, then hints about long-term behavior). either the system can recover some of the distinctions, or it Each of these possibilities warrants much more study. can recognize that it does not have the resources to cope. We close with some of the refactoring “smells” and cor- This is an application of grammatical inference, and iden- rective actions that may apply to knowledge based systems, tifying classes of structures that have the same or a similar whether they are embodied as rules or some other declarative effect, or to which the system responds nearly identically. In mechanism. We describe such a knowledge base as having those cases, the distinction is irrelevant to the response and it several sets of element definitions that define what objects are can be discarded. Of course, if subsequent experience shows being considered, how they relate to each other and how they that the distinction matters, the normal elaboration process will change. The entities and attributes define the objects, and there make that refinement. are relationships among the objects, and activities that change It is extremely important for managing the balance among those objects. The key interconnection is the reference from these processes that the system record all of the elaborations one of these entities to another. and collapsings, so they and their preconditions can be studied. An entity with too many attributes should be separated into For example, when the system operation seems to be getting a hierarchy of multiple entities that group the attributes in slow (or the stored knowledge large), the threshold for approx- a sensible way. An entity with too few attributes could be imate matching can be lowered, so that more responses are too general, needing some new attributes to make appropriate collapsed by this process. When system operation is relatively distinctions (of course, the system needs a reason to make fast, the elaboration mechanism can be turned up a little bit, those distinctions). Two entities with too many relationships so that finer distinctions can be considered. should be better modeled as subordinate to a more general combined entity. Many different entities with the same set of VI. C ONCLUSIONS AND F UTURE P ROSPECTS attributes should be better modeled using a common subordi- In this paper, we have described an application of self- nate containing those attributes. These and other changes are modeling systems to autonomous systems that we expect to relatively easy. The old element references can be adjusted to operate in hazardous or remote environments, and to adapt these new ones (though the system will have to make up some their behavior to the external (and internal, e.g., low battery) names). conditions they encounter. These systems refine designer- Note that this kind of refactoring is almost entirely experi- provided knowledge bases that describes what they should ence driven, and has essentially nothing to do with simplifying expect to encounter from the environment, from themselves, different aspects of original models, since they usually do not and from the complexities of their interactions. We have also exist. described some methods for reducing the size and complexity The more radical restructurings of the knowledge base of the knowledge bases in an attempt to stave off the “Get depend on the semantics of the elements and their connections, Stuck” Theorems, which will allow these self-modeling sys- to which the system has little or no access, so these are tems to operate autonomously for longer periods of time or in generally left for the designers, for now (though there are more dynamic environments. certainly claims in the code refactoring world that many of In general, the question of how to balance expansion and these small changes can add up to a large one). Eventually, contraction, and tune them to the complexity and dynamics of we expect to go farther along the path of having the system the environment, is the main sustainable system question, but identify new core concepts, adjust the knowledge base, and it is our recommendation to keep the system near the higher boundary, to maximize the available size of the semantic space. [17] Christopher Landauer, “Infrastructure for Studying Infrastructure”, A more general answer requires experimentation with some Proc. ESOS 2013: Workshop on Embedded Self-Organizing Systems, 25 June 2013, San Jose, California; part of 2013 USENIX Federated engineering applications, and we expect the result to be quite Conference Week, 24-28 June 2013, San Jose, California (2013) application specific. [18] Christopher Landauer, Kirstie L. Bellman, “Situation Assessment via The important design question is how much of this variation Computational Semiotics”, pp.712-717 in Proc. ISAS’98: The 1998 International MultiDisciplinary Conference on Intelligent Systems and machinery we actually need for a given application, and Semiotics, 14-17 Sep 1998, NIST, Gaithersburg, Maryland (1998) how much of the system structure can remain fixed (and [19] Christopher Landauer, Kirstie L. Bellman, “Generic Programming, unmodeled). This engineering question can only be answered Partial Evaluation, and a New Programming Paradigm”, Chapter 8, pp.108-154 in Gene McGuire (ed.), Software Process Improvement, in the context of a particular application. Idea Group Publishing (1999) The important implementation question is how to make the [20] Christopher Landauer, Kirstie L. Bellman, “Self-Modeling Systems”, analysis fast enough to be useful, or how much of the model pp.238-256 in R. Laddaga, H. Shrobe (eds.), “Self-Adaptive Software”, Springer Lecture Notes in Computer Science, vol.2614 (2002) update process the system can afford to do. This question also [21] Christopher Landauer, Kirstie L. Bellman, “Semiotic Processing in is dependent on the particular application, because that will Constructed Complex Systems”, Proc. CSIS2002: The 4th Interna- determine how much computing power is available for these tional Workshop on Computational Semiotics for Intelligent Systems, JCIS2002: The 6th Joint Conference on Information Sciences, 08-13 sustainability functions. Mar 2002, Research Triangle Park, NC (2002) We know that we can build these self-modeling systems. We [22] Christopher Landauer, Kirstie L. Bellman, “Managing Self-Modeling think that we can learn to tune the balance rules effectively. Systems”, in R. Laddaga, H. Shrobe (eds.), Proc. Third International Workshop on Self-Adaptive Software, 09-11 Jun 2003, Arlington, We expect that they will be useful for difficult applications. Virginia (2003) [23] Christopher Landauer, Kirstie L. Bellman, “Model-Based Cooperative R EFERENCES System Engineering and Integration”, Proc. SiSSy 2016: The Third [1] Dana Angluin, “Finding Patterns Common to a Set of Strings”, J. Workshop on Self-Improving Self-Integrating Systems, 19 Jul 2016, Computer and System Sciences, vol.21, pp.46-62 (1980) Würzburg, Germany (2016) [2] Dana Angluin, “Inductive Inference of Formal Languages from Positive [24] Dr. Christopher Landauer, Dr. Kirstie L. Bellman, Dr. Phyllis R. Data”, Information and Control, vol.45, pp.117-135 (1980) Nelson, “Wrapping Tutorial: How to Build Self-Modeling Systems”, [3] Dana Angluin, Carl H. Smith, “Inductive Inference: Theory and Meth- Proc. SASO 2012: The 6th IEEE Intern. Conf. on Self-Adaptive and ods”, Computing Surveys, vol.15, no.3, pp.237-269 (Sep 1983) Self-Organizing Systems, 10-14 Sep 2012, Lyon, France (2012) [4] Dr. Kirstie L. Bellman, Dr. Christopher Landauer, Dr. Phyllis R. [25] Lillian Lee, “Learning of Context-Free Languages: A Survey of the Nelson, “Managing Variable and Cooperative Time Behavior”, Pro- Literature”, Technical Report TR-12-96, Harvard U. (1996) ceedings SORT 2010: The First IEEE Workshop on Self-Organizing [26] Meir M. Lehman, “Programs, Life Cycles, and Laws of Software Real-Time Systems, 05 May, part of ISORC 2010: The 13th IEEE Evolution”, Proc. IEEE, vol.68, No.9, pp.1060-1076 (1980) International Symposium on Object/component/service-oriented Real- [27] M. M. Lehman and L. A. Belady (eds.), Program evolution. Processes time distributed Computing, 05-06 May 2010, Carmona, Spain (2010) of software change, Academic Press (1985)Professional, Inc., San [5] J. Berstel, L. Boasson, “Context-Free Languages”, Chapter 2, pp.59- Diego, CA, USA 102 in Jan van Leeuwen (Managing Editor), Handbook of Theoretical [28] Pattie Maes, “Computational Reflection”, technical report 87 2, Vrije Computer Science vol. B: Formal Methods and Semantics, MIT (1990) Universiteit Brussel, Artificial Intelligence Laboratory (1987) [6] C. A. Coello Coello, G. B. Lamont, and D. A. Van Veldhuizen, Evo- [29] Pattie Maes, “Concepts and Experiments in Computational Reflection”, lutionary Algorithms for Solving Multi-Objective Problems, Springer pp. 147-155 in Proceedings OOPSLA ’87 (1987) Science+Business Media (2007) [30] Q. Ethan McCallum, Bad Data Handbook, O’Reilly (2012) [7] J. M. Foster, Automatic Syntactic Analysis, American Elsevier (1970) [31] Konstantin Mischaikow, Marian Mrozek, J. D. Reiss, Andrzej Szym- [8] Martin Fowler, Refactoring: Improving the Design of Existing Code, czak, “Construction of Symbolic Dynamics from Experimental Time Addison-Wesley (1999) Series”, Phys. Rev. Lett. vol.82, pp.1144 (8 Feb 1999) [9] K. S. Fu, T. L. Booth, “Grammatical Inference: introduction and [32] Giovanni Petri, Martina Scolamiero, Irene Donato, Francesco Vac- survey”, IEEE Trans. Systems, Man, and Cybernetics, vol.SMC-5, carino. “Topological Strata of Weighted Complex Networks”, PLOS pp.95-111, pp.409-423 (1975) One, vol.8, no.6, e66506 (2013) [10] E. M. Gold, “Language Identification in the Limit”, Information and [33] Ken Thompson, “Reflections on Trusting Trust”, Comm. of the ACM, Control, vol.10, pp.447-474 (1967) vol.27, no.8, pp.761-763 (Aug 1984), also at URL http://www.acm. [11] D. Hadka, P. Reed, “Borg: An Auto-Adaptive Many-Objective Evo- org/classics/sep95/ (availability last checked 24 Jul 2016); see also lutionary Computing Framework”, Evolutionary Computation, vol.21, the commentary in the “back door” entry of “The Jargon Lexicon”, no.2, pp.231-259 (2013) which is widely available on the Web, and in particular, is findable [12] Israel Herraiz, Daniel Rodriguez, Gregorio Robles and Jesus M. by searching with Google for “back door moby hack” (availability last Gonzalez-Barahona, “The evolution of the laws of software evolution: checked 24 Jul 2016) A discussion based on a systematic literature review”, ACM Computing [34] Duncan J. Watts, Steven H. Strogatz, “Collective dynamics of ’small- Surveys, Vol.1, No.1 (June 2013) world’ networks”. Nature, vol.393, pp.440-442 (1998) [13] Colin de la Higuera, Grammatical Inference: Learning Automata and [35] Duncan J. Watts, Small Worlds: The Dynamics of Networks between Grammars, Cambridge U. Press (2010) Order and Randomness, Princeton U. Press (2003) [14] Danijela Horak, Slobodan Maletić and Milan Rajković, “Persistent ho- [36] Herbert S. Wilf, generatingfunctionology, Academic Press (1990) mology of complex networks”, J. Stat. Mech.: Theory and Experiment [37] Afra Zomorodian, “The Tidy Set: A Minimal Simplicial Set for arXiv 0811.2203 (2008) https://arxiv.org/pdf/0811.2203 (availability Computing Homology of Clique Complexes”, pp.257-266 in Afra last checked 24 Jul 2016) Zomorodian (ed.), Proc. SoCG10: 26th Symposium on Computational [15] Joshua Kerievsky, Refactoring to Patterns, Pearson (2004) Geometry, 13-16 Jun 2010, Snowbird, Utah (2010) [16] Philippe Kruchten, “Architectural Blueprints The 4+1 View Model [38] Afra Zomorodian, Topological Data Analysis: Proc. 2011 AMS Short of Software Architecture”, IEEE Software, vol.12, no.6, pp.42-50 Course on Computational Topology, 04-05 Jan 2011, New Orleans, (November 1995) Louisiana, Symposia in Applied Mathematics, v.70, AMS (2012)