We address the problem of observing a moving agent. In particular, we propose a system for observing a manipulation process, where a robot hand manipulates an object. A discrete event dynamic system (DEDS) from work is developed for the hand-object interaction over time and a stabilizing observer is constructed. Low-level modules are developed for recognizing the ``events'' that causes state transitions within the dynamic manipulation system. The work examines closely the possibilities for errors, mistakes and uncertainties in the manipulation system, observer construction process and event identification mechanisms. The system utilizes different tracking techniques in order to observe the task in an active, adaptive and goal-directed manner.
We are conducting research in the area of teleoperation with feedback delay. Delay occurs with earth-based teleoperation in space and with surface-based teleoperation with untethered submersibles when acoustic communication links are involved. the delay in obtaining position and force feedback from remote slave arms makes teleoperation extremely difficult. We are proposing a novel combination of graphics and manipulator programming to solve the problem by interfacing a teleoperator master arm to a graphics based simulator of the remote environment coupled with a robot manipulator at the remote, delayed site. the operator's actions will be monitored to provide both kinesthetic and visual feedback and to generate symbolic motion commands to the remote slave. the slave robot will then execute these symbolic commands delayed in time. While much of a task will proceed error free, when an error does occur the slave system will transmit data back to the master and the master environment will be ``reset'' to the error state.
We describe techniques for interactively controlling bipedal articulated figures through kinematic constraints. These constraints model certain behavioral tendencies which capture some of the characteristics of human-like movement, and give us control over such elements as the figures' balance and stability. They operate in near real-time, so provide behavioral control for interactive manipulation. These constraints form the basis of an interactive motion-generation system that allows the active movement elements to be layered on top of the passive behavioral constraints.
Hands have for centuries been recognized as a fundamental tool for humans to gain an understanding of their environment and at the same time be able to manipulate it. In this presentation we will look at various studies made on the functionality and use of the human hand and examine the different approaches to analyzing and classifying human grasps and building a taxonomy of these grasps. We study the anatomy of the human hand, and examine experiments performed to understand the how gripping forces are applied when lifting objects, and the methods extraction of haptic information, by humans.
We discuss issues involved in the building of electro-mechanical manipulators and some of the mathematics used in analyzing the suitability of a design. We look at one of the earliest designs of a computer controlled articulated gripper, as well as two of the most prevalent designs in today's research world, the Stanford/JPL hand and the Utah/MIT had. Finally, we show why a more fundamental understanding of how human grasping works will help us design more useful manipulators.
In this paper we present the description and experiments with a tightly coupled Hand-Eye-Arm manipulatory system. We explain the philosophy and the motivation for building a tightly coupled system that actually consists of very autonomous modules that communicate with each other via a central coordinator. We describe each of the modules in the system and their interactions with each other. We highlight the need for sensory driven manipulation, and explain how the above system, where the hand is equipped with multiple tactile sensors, is capable of both manipulating unknown objects, but also detecting and complying in the case of collisions. We explain the partition of the control of the system into various closed loops, representing coordination both at the level of gross manipulator motions as well as fine motions. We describe the various modes that the system can work in , as well as some of the experiments that are being currently performed using this system.
We present efficient emulations of the CRCW PRAM on a large class of processor interconnection networks called leveled networks. This class includes the star graph and the n-way shuffle, which have the interesting property that the network diameter is sub-logarithmic in the network size. We show that a CRCW PRAM can be emulated optimally on these networks (i.e., each emulation step takes time linear in the network diameter). this is the first result that demonstrates PRAM emulation in less than logarithmic time.
We also present an efficient emulation of the CRCW PRAM on an n x n mesh. Although an O(n)-time emulation algorithm for the mesh is known, the underlying constant in the run-time is large, making it impractical. We give an improved emulation algorithm whose time bound is only 4n + o(n).
We present a critical review of descriptive complexity approaches to inductive inference. Inductive inference is defined as any process by which a model of the world is formed from observations. The descriptive complexity approach is a formalization of Occam's razor: choose the simplest model consistent with the data. Descriptive complexity as defined by Kolmogorov, Chaitin and Solomonoff is presented as a generalization of Shannon's entropy. We discuss its relationship with randomness and present examples. However, a major result of the theory is negative: descriptive complexity is uncomputable.
Rissanen's minimum description length (MDL) principle is presented as a restricted form of the descriptive complexity which avoids the uncomputability problem. We demonstrate the effectiveness of MDL through its application to AR processes. Lastly, we present and discuss LeClerc's application of MDL to the problem of image segmentation.
In this dissertation we study a higher-order intuitionistic logic used as a specification language for a variety of tasks that treat functional programs as data objects. Such meta-programming tasks offer unique challenges including the representation of programs as data objects and the analysis of these objects. We present a technique, inspired by natural semantics and structural operational semantics, for specifying properties of programs. Specifications of this sort are presented as sets of inference rules and are encoded as clauses in a higher-order, intuitionistic meta-logic. Programs are represented by l-terms and many features of the language such as lexical scoping are enforced through the use of l-abstractions. Program properties are represented as propositions over these terms and are then proved by constructing proofs in our meta-logic. The meta-logic, based on natural deduction, includes inference rules for the introduction and discharge of both hypotheses and eigenvariables. We demonstrate how these rules provide simple and elegant manipulations of bound variables in functional programs. We also demonstrate how transforming proofs and proof systems in this setting provides a means for transforming meta-programs, producing new meta-programs that have certain properties or behaviors.
We argue the following points regarding these specifications and their proofs: (i)the specifications of numerous meta-programming tasks are clear, concise and well structured, providing them with simple explanations and correctness proofs; (ii)a wide variety of meta-programming tasks can be specified in a single unified framework, and thus we can investigate and understand the relationship between various tasks; (iii)proofs describing computations or other kinds of manipulations provide a structure that can be analyzed, using established techniques from proof theory; (iv)specification in our logic have a direct translation to programs in the logic programming language lProlog and this translation provides a mechanism for producing experimental implementations of our meta-programs.
The Two Robotic Arm Coordination System (TRACS) of the GRASP Lab is designed to perform experiments in dynamic two arm control. The system is comprised of two PUMA 250 robot arms with modified controllers, a PA-AT host computer and an AMD 29000 high speed floating point processor board. This manual describes the system software architecture and the software interfaces between the system elements. It is intended to aid in developing software for the system.
The form of rules in combinatory categorial grammars (CCG) is constrained by three principles, called ``adjacency'', ``consistency'' and ``inheritance''. These principles have been claimed elsewhere to constrain the combinatory rules of composition and type raising in such a way as to make certain linguistic universals concerning word order under coordination follow immediately. The present paper shows that the three principles have an extremely natural expression in a unification-based interpretation of CCG in which directional information is an attribute of the arguments of functions grounded in string position. The aforementioned universals can thereby be derived as consequences of more elementary assumptions. some desirable results follow, concerning type-raising and the parser.
The paper briefly reviews a theory of intonational prosody and its relation syntax, and to certain oppositions of discourse meaning that have variously been called ``topic and comment'' ``theme and rheme'', ``given and new'', or ``presupposition and focus''. The theory, which is based on Combinatory Categorial Grammar, is presented in full elsewhere. the present paper examines its consequences for the automatic synthesis and analysis of speech.
There are three parts to this paper. First, I present what I hope is a conclusive, worst-case, complexity analysis of two well-known formulations of the Minimal Diagnosis problem -- those of [Reiter 87] and [Reggia et al 85]. I then show that Reiter's conflict-sets solution to the problem decomposes the single exponential problem into two problems, each exponential, that need be solved sequentially. From a worst case perspective, this only amounts to a factor of two, in which case I see no reason to prefer it over a simple generate-and-test approach. This is only emphasized with the results of the third part of the paper.
Here I argue for a different perspective on algorithms, that of expected, rather than worst-case performance. From that point of view, a sequence of two exponential algorithms has lesser probability to finish early than a single such algorithm. I show that the straightforward generate-and-test approach may in fact be somewhat attractive as it has high probability to conclude in a polynomial time, given a random problem instance.
This paper discusses the motivation behind common knowledge. Common knowledge has been argued to be necessary for joint action in general and for language use as a particular kind of joint action. However, this term has been broadly interpreted. Two major issues must be addressed: (1) What mental state corresponds to common knowledge, ie. is knowledge, belief or supposition the appropriate mental attitude? (2) What inference process allows agents to achieve common knowledge? Most generally, common knowledge is used to describe the knowledge that is evidenced in reflexive reasoning. The term has also been used to refer to facts or objects which are mutually salient. One of the main problems for a theory of common knowledge is whether knowledge is the appropriate mental attitude. It seems as though probabilistic beliefs might approximate the cognitive phenomenon of common knowledge more closely than knowledge. The main problem with a usable notion of common knowledge is that inference must play a critical role in what becomes common knowledge. I discuss the nature of conversational inference. It has a number of properties that distinguish it from other inferential systems, such as being apparently abductive and probabilistic, but a precise characterization of it is an unsolved problem. I suggest that in cases where ensuring common knowledge really matters, participants in dialogue accomplish this is by exploiting opportunities for redundancy in conversation.
The face is an interesting object to animate for several reasons: it is an important channel of communication and therefore important to an human body animation, and it is a complex object in that it is composed of many nonrigid interacting nonarticulated regions. In this paper, we examine the face, and present it as a hierarchically structured regionally defined object. Based on this regional decomposition, and a set of primitive actions, we describe an encoding of a large set of high level facial action descriptors. We also present an application which studies that interaction between intonation and facial expressions for a given emotion. It offers a higher level of representation of the action units by grouping them into specialized functions (lips shape for phonemes, eyebrow movements). An animation system linked to facial motion property is also presented.
Shastri & Ajjanagadde have proposed a biologically plausible connectionist rule-based reasoning system (hereafter referred to as a knowledge base, or KB), that represents a dynamic binding as the simultaneous, or in-phase, activity of the appropriate nodes [9]. This paper makes the first attempt at designing a biologically plausible connectionist interface mechanism between 2 distinct phase-based KB, as the next step toward providing a computational account of common-sense reasoning. The Dynamic Binding Communication Mechanism (DBCM) extracts a dynamic binding from a source KB and incorporates the binding into a destination KB so that it is consistent with the knowledge already represented in the latter. DBCM consists of several distinct, special-purpose modules. The Binding Memory (BM) is made up of several identical banks of nodes. Each time a temporally-encoded dynamic binding is extracted from the source KB, it is transferred into on of the banks, where the binding is converted to a spatially-encoded representation. The Phase Database (PD) monitors the target KB. The Phase Allocator (PA) synthesizes information from the Phase Database and from the target KB to determine the phase in which to introduce the new dynamic binding into the target KB. In turn, the PA extracts a single binding from one of the banks in the BM and introduces it into the target KB. The interface also utilizes 2 searchlight mechanisms: the first governs which bank in the BM receives binding; the second mediates between the active banks (those which are currently representing bindings), and the Phase Allocator.
This report describes the results of twelve months research involving the Hughes array co-processor. This work began with the testing and debugging of the existing system, continued with the development of software to interface the co-processor to a host machine and concluded with the implementation of a trajectory planning algorithm for redundant manipulators. A loader program has been developed which allows simple programs to be executed. A library of C-callable routines has also been created and this enables the fabrication of more complex systems which require a high level of interaction between the host and co-processor. Routines to perform square root, sine and cosine functions have been designed and these have been used successfully in the development of a trajectory planning algorithm. This algorithm uses the co-processor to compute in parallel a large number of forward kinematic solutions and by doing so is able to convert a cartesian space trajectory into a joint space path for a redundant manipulator. The performance of the processor has been analyzed and a number of recommendations have been made concerning future implementations.
We present an approximate analysis of a queue with dynamically changing input rates that are based on implicit on explicit feedback. This is motivated by recent proposals for adaptive congestion control algorithms [RaJa 88, Jac 88], where the sender's window size at the transport level is adjusted based on perceived congestion level of a bottleneck node. We develop an analysis methodology for a simplified system; yet it is powerful enough to answer the important questions regarding stability, convergence (or oscillations), fairness and the significant effect that delayed feedback plays on performance. Specifically, we find that, in the absence of feedback delay, the linear increase/exponential decrease algorithm of Jacobson and Ramakrishnan-Jain [Jac 88, RaJa 88] is provably stable and fair. Delayed feedback on the other hand, introduces oscillations for every individual user as well as unfairness across those competing for the same resource. While the simulation study of Zhang [Zha 89] and the fluid-approximation study of Bolot and Shanker [BoSh 90] have observed the oscillations in cumulative queue length and measurements by Jacobson [Jac 88] have revealed some of the unfairness properties, the reasons for these have not been identified. We identify quantitatively the cause of these effects, via-a-vis the syst ems parameters and properties of the algorithm used. The model presented is fairly general and can be applied to evaluate the performance of a wide range of feedback control schemes. It is an extension of the classical Fokker-Planck equation. Therefore, it addresses traffic viability (to some extent) that fluid approximation techniques do not address.
This manual describes the implementation of Jack with emphasis on how to extend it and modify it. the principle purpose of this manual is to describe what functions in the Jack libraries are available to be used in writing new features for Jack. the manual also gives an overview of how Jack works, for those interested in modifying its current behavior. This manual assumes that you already know how to use Jack, and are familiar with its basic terminology.
Since its beginning in 1983, the GRASP News has chronicled the research efforts of the Grasp Laboratory. This edition, which covers developments for the year 1990, follows the format of previous editions. The Feature Article, however, in a departure from tradition does not highlight a particular research project. The research abstract summarize the progress of students, postdoctoral fellows, visiting researchers, and faculty. The abstracts are classified into three different areas -- Visions Research, Robotics Research and Distributed Real-Time Systems Research. There is also a section on laboratory Software and Hardware Developments. This edition comprises 40 articles from 45 contributors, which makes it the largest GRASP News ever!
This report characterizes the powerdomain constructions which have been used in the semantics of programming languages in terms of formulas of first order logic under a preordering of provable implication. This provides an intuitive representation which suggests a new form of powerdomain---called the mixed powerdomain---which expresses data in a different way from the well-known constructions from programming semantics. It can be shown that the mixed powerdomain has many of the properties associated with the convex powerdomain such as the possibility of solving recursive equations and a simple algebraic characterization.
In this paper, we will describe a tree generating system called tree-adjoining grammar (TAG) and state some of the recent result about TAGs. The work on TAGs is motivated by linguistic considerations. However, a number of formal results have been established for TAGs, which we believe, would be of interest to researchers in tree grammars and tree automata. After giving a short introduction to TAG, we briefly state these result concerning both the properties of the string sets and tree sets. We will also describe the notion of lexicalization of grammars and investigate the relationship of lexicalization to context-free grammars (CFGs) and TAGs.
The definition of Standard ML provides a form of generic equality which is inferred for certain types, called equality types, on which it is possible to define a computable equality relation. However, the standard definition is incomplete in the sense that there are interesting and useful types which are not inferred to be equality types but which nevertheless have a computable equality relation. In this paper we introduce a refinement of the Standard ML system of equality types and prove that our system is sound and complete} with respect to the existence of a computable equality. Our technique is based on an abstract interpretation of ML operators as monotone functions over a three point lattice. We show how the equality relation can be defined (as an ML program) from the definition of a type with our equality property. We then demonstrate a sound, efficient algorithm for inferring the equality property which corrects the limitations of the standard definition in all cases of practical interest.
The unification of simply typed lambda-terms modulo the rules of beta- and eta-conversions is often called ``higher-order'' unification because of the possible presence of variables of functional type. This kind of unification is undecidable in general and if unifiers exist, most general unifiers may not exist. In this paper, we show that such unification problems can be coded as a query of the logic programming language L-lambda in a natural and clear fashion. In a sense, the translation only involves explicitly axiomatizing in L-lambda the notions of equality and substitution of the simply typed lambda-calculus: the rest of the unification process can be viewed as simply an interpreter of L-lambda searching for proofs using those axioms. Appears in the Proceedings of the 1991 International Conference on Logic Progr amming, edited by Koichi Furukawa, June 1991.
Many current grammar formalisms used in computational linguistics take a unification-based approach that use structures (called feature structures) containing sets of feature-value pairs. In this paper, we describe a unification-based approach to Tree Adjoining Grammars (TAG). The resulting formalism (UTAG) retains the principle of factoring dependencies and recursion that is fundamental to TAGs (see Schabes, et. al., 1988). We give some l inguistic examples using UTAG and informally discuss the descriptive capacity of U TAG, comparing it with other unification-based formalisms. Finally, based on the linguistic theory underlying TAGs, we propose some stipulations that can be placed on UTAG grammars. In particular, we stipulate that the feature structures associated with the nodes in an elementary tree are bounded (there is an analogous stipulation on GPSG). Grammars that satisfy these stipulations are equivalent to TAG. Thus, even with these stipulations, UTAGs have more power than CFG-based unification grammars with the same stipulations. To Appear in Unification-Based Grammars'' (ed. Jurgen Wedekind), MIT PRESS, 1991.
A criterion on adequacy is proposed for theories of relevant consequence. According to the criterion, scientists whose deductive reasoning is limited to some proposed subset of the standard consequence relation must not thereby suffer a reduction in scientific competence. A simple theory of relevant consequence is introduced and show to satisfy the criterion with respect to a formally defined paradigm of empirical inquiry.
The task of constructing a volumetric description of a scene from a single image is an underdetermined problem, whether it is a range or an intensity image. To resolve the ambiguities that are caused by occlusions in images, we need to take sensor measurements from several different views. We have limited ourselves to range images obtained by a laser scanning system. It is an actrive system which can encounter two types of occlusions. An occlusion arises either when the refelcted laser light does not reach the camera or when the direct laser light does not reach the scene surface. The task of 3-D data acquisition is divided into two subproblems: to acquire the depth information from one scanning plane and to select the proper scanning planes from which the direct laser light illuminates the entire scene. The first kind of occlusions (range shadows) are easily detected and can be used in designing an efficient algorithm. We develop a strategy to determine the sequence of different views using the information in a narrow zone around the occluded regions. Occluded regions are approximated by polygons. Based on the height information of the border of the occluded regions and geometry of the edges of the polygonal approximation, the next views in the same scanning plane the directions of the next scanning planes for further data acquisition are computed. A condensed and revised version of this technical report also appears as ``Occlusions as a Guide for Planning the Next View,'' University of Pennsylvania Technical Report, MS-CIS-92-40, GRASP LAB 318, 1991.
This report is an investigation of issues encountered in generating a short simulation from a set of instructions. A method for specifying simulations at a task-level, rather than by individual motion, is discussed. The research was conducted using a set of instructions that describe the removal of a Fuel Control Valve from an aircraft.
We study issues that arise in programming with primitive recursion over non-free datatypes such as lists, bags and sets. Programs written in this style can lack a meaning in the sense that their outputs may be sensitive to the choice of input expression. We are, thus, naturally lead to a set-theoretic denotational semantics with partial functions. We set up a logic for reasoning about the definedness of terms and a deterministic and terminating evaluator. The logic is shown to be sound in the model, and its recursion free fragment is shown to be complete for proving definedness of recursion free programs. The logic is then shown to be as strong as the evaluator, and this implies that the evaluator is compatible with the provable equivalence between different set (or bag, or list) expressions . Oftentimes, the same non-free datatype may have different presentations, and it is not clear a priori whether programming and reasoning with the two presentations are equivalent. We formulate these ques tions, precisely, in the context of alternative presentations of the list, bag, an d set datatypes and study some aspects of these questions. In particular, we establish back-and-forth translations between the two presentations, from which it follows that they are equally expressive, and prove results relating proofs of program properties, in the two presentations. This paper has appeared in the Proceedings Of ICALP '91
Interaction between robot and environment is an extremely important aspect of robotic research. Compliance helps reduce the effects of impact when there is robot/environment interaction. To accomplish useful tasks, it is important to implement hybrid control; accurate position control is needed in unconstrained directions and accurate force control is needed in constrained direction. Force control can be more responsive with a compliant force/torque sensor [3], but positional accuracy is reduced with compliance. An instrumented compliant wrist device can be used to achieve both responsive force control and accurate position control. The wrist is connected in series between the end of the robot and the tool. The wrist device uses rubber elements for compliance and damping, and a serial linkage, with potentiometers at each joint, is used for sensing the defections produced in the wrist. Several major improvements are proposed for the Xu wrist. The wrist can be designed to surround the tool, thus reducing the distance between the end of the robot and the end of the tool, thus reducing the distance between the end of the robot and the end of the tool. The compliant structure is redesigned for more even compliance, and the sensing structure kinematics are simplified. In this over, the compliance, kinematics, and accuracy of the wrist will be presented. Also, software for finding the wrist transform, and plans for the wrist are given.
The timed behavior of distributed real-time systems can be specified using a formalism called Communicating Shared Resources, or CSR. The underlying computation model of CSR is resource-based in which multiple resources execute synchronously, while processes assigned to the same resource are interleaved according to their priorities. CSR bridges the gap between an abstract computation model and implementation environments, but is too complex to be treated as a process algebra. We therefore give a calculus for CSR (CCSR), that provides the ability to perform equivalence proofs by syntactic manipulation. We illustrate how a CSR specification can be translated into the CCSR formalism using a periodic timed producer-consumer example, and how a translated CSR specification can be shown correct using syntactic manipulations.
Logic programming languages based on fragments of intuitionistic logic have recently been developed and studied by several researchers. In such languages, implications are permitted in goals and in the bodies of clauses. Attempting to prove a goal of the form D É G in a context G leads to an attempt to prove the goal G in the extended context G{D}. While an intuitionistic notion of context has many uses, it has turned out to be either too powerful or too limiting in several settings. We refine the intuitionistic notion of context by using a fragment of Girard's linear logic that includes additive and multiplicative conjunction, linear implication, universal quantification, the ``of course'' exponential, and the constants 1 (the empty context) and T (for ``erasing'' contexts). After presenting our fragment of linear logic, which contains the hereditary Harrop formulas, we show that the logic has a goal-directed interpretation. We also show that the non-determinism that results from the need to split contexts in order to prove a multiplicative conjunction can be handled by viewing proof search as a process that takes a context, consumes part of it, and returns the rest (to be consumed elsewhere). The complete specification of an interpreter for this logic is presented. Examples taken from theorem proving, natural language parsing, and data base programming are presented: each example requires a linear, rather than intuitionistic, notion of context to be modeled adequately.
This report describes an efficient connectionist knowledge representation and reasoning system that combines rule-based reasoning with inheritance and classification within an IS-A hierarchy. In addition to a type hierarchy, the proposed system can encode generic facts such as `Cats prey on birds' and rules such as `If x preys on y then y is scared of x' and use them to infer that Tweety (who is a Canary) is scared of Sylvester (who is a Cat). The system can also encode qualified rules such as if an animate agent walks into a solid object then the agent gets hurt'. The proposed system can answer queries in time that is only proportional to the length of the shortest derivation of the query and is independent of the size of the knowledge b ase. The system maintains and propagates variable bindings using temporally synchronous --- i.e., in-phase --- firing of appropriate nodes.
This report was originally written to fulfill in part the requirements of the author's WPE examinations, part of the qualifying examinations for the University of Pennsylvania'a Computer Science Ph.D program. The report first introduces CCS and uses it to illustrate various features of established methods of modelling concurrent, communicating systems. The report then goes on to describe and investigate two new models for such systems: The Chemical Abstract Machine, a simple yet predominant in most models for such systems; and the p-calculus, a calculus similar in many respects to CCS, but able to model mobile processes and other, more difficult phenomena.
This paper presents language constructs for the expression of timing and concurrency requirements in distributed real-time programs. Our programming paradigm combines an object-based paradigm for the specification of shared resources, and a distributed transaction-based paradigm for the specification of application processes. Resources provide abstract views of shared system entities, such as devices and data structures. Each resource has a state and defines a set of actions that can be invoked by processes to examine or change its state. A resource also specifies scheduling constraints on the execution of its actions to ensure the maintenance of its state's consistency. Processes access resources by invoking actions and express precedence, consistency. Processes access resources by invoking actions and express precedence, consistency and timing constraints on action invocations. The implementation of our language constructs with real-time scheduling and locking for concurrency control is also described.
We address the problem of observing a moving agent. In particular, we propose a system for observing a manipulation process, where a robot hand manipulates an object. A discrete event dynamic systems (DEDS) frame work is developed for the hand/object interaction over time and a stabilizing overserver is constructed. Low-level modules are developed for recognizing the ``events'' that causes state transitions within the dynamic manipulation system. The work examines closely the possibilities for errors, mistakes and uncertainties in the manipulation system, observer construction process and event identification mechanisms. The system utilizes different tracking techniques in order to observe and recognize the task in an active, adaptive and goal-directed manner.
A new approach in stereo vision is proposed which recovers 3D depth information using continuous vergence angle control with simultaneous local correspondence response. This technique relates elements with the same relative position in the left and right images for a continuous sequence of vergence angles. the approach considers the extremely fine vergence movements about a given fixation point within the depth of field boundaries. It allows the recovery of 3D depth information given the knowledge of the system's geometry and a sequence of pairs [aI, Ci], whereai is the ith vergence angle and Ci is the ith matrix of correspondence responses. The approach has several advantages over the current ones. First, due to its local operation characteristics, the resulting algorithms can be implemented in a modular hardware scheme. Second, unlike currently use algorithms, there is no need to compute depth from disparity values; at the cost of the acquisition of a sequence of images during the micromovements. the approach also greatly reduces the errors in stereo due to the sensor quantization. Last, and most important of all, the approach is supported by experimental results from physiology and psychophysics. Physiological results show that the human eye performs fine movements during the process of fixation on a single point, which are collectively called physiological nystagmus. One such movement, called binocular flicks, happens in opposing directions and produces convergence/divergence of the eyes. These are the micromovements that we suppose are the basis for depth perception. Therefore, the approach proposes a functional correlation between these vergence micromovements, depth perception, stereo acuity and stereo fusion.
In this paper we present an overview for the development of a theory for analyzing and predicting the behavior if discrete event dynamic systems (DEDS). DEDS are dynamic systems in which state transitions are caused by internal, discrete events in the system. DEDS are attracting considerable interest, current applications are found in manufacturing systems, communications and air traffic systems, future applications will include robotics, computer vision and artificial intelligence. We will discuss the perturbation analysis technique (PA) for evaluation the performance of DEDS.
In this report we present an overview for the development of a theory for discrete event dynamic systems (DEDS). Dynamic systems are usually modeled by finite state automata with partially overservable events together with a mechanism for enabling and disabling a subset of state transitions. DEDS are attracting considerable interests, current applications are found in manufacturing systems, communications and air traffic systems, future applications will include robotics, computer vision and AI. We will discuss notions of modeling, stability issues, observability, feedback and invertibility. We will also discuss the perturbation analysis technique (PA) for analyzing and describing the behavior of DEDs.
This dissertation addresses the problem of remote manipulation in the presence of communication delays. Delays occur with earth-based control of a robotic system in space or when an untethered submersible system is controlled from the surface via an acoustic communication channel. The resulting delay in obtaining position and force feedback from the remote slave arm(s) makes direct teleoperation infeasible. We propose a new control methodology, called teleprogramming, which allows for efficient control for a robotic system in the presence of significant feedback delays without substantial degradation in the overall system performance. A teleprogramming system allows the operator to kinesthethically, as well as visually, interact with a graphical simulation of the remote environment and to interactively, on-line teleprogram the remote manipulator through a sequence of elementary symbolic instructions. These instructions are generated automatically by the operator's station software in real time as the task progresses. The slave robot executes these symbolic commands delayed in time and, should an error occur, allows the operator to specify the necessary corrective actions and continue with the task. Teleprogramming offers a practical compromise between the ultimate and the feasible, and provides an effective and time-efficient approach to remote manipulation. Advantages of teleprogramming over existing control methodologies include a relatively modest required level of remote site autonomy, and the absence of the need of complex automatic task planners and preprogrammed error recovery modules. This document describes the overall conceptual architecture of teleprogramming and presents a detailed treatment of all major components of teleprogramming system. An operational prototype system is described an preliminary experimental results are reported. Experimental results have confirmed the validity and feasibility of the teleprogramming control methodology. Sustained and efficient remote control of a robot manipulator in the presence of a five second feedback delay was successfully accomplished for simple contact tasks.
In this paper we address the problem of host to host communication. In particular, we discuss the issue of efficient and adaptive transmission mechanisms over possible physical links. We develop a tool for making decisions regarding the flow of control sequences and data from and to a host. This issue of compression is discussed in details, a decision box and an optimizing tool for finding the appropriate thresholds for a decision are developed. Physical parameters like the data rate, bandwidth of the communication medium, distance between the hosts, abaud rate, levels of discretization, signal to noise ration and propagation speed of the signal are taken into consideration while developing our decision system. Theoretical analysis is performed to develop mathematical models for the optimization algorithm. Simulation models are also developed for testing both the optimization and the decision tool box.
The unique properties of tree-adjoining grammars (TAG) present a challenge for the application of TAGs beyond the limited confines of syntax, for instance, to the task of semantic interpretation or automatic translation of natural language. We present a variant of TAGs, called synchronous TAGs, which characterize correspondences between languages. The formalism's intended usage is to relate expressions of natural languages to their associated semantics represented in a logical form language, or to their translates in another natural language; in summary, we intend it to allow TAGs to be used beyond their role in syntax proper. We discuss the application of synchronous TAGs to concrete examples, mentioning primarily in passing some computational issues that arise in its interpretation.
Lexicalized Tree Adjoining Grammar (LTAG) is an attractive formalism for linguistic description mainly because of its extended domain of locality and its factoring recursion out from the domain of local dependencies (Joshi, 1984, Kroch and Joshi, 1985, Abeille, 1988). LTAG's extended domain of locality enables on to localize syntactic dependencies (such as filler-gap), as well as semantic dependencies (such as predicate-arguments). The aim of this paper is to show that these properties combined with the lexicalized property of LTAG are especially attractive for machine translation. The transfer between two languages, such as French and English, can be done by putting directly into correspondence large elementary universe without going through some interlingual representation and without major changes to the source and target grammars. The underlying formalism fro the transfer is ``synchronous Tree Adjoining Grammars'' (Sheiber and Schabes [1990]). Transfer rules are stated as correspondences between nodes of trees of large domain of locality which are associated with words. We can thus define lexical transfer rules that avoid the defects of a mere word-to-word approach but still benefit from the simplicity and elegance of a lexical approach. We rely on the French and English LTAG grammars (Abeillé [1988], Abeillé [1990(b)], Abeillé et al. [1990], Abeillé and Schabes [1989, 1990]) that have been designed over the past two years jointly at University of Pennsylvania and University of Paris 7-Jussieu.
The problem of part definition, description, and decomposition is central to the shape recognition systems. In this dissertation, we develop an integrated framework for segmenting dense range data of complex 3-D scenes into their constituent parts in terms of surface and volumetric primitives. Unlike previous approaches, we use geometric properties derived from surface, as well as volumetric models, to recover structured descriptions of complex objects without a priori domain knowledge or stored models. To recover shape descriptions, we use bi-quadric models for surface representation and superquadric models for object-centered volumetric representation. The surface segmentation uses a novel approach of searching for the best piecewise description of the image in terms of bi-quadric (z = f(x,y)) models. It is used to generate the region adjacency graphs, to localize surface discontinuities, and to derive global shape properties of the surfaces. A superquadric model is recovered for the entire data set and residuals are computed to evaluate the fit. The goodness-of-fit value based on the inside-outside function, and the mean-squared distance of data from the model provide quantitative evaluation of the model. The qualitative evaluation criteria check the local consistency of the model in the form of residual maps of overestimated and underestimated data regions. The control structure invokes the models in a systematic manner, evaluates the intermediate descriptions, and integrates them to achieve final segmentation. Superquadric and bi-quadric models are recovered in parallel to incorporate the best of the coarse-to-fine and fine-to-coarse segmentation strategies. The model evaluation criteria determine the dimensionality of the scene, and decide whether to terminate the procedure, or selectively refine the segmentation by following a global-to-local part segmentation approach. The control module generates hypotheses about superquadric models at clusters of underestimated data and performs controlled extrapolation of the part-model by shrinking the global model. As the global model shrinks and the local models grow, they are evaluated and tested for termination or further segmentation. We present results on real range images of scenes of varying complexity, including objects with occluding parts, and scenes where surface segmentation is not sufficient to guide the volumetric segmentation. We analyze the issue of segmentation of complex scenes thoroughly by studying the effect of missing data on volumetric model recovery, generating object-centered descriptions, and presenting a complete set of criteria for the evaluation of the superquadric models. We conclude by discussing the applications of our approach in data reduction, 3-D object recognition, geometric modeling, automatic model generation, object manipulation, and active vision.
The self-organizing feature maps developed by Kohonen appear to capture some of the advantages of the natural systems on which they are based. A summary of the operation of this form of artificial neural network is presented. It was concluded that the primary benefits of using self-organizing feature maps result from their adaptability and plasticity while most problems are largely caused by the lack of a rigorous mathematical foundation. Two different robotics applications are described. In the first, developed by Martinez and Schulten, a hierarchical structure composed of many self-organizing feature maps is used to control a five degree of freedom robot arm. While it was noted that there may be some practical problems, the general idea of using a hierarchical structure appears sound and may be applicable to a wider range of problems. The second robotics application was developed by Saxon and Mukherjee. They used a single self-organizing feature map to learn the motion map of a two degree of freedom arm. The use of such a system should simplify path planning by combining multiple constraints into a 2-D structure.
In this paper, we present a randomnized algorithm for the multipacket (i.e., k - k) routing problem on an n x n mesh. The algorithm competes with high probability in at most kn + O(k log n) parallel communication steps, with a constant queue size of O(k). The previous best known algorithm [4] takes [5/4] kn + O([kn/f(n)]) steps with a queue size of O(k f(n)) (for any 1 £n). We will also present a randomnized algorithm for the wormhold model permutation routing problem for the mesh that completes in at the most kn + O(k log n) steps, with a constant queue size of O(k), where k is the number of flits that each packet is divided into. The previous best result [6] was also randomnized and had a time bound of kn +O ([kn/f(n)]) with a queue size of O(k f(n)) for any 1 £ f(n). The two algorithms that we will present are optimal with respect to queue size. The time bounds are within a factor of two of the only known lower bound.
In many engineering applications such as assembly of mechanical components, robot manipulation, gripping, fixturing and part feeding, there are situations in which a rigid body is subject to multiple frictional contacts with other bodies. It is proposed to develop a systematic method for the analysis and simulation of such systems. A detailed study is presented on rigid body impact laws, and the assumption of contact compliance is investigated.
A general technique for merging database schemas is developed that has a number of advantages over existing techniques, the most important of which is that schemas are placed in a partial order that has bounded joins. This means that the merging operation, when it succeeds, is both associative and commutative, i.e., that the merge of schemas is independent of the order in which they are considered -- a property not possessed by existing methods. The technique is interactive in that users made assertions about the relationships between the nodes of the schemas to be merged. These assertions are then considered to be elementary schemas, and are combined with the schemas using precisely the same merging operation. The technique is general and can be applied to a variety of data models. It can also deal with certain cardinality constraints that arise through the imposition of keys. A prototype implementation, together with a graphical interface, has been developed.
We establish a link from natural language statements describing actions to be performed by an agent to a semantic representation suitable for achieving effective control of a computer-driven graphical animation system. A representation scheme based on decompositional analysis is developed emphasizing the requirement that algorithmic implementability of the underlying semantic primitives is our primary concern. Our primitives pertain to mechanical characteristics of the ``kernel'' tasks denoted by a class of action verbs (verbs whose underlying tasks deal with an agent manipulating one or more objects); they refer to geometric constraints and goals that need to be achieved, kinematic and dynamic characteristics, and certain aspectual characteristics such as repetitiveness of one or more sub-actions, definedness of termination points, etc. We provide lexical entries for a few verbs in terms of such primitives. We also analyze the manner in which prepositional and adverbial modifiers affect the representation as well as the execution of the basic actions denoted by the verbs. Such modifiers either provide values of arguments for the verbs' internal representations, modify default argument values, or provide values of non-obligatory arguments. We obtain semantic representations for a few prepositions and adverbs in a fashion integrable into the scheme for verbal meaning representation. We have developed a system to demonstrate the validity of the results obtained; such a system establishes channels of communication with existing animation software developed at the Graphics Laboratory at the University of Pennsylvania.
In an environment where network resources are reserved e.g, telephone networks, the path with smallest number of hops is prefered and other alternate paths are used only when there the shortest path is full. However if the alternate path is longer more network resources are devoted to the circuit and this in turn could worsen the situation. Circuit migration is a solution to reduce the amount of resources inefficiently used due to alternate routing in connection oriented networks. By rerouting a circuit when its shortest path becomes available, one can smooth out the congestion and increases the utilization of the network. The overhead of circuit migration is comparable to call set up and the tradeoff of circuit migration is improvement in performance vs. some additional call processing capacity. In this report we will focus on the above tradeoff, evaluating it analytically and by simulation on a completely connected topology. Our initial results indicate that migration could improve the performance of the network at high load but it has to be done very often. Such a large amount of overhead could be expensive enough to offset the gain in performance. On further investigation, we discover that threshing can also occur in circuit migration. We proposed two solutions to the problem. The first solution is to migrate only when the shortest path is no longer highly utilized. The second solution migrates a circuit only if its path is congested. A hybrid solution using the two above is also examined. We will also address the reordering problem that could occur when a circuit is transferred to a new path.
One of the most fundamental and frequently used operations in the process of simulating a stochastic discrete event system is the generation of a nonuniform discrete random variate. The simplest form of this operation can be stated as follows: Generate a random variable X which is distributed over the integers 1,2, ¼ such that P(X = i) = pi. A more difficult problem is to generate X when the pi's change with time. For this case, there is a well-known algorithm which takes O( log n) time to generate each variate. Recently Fox [4] presented an algorithm that takes an expected o( log n) time to generate each variate under assumptions restricting the way the pi's can change. In this paper we present algorithm for discrete random variate generation that take an expected O(1) time to generate each variate. Furthermore, our assumptions on how the pi 's change are less restrictive than those of Fox. The algorithms are quite simple and can be fine-tuned to suit a wide variety of application. The application to the simulation of queueing networks is discussed in some detail.
This paper presents a set of mechanisms for congestion control of data traffic in high speed wide area networks (HSWANs) along with preliminary performance results. The model of the network assumes reservation of resources based on average requirements. The mechanisms address (a) the different network time constants (short term and medium-term), (b) admission control that allows controlled variance of traffic as a function of medium-term congestion, and (c) prioritized scheduling which is based on a new fairness criterion. This latter criterion is perceived as the appropriate fairness measure for HSWANs. Preliminary performance studies show that the queue length statistics at switching nodes (mean, variance and max) are approximately proportional to the end-point 'time window' size. Further,
We describe a system, TraumAID, which has been designed to provide decision support throughout the initial definitive management of severely injured patients (i.e., after their initial evaluation, resuscitation, and stabilization). Over the course of initial definitive management, TraumAID recommends appropriate procedures to be carried out, based on currently available evidence and on the complexity and urgency of the situation. TraumAID's ability to deal flexibly with complex and often urgent situations comes from its ability to reason separately about the management goals that should be achieved and about the means that are situationally appropriate for achieving them. In this paper, we describe TraumAID's approach to trauma management in more detail, showing in particular how it enables TraumAID to adapt its reasoning and recommendations to the urgency with which a patient's condition must be addressed.
Concurrent real-time applications are complicated since both timing and consistency constraints must be met for correct performance. Furthermore, techniques to enforce these two forms of constraints are often incompatible. For instance, priority-driven preemptive scheduling, which is optimal for meeting timing constraints in some systems, may leave a shared resource's state inconsistent. On the other hand, mutual exclusion techniques that ensure the consistency of shared resources are not well-suited to meeting timing constraints. This dissertation develops concepts and programming language constructs for facilitating the enforcement of both real-time and consistency constraints in applications with concurrency. Our programming paradigm combines an object-based paradigm for the specification of shared resources, and a distributed transaction-based paradigm for the specification of application processes. Resources provide abstract views of shared system entities, such as devices and data structures. Each resource has a state and defines a set of actions that can be invoked by processes to examine or change its state. A resource also specifies scheduling constraints on the execution of its actions to ensure the maintenance of its state's consistency. Processes access resources by invoking actions and express precedence, consistency and timing constraints on action invocations. The implementation of our language constructs with real-time scheduling and locking for concurrency control is also described, including a novel deadlock prevention technique. The utility of the constructs are demonstrated in two ways. First, we describe their use to solve a general concurrent real-time problem called timed atomic commitment . We then describe how they were used to program a graphic simulation of two robot arms coordinating to pick up a moving object under timing constraints.
This thesis deals with the problem of the 3D workspace visualization for anthropomorphic linkages, not only those with redundant degrees of freedom but also those with joint limits. Although the workspace problem has important applications in a variety of fields such as computer-aided design, ergonomic studies, and robotics, the problem's computational complexity has never been analyzed. In addition, previous techniques suffer from one or more of the following drawbacks: high computational cost, computing 2D workspace cross sections, dealing with manipulators that have specialized geometry, or sensitivity to geometrical and numerical errors or approximations. We analyze the computational complexity of the problem and prove that it is NP-hard. Then, we decompose it into three major subproblems: workspace point generation, visualization, and criteria selection. We describe and compare different techniques for computing workspace points: direct kinematics based algorithms, nonlinear programming based algorithms, and force application based algorithms. Each class of these algorithms has advantages and disadvantages, and none of them supersedes the others in all applications. Instead of debating the merits of these algorithms, we integrate them into ``Hybrid algorithms'' that are capable of generating workspace points efficiently. The visualization module can be built by either surface-based or volume-based algorithms. Each class of these algorithms is more suitable than the others for certain applications. The criteria selection module interacts with the user and tailors the most appropriate techniques, from the workspace point generation and the visualization modules, based on the application requirements.
The timing behavior of a real-time system depends not only on delays due to process synchronization, but also on the availability of shared resources. Most current real-time models capture delays due to process synchronization; however, they abstract out resource-specific details by assuming idealistic operating environments. On the other hand, scheduling and resource allocation algorithms used for real-time systems ignore the effect of process synchronization except for simple precedence relations between processes. To bridge the gap between these two disciplines, we have developed a methodology called Communicating Shared Resources, or CSR. In this dissertation we describe our approach to the specification and verification of real-time systems. Application processes are specified in the CSR application language, which includes language constructs that are essential in real-time settings, such as timeouts, deadlines, periodic processes, interrupts and exception-handling. Then, a configuration schema is used to map the processes to system resources, and to specify the physical communication links between them. To analyze and execute the entire system, we automatically translate the result of the mapping into the CCSR process algebra. CCSR characterizes CSR's resource-based computation model by a priority-sensitive, operational semantics. To do this, we have formulated a natural treatment of preemption, which is based not only on priority, but also on resource utilization and inter-resource synchronization. The preemption ordering leads to a compositional proof system, which allows the syntactic manipulation of CCSR terms. Using this proof system, we perform the algebraic verification of our original real-time system.
Existing approaches to semantics of algebraically specified data types such as Initial Algebra Semantics and Final Algebra Semantics do not take into account the possibility of general recursion and hence non-termination in the ambient programming language. Any technical development of this problem needs to be in the setting of domain theory. In this paper we present extensions of initial and final algebra semantics to algebras with an underlying domain structure. Four possibilities for specification methodologies arise: two each in the Initial and Final algebra paradigms. We demonstrate that the initial/final objects (as appropriate) exist in all four situations. The final part of the paper attempts to explicate the notion of abstractness of ADT's by defining a notion of operational semantics for ADT's, and then studying the relationship between the various algebraic-semantics proposed and the operational semantics.
A typed, modular paradigm for polynomial time computation is proposed.
This document describes developing an environment for effective use of functional/equational programs and rule-based expert systems. There are significant advantages in using these paradigms for reliability, parallelism, and accumulation of expertise in knowledge bases. The environment will make it easier to understand and use these paradigms, construct more reliable systems, and automatically enrich rule-based knowledge bases with the expertise. It will consist of the following components: (1) Visualization: for composing systems using a graphical interface and for understanding of algorithms. (2) Consistency Checking: for an equational and a rule-based languages in accordance with the semantics of the languages. (3) Knowledge Base Generation and Testing: a translator that extracts expertise from existing programs and accumulates it as rules in knowledge bases; the rules are tested to enhance reliability. (4) Verification: interactive heterogeneous reasoning that consists of equational reasoning based on visual and textual information. These tools will be integrated in the proposed environment. The environment will greatly reduce the costs and increase the reliability of functional/equational and rule-based systems.
The way to specify a programming language has been a topic of heated debate for some decades and at present there is no consensus on how this is best done. Real languages are almost always specified informally; nevertheless, precision is often enough lacking that more formal approaches could benefit both programmers and language implementors. My purpose is to look at a few of these formal approaches in hope of establishing some distinctions or at least stirring some discussion.
Recently Rajasekaran and Ross [1] presented an algorithm that takes an expected 0(1) time to generate a nonuniform discrete random variate. In this paper we discuss how this algorithm can be employed in the efficient simulation of large-scale telephone networks. In a simulation based upon a standard event-list approach, the generation of a new event in the systems take 0(log n) time. With this new algorithm, event generation becomes an 0(1) process, and simulation times for large networks can be reduced.
The paper briefly reviews a theory of intonational prosody and its relation syntax, and to certain oppositions of discourse meaning that have variously been called ``topic and comment'', ``theme and rheme'', ``given and new'', or ``presupposition and focus.'' The theory, which is based on Combinatory Categorial Grammar, is presented in full elsewhere. The present paper examines its implications for the semantics of ``focus''.
We examine the problem of finding fully abstract translations between programming languages, i.e., translations that preserve code equivalence and nonequivalence. We present three examples of fully abstract translations: one from call-by-value to lazy PCF, one from call-by-name to call-by-value PCF, and one from lazy to call-by-value PCF. The translations yield upper and lower bounds on decision procedures for proving equivalences of code. We finally define a notion of ``functional translation'' that captures the essence of the proofs of full abstraction, and show that some languages cannot be translated into others.
We examine various computational accounts of aspects of music understanding. These accounts involve programs which can notate melodies based on pitch and duration information. It is argued that this task involves significant musical intelligence. In particular, it requires an understanding of basic metric and harmonic relations implicit in the melody. We deal only with single-voice, tonal melodies. While the task is a limited one, and the programs give only partial solutions to this task, we argue that this represents a first step towards a computational realization of significant aspects of musical intelligence.
Recent research has abstracted diagnosis away from the activity needed to acquire information and to act on diagnosed disorders. In some problem domains, however, such abstraction is counter-productive and does not reflect real-life practice, which integrates diagnostic and therapeutic activity. Trauma management is a case in point. Here, we discuss a formalization of the integrated approach taken in TraumAID, a system we have developed to serve as an artificial aide to residents and physicians dealing with multiple trauma. Among other things, the active pursuit of information raises the question of what is and what is not worth pursuing. In TraumAID 2.0, we take the view that the process of diagnosis should continue only as long as it is likely to make a difference to future actions. That view is formalized in the goal-directed diagnostic paradigm (GDD). Unlike other diagnostic paradigms, goal-directed diagnosis is first and foremost concerned with setting goals based on its conclusions. It regards the traditional construction of an explanation for the faulty behavior as secondary.
In order to explicitly represent goal-directedness, the diagnostic process is viewed as search in a space of attitude-beliefs. From this, we derive a high-level algorithm that produces appropriate requests for action while searching for an explanation. A complete explanation, however, is not the criterion for terminating action. Such a criterion, we argue, is better treated in terms of goal-means tradeoffs. TraumAID's architecture, in so far as it embodies this goal-directed approach, assigns to a complementary planner the resolution of such tradeoffs.
Teleprogramming was developed as a solution to problems of teleoperation systems with significant time delays [5]. In teleprogramming, the human operator interacts in real time with a graphical model of the remote site, which provides for real time visual and force feedback. The master system automatically generates symbolic commands based on the motions of the master arm and the manipulator/model interactions, given predefined criteria of what types of motions are to be expected. These commands are then sent via a communication link, which may delay the signals, to the remote site. Based upon a remote world model, predefined and possibly refined as more information is obtained, the slave carries out commanded operations in the remote world and decides whether each step has been executed correctly. Contact operations involve the remote site manipulator interacting with the environment, including planned collisions, and motion with contact with the environment. A hybrid position/force control scheme using a instrumented compliant wrist has been demonstrated to be very effective for these types of operations. In particular, switching between position and force modes (when contacting a surface, for example) does not present problems for the system. A brief introduction of teleprogramming and contact operations is presented, including a model of sliding motions and early experimental results. Problems with these early experiments are presented, and solutions discussed. The criteria for an object to slide rather than tip over are presented, relating to the geometry of the object and the applied forces. Finally, methods are presented to match the experimental results to a simple model, to help the remote manipulator to quickly and robustly sense collisions.
There are several applications in robotics and manufacturing in which nominally rigid objects are subject to multiple frictional contacts with other objects. In most previous work, rigid body models have been used to analyze such systems. There are two fundamental problems with such an approach. Firstly, the use of frictional laws, such as Coulomb's law, introduce inconsistencies and ambiguities when used in conjunction with the principles of rigid body dynamics. Secondly, hypotheses traditionally used to model frictional impacts can lead to solutions which violate principles of energy conservation. In this paper these problems are explained with the help of examples. A new approach to the simulation of mechanical systems with multiple, frictional constraints is proposed which is free of inconsistencies.
In this paper we examine parallel algorithms for performing a depth-first search (DFS) of a directed or undirected graph in sub-linear time. this subject is interesting in part because DFS seemed at first to be an inherently sequential process, and for a long time many researcher believed that no such algorithms existed. We survey three seminal papers on the subject. The first one proves that a special case of DFS is (in all likelihood) inherently sequential; the second shows that DFS for planar undirected graphs is in NC; and the third shows that DFS for general undirected graphs is in RNC. We also discuss randomnized algorithms, P-completeness and matching, three topics that a re essential for understanding and appreciating the results in these papers
When writing programs to manipulate structures such as algebraic expressions, logical formulas, proofs, and programs, it is highly desirable to take the linear, human-oriented, concrete syntax of these structures and parse them into a more computation-oriented syntax. For a wide variety of manipulations, concrete syntax contains too much useless information (e.g., keywords and white space) while important information is not explicitly represented (e.g., function-argument relations and the scope of operators). In parse trees, much of the semantically useless information is removed while other relationships, such as between function and argument, are made more explicit. Unfortunately, parse trees do not adequately address important notions of object-level syntax, such as bound and free object-variables, scopes, alphabetic changes of bound variables, and object-level substitution. I will argue here that the abstract syntax of such objects should be organized around a-equivalence classes ofl -terms instead of parse trees. Incorporating this notion of abstract syntax into programming languages is an interesting challenge. This paper briefly describes a logic programming language is presented to illustrate its approach to handling object-level syntax. A model theoretic semantics for this logic programming language is also presented.
We present a general introduction and critical review of descriptive complexity approaches to inductive inference, that is, the problem of determining a model from observation. Descriptive complexity, as defined by Kolmogogov, Chaitin and Solomonoff is presented as a generalization of Shannons entropy. Its relations with randomness is discussed and examples are presented. the practicability of descriptive complexity theory is discussed. We then present Rissanen's MDL principle as a restriction of descriptive complexity. We demonstrate the effectiveness of MDL by applying it it AR processes. Lastly, we present and discuss LeClerc's application of MDL to image segmentation.
The purpose of this paper is to give an exposition of material dealing with constructive logic, typed l-calculi, and linear logic. The emergence in the past ten years of a coherent field of research often named ``logic and computation'' has had two major (and related) effects: firstly, it has rocked vigorously the world of mathematical logic; secondly, it has created a new computer science discipline, which spans from what is traditionally called theory of computation, to programming language design. Remarkably, this new body of work relies heavily on some ``old'' concepts found in mathematical logic, like natural deduction, sequent calculus, and l-calculus (but often viewed in a different light), and also on some newer concepts. Thus, it may be quite a challenge to become initiated to this new body of work (but the situation is improving, there are now some excellent texts on this subject matter). This paper attempts to provide a coherent and hopefully ``gentle'' initiation to this new body of work. We have attempted to cover the basic material on natural deduction, sequent calculus, and typed l -calculus, but also to provide an introduction to Girard's linear logic, one of the most exciting developments in logic these past five years. The first part of these notes gives an exposition of background material (with the exception of the Girard-translation of classical logic into intuitionistic logic, which is new). The second part is devoted to linear logic and proof nets.
The purpose of this paper is to give an exposition of material dealing with constructive logics, typed l-calculi, and linear logic. The first part of this paper gives an exposition of background material (with the exception of the Girard-translation of classical logic into intuitionistic logic, which is new). This second part is devoted to linear logic and proof nets. Particular attention is given to the algebraic semantics (in Girard's terminology, phase semantics) of linear logic. We show how phase spaces arise as an instance of a Galois connection. We also give a direct proof of the correctness of the Danos-Regnier criterion for proof nets. This proof is based on a purely graph-theoretic decomposition lemma. As a corollary, we give an O(n2)-time algorithm for testing whether a proof net is correct. Although the existence of such an algorithm has been announced by Girard, our algorithm appears to be original.
Unification procedures arising in methods for automated theorem proving based on matings are surveyed. We begin by reviewing some fundamentals of automated deduction, including the Skolem form and the Skolem-Herbrand-Godel theorem. Next, the method of matings for first-order languages without equality due to Andrews and Bibel is presented. Standard unification is described in terms of transformations on systems (following the approach of Martelli and Montanari, anticipated by Herbrand). Some fast unification algorithms are also sketched, in particular, a unification closure algorithm inspired by Paterson and Wegman's method. The method of matings is then extended to languages with equality. This extention leads naturally to a generalization of standard unification called rigid E-unification (due to Gallier, Narendran, Plaisted, and Snyder). The main properties of rigid E-unification, decidability, NP-completeness, and finiteness of complete sets, are discussed.
Our goal is to produce a high level programming language or tool for 3D animation of facial expressions, especially, those conveying information correlated with the intonation of the voice: this includes the differences of timing, pitch, and emphasis that are related to such semantic distinctions of discourse as ``given'' and ``new'' information, some of which are also correlated with affect or emotion. Up till now, systems have not embodies such rule-governed taken into account any auto matic translation from speech and utterance meaning to facial expressions. Our algorithm embodies rules that describe and coordinate these relations intonation/information, intonation/emotions and facial expressions/emotions. Given an utterance, we consider how the discourse information (what is new/old} information in the given context, or what is the ``topic'' of the discourse) is transmitted through the choice of accents and their placement, how it is conveyed over facial expression and how the two are coordinated. The facial model integrates the action at several levels, including individual muscle, group of muscles, and eye- and head-motion, as well as the propagation of or interaction of these movements, especially coarticulation effects. This study offers a higher level of representation of facial actions by grouping them into specialized functions (lip shapes for phonemes, eyebrow and head motions as emphatic movements). The major ``key phrases'' of this work involves the integration of FACS (facial notational system derived by P. Ekman and W. Friesen), and the Action Units (muscle actions); it offers a solution to li p synchronization as well as it provides a repertory of the different types of fac ial expressions involved with speech; it considers speaker/listener interaction. This representation is used to drive an animation system linked to facial motion.
When multiple arms are used to manipulate a large object, it is necessary to maintain and control contacts between the object and effector(s) on one or more arms. The contacts are characterized by holonomic as well as nonholonomic constraints. This paper addresses the control of mechanical systems subject to nonholonomic constraints, rolling constraints in particular. It has been shown that such a system is always controllable, but cannot be stabilized to a single equilibrium by smooth feedback. In this paper, we show that the system is not input-state linearizable though input-output linearization is possible with appropriate output equations. Further, if the system is position-controlled (i.e., the output equation is a functions of position variables only), it has a zero dynamics which is Lagrange stable but not asymptotically stable. We discuss the analysis and controller design for planar as well as spatial multi-arm systems and present results from computer simulations to demonstrate the theoretical results.
A new range finding method is proposed in this paper which makes use of a varifocal mirror. The three-dimensional object space is first discretized into a sequence of spherical shells with a specially designed nonlinear vibrating varifocal mirror. These discrete spherical shell images are then recorded by a video camera. A deblurring algorithm is introduced in this paper which is used to remove the blurred components in the images. Different depth ranges can be obtained by controlling the vibration amplitude and the direct current component of the driving wave for the varifocal mirror. The depth accuracy is adjusted by varying the vibration period of the varifocal mirror. This range finding technique can be made real time by increasing the frame frequency of the camera.
Unification problems are identified with conjunctions of equations between simply typed l-terms where free variables in the equations can be universally or existentially quantified. Two schemes for simplifying quantifier alternation, called Skolemization and raising (a duel of Skolemization), are presented. In this setting where variables of functional type can be quantified and not all types contain closed terms, the naive generalization of first-order Skolemization has several technical problems that are addressed. The method of searching for pre-unifiers described by Huet is easily extended to the mixed prefix setting, although solving flexible-flexible unification problems is undecidable since types may be empty. Unification problems may have numerous incomparable unifiers. Occasionally, unifiers shard common factors and several of these are presented. Various optimizations on the general unification search problem as as discussed.
Interactive postural control is the process of interactively pushing, poking, and twisting parts of an articulated geometric figure for the express purpose of getting it into a desired posture. Many motion algorithms and computer animation techniques generate motion sequences based on starting and ending postures for geometric figures, but few of these techniques address the fundamental problem of specifying these postures. The goal of this thesis is to develop a system that allows us to specify postures of animate geometric figures in ways that suggest how we interact with real people. The emphasis of this thesis is on real-time interactive 3D manipulation. The elements of the interaction techniques form a powerful vocabulary for describing postures and postural adjustments. The vocabulary is not a spoken or written one; rather, it includes verbs acted out by the user through the movement of input devices. There are three major components to this work. The first component is a real-time 3D direct manipulation technique that allows the user to intuitively translate and rotate ``handles'' on objects using only a three button mouse as input. The second component is an inverse kinematics algorithm that uses the notion of constraints, or desired geometric relationships, to control postures of articulated figures. The inverse kinematics formulation is well suited to highly redundant figures. The final component is the system of behaviors. Behaviors provide coordination between the parts of the figure, so that when one part of a figure moves, the body reacts as a whole. One of the most important behaviors, and the one requiring the most coordination, is balance. The behaviors magnify the effect of the basic manipulation commands so that relatively few invocations of the commands are necessary to accomplish a complex positioning task.
This paper studies force-closure grasps of rigid objects by using two palms. The two palms are instrumented with tactile sensors capable of detecting the presence of contacts, and are assumed to be respectively installed on two robotic manipulators capable of motion and force control. Established in this paper is an existence condition under which the two palms form a force-closure grasp. The salient feature of this condition is that it does not require the information on the shape of the object and the contact locations. A configuration of the two palms in contact with the object satisfying this condition is called a force-closure grasp configuration (FCGC). Further an algorithm is developed to check the condition for FCGC in terms of the position and orientation of the palms.
The goal of our research is to investigate manipulation, mobility, sensing, control and coordination for a multiagent robotic system employed in the task of material handling, in an unstructured, indoor environment. In this research, manipulators, observers, vehicles, sensors, and human operator(2) are considered by be agents. Alternatively, an agent can be a general-purpose agent (for example, a six degree of freedom manipulator on a mobile platform with visual force, touch and position sensors). Possible applications for such a system includes handling of waste and hazardous materials, decontamination of nuclear plants, and interfacing between special purpose material handling devices in warehouses. The fundamental research problems that will be studied are organization, or the decomposition of the task into subtasks and configuring the multiple agents with appropriate human interaction, exploration, or the process of exploring geometric, material and other properties about the environment and other agents, and coordination, or the dynamic control of multiple agents for manipulation and transportation of objects to a desired destination.
We propose that some aspects of task based learning in robotics can be approached using nativist and constructivist views on human sensorimotor development as a metaphor. We use findings in developmental psychology, neurophysiology, and machine perception to guide a robotic learning system's level of representation both for actions and for percepts. Visually driven grasping is chosen as the experimental task since it has general applicability and it has been extensively researched from several perspectives. An implementation of a robotic system with a dexterous three fingered hand, compliant instrumented wrist, arm and vision is used to test these ideas. Several sensorimotor primitives (vision segmentation and manipulatory reflexes) are implemented in this system and may be thought of as the ``innate'' perceptula and motor abilities of the system. Applying empirical learning techniques to real situations brings up some important issues such as observation sparsity in high dimensional spaces, arbitrary underlying functional forms of the reinforcement distribution and robustness to noise in exemplars. The well established technique of non-parametric projection pursuit regression (PPR) is used to accomplish reinforcement learning by searching for generalization directions determining projections of high dimensional data sets which capture task invariants. Additionally, the learning process generally implies failures along the way. Therefore, the mechanics of the untrained robotic system must be able to tolerate grave mistakes during learning and not damage itself. We address this by the use of an instrumented compliant robot wrist which controls impact forces.
We address the problem of observating a moving agent. In particular, we propose a system for observing a manipulation process, where a robot hand manipulates an object. A discrete event dynamic systems (DEDS) frame work is developed for the hand/object interaction over time and a stabilizing observer is constructed. Low-level modules are developed for recognizing the ``events'' that causes state transitions within the dynamic manipulation system. The work examines closely the possibilities for errors, mistakes and uncertainties in the manipulation system, observer construction process and event identification mechanisms. The system utilizes different tracking techniques in order to observe and recognize the task in an active, adaptive and goal-directed manner.
We propose that some aspects of task based learning in robotics can be approached using nativist and constructivist views on human sensorimotor development as a metaphor. We use findings in developmental psychology, neurophysiology, and machine perception to guide a robotic learning system's level of representation both for actions and for percepts. Visually driven grasping is chosen as the experimental task since it has general applicability and it has been extensively researched from several perspectives. An implementation of a robotic system with a dexterous three fingered hand, compliant instrumented wrist, arm and vision is used to test these ideas. Several sensorimotor primitives (vision segmentation and manipulatory reflexes) are implemented in this system and may be though of as the ``innate'' perceptual and motor abilities of the system. Applying empirical learning techniques to real situations brings up some important issues such as observation sparsity in high dimensional spaces, arbitrary underlying functional forms of the reinforcement distribution and robustness to noise in exemplars. The well established technique of non-parametric projection pursuit regression (PPR) is used to accomplish reinforcement learning by searching for generalization directions determining projections of high dimensional data sets which capture task invariants. Additionally, the learning process generally implies failures along the way. Therefore, the mechanics of the untrained robotic system must be able to tolerate grave mistakes during learning and not damage itself. We address this by the use of an instrumented compliant robot wrist which controls impact forces. [Accepted: AAAI Fall Symposium on Sensory Aspects of Robot Intelligence, Asilomar, CA, November 14-17 1991]
This paper addresses force control in overconstrained dynamic systems with special emphasis on robot control and multiarm coordination. Previous approaches to force control are studied and many of these are shown to be unsuitable for dynamic force control. Practical and theoretical considerations for designing force control algorithms are discussed. Experimental and simulation results that validate the theoretical findings are presented for a single-degree-of-freedom pneumatic force controller. Finally the theoretical development of a two-arm manipulation system with an extended statespace formulation and a computer simulation of the system are presented to illustrate the application of the basic ideas to a more complicated system.
We endevour to build a robotic manipulation system that is capable of functioning in an unstructured environment. In order to provide such functionality, the system must be capable of reacting in a compliant manner to any stimuli in the environme nt at the motor level, and use the same information to modify its existing plan of action. To build a general enough system that can handle a wide range of manipulatory tasks we build motion primitives both at the task level, which we term motor programs, and at the motor level which we term reflexes. Motor programs specify the behavior of the system at the motor level in terms of the desired stimuli response characteristic. Thus we introduce the concept of behavior to represent the sensorimotor relationship that can be defined at different levels of detail. M ore complex behaviors are manifested by coordinating the behavior of a number of m otor systems. Borrowing extensively from advances in the area of neurobiology and neuropsychology, we mimic the human motor control system by creating a hierarchical control system in which we incorporate the motor programs at the highest level. At the lower levels we breakdown the specified behavior into a constituent reflex actions for each of the manipulators in the system. Between the task level and the motor programs, and a sensorimotor level that reactively coordinates the behavior of the manipulators in the system to produce intelligent behavior. The behavioral robotic framework is used both on a graphics simulator as well as an experimental testbed. The test bed consists of two robot arms, one mounted with an articulated mechanical hand instrumented with tactile sensors, and the other mounted with a mobile range scanner. We test, and extend the hypothesis that complex actions can be accomplished using simpler but coordinated reflexive motions.
The main goal of this paper is to show that there is a natural flow from active perception through exploration of perceptual learning. We have attempted to conceptualize the perceptual process of an organism that has the top-level task of surviving in an unknown environment. During this conceptualization process, four necessary ingredients have emerged for either artificial or biological organisms. First, the sensory apparatus and processing of the organism must be active and flexible. Second, the organism must have exploratory capabilities. Third, the organism must be selective in its data acquisition process. Fourth, the organism must be able to learn. In the section on learning, we have clearly delineated the difference between what must be innate and what must be learned. In order to test our theory, we present the system's architecture that follows from the perceptual task decomposition. The predictions of this theory are that an artificial system can explore and learn about its environment modulo its sensors, manipulators, end effectors and exploratory procedures/attribute extractors. It can describe its world with respect to the built-in alphabet, that is the set of perceptual primitives.
Packet routing is an important problem of parallel computing since a fast algorithm for packet routing will imply 1) fast inter-processor communication, and 2) fast algorithms for emulating ideal models like PRAMs on fixed connection machines.There are three different models of packet routing, namely 1) Store and forward, 2) Multipacket, and 3) Cut through. In this paper we provide a survey of the best known randomized algorithms for store and forward routing, k-k routing, and cut through routing on the Mesh Connected Computers.
In this paper we present randomized algorithms for k-k routing, k-k sorting, and cut through routing. The stated resource bounds hold with high probability. The algorithm for k-k routing runs in \lceil[k/2]\rceil n+o(kn) steps. We also show that k-k sorting can be accomplished within \lceil[k/2]\rceil n+n+o(kn) steps, and cut through routing can be done in [3/4]kn+[3/2]n+o(kn) steps. The best known time bounds (prior to this paper) for all these three problems were kn+o(kn) . [kn/2] is a known lower bound for all the three problems (which is the bisection bound), and hence our algorithms are very nearly optimal. All the above mentioned algorithms have optimal queue length, namely k+o(k). These algorithms also extend to higher dimensional meshes.
This paper focuses on algorithms that solve CSAT (conjunctive normal form satisfiability) by searching for a satisfying truth assignment for the given formula F. We identify four basic ways to improve the basic search procedure: constraint propagators, simplifying transformations, heuristics, and other miscellaneous improvements. In each of these categories, we survey the existing improvements and suggest new ones. We lower the average time it takes to perform the simplest kind of constraint propagation from O(L) to O([L/P]), where L is the length of F and P is the number of propositions in F; this is optimal. We lower the current upper bound for CSAT from O(20.128L) to O(20.128(L - N)), where N is the number of clauses in F. Finally, we experimentally determine the fastest possible algorithm with respect to each of the basic improvements we consider.
In this paper we present a framework for research into the development of an Active Observer. The components of such an observer are the low and intermediate visual processing modules. Some of these modules have been adapted from the community and some have been investigated in the GRASP laboratory, most notably modules for the understanding of surface reflections via color and multiple views and for the segmentation of three dimensional images into first or second order surfaces via superquadric/parametric volumetric models. However the key problem in Active Observer research is the control structure of its behavior based on the task and situ ation. This control structure is modeled by a formalism called Discrete Events Dynamic Systems (DEDS).
We describe a layered approach to the specification and verification of real-time systems. Application processes are specified in the CSR application language, which includes high-level language constructs such as timeouts, deadlines, periodic processes, interrupts and exception-handling. Then, a configuration scema is used to map the processes to system resources, and to specify the physical communication links between them. To analyze and execute the entire system, we automatically translate the result of the mapping into the CCSR process algebra. CCSR characterizes CSR's resource-based computatin model by a priority-sensitive, operational semantics, which yields a set of equivalence-preserving proof rules. Using this proof system, we perform the algebraic verification of our original real-time system.
The extensions of first-order logic with a least fixed point operators (FO + LFP) and with a partial fixed point operator (FO + PFP) are known to capture the complexity classes P and PSPACE respectively in the presence of an ordering relation over finite structures. Recently, Abiteboul and Vianu [AV91b] investigated the relation of these two logics in the absence of an ordering, using a mchine model of generic computation. In particular, they showed that the two languages have equivalent expressive power if and only if P = PSPACE. These languages can also be seen as fragments of an infinitary logic where each formula has a bounded number of variables, Lw ¥w (see, for instance, [KV90]). We present a treatment of the results in [AV91b] from this point of view. In particular, we show that we can write a formula of FO + LFP and P from ordered structures to classes of structures where every element is definable. We also settle a conjecture mentioned in [AV91b] by showing that FO + LFP in properly contained in the polynomial time computable fragment of Lw¥w, raising the question of whether the latter fragment is a recursively enumerable class.
We develop a tool for the rigorous formulation and proof of properties of runtime memory management for a sample programming language based on a linear type system. Two semantics are described, one at a level of observable results of computations and one that describes linear connectives in terms of memory-management primitives. The two semantics are proven equivalent and the memory-management model is proven to satisfy fundamental correctness criteria for reference counts.
In this work we establish a framework for the general problem of observation, which may be applied to different kinds of visual tasks. We construct ``intelligent'' high-level control mechanisms for active visual recognition of different processes within a hybrid dynamic system. We address the problem of observing a manipulation process in order to illustrate the ideas and motive behind our framework. Active and autonomous tracking mechanisms are developed for the observer agent which is completely decoupled from the manipulation agent. We use a discrete event dynamic system as a high-level structuring technique to model the manipulation system. The formulation utilizes the knowledge about the system and the different actions in order to solve the observer problem in an efficient, stable and practical manner. The model uses different tracking mechanisms so that the observer can ``see'' the workspace of the manipulating robot. An automaton is developed for the hand/object interaction over time and a stabilizing observer is constructed. Low-level modules are developed for recognizing the visual ``events'' that causes state transitions within the dynamic manipulation system in real time. A coarse quantization of the manipulation actions is used in order to attain an active, adaptive and goal-directed sensing mechanism. The formulation provides high-level symbolic interpretations of the scene under observation. The discrete event framework is augmented with mechanisms for recovering the continuous parametric evolution of the scene under observation and for asserting the state of the manipulation agent. This work examines closely the possibilities for errors, mistakes and uncertainties in the manipulation system, observer construction process and event identification mechanisms. We identify and suggest techniques for modeling these uncertainties. Ambiguities are allowed to develop and are resolved after finite time. Error recovery mechanisms are also devised. The computed uncertainties are utilized for navigating the observer automaton state space, asserting state transitions and developing a suitable tracking strategy for the observer agent. The computed uncertainties are utilized for navigating the observer automaton state space, asserting state transition and developing a suitable tracking strategy for the observer agent. The approach used can be considered as a framework for a variety of visual tasks, as it lends itself to be a practical and feasible solution that uses existing information in a robust and modular fashion. Theoretical aspects and experimental results of the work support adopting this framework as a new basis for performing several task-oriented recognition, inspection and observation of visual phenomena.
An autonomous vehicle must be able to find and maintain visual contact with a negotiable path before it. In outdoor environments this generally means locating a road in front of the vehicle. this masters thesis presents a strategy for road tracking that uses two road cues in order to maintain better visual contact with a road than could be achieved with either cue alone. Until recently, most autonomous vehicles relied on a single cue to find the road in front of them. Using multiple measurements from the image we can produce a more robust system. Also, using two cues to find the road, we have been able to study the ability of the system to recover when contradictory evidence exits concerning the location of the road in front of the vehicle. The two cues to the road's location we use are the road's surface shading and its boundaries. The road's surface properties as captured in an image are modeled by bi-variate polynomial surface patches of up to second order. This is the first time that shading information has been used in vision for autonomous navigation. The road's boundaries, and other line-like features of a road, are modeled by line segments fit the image edges. With these two cues, we have a complementary description of an image - the surface patches describe the continuous portions of the image and the line segments describe the discontinuous portions of the image. The two cues also provide different information about the three dimensional environment in which the road and vehicle exist. The surface patches provide information about the material characteristics of the road and the illumination properties of the scene. The line segments representing the sides of a constant width road provide information about the relationship between the road and the vehicle in space in accordance with the laws of perspective viewing. The surface patches and line segments that model the road in one image are used along with knowledge of the vehicle's motion to predict the appearance of the road in a subsequent image. At each image frame the models are updated to take into account new aspects of the road's appearance. The modeling states with the system segmenting under guidance from a human operator an image of the scene in front of the vehicle.
This thesis presents the design of an experimental platform for parallel systems--E-kernel on the Victor V256 parallel system. E-kernel is an embedding kernel developed for the support of program mapping and network reconfiguration. E-kernel supports two levels of embedding: in the first level, the embedding of a network topology onto Victor's 2-d mesh network, and in the second level, the embedding of a task graph onto the system network. The first level corresponds to network reconfiguration (through software) and the second level to program mapping (placement of processes to processors through software). Victor is a partitionable, message passing, experimental parallel system that has been designed and developed in the modular microsystems group of the parallel systems department at the IBM Thomas J. Watson Research Center in part to support this research. Key architectural features incorporated into Victor, such as the need to partitioning and monitoring, have been driven by this research, and solutions in part are a result of it. The development of E-kernel translates some of the many theoretical results in graph embeddings into practical tools for program mapping and network reconfiguration in a parallel system. With hardware and software system supports like these, users are able to design their programs according to the most natural task graph topologies, with the system attempting the communication optimization automatically on its network. Victor V256, together with E-kernel, provides a rich experimentation environment for parallel systems.