Context-free languages over infinite alphabets

In this paper we introduce context-free grammars and pushdown automata over infinite alphabets. It is shown that a language is generated by a context-free grammar over an infinite alphabet if and only if it is accepted by a pushdown automaton over an infinite alphabet. Also the generated (accepted) languages possess many of the properties of the ordinary context-free languages: decidability, closure properties, etc.. This provides a substantial evidence for considering context-free grammars and pushdown automata over infinite alphabets as a natural extension of the classical ones. Received November 27, 1995 / March 4, 1997     

An Autonomous Spacecraft Agent Prototype

This paper describes the New Millennium Remote Agent (NMRA) architecture for autonomous spacecraft control systems. The architecture supports challenging requirements of the autonomous spacecraft domain not usually addressed in mobile robot architectures, including highly reliable autonomous operations over extended time periods in the presence of tight resource constraints, hard deadlines, limited observability, and concurrent activity. A hybrid architecture, NMRA integrates traditional real-time monitoring and control with heterogeneous components for constraint-based planning and scheduling, robust multi-threaded execution, and model-based diagnosis and reconfiguration. Novel features of this integrated architecture include support for robust closed-loop generation and execution of concurrent temporal plans and a hybrid procedural/deductive executive.We implemented a prototype autonomous spacecraft agent within the architecture and successfully demonstrated the prototype in the context of a challenging autonomous mission scenario on a simulated spacecraft. As a result of this success, the integrated architecture has been selected to fly as an autonomy experiment on Deep Space One (DS-1), the first flight of NASA';s New Millennium Program (NMP), which will launch in 1998. It will be the first AI system to autonomously control an actual spacecraft.     

Rapid Anisotropic Diffusion Using Space-Variant Vision

Many computer and robot vision applications require multi-scale image analysis. Classically, this has been accomplished through the use of a linear scale-space, which is constructed by convolution of visual input with Gaussian kernels of varying size (scale). This has been shown to be equivalent to the solution of a linear diffusion equation on an infinite domain, as the Gaussian is the Green's function of such a system (Koenderink, 1984). Recently, much work has been focused on the use of a variable conductance function resulting in anisotropic diffusion described by a nonlinear partial differential equation (PDE). The use of anisotropic diffusion with a conductance coefficient which is a decreasing function of the gradient magnitude has been shown to enhance edges, while decreasing some types of noise (Perona and Malik, 1987). Unfortunately, the solution of the anisotropic diffusion equation requires the numerical integration of a nonlinear PDE which is a costly process when carried out on a uniform mesh such as a typical image. In this paper we show that the complex log transformation, variants of which are universally used in mammalian retino-cortical systems, allows the nonlinear diffusion equation to be integrated at exponentially enhanced rates due to the nonuniform mesh spacing inherent in the log domain. The enhanced integration rates, coupled with the intrinsic compression of the complex log transformation, yields a speed increase of between two and three orders of magnitude, providing a means of performing rapid image enhancement using anisotropic diffusion.     

Conjectural Equilibrium in Multiagent Learning

Learning in a multiagent environment is complicated by the fact that as other agents learn, the environment effectively changes. Moreover, other agents' actions are often not directly observable, and the actions taken by the learning agent can strongly bias which range of behaviors are encountered. We define the concept of a conjectural equilibrium, where all agents' expectations are realized, and each agent responds optimally to its expectations. We present a generic multiagent exchange situation, in which competitive behavior constitutes a conjectural equilibrium. We then introduce an agent that executes a more sophisticated strategic learning strategy, building a model of the response of other agents. We find that the system reliably converges to a conjectural equilibrium, but that the final result achieved is highly sensitive to initial belief. In essence, the strategic learner's actions tend to fulfill its expectations. Depending on the starting point, the agent may be better or worse off than had it not attempted to learn a model of the other agents at all.     

Extracting Hidden Context

Concept drift due to hidden changes in context complicates learning in many domains including financial prediction, medical diagnosis, and communication network performance. Existing machine learning approaches to this problem use an incremental learning, on-line paradigm. Batch, off-line learners tend to be ineffective in domains with hidden changes in context as they assume that the training set is homogeneous. An off-line, meta-learning approach for the identification of hidden context is presented. The new approach uses an existing batch learner and the process of contextual clustering to identify stable hidden contexts and the associated context specific, locally stable concepts. The approach is broadly applicable to the extraction of context reflected in time and spatial attributes. Several algorithms for the approach are presented and evaluated. A successful application of the approach to a complex flight simulator control task is also presented.     

Summative evaluation of the SINCGARS Tutor

In an earlier set of studies with a different Intelligently Coached Simulation (Orey, M.A., Fan, H., Park, J., Tzeng, S., & Gustafson, K. (1995). Evaluation of Device operator in a context of a coached simulation environment), we found a retention and a transfer problem. We tried to solve these problems while building a new Intelligently Coached Simulation (the SINCGARS Tutor). The solutions to the two problems were to use an interactive conceptual model for the retention problem and we used photographs of the equipment as the visuals of the simulation. We then tested this new tutor with a group of 22 officers who were not only required to know how to operate the SINCGARS radio, but would be responsible for teaching others in their unit when their training was complete. We had one group of officers train on the real equipment, in pairs, with one instructor available for guidance. The other group of 11 learned via the SINCGARS Tutor. The post test was to put an actual radio into operation while being observed by a trained observer. Results indicate that not only did the transfer problem go away, but officers trained on the computer performed the task more accurately both initially on the immediate post test and again on a surprise four-week delayed post test. The SINCGARS Tutor was found to be a very good training solution.     

Oxide dispersion strengthening of nickel electrodeposits for microsystem applications

Oxide dispersion strengthened nickel (ODS-Ni) electrodeposits were fabricated to net shape using the lithography, electroforming, and molding (LIGA) process in a nickel sulfamate bath containing a suspension of 10 nm diameter Al₂O₃ particulates. Mechanical properties were compared to baseline specimens fabricated using an identical sulfamate bath chemistry without the particulates. Results revealed that the as-deposited ODS-Ni exhibited significantly higher yield strength and ultimate tensile strength (∼50 pct) than the baseline material. This increase in as-deposited strength was attributed to Orowan strengthening. The ODS-Ni also showed improved retention of room-temperature strength after annealing over a range of temperatures up to 600 °C. Nanoindentation measurements revealed that the properties of the dispersion-strengthened deposit were uniform through its thickness, even in narrow, high aspect ratio structures. Microscopy revealed that this resistance to anneal softening was due to an inhibition of grain growth in the presence of the oxide dispersion. At elevated temperatures, the strength of the ODS-Ni was approximately 3 times greater than that of the baseline material although with a significant reduction in hot ductility.     

Mutilated chessboard problem is exponentially hard for resolution

Mutilated chessboard principle CB_n says that it is impossible to cover by domino tiles the chessboard 2n×2n with two diagonally opposite corners removed. We prove lower bound on the size of minimal resolution refutation of CB_n.     

Robust and Rapid Generation of Animated Faces from Video Images: A Model-Based Modeling Approach

We have developed an easy-to-use and cost-effective system to construct textured 3D animated face models from videos with minimal user interaction. This is a particularly challenging task for faces due to a lack of prominent textures. We develop a robust system by following a model-based approach: we make full use of generic knowledge of faces in head motion determination, head tracking, model fitting, and multiple-view bundle adjustment. Our system first takes, with an ordinary video camera, images of a face of a person sitting in front of the camera turning their head from one side to the other. After five manual clicks on two images to indicate the position of the eye corners, nose tip and mouth corners, the system automatically generates a realistic looking 3D human head model that can be animated immediately (different poses, facial expressions and talking). A user, with a PC and a video camera, can use our system to generate his/her face model in a few minutes. The face model can then be imported in his/her favorite game, and the user sees themselves and their friends take part in the game they are playing. We have demonstrated the system on a laptop computer live at many events, and constructed face models for hundreds of people. It works robustly under various environment settings.