TRANSLATIONS OF NETWORK LANGUAGES D R A F T
Boris Stilman · 1994
Department of Computer Science & Engineering, University of Colorado at DenverCampus Box 109, Denver, CO 80217-3364. Email: [email protected] —In this paper we describe new results of research on geometrical properties of complexcontrol systems, the so-called Linguistic Geometry. This research includes the development ofsyntactic tools for knowledge representation and reasoning about large-scale hierarchical complexsystems. It relies on the formalization of search heuristics of high-skilled human experts that haveresulted in the development of successful applications in different areas. A hierarchy of subsystemsof a complex system, the networks of paths, is represented as a hierarchy of formal languages. Inthis paper we investigate transformations of these networks while system moves from one state toanother. The investigation consists of formal, constructive separation of changed and unchangedparts of system representation, the hierarchy of languages. Thus, we address the problem relativeto the well-known Frame Problem for planning systems. A partial solution is presented in the formof the theorem about translations of network languages. Formal considerations are illustrated byexample of Air Force robotic vehicles.1. Introduction Important real-world problems can be formally represented as problems of reasoning aboutcomplex control systems. The difficulties we meet trying to find the optimal operation for real -world complex systems are well known. While the formalization of the problem, as a rule, is notdifficult, an algorithm that finds its solution usually results in the search of many variations. Forsmall-dimensional toy problems a solution can be obtained; however, for most real-worldproblems the dimension increases and the number of variations increases significantly, usuallyexponentially, as a function of dimension [1]. Thus, most real-world search problems are notsolvable with the help of exact algorithms in a reasonable amount of time.There have been many attempts to design different approximate algorithms. One of thebasic ideas is to decrease the dimension of the real-world problem following the approach of ahuman expert in a certain field , by breaking the problem into smaller subproblems. There are twomost important issues in this decomposition.The first issue is to find out how to break a complex system down into subsystems, tostudy these subsystems separately or in combinations, making appropriate searches, and eventuallycombine optimal solutions for the subsystems into an approximately optimal solution for the entiresystem [2–4]. It is easy if the system can be decomposed into completely independent subsystems.Usually, the subsystems are not independent, and the system can be considered as nearlydecomposable [2]. For such problems we need the techniques that can handle each subsystemseparately and then introduce the impact of potential interactions of these subsystems into the finalsolution.The second issue is to avoid recomputation of the entire system state provided that systemoperates by moving from one state to another. Instead, we should consider only that part of thestate that may have changed. For complex systems the Problem of Change or Frame Problem [5–8] consists of representation of knowledge in such a way that we can effectively determine which