I. Ordonez and F. Zhao, ``STA: Spatio-Temporal Aggregation with Applications to Analysis of Diffusion-Reaction Phenomena.'' Proc. of AAAI, 2000. Copyright 2000, American Association for Artificial Intelligence (www.aaai.org).

Spatio-temporal data sets arise when time-varying physical fields are discretized for simulation or analysis. Examples of time-varying fields are isothermal regions in the sea or pattern formations in natural systems, such as convection rolls or diffusion-reaction systems. The analysis of these data sets is essential for generating qualitative interpretations for human understanding. This paper presents Spatio-Temporal Aggregation (STA), a system for recognizing and tracking qualitative structures in spatio-temporal data sets. STA algorithms record and maintain temporal events and compile event sequences into concise history descriptions. This is carried out at several levels of description, from the bottom up: first, low level events are identified and tracked, and then a subset of those events, relevant at the next description level, is identified. The process is iterated until a high level description of the system's temporal evolution is obtained. STA has been demonstrated on a class of diffusion-reaction systems in two dimensions and has successfully generated high-level symbolic descriptions of systems similar to those produced by scientists through carefully hand-tuned computational experiments.

(get full paper (pdf) here)

Sensor-rich systems typically employ extensive signal processing techniques for fault detection and isolation tasks. Sensor-poor systems, on the other hand, require system models and analytical redundancy techniques to make diagnostic inferences. The increasing availability of inexpensive, batch-fabricated micro-controllers and MEMS sensors enables deployment of a multitude of sensors and microprocessors for control and diagnosis of embedded systems. We develop a diagnosis method that combines model-based diagnosis with signal processing techniques to address the challenges in diagnosing complex systems with hybrid discrete/continuous behaviors and to reduce the computational requirements by focusing the signal processing algorithms. We demonstrate the approach on problems in reprographic copier paper path diagnosis.

(get full paper (pdf) here)

Contoured charts are widely used to visualize 2D physical fields. Experts can identify global patterns and structures in a contoured chart by looking at the iso-curves and reasoning about their spatial relations. We develop an algorithm for computing the topological adjacency relations between iso-contours. The algorithm is novel in that it grounds the computation of spatial relations between aggregate spatial objects upon the computation of relations between the constituents. It is scale-independent and efficient. We present an application of the algorithm to weather data analysis for extracting patterns from numerical weather datasets.

(get full paper here)

Recent rapid advances in MEMS and information processing technology have enabled a new generation of AI robotic systems -- so-called Smart Matter systems -- that are sensor rich and physically embedded. These systems range from decentralized control systems that regulate building temperature (smart buildings) to vehicle on-board diagnostic and control systems that interrogate large amounts of sensor data. One of the core tasks in the construction and operation of these Smart Matter systems is to synthesize optimal control policies using data rich models for the systems and environment. Unfortunately, these models may contain thousands of coupled real-valued variables and are prohibitively expensive to reason about using traditional optimization techniques such as neural nets and genetic algorithms. This paper introduces a general mechanism for automatically decomposing a large model into smaller subparts so that these subparts can be separately optimized and then combined. The mechanism decomposes a model using an influence graph that records the coupling strengths among constituents of the model. This paper demonstrates the mechanism in an application of decentralized optimization for a temperature regulation problem. Performance data has shown that the approach is much more efficient than the standard discrete optimization algorithms and achieves comparable accuracy.

(get full paper here)

Many important science and engineering applications, such as predicting weather patterns, controlling the temperature distribution over a semiconductor wafer, and controlling the noise of a photocopy machine, require interpreting data and designing decentralized controllers for spatially distributed systems. This thesis describes the Spatial Aggregation Language (SAL), a novel programming language and environment supporting data interpretation and control tasks for distributed physical systems. SAL provides a set of powerful, high-level components that make explicit use of domain-specific physical knowledge, such as metrics, adjacency relations, and equivalence predicates, in order to uncover and exploit structures in distributed physical data at multiple levels of abstraction. The language data types and operators manipulate structured representations of spatial objects in distributed physical systems at multiple levels of abstraction. The programming environment supports rapid prototyping of application programs and interactive manipulation of the resulting structures. In comparison with existing tools, the Spatial Aggregation Language offers high level programming abstractions explicitly encoding physical knowledge; this approach supports a variety of inference, explanation, tutoring, and design tasks.

This thesis presents as a case study novel approaches to decentralized control design, in the context of thermal regulation. This case study develops novel algorithms for control placement and parameter design for systems with large numbers of coupled variables. These algorithms exploit physical knowledge of locality, linear superposability, and continuity, encapsulated in influence graphs representing dependencies of field nodes on control nodes. The control placement design algorithms utilize influence graphs to decompose a problem domain so as to decouple the resulting regions. The decentralized control parameter optimization algorithms utilize influence graphs to efficiently evaluate thermal fields and to explicitly trade off computation, communication, and control quality. By leveraging the physical knowledge encapsulated in influence graphs, these control design algorithms are more efficient than standard techniques, and produce designs explainable in terms of problem structures. This case study demonstrates the utility of the Spatial Aggregation Language operators in supporting the programming of these computations in a vocabulary natural for the domain.

(get thesis document here)

This paper describes problems, challenges, and opportunities for {\em intelligent simulation} of physical systems. Prototype intelligent simulation tools have been constructed for interpreting massive data sets from physical fields and for designing engineering systems. We identify the characteristics of intelligent simulation and describe several concrete application examples. These applications, which include weather data interpretation, distributed control optimization, and spatio-temporal diffusion-reaction pattern analysis, demonstrate that intelligent simulation tools are indispensable for the rapid prototyping of application programs in many challenging scientific and engineering domains.

(get full paper (pdf) here)

This paper describes a diagnostic system for processing high-bandwidth vibration data from distributed sensors for monitoring and diagnosis of electromechanical machines. The system employs time-frequency and principal component analysis techniques to extract and compress features and a Bayesian decision analysis to combine and classify data from multiple sources. Experimental multi-sensor diagnosis results are reported for classifying motor and solenoid vibration signatures from the paper drive plate of the Xerox DC265 digital copier.

(get full paper (pdf) here)

Intelligent simulation is a new problem-solving paradigm for data interpretation and control tasks in science and engineering. Because of rapid advances in information processing and microelectronics, many practical applications require real-time interpretation of information in order to effectively interact with the environment. The information is often in a data-rich form such as images, videos, or spatially distributed measurements of physical processes. For example, a network of computational agents embedded in a "smart building" must stitch together local measurements in order to ensure occupant comfort while minimizing energy consumption.

This tutorial introduces a body of computational theories, techniques, and languages collectively called intelligent simulation. We will develop imagistic reasoning techniques for finding structures in large scientific and engineering data sets and the spatial aggregation (SA) language for rapid prototyping of imagistic problem solvers. SA draws upon the experience gained in developing applications in a number of challenging domains such as data analysis and visualization (KAM), control (MAPS), and mechanical design (HIPAIR); it incorporates techniques from computer vision, qualitative reasoning, scientific computing, and computational geometry. We will demonstrate how new applications can be prototyped with the SA language, using case studies including weather data interpretation, fluid simulation, and nonlinear maglev control design. No previous knowledge of intelligent simulation is required.

(get slides handout (2 per page) here)

This paper presents an algorithm for verifying control laws using phase-space geometric modeling of dynamical systems. The algorithm evolves a hierarchically-refined bound of system nonlinear dynamics and can address practical concerns such as sensor, actuator, and modeling uncertainties in a systematic manner. The algorithm has been applied to verifying a control law for a magnetic levitation system, and the computational results are compared against the performance of the actual physical system.

(get full paper here)

We describe the Phase-Space Nonlinear Control Toolbox, a suite of computational tools for synthesizing, evaluating, and verifying control laws for a broad class of nonlinear dynamical systems. The Toolbox comprises computational algorithms for identifying optimal control reference trajectories in the phase space of dynamical systems, experimental methods for evaluating performance of the control laws, and algorithms for verifying correct behaviors of the synthesized control laws. These algorithms combine knowledge of the geometric theory of modern nonlinear dynamical systems with efficient computational methods for geometric reasoning and graph search. They define the properties of controllability and robustness in terms of phase-space geometric structures and exploit the phase-space neighborhood adjacencies to obtain computational efficiency. They evolve a hierarchically-refined bound of system nonlinear dynamics during verification and can address practical concerns such as sensor, actuator, and modeling uncertainties in a systematic manner. Compared to the traditional analytic control design methods, the phase-space based control synthesis and verification rely on high-performance computational techniques and are applicable to physical systems operating in large nonlinear regimes. Using a proof-of-concept physical experiment for stabilizing a nonlinear magnetic levitation system, we have successfully demonstrated the feasibility of the phase-space control technology.

(get full paper here)

Many important physical phenomena, such as temperature distribution, air flow, and acoustic waves, are described as continuous, distributed parameter fields. Analyzing and controlling these physical processes and systems are common tasks in many scientific and engineering domains. However, the challenges are multifold: distributed fields are conceptually harder to reason about than lumped parameter models; computational methods are prohibitively expensive for complex spatial domains; the underlying physics imposes severe constraints on observability and controllability.

This paper develops an ontological abstraction and a structure-based design mechanism, in a framework collectively known as spatial aggregation (SA), for reasoning about and synthesizing distributed control schemes for physical fields. The ontological abstraction models a physical field as a hierarchy of networks of spatial objects. SA applies a small number of generic operators to a field to compute concise structural descriptions such as iso-contours, gradient trajectories, and influence graphs. The design mechanism uses these representations to find feasible control configurations. We illustrate the mechanism using a thermal control problem from industrial heat treatment and demonstrate that the active exploitation of structural knowledge in physical fields yields a significant computational advantage.

(get full paper here)

We develop the influence graph mechanism for reasoning about and optimizing decentralized controls for distributed parameter physical systems. Distributed parameter systems, such as air flow around an airplane wing, temperature over a semiconductor wafer, and noise from a photocopy machine, are common physical phenomena. The influence graph mechanism encodes the structural dependency information in a distributed parameter system and exploits the information to (1) alleviate redundant computation and (2) reduce communication and support cooperation among local control processes. Using the mechanism, we obtained a dramatic computational speed-up in optimizing control design for a distributed temperature field.

(get full paper here)

Regularities exist in datasets describing spatially distributed physical phenomena. Human experts often understand and verbalize the regularities as abstract spatial objects evolving coherently and interacting with each other in the domain space. We describe a novel computational approach for identifying and extracting these abstract spatial objects through the construction of a hierarchy of spatial relations. We demonstrate the approach with an application to finding troughs in weather data sets.

(get full paper here)

X. Huang and F. Zhao, ``Finding Structures in Weather Maps.'' Tech. Report OSU-CISRC-3/98-TR11, Dept. of Comp. & Info. Sci., Ohio State, March, 1998.

We describe an effective computational method for extracting structural information from spatial data sets. For instance, the structural information such as the location, shape, size, and movement about pressure cells and troughs are important for weather prediction. We are interested in extracting these structures and representing them at aggregate levels where salient geometric features are highlighted. The computational challenge is to quantify these features at multiple levels of granularity and find them incrementally. We introduce two types of spatial adjacency relations for spatial objects and present an effective algorithm for extracting and abstracting structural objects using the relational information. An application to finding local pressure cells in the weather data sets is demonstrated.

Keywords. Spatial knowledge discovery, proximity relationships, weather map analysis, spatial reasoning, computational tools and algorithms.

(get full paper here)

I. Ordonez and F. Zhao, ``An Algorithm for Identifying and Tracking Structures in Time-Varying Physical Fields.'' Tech. Report OSU-CISRC-9/98-TR39, Dept. of Comp. & Info. Sci., Ohio State, Sept. 1998.

Data sets modeling spatially distributed physical phenomena often exhibit regions of uniformity. Example of such data sets include spatial patterns in certain Diffusion-Reaction systems, weather maps, and pressure distribution in regions of sea. This paper describes an algorithm for identifying and tracking coherent regions in spatial fields produced by a class of diffusion-reaction systems. Such systems describe a number of physical, chemical, and biological phenomena, and their study may shed light on how nature constructs and evolves structures that exhibit a high degree of regularity. The algorithm adaptively samples a spatial field using a particle system, aggregates the sampled points into a neighborhood graph, classifies the structure into coherent regions, and tracks the regions over time to produce a qualitative description of the temporal evolution of the field. Because the adaptive sampling grid varies smoothly with the temporal evolution of the underlying field, the algorithm is able to efficiently track the corresponding objects over successive time frames by minimally updating the grid.

(get full paper in postscript or in PDF here)

F. Zhao, S. Loh and J. May, ``Phase-Space Nonlinear Control Toolbox: The Maglev Experience.'' Hybrid Systems '97.

We describe the Phase-Space Nonlinear Control Toolbox, a suite of computational tools for synthesizing and evaluating control laws for a broad class of nonlinear dynamical systems. The Toolbox comprises computational algorithms for identifying optimal control reference trajectories in the phase space of dynamical systems and experimental methods for evaluating performance of the control laws. These algorithms combine knowledge of the geometric theory of modern nonlinear dynamical systems with efficient computational methods for geometric reasoning and graph search; they define the property of controllability and robustness in terms of phase-space geometric structures and exploit the phase-space neighborhood adjacencies to obtain computational efficiency. Compared to the traditional analytic control design methods, the phase-space based control synthesis and evaluation rely on high-performance computational techniques and are applicable to physical systems operating in large nonlinear regimes. Using a proof-of-concept physical experiment for stabilizing a nonlinear magnetic levitation system, we have successfully demonstrated the feasibility of the phase-space control technology.

(get full paper here)

Many important physical phenomena, such as temperature distribution, air flow, and acoustic waves, are described as continuous, distributed parameter fields. Controlling and optimizing these physical processes and systems are common design tasks in many scientific and engineering domains. However, the challenges are multifold: distributed fields are conceptually harder to reason about than lumped parameter models; computational methods are prohibitively expensive for complex spatial domains; the underlying physics imposes severe constraints on observability and controllability.

This paper develops an ontological abstraction and an aggregation-disaggregation mechanism, in a framework collectively known as spatial aggregation (SA), for reasoning about and synthesizing distributed control schemes for physical fields. The ontological abstraction models physical fields as networks of spatial objects. The aggregation-disaggregation mechanism employs a set of data types and generic operators to find a feasible control structure, specifying control placement and associated actions that satisfy given constraints. SA abstracts common computational patterns of control design and optimization in a small number of operators to support modular programming; it builds concise and articulable structural descriptions for physical fields. We illustrate the use of the SA ontological abstraction and operators in an example of regulating a thermal field in industrial heat treatment.

Keywords. Qualitative reasoning; Spatial reasoning; Ontologies; Decentralized control; Distributed AI; Programming languages.

(get full paper here)

Hybrid systems possess continuous dynamics defined within regions of state spaces and discrete transitions among the regions. Many practical control verification and synthesis tasks can be reduced to reachability problems for these systems that decide if a particular state-space region is reachable from an initial operating region. In this paper, we present a computational analysis of the face reachability problem for a class of three-dimensional dynamical systems whose state spaces are defined by piecewise constant vector fields and whose trajectories never return to a state- space region once they exit the region. These systems represent a restricted class of control systems whose dynamics results from a juxtaposition of piecewise parame terized vector fields. We had previously developed a computational algorithm for synthesizing the desired dynamics of a system in phase space by piecing together vector fields geometrically. We demonstrate in this paper that the reachability prob lem for this class of systems is decidable while the computation is provably intrac table (i.e., PSPACE-hard). We prove the intractability via a reduction of satisfiability of quantified boolean formulas to this reachability problem. This result sheds light on the computational complexity of phase-space based control synthesis methods and extends the work of Asarin, Maler, and Pnueli (1995) that proves com putational undecidability for three-dimensional constant-derivative systems.

(get full paper here)

P.J. Mosterman, F. Zhao, G. Biswas, ``Model semantics and simulation for hybrid systems operating in sliding regimes.'' AAAI 1997 Fall Symposium on Model-Directed Autonomous Systems, Cambridge, MA, Nov. 1997.

We describe a model semantics and a simulation algorithm for characterizing a class of dynamic physical systems operating in the so-called sliding regimes. Many continuous physical systems operate at multiple time scales. To simplify behavior generation, we often abstract away details at faster time scales or near discontinuous boundaries and describe the resulting system as a hybrid system with distinct modes. Mode transitions are induced by internal state changes or external control signals. It is common for such systems to exhibit chattering behaviors at the discontinuous transition boundaries which presents challenges to conventional numerical methods for analyzing system behaviors. We present an efficient, adaptive algorithm for simulating this class of systems, based on a careful analysis of the model semantics at the boundaries of discontinuity. Simulation results show that the algorithm is chatter free and more efficient than conventional integration methods for sliding-mode systems.

(get full paper here)

F. Zhao and V. I. Utkin, ``Adaptive Simulation and Control of Variable-Structure Control Systems in Sliding Regimes.'' Automatica, 32(7):1037-1042, Pergamon, 1996.

Conventional simulation and control methods for sliding mode control systems are limited by the available sampling bandwidth and allowable tracking error. Consequently, these methods suffer from harmful chattering. This paper presents an adaptive method for the discrete-time simulation and control of sliding mode control systems, based on an analysis on the relationship between tracking error and sampling rate for these systems. Our analysis shows that the tracking error decreases as the sampling time interval decreases when the sliding condition exists. The adaptive method exploits the concept of discrete-time sliding mode; the method adjusts its sampling rate to ensure that the tracking error is bounded within a boundary layer of the sliding surface. To simulate a sliding mode system in discrete time, we present an adaptive integration scheme that follows the ideal system within a given tolerance. Likewise, the adaptive method can be used to generate discrete control signals for sliding mode systems. Simulation results on examples have shown that the adaptive method is free of chattering.

(get full paper here)

C. Bailey-Kellogg, F. Zhao, and K. Yip, ``Spatial Aggregation: Language and Applications.'' Proc. of AAAI, 1996.

Spatial aggregation is a framework for organizing computations around image-like, analogue representations of physical processes in data interpretation and control tasks. It conceptualizes common computational structures in a class of implemented problem solvers for difficult scientific and engineering problems. It comprises a mechanism, a language, and a programming style. The spatial aggregation mechanism transforms a numerical input field to successively higher-level descriptions by applying a small, identical set of operators to each layer given a metric, neighborhood relation and equivalence relation. This paper describes the spatial aggregation language and its applications.

The spatial aggregation language provides two abstract data types --- neighborhood graph and field --- and a set of interface operators for constructing the transformations of the field, together with a library of component implementations from which a user can mix-and-match and specialize for a particular application. The language allows users to isolate and express important computational ideas in different problem domains while hiding low-level details. We illustrate the use of the language with examples ranging from trajectory grouping in dynamics interpretation to region growing in image analysis. Programs for these different task domains can be written in a modular, concise fashion in the spatial aggregation language.

Keywords: Qualitative Reasoning, geometric/spatial reasoning, programming language, ontologies, applications.

(get full paper here)

K. Yip and F. Zhao, ``Spatial Aggregation: Theory and Applications.'' J. of Artificial Intelligence Research, Vol. 5, Aug 1996, pp. 1-26.

Visual thinking plays an important role in scientific reasoning. Based on the research in automating diverse reasoning tasks about dynamical systems, nonlinear controllers, kinematic mechanisms, and fluid motion, we have identified a style of visual thinking, imagistic reasoning. Imagistic reasoning organizes computations around image-like, analogue representations so that perceptual and symbolic operations can be brought to bear to infer structure and behavior. Programs incorporating imagistic reasoning have been shown to perform at an expert level in domains that defy current analytic or numerical methods.

We have developed a computational paradigm, spatial aggregation, to unify the description of a class of imagistic problem solvers. A program written in this paradigm has the following properties. It takes a continuous field and optional objective functions as input, and produces high-level descriptions of structure, behavior, or control actions. It computes a multi-layer of intermediate representations, called spatial aggregates, by forming equivalence classes and adjacency relations. It employs a small set of generic operators such as aggregation, classification, and localization to perform bidirectional mapping between the information-rich field and successively more abstract spatial aggregates. It uses a data structure, the neighborhood graph, as a common interface to modularize computations. To illustrate our theory, we describe the computational structure of three implemented problem solvers -- KAM, MAPS, and HIPAIR --- in terms of the spatial aggregation generic operators by mixing and matching a library of commonly used routines.

(get full paper in pdf or ps here)

K. Yip, F. Zhao and E Sacks, ``Imagistic Reasoning.'' ACM Computing Survey, Sept 1995.

Imagistic reasoning is a new paradigm for understanding sensory data and controlling environment based on the construction, interpretation, and manipulation of image-like, analog representations of physical systems. The reasoning is primarily perceptual and only secondarily symbolic. In the past decade, we have built several imagistic reasoners that perform at an expert level on scientific problems that defy current analytical methods, including helping us solve open problems. We hypothesize that much of scientific reasoning is imagistic and that this reasoning is best automated by imagistic algorithms. The classical artificial intelligence architecture---a central deductive reasoner operating on symbolic predicates delivered by low-level perceptual preprocessors---is unsuitable for these tasks. Imagistic reasoners are faster and more efficient because they trade many inferences for sensing and action. Their behavior is easier to understand and debug because they deal directly with geometric structures and their interactions.

(hardcopy available upon request)

F. Zhao, ``Intelligent Simulation in Designing Complex Dynamical Control Systems'', Book chapter in Artificial Intelligence in Industrial Decision Making, Control, and Automation, Tzafestas and Verbruggen (eds.), pp. 127-158, Kluwer, 1995.

We develop and demonstrate an autonomous control synthesis system called Phase Space Navigator for nonlinear control systems, with which a global, nonlinear controller for a dynamical system can be automatically synthesized. The Phase Space Navigator intelligently plans and navigates system trajectories in phase space. It finds optimal global paths from an initial state to the goal state in the phase space, consisting of a sequence of path segments connected at intermediate points where the control parameter changes. The method relies on the knowledge of dynamics in terms of phase-space geometry. Modeling and parsing phase spaces into trajectory flow pipes provide a way to efficiently reason about the phase-space structures and search for global control paths. The Phase Space Navigator has automatically synthesized a high-quality global controller for stabilizing a maglev train.

The Phase Space Navigator is particularly suitable for synthesizing high-performance control systems that do not lend themselves to traditional design and analysis techniques. It can also assist control engineers in exploring much larger design spaces than otherwise possible.

Keywords. Artificial intelligence; control system synthesis; computer-aided design; nonlinear control systems; numeric/symbolic processing.

(get full paper here)

F. Zhao, ``Extracting and Representing Qualitative Behaviors of Complex Systems in Phase Spaces'', Artificial Intelligence, 69(1-2):51-92, 1994.

This paper presents a computational method for automatically analyzing qualitative behaviors of complex dynamical systems in phase space. To demonstrate this method, a program called MAPS has been constructed that understands qualitatively distinct features of a phase space and represents geometric information about these features in a dimension-independent description, using deep domain knowledge of dynamical systems theory. Given a dynamical system specified as a system of governing equations, MAPS incrementally extracts the qualitative information about the system in terms of a qualitative phase-space structure describing steady-state behaviors, stabilities, and transient properties. MAPS generates a high-level symbolic description of the system sensible to human beings and manipulable by other programs, through a combination of numerical, combinatorial, and geometric computations and spatial reasoning techniques. MAPS has successfully demonstrated its power in a difficult engineering domain of nonlinear control design.

(get full paper here)

F. Zhao, ``Intelligent Computing About Complex Dynamical Systems.'' Mathematics and Computers in Simulation, 36:423-432, Elsevier, 1994.

We develop computational mechanisms for intelligently simulating nonlinear control systems. These mechanisms enhance numerical Simulations with deep domain knowledge of dynamical systems theory and control theory, a qualitative phase-space representation of dynamical systems, symbolic and geometric manipulation capabilities, and a high-level interface. Programs equipped with these capabilities are able to autonomously simulate a dynamical system, analyze the simulation results, and utilize the analysis to perform design tasks. We demonstrate the mechanisms with an implemented computational environment called the Control Engineer's Workbench.

(get full paper here)

F. Zhao, ``Computational Dynamics: Modeling and Visualizing Trajectory Flows in Phase Space.'' Annals of Mathematics and Artificial Intelligence, 8(3-4):285-300, 1993.

This paper describes a computational technique for modeling and Visualizing dynamical behaviors of complex systems in phase space. The technique employs a novel idea of flow pipes to model trajectory bundles that exhibit the same qualitative features. It parses a continuous phase space of a dynamical system, consisting of an infinite number of individual trajectories, into a manageable discrete collection of flow pipes that a computer can efficiently reason about. The technique provides a computational way for both machines and humans to visualize and manipulate dynamics of a physical system.

The flow-pipe modeling technique is implemented in a program called MAPS. The technique has been applied to the automatic control synthesis in which programs automatically analyze and design high-performance, global controllers.

(get full paper here)

E. Bradley and F. Zhao, ``Phase-Space Control System Design.'' IEEE Control Systems, 13(2):39-47, 1993.

This paper describes a computational environment that has been developed to aid control system design for a particular class of nonlinear applications. The analysis and design tools comprising this environment are based upon knowledge about phase-space dynamics of nonlinear and chaotic systems. We describe two implemented, complementary programs that exploit the special properties of such systems to automatically synthesize powerful control systems. Phase Space Navigator visualizes phase-space dynamics through flow pipes and navigates systems along automatically synthesized reference trajectories. Perfect Moment} identifies and uses chaotic phase-space features like strange attractors in its segmented control trajectories, gaining otherwise-unobtainable performance. Though the phase-space paradigm is very powerful, its global and computationally-intensive nature makes some of the techniques that exploit it difficult to implement. Fast computers and powerful computational techniques that combine symbolic/numeric and algebraic/geometric computing with new reasoning mechanisms from artificial intelligence make this paradigm feasible in spite of its inherent demands.

(hardcopy available upon request)

F. Zhao, ``Automatic Analysis and Synthesis of Controllers for Dynamical Systems Based on Phase-Space Knowledge'', PhD Thesis, Technical Report AI-TR-1385, M.I.T. AI Lab, Sept. 1992.

This thesis presents a novel design methodology for the synthesis of automatic controllers, together with a computational environment---the Control Engineer's Workbench---integrating a suite of programs that automatically analyze and design controllers for high-performance, global control of nonlinear systems. This work demonstrates that difficult control synthesis tasks can be automated, using programs that actively exploit and efficiently represent knowledge of nonlinear dynamics and phase space and effectively use the representation to guide and perform the control design. The Control Engineer's Workbench combines powerful numerical and symbolic computations with spatial reasoning techniques. The two major programs in the Workbench---Phase Space Navigator and MAPS---work together to model and reason about the phase-space geometry and topology of a given system, to plan global control reference trajectories, and to navigate the system along the planned trajectories. They use a novel technique of ``flow pipes'' to group infinite numbers of distinct behaviors into a manageable discrete set that becomes the basis for establishing the reference trajectories.

As a demonstration of this approach, I exhibit the automatic design of a nonlinear controller for a magnetic levitation system. The control system synthesized by the Workbench can stabilize a maglev vehicle with large initial displacements from an equilibrium and outperform the classical linear feedback design for the same system by a factor of 20.

Keywords. Artificial intelligence, scientific computing, control system design, numeric/symbolic processing, qualitative reasoning, geometric modeling, nonlinear dynamics.

(hardcopy available upon request)

F. Zhao, ``Machine Recognition as Representation and Search --- A Survey'', Int'l J. of Pattern Recognition & Artificial Intelligence, 5(5):715-747, Dec. 1991.

Generality, representation, and control have been the central issues in machine recognition. Model-based recognition is the search for consistent matches of the model and image features. We present a comparative framework for the evaluation of different approaches, particularly those of Acronym, Raf, and Ikeuchi et al. The strengths and weaknesses of these approaches are discussed and compared and the remedies are suggested. Various tradeoffs made in the implementations are analyzed with respect to the systems' intended task-domains. The requirements for a versatile recognition system are motivated. Several directions for future research are pointed out.

Keywords: computer vision, model-based recognition, representation, object modeling, search control, consistent labeling.

(hardcopy available upon request)

F. Zhao and L. Johnsson, ``The Parallel Multipole Method on the Connection Machine'', SIAM J. on Scientific & Statistical Computing, 12(6):1420-1437, 1991.

This paper reports on a fast implementation of the three-dimensional non-adaptive Parallel Multipole Method (PMM) on the Connection Machine system model CM--2. The data interactions within the decomposition tree are modeled by a hierarchy of three dimensional grids forming a pyramid in which parent nodes have degree eight. The base of the pyramid is embedded in the Connection Machine as a three dimensional grid. The standard grid embedding feature is used. For 10 or more particles per processor the communication time is insignificant. The evaluation of the potential field for a system with 128k particles takes 5 seconds, and a million particle system about 3 minutes. The maximum number of particles that can be represented in 2G bytes of primary storage is ~ 50 million. The execution rate of this implementation of the PMM is at about 1.7 Gflops/sec for a particle-processor-ratio of 10 or greater. A further speed improvement is possible by an improved use of the memory hierarchy associated with each floating-point unit in the system.

(get full paper here)

F. Zhao, ``An O(N) Algorithm for Three-dimensional N-body Simulations'', Technical Report AI-TR-995, M.I.T. AI Lab, Oct. 1987.

We develop an algorithm that computes the gravitational potentials and forces on N point-masses interacting in three-dimensional space. The algorithm, based on analytical techniques developed by Rokhlin and Greengard, runs in order N time. In contrast to other fast N-body methods such as tree codes, which only approximate the interaction potentials and forces, this method is exact---it computes the potentials and forces to within any prespecified tolerance up to machine precision. We present an implementation of the algorithm for a sequential machine. We numerically verify the algorithm, and compare its speed with that of an O(N^2) direct force computation. We also describe a parallel version of the algorithm that runs on the Connection Machine in order O(log N) time. We compare experimental results with those of the sequential implementation and discuss how to minimize communication overhead on the parallel machine.

(get full paper (pdf) here)