MS-CIS-90-01 (LINC LAB 161)

The Convergence of Mildly Context-Sensitive Grammar Formalisms

Aravind K. Joshi, K. Vijay-Shanker, David Wei

Investigations of classes of grammars that are nontransformational and at the same time highly constrained are of interest both linguistically and mathematically. Context-free grammars (CFG) obviously form such a class. CFGs are not adequate (both weakly and strongly) to characterize some aspects of language structure. Thus how much more power beyond CFG is necessary to describe these phenomena is an important question. Based on certain properties of tree adjoining grammars (TAG) an approximate characterization of class of grammars, mildly context-sensitive grammars (MCGS), has been proposed earlier. In this paper, we have described the relationship different grammar formalisms, all of which belong to MCSG. In particular, we have shown that head grammars (HG), combinatory categorial grammars (CCG), and linear indexed grammars (LIG) and TAG are all weakly equivalent. These formalisms are all distinct from each other at least in the following aspects: (a) the formal objects and operations in each formalism, (b) the domain of locality over which dependencies are specified, (c) the degree to which recursion and the domain of dependencies are factored, and (d) the linguistic insights that are captured in the formal objects and operations in each formalism. A deeper understanding of this convergence is obtained by comparing these formalisms at the level of the derivation structures in each formalism. We have described a formalism, the linear context-free rewriting system (LDFR), as a first attempt to capture the closeness of the derivation structures of these formalisms. LCFRs thus make the notion of MCSGs more precise. We have shown that LCFRs are equivalent to multicomponent tree adjoining grammars (MCTAGs), and also briefly discussed some variants of TAGs, lexicalized TAGs, feature structure based TAGs, and TAGs in which local domination and linear precedence are factored TAG(LD/LP).

MS-CIS-90-02 (GRASP LAB 200)

Underestimation of Visual Texture Slant by Human Observers: A Model

M. Turner, G. Gerstein, R. Bajcsy

The perspective image of an obliquely inclined textured surface exhibits shape and density distortions of texture elements which allow a human observer to estimate the inclination angle of the surface. However, since the work of Gibson (1950) it has been known that, in the absence of other cues, humans tend to underestimate the slant angle of the surface, particularly when the texture is perceived as being ``irregular.''

The perspective distortions which affect texture elements also shift the projected spatial frequencies of the texture in systematic ways. Using a suitable local spectral filter to measure these frequency gradients, the inclination angle of the surface my be estimated. A computational model has been developed which performs this task using distributions of outputs from filters found to be a good description of simple cell receptive fields. However, for ``irregular'' textures the filter output distributions are more like those of regular textures at shallower angles of slant, leading the computational algorithm to underestimate the slant angle. This behavioral similarity between human and algorithm suggest the possibility that a similar visual computation is performed in cortex.

MS-CIS-90-05 (LINC LAB 162)

From Simple Associations So Systematic Reasoning A Connectionist Representation Of Rules, Variables and Dynamic Bindings

Lokendra Shastri, Venkat Ajjanagadde

Human agents draw a variety of inferences effortlessly, spontaneously, and with remarkable efficiency--as though these inferences are a reflex response of their cognitive apparatus. The work presented in this paper is a st ep toward a computational account of this remarkable reasoning ability. We des cribe how a connectionist system made up of simple and slow neuron-like element s can encode millions of facts and rules involving predicates and variables, and yet perform a variety of inferences within hundreds of milliseconds. We observe that an efficient reasoning system must represen t and propagate, dynamically, a large number of variable bindings. The propose d system does so by propagating rhythmic patterns of activity wherein dynamic binding are represented as the in-phase , i.e., synchronous, firing of appropriate nodes. The mechanisms for representing and propagating dynamic bindings are biologically plausible. Neurophysiological evidence suggests that similar mechanisms may in fact be used by the brain to represent and process sensorimotor information.

MS-CIS-90-06 (LINC LAB 181)

Interpretive Value Analysis

David Klein

This dissertation presents interpretive value analysis (IVA), a framework for explaining and refining choices among competing alternatives in the context of intelligent systems. IVA increases the transparency of value theory, a formal model of choice, to provide a framework for modeling choices that is both formal and transparent. The components of IVA include (1) an interpretation of value theory that provides an intuitive yet formally sound vocabulary for talking about choices, (2) a set of strategies for explaining choices, and (3) a set of strategies for refining choices.

IVA at one addresses problems in artificial intelligence (AI) and in decision analysis (DA). From an AI perspective, IVA provides a general foundation for building formally justifiable, intelligible, modifiable systems for choosing among alternatives. A secondary contribution of the work to AI is a set of observations concerning formality and transparency; although previous approaches to modeling choices in a systems context generally have reflected a view of formality and transparency as competitive properties of representations, our experience developing IVA suggests that these properties are synergistic. Finally, the dissertation outlines a potential approach to employing other formal models in the context of intelligent systems.

From a DA perspective, IVA addresses problems of transparency. First, IVA can potentially increase the acceptance of decision-theoretic advice by providing methods for justifying that advice in intuitive terms. Second, IVA provides an approach to managing bias in parameter assessment; the framework provides users with an opportunity to observe the step-by-step effect of a parameter value on the final result, so that users' responses may potentially be influenced less by the fashion in which parameter-assessment questions are posed. Third, IVA can potentially reduce the demands on parameter-assessment methods by providing for the incremental repair of model parameters. Finally, the framework provides and approach to the problem of managing changing preferences over time.

Many of the elements of IVA are implemented in VIRTUS, a shell for building systems that choose among competing alternatives. Three practical systems have been constructed using VIRTUS, in the domains of marketing process control and medicine.

MS-CIS-90-07 (GRASP LAB 2020)

A Distributed System for Robot Manipulator Control NSF Grant ECS-11879 - Fourth Report

Richard P. Paul, Peter Corke, Janez Funda, Gaylor Holder, Hiroaki Kobayashi, Yangsheng Xu, Yehong Zhang

This is the fourth annual report representing our last years work under the current grant. This work was directed to the development of a distributed computer architecture to function as a force and motion server to a robot system. In the course of this work we developed a compliant contact sensor to provide for transitions between position and force control; developed an end-effector capable of securing a stable grasp on an object and a theory of grasping; developed and build a controller which minimizes control delays; explored a parallel kinematics algorithms for the controller; developed a consistent approach to the definition of motion both in joint coordinates and in Cartesian coordinates; developed a symbolic simplification software package to generate the dynamics equations of a manipulator such that the calculations may be split between background and foreground.

MS-CIS-90-08 (GRASP LAB 203)

Redundancy Control of A Robot Manipulator Using A Systolic Array Processor

Yehong Zhang

This thesis provides an approach to the solution of a number of key problems in Robotics, namely planning, force and motion control of a highly redundant manipulator system by means of a special computer architecture. Robotic control is a computationally intensive task. The real time requirement makes many control formulations impractical. In particular, planning and redundancy control require so much computation that they are performed off-line. Planning algorithms are global in nature and are carried out before motion starts. Redundancy control involves the computation of a pseudoinverse of 6xn matrix which is computationally expensive and thus real time control is very difficult.

In this thesis, the motion and force control of a highly redundant robotic system is studied. A local, time optimal planning algorithm is formulated to provide the robot with a time optimal trajectory. A hybrid motion/force control method for a highly redundant system using joint space partition and compensation is also presented. At the same time, a special purpose Systolic Array Processor is studied and is applications in Robotics are explored. Because of the matrix nature of control formulations, a matrix engine based on the systolic computational structure greatly enhances the computational power of the robot controller making real time planning and control possible.

MS-CIS-90-09 (LINC LAB 163)

TraumAID: AI Support For The Management Of Multiple Trauma

Bonnie L. Webber, John R. Clarke, Ron Rymon, Michael Niv

This paper outlines the particular demands that multiple trauma makes on systems designed to provide appropriate decision support, and the ways that these demands are currently being met in our system, TraumAID. The demands follow from: (1) the nature of trauma and the procedures used in diagnosis, (2) the need to adjust diagnostic and therapeutic procedures to available resource levels, (3) the role of anatomy in trauma and the need for anatomical reasoning, and (4) the competing demands of multiple injuries and the consequent need for planning. We believe that these demands are not unique to multiple trauma, so that the paper may be of general interest to expert system research and development. (This paper appears in the Proceedings of the 1990 AAAI Symposium on Artificial Intelligence and Medicine, Stanford University, CA March 1990)

MS-CIS-90-10 (GRASP LAB 204)

Analysis Of The Effects Of Model Mismatch And Flat MMF For Estimating Particle Motion

Siu-Leong Iu

In this report, we analyze the performance degradation due to three classes of model mismatch: parameter jumping, undermodeling and overmodeling, in estimating the particle motion by using the orthogonal polynomials to model the trajectory. We find that these model mismatches make the `optimal estimator' to have large bias and mean squared error. For the case of undermodeling, the estimation error increases, in general, without a bound as the observation interval increases. We then propose the Finite Lifetime Alternately Triggered Multiple Model Filter (FLAT MMF), as a solution. FLAT MMF is a filter composed of a set of K indentical conventional state estimation filters, each triggered alternately. After the last filter is triggered, the oldest one is triggered again and so on. The structure of Multiple Model Filter is used to combine these estimates optimally, in the sense of minimum mean squared error. We find that the ration of weightings in FLAT MMF are related to some independent non-central X² random variables. Consequently, we show that the FLAT MMF can provide an estimate that follows abrupt changes in the trajectory and has the small bias for undermodeling. For the case of overmodeling or the case that the trajectory model matches to the actual motion, the estimate does not degrade significantly.

A number of simulations are conducted to illustrate the estimation performance degradation due to the model mismatches for the convential Kalman filter and the performance improvement as the proposed FLAT MMF is used.

MS-CIS-90-11 (LINC LAB 164)

Parsing With Lexicalized Tree Adjoining Grammar

Yves Schabes, Aravind K. Joshi

Most current linguistic theories give lexical accounts of several phenomena that used to be considered purely syntactic. The information put in the lexicon is thereby increased in both amount and complexity: see, for example, lexical rules in LFG, GPSG, HPSG, Combinatory Categorial Grammars, some versions of GB theory, and Lexicon-Grammars.

We would like to take into account this fact while defining a formalism. We therefore explore the view that syntactical rules are not separated from lexical items. We say that a grammar is lexicalized if it consists of:

· A finite set of structures each associated with lexical items; each

lexical item will be called the anchor of the corresponding structure; the structures define the domain of locality over which constraints are specified.

· An operation or operations for composing the structures.

There is a natural general two-step parsing strategy that can be defined for `lexicalized' grammars. In the first stage, the parser selects a set of elementary structures associated with the lexical items in the input sentence, and in the second stage the sentence is parsed with respect to this set. The strategy is independent of the nature of the elementary structures in the underlying grammar. In principle, any parsing algorithm can be used in the second stage.

We consider Lexicalized Tree Adjoining Grammars as an instance of lexicalized grammars. We take three main types of parsing algorithms: purely top-down (as in definite clause parsing), purely bottom-up (as the Earley-type parser). For each type, we investigate if the two-step strategy provides any improvement. For the Earley-type parser, we evaluate the two-step strategy with respect to two characteristics. First, the amount of filtering on the entire grammar is considered: once the first pass is performed, the parser uses only a subset of the grammar. Second, we evaluate the use of non-local information: The structures selected during the first pass encode the morphological value (and therefore the position in the string) of their anchor.

MS-CIS-90-12 (GRAPHICS LAB 32)

Interactive Real-Time Articulated Figure Manipulation Using Multiple Kinema tic Constraints

Cary B. Phillips, Jianmin Zhao, Norman I. Badler

In this paper, we describe an interactive system for positioning articulated figures which uses a 3D direct manipulation technique to provide input to an inverse kinematics algorithm running in real time. The system allows the user to manipulate highly articulated figures, such as human figure models, by interactively dragging 3D ``reach goals''. The user may also define multiple ``reach constraints'' which are enforced during the manipulation. The 3D direct manipulation interface provides a good mechanism for control of the inverse kinematics algorithm and helps it to overcome problems with redundancies and singularities which occur with figures of many degrees of freedom. We use an adaptive technique for evaluating the constraints which allows us to ensure that only a certain user-controllable amount of time will be consumed by the inverse kinematics algorithm at each iteration of the manipulation process. This technique is also sensitive to the time it takes to redraw the screen, so it prevents the frame display rate of the direct manipulation from becoming too slow for interactive control.

MS-CIS-90-13 (GRASP LAB 205)

Multi-Oriented Multi-Resolution Edge Detection

Laurent Peytavin

In order to build an edge detector that provides information on the degree of importance spatial features represent in the visual field, I used the wavelet transform applied to two-dimensional signals and performed a multi-resolution multi-oriented edge detection. The wavelets are functions well-localized in spatial domain and in frequency domain. Thus the wavelet decomposition of a signal or an image provides outputs in which you can still extract spatial features and not only frequency components.

In order to detect edges the wavelet I chose is the first derivative of a smoothing function. I decompose the images as many times as I have directions of detection. I decided to work for the momment on the X-direction and the Y-direction only. Each step of the decomposition corresponds to a different scale. I use a discrete scale s =2^j (dyadic wavelet) and a finite number of decomposed images. Instead of scaling the filters at each step I sample the image by 2 (gain in processing time). Then, I extract the extrema, track and link them from the coarsest scale to the finest one. I build a symbolic image in which the edge-pixels are not only localized but labelled too, according to the number of appearances in the different scales and according to the contrast range of the edge. Without any arbitrary threshold I can subsequently classify the edges according to their physical properties in the scene and their degree of importance.

This process is subsequently intended to be part of more general perceptual learning procedures. The context should be: none or as little as possible a priori knowledge, and the ultimate goal is to integrate this detector in a feedback system dealing with color information, texture and smooth surfaces extraction. Then decisions must be taken on symbolic levels in order to make new interpretation or even new edge detection on ambiguous areas of the visual field.

MS-CIS-90-14 (GRASP LAB 206)

Final Report On Advanced Research In Range Image Interpretation For Automat ed Mail Handling

Ruzena Bajcsy, Kwangyoen Wohn, Franc Solina, Alok Gupta, Gareth Funka-L ea, Celina Imielinska, Pramath Sinha, Constantine Tsikos

We discuss an implemented software system that interprets dense range images obtained from scenes of heaps of postal pieces: letter, parcels, etc. We describe a model-based system consisting of segmentation, modeling, and classification procedures.

First, the range image is segmented into regions and reasoning is done about the physical support of these regions. Second, for each region several possible 3-D interpretations are made based on the partial knowledge which is updated whenever a new interpretation is obtained. Finally each interpretation is tested against the data for its consistency.

We have chose the superquadric model as our 3-D shape descriptor, plus deformations such as tapering and bending along the major axis. The superquadric model is an analytic representation of volume for which a cross-section is one of a class of curves varying between rectangular to elliptical shaped. Superquadric parameters are recovered by minimizing the least-squares error between the superquadric surface and the range data. The system recovers p position, orientation, shape, size and class of the object. Using the goodness of fit and Euclidean distance measures, and the shape and size parameters of the recovered model, objects are classified into one of the following broad categories: flat (letters), box (parcels), roll (circular and elliptical cylinders), and irregular (film mailers etc.).

The overall approach to this problem has been to find the most general yet computationally economical method to interpret the data. Experimental results obtained from a large number of complex range images are reported.

MS-CIS-90-15 (GRASP LAB 207)

Grasp News

Volume 6/Number 1 - Fall 1989

The Volume 6, Number 1 edition of the Grasp News marks the revival of a longstanding tradition. 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 1989, follows the format of previous edit ions. The Feature Article, which highlights the research of Raymond McKendall, Gerda Kamberova, and Professor Max Mintz, is entitled Robust Fusion of Location Data: A Decision-Theoretic Approach. The research abstracts summarize the progress of students, postdoctoral fellows, visiting professors, and faculty. The Vision Research sections cover topics specifically related to vision, while the Robotics Research sections cover subjects such as the kinematics and dynamics of mechanical systems and real-time processing. There is also a section on laboratory Software and Hardware Developments . This edition comprises over 33 articles from 48 contributors, which makes it the largest Grasp News ever!

MS-CIS-90-16 (GRASP LAB 208)

CCSR: A Calculus For Communicating Shared Resources

Richard Gerber, Insup Lee

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 formalism called Communicating Shared Resources, or CSR. This paper presents the priority-based process algebra called the Calculus for Communicating Shared Resources (CCSR), which provides an equational characterization of the CSR language. The computation model of CCSR is resource-based in that multiple resources execute synchronously, while processes assigned to the same resource are interleaved according to their priorities. CCSR possesses a prioritized strong equivalence for terms based on strong bisimulation. The paper also describes a producer and consumer problem whose correct timing behavior depends on priority.

MS-CIS-90-17 (GRAPHICS LAB 33 & LINC LAB 165)

Animation From Instructions

Norman I. Badler, Bonnie L. Webber, Jugal Kalita, Jeffrey Esakov

We believe that computer animation in the form of narrated animated simulations can provide an engaging, effective and flexible medium for instructing agents in the performance of tasks. However, we argue that the only way to achieve the kind of flexibility needed to instruct agents of varying capabilities to perform tasks with varying demands in work places of varying layout is to drive both animation and narration from a common representation that embodies that same conceptualization of tasks a nd actions as Natural Language itself. To this end, we are exploring the use of Natural Language instructions to drive animated simulation s. In this paper, we discuss the relationship between instructions and behavio r that underlie our work and the overall structure of our system. We then desc ribe in somewhat more detail three aspects of the system - the representation u sed by the Simulator and the Motion Generators used in the system.

MS-CIS-90-18 (LINC LAB 166)

Encoding A Dependent-Type l-Calculus In A Logic Programming Language

Amy Felty, INRIA Sophia-Antipolis, Dale Miller, University of Pennsylvania

Various forms of typedl-calculi have been proposed as specification languages for representing wide varieties of object logics. The logical framework, LF, is an example of such a dependent-type l-calculus. A small subset of intuitionistic logic with quantification over simple type l-calculus has also been proposed as a framework for specifying general logics. The logic of hereditary Harrop formulas with quantification at all non-predicate types, denoted here as hh^w, is such a meta-logic that has been implemented in both the Isabelle theorem prover and the l-Prolog logic programming language. Both frameworks provide for specifications of logics in which details involved with free and bound variable occurrences, substitutions, eigenvaribles, and the scope of assumptions within object logics are handled correctly and elegantly at the ``meta'' level. In this paper, we show how LF can be encoded into hh^w in a direct and natural way by mapping the typing judgments in LF into propositions in the logic of hh^w clauses, and the proofs in one system correspond directly to proofs in the other system. Relating these two languages makes it possible to provide implementations of proof checkers and theorem provers for logics specified in LF by using standard logic programming techniques which can be used to implement hh^w.

MS-CIS-90-19 (GRASP LAB 209)

A Contact Stress Model For Determining Forces In An Equilibrium Grasp

Pramath Raj Sinha

Most available methods that predict the forces necessary to grasp an arbitrary object treat the object and the fingers as rigid bodies and the finger/object interface as a point contact with Coulomb friction. For statically indeterminate grasps, therefore, while it is possible to find grasps that are stable, there is no unique determination of the actual forces at the contact points and equilibrium grasps are determined as many-parameter families of solutions. Also, these models sometimes lead to phenomenologically incorrect results which, while satisfactory from a purely mathematical viewpoint, are counterintuitive and not likely to be realized in practice. The model developed here utilizes a contact-stress analysis of an arbitrarily shaped object in a multi-fingered grasp. The fingers and the object are all treated as elastic bodies and the region of contact is modeled as a deformable surface patch. The relationship between the friction and normal forces is now nonlocal and nonlinear in nature and departs from the Coulomb approximation. The nature of the constraints arising out of conditions for compatibility and static equilibrium motivated the formulation of the model as a non-linear constrained minimization problem. The total potential energy of the system is minimized, subject to the nonlinear, equality and inequality constraints on the system, using the Schittkowski algorithm. The model is able to predict the magnitude of the inwardly directed normal forces, and both the magnitude and direction of the tangential (friction) forces at each finger/object interface for grasped objects in static equilibrium. Examples in two and three dimensions are presented along with application of the model to the grasp transfer maneuver.

MS-CIS-90-20 (LINC LAB 167)

Extending Definite Clause Grammars with Scoping Constructs

Remo Pareschi, Dale Miller

Definite Clause Grammars (DCGs) have proved valuable to computational linguists since they can be used to specify phrase structured grammars. It is well known how to encode DCGs in Horn clauses. Some linguistic phenomena, such as filler-gap dependencies, are difficult to account for in a completely satisfactory way using simple phrase structured grammar. In the literature of logic grammars there have been several attempts to tackle this problem by making use of special arguments added to the DCG predicates corresponding to the grammatical symbols. In this paper we take a different line, in that we account the filler-gap dependencies by encoding DCGs within hereditary Harrop formulas, an extension of Horn clauses (proposed elsewhere as a foundation for logic programming) where implicational goals and universally quantified goals are permitted. Under this approach, filler-gap dependencies can be accounted for in terms of the operational semantics underlying hereditary Harrop formulas, in a way reminiscent of the treatment of such phenomena in Generalized Phrase Structure Grammar (GPSG). The main features involved in this new formulation of DCGs are mechanisms for providing scope to constants and program clauses along with a mild use of l-terms and l-conversion.

MS-CIS-90-21 (LINC LAB 168)

From Operational Semantics to Abstract Machines: Preliminary Results

John Hannan, Dale Miller

The operational semantics of functional programming languages is frequently presented using interence rules in with simple meta-logics. Such presentations of semantics can be high-level and perspicuous since meta-logics often handle numerous syntactic details in a declarative fashion. This is particularly true of the meta-logic we consider here, which includes simply types l-terms, quantification at higher types, and b-conversion. Evaluation of functional programming languages is also often presented using low-level descriptions based on abstract machines: simple term rewriting systems in which few high-level description of evaluation using inference rules can be systematically transformed into a low-level abstract machine by removing dependencies on high-level features of the meta-logic until the resulting inference rules are so simple that they can be immediately identified as specifying an abstract machine. In particular, we present in detail the transformation of two inference rules specifying call-by-name evaluation of the untyped l-calculus into the Krivine machine, a stack-based abstract machine that implements such evaluation. The resulting machine uses de Bruijn numerals and closures instead of formal substitution. We also comment on a construction of a simplified SECD machine implementing call-by-value evaluation. This approach to abstract machine construction provides a semantics-directed method for motivating, proving correct, and extending such abstract machines.

MS-CIS-90-22 (GRASP LAB 210)

Estimation Of General Rigid Body Motion From A Long Sequence Of Images

Sui-Leong Iu

In estimating the 3-D rigid body motion and structure from time-varying images, most of previous approaches which exploit a large number of frames assume that the rotation, and the translation in some case, are constant. For a long sequence of images, this assumption in general is not valid. In this paper, we propose a new state estimation formulation for the general motion in which the 3-D translation and rotation are modeled as the polynomials of arbitrary order. Extended Kalman filter is used to find the estimates recursively from noisy images. A number of simulations including the Monte Carlo analysis are conducted to illustrate the performance of the proposed formulation.

MS-CIS-90-23 (LINC LAB 169)

Structure and Intonation In Spoken Language Understanding

Mark Steedman

The structure imposed upon spoken sentences by intonation seems frequently to be orthogonal to their traditional surface-syntactic structure. However, the notion of ``intonational structure'' as formulated by Pierrehumbert, Selkirk, and others, can be subsumed under a rather different notion of syntactic surface structure that emerges from a theory of grammar based on a ``Combinatory'' extension to Categorial Grammar. Interpretations of constituents at this level are in turn directly related to ``information structures'', or discourse-related notions of ``theme'', ``rheme'', ``focus'' and presupposition''. Some simplifications appear to follow for the problem of integrating syntax and other high-level modules in spoken language systems.

MS-CIS-90-24 (LINC LAB 170)

A Lexicalized Tree Adjoining Grammar for English

Anne Abeilleé, Kathleen Bishop, Sharon Cote, Yves Schabes

This paper presents a sizable grammar for English written in the Tree Adjoining grammar (TAG) formalism. The grammar uses a (TAG) that is both lexicalized (Schabes, Abeille, Joshi 1988) and feature based (Vijay-Shanker, Joshi 1988). In this paper, we describe a wide range of phenomena that it covers.

A Lexicalized TAG (LTAG) is organized around a lexicon, which associates sets of elementary trees (instead of just simple categories) with the lexical items. A Lexicalized TAG consists of a finite set of trees associated with lexical items, and operations (adjunction and substitution) for composing the trees. A lexical item is called the anchor of its corresponding tree and direc tly determines both the tree's structure and its syntactic features. In particular, the trees define the domain of locality over which constraints are specified and these constraints are local with respect to their anchor. In this paper, the basic tree structures of the English LTAG are described, along with some relevant features. The interaction between the morphological and the syntactic components of the lexicon is also explained.

Next, the properties of the different tree structures are discussed. The use of S complements exclusively allows us to take full advantage of the treatment of unbounded dependencies originally presented in Joshi (1985) and Kroch and Joshi (1985). Structures for auxiliaries and raising-verbs which use adjunction trees are also discussed. We present a representation of prepositional complements that is based on extended elementary trees. This representation avoids the need for preposition incorporation in order to account for double wh-questions (preposition stranding and pied-piping) and the pseudo-passive.

A treatment of light verb constructions is also given, similar to what Abeille (1988c) has presented. Again, neither noun nor adjective incorporation is needed to handle double passives and to account for a CNPC violations in these constructions. TAG's extended domain of locality allows us to handle, within a single level of syntactic description, phenomena that in other frameworks require either dual analyses or reanalysis.

In addition, following Abeillé and Schabes (1989), we describe how to deal with semantic non compositionality in verb-particle combinations, light verb constructions and idioms, without losing the internal syntactic composition of these structures.

The last sections discuss current work on PRO, case, anaphora and negation, and outline future work on copula constructions and small clauses, optional arguments, adverb movement and the nature of syntactic rules in a lexicalized framework.

MS-CIS-90-25 (GRASP LAB 211)

Constant Queue Route On A Mesh

Sanguthevar Rajasekaran, Richard Overholt

Packet routing is an important problem in parallel computation since a single step of inter-processor communication can be thought of as a packet routing task. In this paper we present an optimal algorithm for packet routing on a mesh-connected computer.

Two important criteria for judging a routing algorithm will be 1) its run time, i.e., the number of parallel steps it takes for the last packet to reach its destination, and 2) its queue size, i.e., the maximum number of packets that any node will have to store at any time during routing. We present a 2n - 2 step routing algorithm for an n x n mesh that requires a queue size of only 58. The previous best known result is a routing algorithm with the same time bound but with a queue size of 672. The time bound of 2n - 2 is optimal. A queue size of 672 is rather large for practical use. We believe that the queue size of our algorithm is practical. The improvement in the queue size is possible due to (from among other things) a new 3s + o(s) sorting algorithm for an sx s mesh.

MS-CIS-90-26 (GRASP LAB 212)

Randomized Parallel Selection

Sanguthevar Rajasekaran

We show that selection on an input of size N can be performed on a P-node hypercube (P = N/(log N)) in time O(n/P) with high probability, provided each node can process all the incident edges in one unit of time (this model is called the parallel model and has been assumed by previous researchers (e.g.,[17])). This result is important in view of a lower bound of Plaxton that implies selection takes w((N/P)loglogP + logP) time on a P-node hypercube if each node can process only one edge at a time (this model is referred to as the sequential model).

MS-CIS-90-27 (GRASP LAB 213)

Teleoperation In The Presence Of Communication Delays

Janez Funda, Thierry Simeon, Richard P. Paul

MS-CIS-90-28 (GRASP LAB 214)

Minimax Estimation Of A Discrete Location Parameter For A Continuous Distri bution (Dissertation)

Raymond A. McKendall

The subject of this research is the following stochastic model: Z = q+V. The random variable Z is a measurement of the discrete location parameter $\theta$ in continuous, additive noise V. The possible values of q are 0, ±u, ±2u, ¼,±Nu, where N is a positive integer and u is a positive number. The distribution of Z, denoted F_Z(·\midq), is continuous and increasing on  and has a continuous density. In a standard-estimation problem, the distribution F_Z(·\midq) is known. In a robust-estimation problem, the distribution F_Z(·\midq) is uncertain: It is an unknown member of an uncertainty class of distributions. In either case, the goal of this research is to find a minimax estimator of the location parameter q from an observation Z. This goal subsumes the identification of equalizer decision rules and Bayes decision rules for estimating q. The loss function in the underlying statistical decision problem is the zero-one loss function with error tolerance e (a non-negative integer):

Chapters 2 - 7 summarize the main results. Chapters 8 - 21 give the analysis.

MS-CIS-90-29 (LINC LAB 171)

Computation and Linguistics Theory: A Government Binding Theory Parser Usin g Tree Adjoining Grammar (Master's Thesis)

Robert Frank

Government Binding (GB) theory, as a competence theory of grammar, is intended to define what a speaker's knowledge of language consists of. The theory proposes a system of innate principles and constraints which determine the class of possible languages and once instantiated by the parameter values for a given language, the class of well-formed sentences of that language [Chomsky, 1981].

In this thesis, I address the problem of how this knowledge of language is put to use. The answer I give to this question takes the shape of an implemented computational model, a parser, which utilizes the formulation of knowledge of language as proposed in GB theory. GB as a theory of grammar poses a particular problem for instantiation within a cognitively feasible computational model. It has a rich deductive structure whose obvious direct implementation as a set of axioms in a first order theorem prover runs up against the problem of undecidability. Thus, if we accept GB theory as psychologically real, and thus as functioning casually with respect to linguistic processing, there seems to be a paradox: we need a way of putting our knowledge of language, represented in GB theory, to use in a processing theory in an efficient manner.

I will suggest a way out of this paradox. I propose to constrain the class of possible grammatical principles by requiring them to be statable over a linguistically and mathematically motivated domain, that of a tree adjoining grammar (TAG) elementary tree. The parsing process consists of the construction of such primitive structures, using a generalization of licensing relations of proposed in [Abney, 1986], and checking that the constraints are satisfied over these local domains. Since these domains are of bounded size, the constraints will be checkable in constant time and we will be guaranteed efficient, linear time, parsing. Additionally, the incrementality of the construction of the TAG elementary trees is consistent with intuitions of incremental semantic interpretation.

MS-CIS-90-30 (GRASP LAB 215)

Segmentation Of Range Images As The Search For The Best Best Description Of The Scene In Terms Of Geometric Primitives

A. Leonardis, Alok Gupta, Ruzena Bajcsy

Segmentation of range images has long been considered in computer vision as an important but extremely difficult problem. In this paper we present a new paradigm for the segmentation of range images into piecewise continuous patches. Data aggregation is performed via model recovery in terms of variable-order bi-variate polynomials using iterative regression. All the recovered models are potential candidates for the final description of the data. Selection of the models is achieved through a maximization of quadratic Boolean problem. The procedure can be adapted to prefer certain kind of descriptions (one which describes more data points, or has smaller error, or has lower order model). We have developed a fast optimization procedure for model selection. The major novelty of the approach is in combining model extraction and model selection in a dynamic way. Partial recovery of the models is followed by the optimization (selection) procedure where only the ``best'' models are allowed to develop further. The results obtained in this way are comparable with the results obtained when using the selection module only after all the models are fully recovered, while the computational complexity is significantly reduced. We test the procedure on several real range images.

MS-CIS-90-31 (LINC LAB 172)

Representing Object in a Logic Programming Language with Scoping Constructs

Joshua S. Hodas, Dale Miller

We present logic programming language that uses implications and universal quantifiers in goals and in the bodies of clauses to provide a simple scoping mechanism for program clauses and constants. Within this language it is possible to define a simple notion of parametric module and local constant. Given this ability to structure programs, we explore how object-oriented programming, where objects are viewed as abstractions with behaviors, state, and inheritance, might be accommodated. To capture the notion of mutable state, we depart from the pure logic setting by adding a declaration that certain local predicates are deterministic (they succeed at most once). This declaration, along with a goal-continuation passing style of programming is adequate to model the state of objects. We also examine a few aspects of how having objects embedded in logic programming can be used to enrich the notion of object: for example, objects may be partial (that is, may contain free variables) and non-deterministic, and it is possible not only to search for objects with certain properties but also to do hypothetical reasoning about them.

MS-CIS-90-32 (LINC LAB 173)

Natural Language Generation As An Intelligent Activity (Proposal for Dissertation Research)

Robert Rubinoff

In this proposal, I outline a generator conceived of as part of a general intelligent agent. The generator's task is to provide the overall system with the ability to use communication in language to serve its purposes, rather than to simply encode information in language. This requires that generation be viewed as a kind of goal-directed action that is planned and executed in a dynamically changing environment. In addition, the generator must not be dependent on domain or problem-specific information but rather on a general knowledge base that it shares with the overall system. These requirements have specific consequences for the design of the generator and the representation it uses. In particular, the text planner and the low-level linguistic component must be able to interact and negotiate over decisions that involve both high-level constraints. Also, the knowledge representation must allow for the varying perspective that an intelligent agent will have on the things it talks about; the generator must be able to appropriately vary how it describes things as the system's perspective on them changes. The generator described here will demonstrate how these ideas work in practice and develop them further.

MS-CIS-90-33 (LOGIC & COMPUTATION 19)

Notes On Hierarchies And Inductive Inference

Daniel N. Osherson (M.I.T.), Scott Weinstein (University of Pennsylvania)

MS-CIS-90-34 (GRASP LAB 216)

A Framework For Observing A Manipulation Process

Ruzena Bajcsy, Tarek Sobh

We propose a system for observing a robot hand manipulating an object. A discrete event dynamic system is used as a model for the manipulation process. A framework for the hand/object relationship developed and a stabilizing observer is constructed for the system. We describe low-level modules for recognizing the ``events'' that causes state transitions within the dynamic manipulation system. Our system uses different tracking mechanisms in order to control the observation process in an efficient and stable manner.

MS-CIS-90-35 (GRASP LAB 217)

Teleprogramming: Overcoming Communication Delays In Remote Manipulation (Dissertation Proposal)

Janez Funda

MS-CIS-90-36 (LOGIC & COMPUTATION 20)

Polymorphic Rewriting Conserves Algebraic Strong Normalization

Val Breazu-Tannen, Jean Gallier

We study combinations of many-sorted algebraic term rewriting systems and polymorphic lambda term rewriting. Algebraic and lambda terms are mixed by adding the symbols of the algebraic signature to the polymorphic lambda calculus, as higher-order constants.

We show that if a many-sorted algebraic rewrite system R is strongly normalizing (terminating, noetherian), then R + b + h + type-h rewriting of mixed terms is also strongly normalizing. The result is obtained using a technique which generalizes Girard's ``candidats de reductibilité'', introduced in the original proof of strong normalization for the polymorphic lambda calculus.

MS-CIS-90-37 (LOGIC & COMPUTATION 20 1/2)

Polymorphic Rewriting Conserves Algebraic Confluence

Val Breazu-Tannen, Jean Gallier

We study combinations of many-sorted algebraic term rewriting systems and polymorphic lambda term rewriting. Algebraic and lambda terms are mixed by adding the symbols of the algebraic signature to the polymorphic lambda calculus, as higher-order constants. We show that if a many-sorted algebraic rewrite system R has the Church-Rosser property (is confluent), then R + b + type-b + type-b rewriting of mixed terms has the Church-Rosser property too.

b reduction does not commute with algebraic reduction, in general. However, using long normal forms, we show that if R is canonical (confluent and strongly normalizing) then equational provability from R + b + h + type-b + type-h is still decidable.

MS-CIS-90-38 (GRASP LAB 218)

Computational Methods For Task-Directed Sensor Data Fusion and Sensor Planning

Greg Hager, Max Mintz

In this paper, we consider the problem of task-directed information gathering. We first develop a decision-theoretic model of task-directed sensing in which sensors are modeled as noise-contaminated, uncertain measurement systems and sensing tasks are modeled by a transformation describing the type of information required by the task, a utility function describing sensitivity to error, and a cost function describing time or resource constraints on the system.

This description allows us to develop a standard conditional Bayes decision-making model where the value of information, or payoff, of a n estimate is defined as the average utility (the expected value of some functi on of decision or estimation error) relative to the current probability distribution and the best estimate is that which maximizes payoff. T he optimal sensor viewing strategy is that which maximizes the net payoff (decision value minus observation costs) of the final estimate. The advantage of this solution is generality--it does not assume a particular sensing modality or sensing task. However, solutions to this updating problem do not exist in closed-form. This, motivates the development of an approximation to the optimal solution based on a grid-based implementation of Bayes' theorem.

We describe this algorithm, analyze its error properties, and indicate how it can be made robust to errors in the description of sensors and discrepancies between geometric models and sensed objects. We also present the results of this fusion technique applied to several different information gathering tasks in simulated situations and in a distributed sensing system we have constructed.

To appear in the International Journal of Robotics Research.

MS-CIS-90-39 (GRASP LAB 219)

How To Decide From The First View Where To Look Next

Jasna Maver, Ruzena Bajcsy

The task we want to achieve is the description of a random arrangement of unknown objects in a scene. First, a complete spatial map of the scene has to be acquired. To resolve the ambiguities that are caused by occlusions in range images, we need to take sensor measurements from several different views. We have limited ourselves to the images obtained by a laser scanning system which possesses certain features --- occluded regions which 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 are determined.

MS-CIS-90-40 (GRASP LAB 220)

Design, Implementation, and Evaluation Of A Distributed Real-Time Kernel Fo r Distributed Robotics (Dissertation Proposal)

Robert King

Modern robotics applications are becoming more complex due to greater numbers of sensors and actuators. The control of such systems may require multiple processors to meet the computational demands and to support the physical topology of the sensors and actuators. A distributed real-time system is needed to perform the required communication and processing while meeting application-specified timing constraints.

We are designing and implementing a real-time kernel for distributed robotics applications. The kernel's salient features are consistent, user-definable scheduling, explicit dynamic timing constraints, and a two-tiered interrupt approach. The kernel will be evaluated by implementing a two-arm robot control example. Its goal is to locate and manipulate cylindrical objects with spillable contents. Using the application and the kernel, we will investigate the effects of time granularity, network type and protocol, and the handling of external events using interrupts versus polling. Our research will enhance understanding of real-time kernels for distributed robotics control.

MS-CIS-90-41 (GRASP LAB 221)

Robotics Exploration Of Surfaces To Measure Mechanical Properties

Pramath R. Sinha, Ruzena Bajcsy

This paper presents an overview of ongoing research on surface exploration at the GRASP Lab. We are investigating the necessary components and modules that must be embedded into a robot for it to have the exploratory capabilities required to recover mechanical properties from a surface, given minim al a priori information. Eventually, this information will be used t o enable a robot to stand and walk stably on a surface that is unknown and unconstrained. A robot in the agricultural environment will specially benefit from such capabilities since it will need to step and walk on soils with variable properties. The paper proposes a framework for the recovery of the attributes of interest, and describes the laboratory setup designed to test the framework. The design and implementation of exploratory procedures (ep's) to recover penetrability, material hardness and surface roughness by exploring the surface is also described.

MS-CIS-90-42 (GRASP LAB 222)

Exploration Of Surfaces For Robot Mobility

Ruzena K. Bajcsy, Pramath R. Sinha

This paper presents an overview of ongoing research in surface exploration at the GRASP Lab. The objective of the work presented here is to design a system that will explore an environment that is unknown and unconstrained and will enable a robot to adapt to varying surroundings. We are investigating the necessary components/modules that must be embedded into a robot for it to have exploratory capabilities. We have designed and are implementing exploratory procedures (ep's) to recover the mechanical properti es from a surface given minimal a priori information so that a robot or a vehicle can decide whether to and how to move on this surface. The labora tory setup involves a compliant wrist with six degrees of freedom, mounted on a robot arm, and a laser range finder, mounted on another robot arm, as the primary sensors to detect the response of surfaces with varying mechanical properties.

MS-CIS-90-43 (GRASP LAB 223)

How Does A Robot Know Where To Step? Measuring The Hardness and Roughness Of Surfaces

Pramath R. Sinha, Ruzena K. Bajcsy, Richard P. Paul

This paper presents an overview of ongoing research on surface exploration at the GRASP Lab. We are investigating the necessary components and modules that must be embedded into a robot for it to have the exploratory capabilities required to recover mechanical properties from a surface given minima l a priori information. Eventually, this information will be used to enable a robot stand and walk stably in an environment that is unknown and unconstrained. The laboratory setup involves a compliant wrist with six degrees of freedom, mounted on a robot arm, and a prototype foot mounted on the wrist. We have successfully designed and implemented exploratory procedures (ep's) to recover penetrability, material hardness and friction al characteristics by exploring the surface.

MS-CIS-90-44 (LOGIC & COMPUTATION 21)

A Proof of Strong Normalization For The Theory of Constructions Using A Kripke-Like Interpretation

Thierry Coquand, Jean Gallier

We give proof that all terms that type-check in the theory of constructions are strongly normalizing (under b-reduction). The main novelty of this proof is that is uses a ``Kripe-like'' interpretation of the types and kinds, and that it does not use infinite contexts. We explore some consequences of strong normalization, consistency and decidability of type-checking. We also show that our proof yields another proof of strong normalization for LF (under b-reduction), using the reducibility method.

MS-CIS-90-45 (LINC LAB 174)

Structure and Intonation

Mark Steedman

Rules for assigning phrasal intonation to sentences are often assumed to require an autonomous level of ``intonational structure'', distinct from what is usually thought of as surface syntactic structure. The present paper argues that the requisite notion of structure can be subsumed under the generalized notion of surface structure that emerges from the combinatory extension of Categorial Grammar. According to this theory, the syntactic structures and the intonational structures of English are one, and can be captured in a single unified grammar. The interpretations that the grammar provides for such constituents correspond to the entities and open propositions that are concerned in certain discourse-related aspects of intonational meaning that have variously been described as ``theme'' and ``rheme'', ``given'' and ``new'', or ``presupposition'' and ``focus''.

MS-CIS-90-46 (LINC LAB 175)

First Steps Towards An Annotated Database of American English

Mitchell P. Marcus, Beatrice Santorini, David Magerman

This paper reports on one of the first steps in building a very large annotated database of American English. We present and discuss the results of an experiment comparing manual part-of-speech tagging with manual verification and correction of automatic stochastic tagging. The experiment shows that correcting is superior to tagging with respect to speed, consistency and accuracy.

MS-CIS-90-47 (LINC LAB 178)

Part-Of-Speech Tagging Guidelines For The Penn Treebank Project (3rd Revision)

Beatrice Santorini

MS-CIS-90-48 (LINC LAB 179)

Mathematical And Computational Aspects Of Lexicalized Grammars (Dissertation)

Yves Schabes

Most current linguistic theories give lexical accounts of several phenomena that used to be considered purely syntactic. The information put in the lexicon is thereby increased both in amount and complexity. We explore the view that syntactic rules are not separated from lexical items. In this approach, each elementary structure is associated with a lexical item called the anchor. These structures specify extended domains of locality (as compared to context-free grammars) over which constraints can be stated. The `grammar' consists of a lexicon where each lexical item is associated with a finite number of structures for which that item is the anchor. There are `rules' which tell us how these structures are composed. A grammar of this form will be said to be lexicalized.

The process of lexicalization of context-free grammars (CFGs) constrained by linguistic requirements forces us to use operations for combining structures that make the formalism fall in the class of mildly context sensitive languages. We show that substitution, the combining operation corresponding to CFGs, does not allow one to lexicalize CFGs but the combination of substitution and adjunction does. We show how tree-adjoining grammar (TAG) is derived from the lexicalization process of CFGs. Then we show that TAGs are closed under lexicalization and we illustrate the main structures found in a lexicalized TAG for English. The properties of TAGs permit us to encapsulate diverse syntactic phenomena in a very natural way. TAG's extended domain of locality and its factoring of recursion from local dependencies enable us to localize many syntactic dependencies (such as filler-gap) as well as semantic dependencies (such as predicate-arguments).

We investigate the processing of lexicalized TAGs. We first present two general practical parsers that follow Earley-style parsing. They are practical parsers for TAGs because, as for CFGs, the average behavior of Earley-type parsers is superior to its worst case complexity. They are both left to right bottom-up parsers that use top-down predictions but they differ in the way the top down prediction is used.

Then we explain the building of a set of deterministic bottom-up left to right parsers which analyze a subset of tree-adjoining languages. The LR parsing strategy for CFGs is extended to TAG by using a machine, called Bottom-up Embedded Push Down Automaton (BEPDA), that recognizes in a bottom-up fashion the set of tree-adjoining languages (and exactly this set).

Finally we show how lexicalized grammars suggest a natural two-step parsing strategy. We consider lexicalized TAGs as an instance of lexicalized grammar and we examine the effect of the two-step parsing strategy on main types of parsing algorithms.

MS-CIS-90-49 (GRAPHICS LAB 33)

Human Strength Database And Multidimensional Data Display (Dissertation)

Susanna Wei

We study human figure modeling with strength capability to achieve more realistic and natural human motions in a task simulation. First, we develop a strength model and incorporate it in the computer graphics human figure definition. Strength information (maximum torques) is defined as muscle group strengths and is stored on a joint degree of freedom basis in the human figure model. Modeling strength in terms of muscle group strength allows different people to possess different capacities in different muscle groups. Each muscle group strength is modeled as a function of body position, anthropometry, gender, handedness, fatigue, and other strength parameters. In terms of body position, we choose a more generalized model that takes the effects of adjacent joint angles into consideration.

To facilitate the use of strength information (data) in the human-task simulation environment, we have designed and implemented a relational strength database system. Because strength data are sparsely measured over the space of input parameters, we develop interpolation and scaling techniques for the system to estimate the strengths when they are not measured directly. To allow a user to have easy and effective access to the strength database, we have also designed and implemented an interface.

To further enhance the effective use of the strength information, we develop graphical methods to display the multidimensional characteristics of the strength data. We use human figures together with two or three dimensional graphical symbols, colors, and other computer graphics techniques so that the user can visualize the effects of different parameters on strength. These displays give a dynamic changing view of the effects of parameters on strength, and illustrate safe and forbidden body postures (or regions) in terms of strength capability.

MS-CIS-90-50 (LINC LAB 180)

TraumAID: Reasoning and Planning In The Initial Definitive Management Of Multiple Injuries

Bonnie L. Webber, John R. Clarke, Michael Niv, Ron Rymon, Maria Milagros Ibanez

The TraumAID system has been designed to provide computerized decision support to optimize the initial definitive management of acutely injured pati ents after resusitation and stabilization. The currently deployed sy stem, TraumAID 1.0, addresses penetrating injuries to the abdomen and to the ch est. Our experience with TraumAID 1.0 has demonstrated some major deficiencies in rule-based reasoners faced with problems of both diagnosis and treatment. To address these deficiencies, we have redesigned the system (TraumAID 2.0), factoring it into two modules: (1) a rule-based reasoner embodying the knowledge and logical machinery needed to link clinical evidence to diagnostic and therapeutic goals and (2) a planner embodying the global knowledge and logical machinery needed to create a plan that address combinatio ns of them. After describing TraumAID 2.0, we discuss an extension of the traumAID interface(critique mode interaction) that may improve its acceptability in a clinical setting. We close with a brief discussion of management support in resource-limited environments, which is an important issue in the time-critical context of multiple trauma.

MS-CIS-90-51 (GRASP LAB 224)

A Robotic Haptic System Architecture

Mario Campos, Ruzena Bajcsy

In order to carry out a given task in a unstructured environment, a robotic system must extract physical and geometric properties about the environment and the objects therein. We are interested in the question of what are the necessary elements to integrate a robotics system that would be able to carry out a task i.e pick-up and transport objects in an unknown environment. One of the major concerns is to insure adequate data throughout and fast communication between modules within the system, so that haptic tasks can be adequately carried out. We also discuss the communication issues involved in the development of such a system.

MS-CIS-90-52 (GRASP LAB 225)

Image Understanding at the GRASP Laboratory

Ruzena Bajcsy

Research in the GRASP Laboratory has two main themes, parameterized multi-dimensional segmentation and robust decision making under uncertainty. The multi-dimensional approach interweaves segmentation with representation. The data is explained as a best fit in view of parametric primitives. These primitives are based on physical and geometric properties of objects and are limited in number. We use primitives at the volumetric level, the surface level, and the occluding contour level, and combine the results. The robust decision making allows us to combine data from multiple sensors. Sensor measurements have bounds based on the physical limitations of the sensors. We use this information without making a priori assumptions of distributions within the intervals of a priori assumptions of the probability of a given result.

MS-CIS-90-54 (LINC LAB 182)

A Logic Programming Language with Lambda-Abstraction, Function Variables, a nd Simple Unification

Dale Miller

It has been argued elsewhere that a logic programming language with function variables and lambda-abstractions within terms makes a very good meta-programming language, especially when an object language contains notions of bound variables and scope. The lambda Prolog logic programming language and the closely related Elf and Isabelle systems provide meta-programs with both function variables and lambda-abstractions by containing implementations of higher-order unification. In this paper, we present a logic programming language, called L-lambda, that also contains both function variables and lambda-abstractions, but certain restriction are placed on occurrences of function variables. As a result, an implementation of L-lambda does not need to implement full higher-order unification. Instead, an extension to first-order unification that respects bound variable names and scopes is all that is required. Such unification problems are shown to be decidable and to possess most general unifiers when unifiers exist. A unification algorithm and logic programming interpreter are described and proved correct. Several examples of using L-lambda as a meta-programming language are presented.

To appear in Extensions of Logic Programming, edited by Peter Schroeder-Heister, Lecture Notes in Artificial Intelligence, Springer-Verlag. Supported in part by grants ONR N00014-88-K-0633, NSF CCR-87-05596, and DARPA N00014-85-K-0018.

MS-CIS-90-54 (LINC LAB 182)

A Logic Programming Language with Lambda-Abstraction, Function Variables, and Simple Unification

Dale Miller

It has been argued elsewhere that a logic programming language with function variables and lambda-abstractions within terms makes a very good meta-programming language, especially when an object language contains notions of bound variables and scope. The lambda Prolog logic programming language and the closely related Elf and Isabelle systems provide meta-programs with both function variables and lambda-abstractions by containing implementations of higher-order unification. In this paper, we present a logic programming language, called L-lambda, that also contains both function variables and lambda-abstractions, but certain restriction are placed on occurrences of function variables. As a result, an implementation of L-lambda does not need to implement full higher-order unification. Instead, an extension to first-order unification that respects bound variable names and scopes is all that is required. Such unification problems are shown to be decidable and to possess most general unifiers when unifiers exist. A unification algorithm and logic programming interpreter are described and proved correct. Several examples of using L-lambda as a meta-programming language are presented.

MS-CIS-90-55 (GRASP LAB 227)

Statistical Decision Theory For Sensor Fusion

Raymond McKendall

This article is a brief introduction to statistical decision theory. It provides background for understanding the research problems in decision theory motivated by the sensor-fusion problem.

MS-CIS-90-56 (GRASP LAB 228)

Non-Monotonic Decision Rules For Sensor Fusion

Raymond McKendall, Max Mintz

This article describes non-monotonic estimators of a location parameter q from a noisy measurement Z = q + V when the possibly values of q have the form 0, ±1,±2¼, ±n. If the noise V is Cauchy, then the estimator is a non-monotonic step function. The shape of this rule reflects the non-monotonic shape of the likelihood ratio of a Cauchy random variable. If the noise V is Gaussian with one of two possible scales, then the estimator is also a non-monotonic shape of the likelihood ratio of the marginal distribution of Z given q under a least-favorable prior distribution.

MS-CIS-90-57 (GRASP LAB 229)

Robust Multi-Sensor Fusion: A Decision-Theoretic Approach

Gerda Kamberova, Max Mintz

Many tasks in active perception require that we be able to combine different information from a variety of sensors that relate to one or more features of the environment. Prior to combining these data, we must test our observations for consistency. The purpose of this paper is to examine sensor fusion problems for linear location data models using statistical decision theory (SDT). The contribution of this paper is the application of SDT to obtain: (i) a robust test of the hypothesis that data from different sensors are consistent; and (ii) a robust procedure for combining the data that pass this preliminary consistency test. Here, robustness refers to the statistical effectiveness of the decision rules when the probability distributions of the observation noise and the a priori position information associated with the individual sensors are uncertain. The standard linear location data model refers to observations of the form: Z = q + V, where V represent additive sensor noise and q denotes the ``sensed'' parameter of interest to the observer. While the theory addressed in this paper applies to many uncertainty classes, the primary focus of this paper is on asymmetric and/or multimodal models, that allow one to account for very general deviations from nominal sampling distribution. This paper extends earlier results in SDT and multi-sensor fusion obtained by [Zeytinoglu and Mintz, 1984], [Zeytinoglu and Mintz, 1988], and [McKendall and Mintz, 1988].

MS-CIS-90-58 (LINC LAB 183)

Structure and Ostension In The Interpretation of Discourse Deixis

Bonnie Lynn Webber

This paper examines demonstrative pronouns used as deictics to refer to the interpretation of one or more clauses. Although this usage is frowned upon in style manuals such as (Strunk and White, 1959), who say `` This." The pronoun this, referring to the complete sense of a preceding sentence or clause, cannot always carry the load and so may produce an imprecise statement.''

It is nevertheless very common in written text. Handling this usage poses a problem for Natural Language Understanding systems. The solution I propose is based on distinguishing between what can be pointed to and what can be referred to by virtue of pointing. I argue that a restricted set of discourse segments yield what such demonstrative pronouns can point to in the discourse model and a restricted set of what Nunberg (1979) has called referring functions yield what they can refer to by virtue of that pointing.

MS-CIS-90-59 (LINC LAB 184)

An Extension To ML To Handle Bound Variables In Data Structures (Preliminary Report)

Dale Miller

Most conventional programming languages have direct methods for representing first-order terms (say, via concrete datatypes in ML). If it is necessary to represent structures containing bound variables, such as lambda-terms, formulas, types, or proofs, these must first be mapped into first-order terms, and then a significant number of auxiliary procedures must be implemented to manage bound variable names, check for free occurrences, do substitution, test for equality modulo alpha-conversion, etc. We shall show how the applicative core of the ML programming language can be enhanced so that lambda-terms can be represented more directly and so that the enhanced language, called ML-lambda, provides a more elegant method of manipulating bound variables within data structures. In fact, the names of bound variables will not be accessible to the ML-lambda programmer. This extension to ML involves the following: introduction of the new type constructor 'a => 'b for the type of lambda-terms formed by abstracting a parameter of type 'a out of a term of type 'b; a very restricted and simple form of higher-order pattern matching; a method for extending a given data structure with a new constructor; and, a method for extending function definitions to handle such new constructors. We present several examples of ML-lambda programs.

Appears in the Proceedings of the Logical Frameworks BRA Workshop, Nice, June 1990.

MS-CIS-90-60 (GRASP LAB 230)

TRACS: An Experimental Multiagent Robotic System

Xiaoping Yun, Eric Paljug, Ruzena Bajcsy

TRACS (Two Robotic Arm Coordination System), developed at the GRASP Laboratory at University of Pennsylvania, is an experimental system for studying dynamically coordinated control of multiple robotic manipulators. The systems is used to investigate such issues as the design of controller architectures, development of real-time control and coordination programming environments, integration of sensory devices, and implementation of dynamic coordination algorithms. The system consists two PUMA 250 robot arms and custom-made end effectors for manipulation and grasping. The controller is based an IBM PC/AT for its simplicity in I/O interface, ease of real-time programming, and availability of low-cost supporting devices. The Intel 286 in the PC is aided by a high speed AMD 29000 based floating point processor board. They are pipelined in such a way that the AMD 29000 processor performs real-time computations and the Intel 286 carries out I/O operations. The system is capable of implementing dynamic coordinated control of the two manipulators at 200 Hz.

TRACS utilizes a C library called MO to provide the real-time programming environment. An effort has been made to separate hardware-dependent code from hardware-independent code. As such, MO is used in the laboratory to control different robots on different operating systems (MS-DOS and Unix) with minimal changes in hardware-dependent code such as reading encoders and setting joint torques.

TRACS utilizes all off-the-shelf hardware components. Further, the adoption of MS-DOS instead of Unix or Unix-based real-time operating systems makes the real-time programming simple and minimizes the interrupt latencies. The feasibility of the system is demonstrated by a series of experiments of grasping and manipulating common objects by two manipulators.

MS-CIS-90-61 (GRASP LAB 231)

Singularity Avoidance and The Kinematics Of An Eight-Revolute-Joint Manipulator (Dissertation)

Gregory Lynn Long

Many general purpose robot manipulators consist of six serially connected actuators whose functional intent is to provide six Cartesian degrees-of-freedom to an end effector. This kinematic mapping of actuator freedoms to Cartesian freedoms is valid only when the six actuator-screws are linearly independent. When the six actuator-screws become linearly dependent, the manipulator has lost full freedom and the end-effector is unable to follow arbitrary Cartesian trajectories with finite actuator speeds.

We begin our study with a geometrically ``optimum'' six-revolute-joint robot manipulator, which is decoupled into a regional structure and an orientation structure. Since the 6R manipulator is kinematically decoupled, the regional and orientation structures comprise two separate screw systems, both of third order. When the order of either of these systems falls below three, the 6R manipulator will be at a configuration singularity.

With the three actuator-screws of the orientation structure placed in a configuration singularity, we find the screw which is instantaneously reciprocal to this system. With this reciprocal screw we locate a fourth ``redundant'' actuator-screw ``best'' suited for returning freedom to the orientation structure. With the regional structure placed in its configuration singularity, we do likewise by adding to it the actuator-screw ``best'' suited for returning the lost freedom. Hence, the orientation and regional structures form two separate 4R structures, taken together forming an 8R manipulator.

Conceptually, the algorithms to control both the 4R orientation and 4R regional structures begin in primary mode with three actuator-screws apiece. In primary mode we use the traditional position kinematics approach. Whenever either of the orientation or regional structure has difficulty following its Cartesian trajectory, control for the structure goes into secondary mode, where the redundant actuator is then called upon.

The algorithms maintain a sixth-order screw system for an 8R manipulator with bounded actuator rates and well-behaved actuator values. The numerical computations for an 8R manipulator are comparable to those for the ``optimum'' 6R manipulator and can be implemented in real-time.

MS-CIS-90-62 (LOGIC & COMPUTATION)

Heterogeneous Collections In A Static Type System (Extended Abstract)

Peter Buneman (University of Pennsylvania), Atsushi Ohori (University of Glasgow)

We consider the problem of representing heterogeneous collections of objects in a type polymorphic programming language in such a way that common properties of members of a collection, such as having commonly named filed with a common type can be expressed in the type system. The use of such collections is widespread in object-oriented and database programming and has so far been achieved in statically typed systems only through the use of a single dynamic type, which effectively hides all the structure of a value. In this paper we expl oit a system of types and kinds (sets of types) to represent dynamic values with some known properties. The type system is shown to be sound and to have a complete type inference algorithm.

MS-CIS-90-63 (GRASP LAB 232)

Estimation Of Three-Dimensional Motion And Structure From Images By Using A Temporally-Oriented Approach (Dissertation)

Siu-Leong Iu

This dissertation explores the problem of estimating the 3-D motion and the structure of an object from video images using a new approach which looks for the temporal information prior to the spatial information. Since motion is observed over an extended period of time, we can reduce the number of features required by the conventional approach and improve significantly the estimation performance.

In recovering the motion of a single particle or a rigid body, we prove that, under some conditions, the solution is unique. Regression relations between the unknown motion parameters and the projective trajectories are obtained for general particle motion and constant rigid motion. The method of maximum likelihood is used to estimate the motion. Using the non-linear state estimation formulation, the extended Kalman filter is applied to obtain the estimate recursively.

We propose an approach to estimate a general non-constant rigid motion in which the orders of translation and rotation can be arbitrary. We also show that for some special angular velocities, non-constant rigid motion has closed-form evolution, and discuss how to reduce the number of unknowns if all the points lie on a planar surface.

We have addressed the problem of model mismatches for parameter jumping, undermodeling and overmodeling. We find that the model error makes the conventional approach break down. In order to solve this problem, we develop a new filter called Finite Lifetime Alternately Triggered Multiple Model Filter (FLAT MMF) is a filter composed of a number of identical conventional state estimation filters, each triggered alternately. After the last filter is triggered, the oldest one is triggered again and, so on. Experiments on the simulated trajectory and the real images show the FLAT MMF is quite effective in suppressing the model errors. For the particle motion without a depth change, we obtain the analytic, closed-form estimate for cases of model match and mismatch. We show that the filter that provides the best estimates dominates the final estimate. Finally, we show the potential of FLAT MMF for real-time object tracking.

MS-CIS-90-64 (LOGIC & COMPUTATION 23)

Polymorphism and Type Inference In Database Programming

Peter Buneman (University of Pennsylvania), Atsushi Ohori (University of Glasgow)

The polymorphic type system of ML can be extended in two ways that make it appropriate as the basis of a database programming language. The first is an extension to the language of types that captures the polymorphic nature of field selection; the second is a technique that generalizes relational operators to arbitrary data structures. The combination provides a statically typed language in which relational databases may be cleanly represented as typed structures. As in ML types are inferred, which relieves the programmer of making the rather complicated type assertions that may be required to express the most general type of a program that involves field selection and generalized relational operators.

It is also possible to use these ideas to implement various aspects of object-oriented databases. By implementing database objects as reference types and generating the appropriate views -- sets of structures with ``identity'' -- we can achieve a degree of static type checking for object-oriented databases. Moreover it is possible to exploit the type system to check the consistency of object-oriented classes (abstract data types with inheritance). A prototype language based on these ideas has been implemented. While it lacks some important practical features, it demonstrates that a wide variety of database structures can be cleanly represented in a polymorphic programming language.

MS-CIS-90-65 (LOGIC & COMPUTATION 24)

Logic and Learning

Daniel N. Osherson (M.I.T.), Michael Stob (Calvin College), Scott Weinstein (University of Pennsylvania)

The theory of first-order logic -- or ``Model Theory'' -- appears in few studies of learning and scientific discovery. We speculate about the reasons for this omission, and then argue for the utility of Model Theory in the analysis and design of automated systems of scientific discovery. One scientific task is treated from this perspective in detail, namely, concept discovery. Two formal paradigms bearing on this problem are presented and investigated using the tools of logical theory. One paradigm bears on PAC learning, the other on identification in the limit.

MS-CIS-90-66 (GRASP LAB 233)

Identification of Address Blocks Through Multiple Illuminations, Multiple Images and Multicolor Images

Ruzena Bajcsy, Helen Anderson, Sang Wook Lee

We propose a methodology to identify the address labels on flat mail pieces, for the cases where the surface characteristics of the address label are different from the remaining surface. Two methods are used: movement of highlights with differing illumination, and identification of highlights using color information. Reasoning about changes in hue, saturation and intensity, using a new representation of color, allows us to discriminate between matte and glossy surfaces. On grayscale images, we separate diffuse reflectance areas from glossy reflectance areas, using highlights which change with illumination angle. If that does not disambiguate the label, we use color, reasoning that highlights decrease the saturation value and increase the saturation value and increase the intensity.

MS-CIS-90-67 (GRAPHICS LAB 34)

Human Factors Simulation Research At The University of Pennsylvania

Norman I. Badler

Jack is a Silicon Graphics Iris 4D workstations-based system for the definition, manipulation, animations, and human factors performance analysis of simulated human figures. Built on a powerful representation for articulated figures, Jack offers the interactive user a simple, intuitive, and yet extremely capable interface into any 3-D articulated world. Jack incorporates sophisticated systems for anthropometric human figure generation, multiple limb positioning under constraints, view assessment, and strength model-based performance simulation of human figures. Geometric workplace models may be easily imported into Jack. Various body geometries may be used, from simple polyhedral volumes to contour-scanned real figures. High quality graphics of environments and clothed figures are easily obtained. Descriptions of some work in progress are also included.

MS-CIS-90-68 (GRASP LAB 234)

Sensor-Fusion with Statistical Decision Theory: A Prospectus of Research in the GRASP Lab

Raymond McKendall, Max Mintz

The purpose of this report is to describe research in sensor fusion with statistical decision theory in the GRASP Lab, Department of Computer and Information Science, University of Pennsylvania. This report is thus a tutorial overview of the general research problem, the mathematical framework for the analysis, the results of specific research problems, and directions of future research. The intended audience for this report includes readers seeking a self-contained summary of the research as well as students considering study in this area. The prerequisite for understanding this report is familiarity with basic mathematical statistics.

MS-CIS-90-69 (GRASP LAB 235)

A Resource-Based Prioritized Bisimulation for Real-Time Systems

Richard Gerber, Insup Lee

The 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 executed synchronously, while processes assigned to the same resource are interleaved according to their priorities. In this paper we introduce a proof system for CCSR, a process algebra based on the CSR model. CCSR allows the algebraic specification of timeouts, interrupts, periodic behaviors and exception. We provide a rigorous treatment of preemption, which is based not only on priority, but also on resource utilization and inter-resource synchronization. The theory of preemption leads to a term equivalence based on strong bisimulation, which yields a set of rules forming the proof system. As an illustration we present a resource-sharing, producer-consumer problem, and we use our laws to prove its correctness.

MS-CIS-90-70 (GRASP LAB)

TRACS: The Hardware and Software Architecture Of A New Two Robotic Arm Coordination System

Eric Paljug, Xiaoping Yun, Filip Fuma

This paper presents the hardware and software architecture implemented in the Two Robotic Arm Coordination System (TRACS) at the GRASP Lab of the University of Pennsylvania. It is developed to perform experiments on dynamically coordinated control of multiple robotic manipulators. Its architecture avoids complexities and allows the user to easily implement desired control algorithms. This system controls two PUMA 250 robot manipulators, each with 6 DOF. The IBM PC-AT is chosen as the host computer because of its ease in real-time programming, simplicity of I/O interfacing, and low cost of hardware and maintenance. The Intel 286 processor of the PC-AT is aided by a AMD 29000 high speed floating point processor based board. Together, the 286 provides the real-time environment and performs sensor and manipulator I/O while the AMD 29000 calculates the real-time control algorithms. TRACS incorporates MO, a C library of routines being developed in the Grasp Lab to control robots. MO separates hardware dependent software from hardware independent code and provides the user with a virtual robot interface. End-effectors are built to perform two arm grasping and manipulating of large objects. The end-effectors are outfitted with contact/force sensors. The system is capable of controlling of the two cooperative manipulators at 200 Hz.

MS-CIS-90-71 (GRASP LAB 237)

Coordination of Two-Arm Pushing

Xiaoping Yun

Coordination of two manipulators performing the task of transporting objects is studied in this paper. Each manipulator is equipped with end effector --- a flat surface palm. Grasping is achieved by the two palms pushing an object from two ends. The task requires simultaneous control of the object motion and the interaction force. The control of the interaction force is needed to ensure that the object is not dropped and to avoid excessive pressing. The motion and force control problem is further complicated by the presence of unilateral constraints since the manipulators can only push the object. This paper describes a control method which utilizes a state feedback to decouple position control and force control loops. A force control planning algorithm is also proposed which ensures the satisfaction of unilateral constraints. The effectiveness of the control method is verified by simulations.

MS-CIS-90-72 (GRASP LAB 238)

Mechanical Design Optimization Of Robot Manipulator Performance (Dissertation)

Nathan Thatcher Ulrich

This dissertation presents mechanical design techniques of improving the performance of robot manipulators. Although measures of robot performance for conventional applications---such as payload, dynamic response, accuracy, economy and reliability---are considered, this research is especially concerned with the behavior of robots in unstructured environments. In such a setting, the total system mass, the energy efficiency, and the ability of a manipulator arm to interact positively with its surroundings are also important. Included here are three methods of overcoming performance limitations.

Gravity-induced joint torques can seriously degrade manipulator performance. A method of passive and energy-conservative mechanical gravity compensation is developed which can be applied to a wide range of manipulator geometries, two examples of which are presented. Experimental verification of compensation performance for one- and two-link implementations is reported, which shows the method to be accurate to well within one percent, and to be stable under a wide range of dynamic and static loading conditions. This approach to gravity compensation is also economical and easily applied.

Another method is a means of modifying the transmission characteristics of a robot manipulator to improve the predictability of actuator response. This is accomplished by optimizing the transmitted inertia matrix relating actuator inputs to joint outputs. Included is an application of this technique to a two-joint planar manipulator. Also discussed are methods of regenerating the energy expended in accelerating members to reduce energy consumption.

Finally, a new robot arm design is presented as an example of the use of mechanical design ideas to improve the performance of robot manipulators. The design is a demonstration of the benefits of applying these research results: in comparison to an advanced conventional arm, the new design uses less than a tenth as much energy, has better dynamic and static performance, and has lower mass and inertia.

MS-CIS-90-73 (LOGIC & COMPUTATION 24)

Type Inference For Records In A Natural Extension Of ML

Didier Remy

We describe an extension of ML with records where inheritance is given by ML generic polymorphism. All operation on records introduced by Wand in [Wan87] are supported, in particular the unrestricted extension of a field, and other operations such as renaming of fields are added. the solution relies on both an extension of ML, where the language of types is sorted and considered modulo equations [Rem 90b], and on a record extension of types [Rem90c]. the solution is simple and modular and the type inference algorithm is efficient in practice.

MS-CIS-90-74 (DISTRIBUTED SYSTEMS LAB 3)

MIRAGE: A Model For Latency In Communication (A Proposal for Dissertation Research)

Joseph D. Touch

Mirage is a research effort which attempts to provide a basis for analysis and design of gigabit communications networks. As part of the overall Mirage project, we develop here the Mirage model, a formal model for the design and analysis of high-speed wide-area network protocols. The primary goal of this research is to understand the effects of moving to the gigabit domain in wide-area networks, verifying or disproving the predicted failure of existing protocols, and anticipating potential solutions. A derivative and more fundamental goal is to provide a framework for understanding the effects of latency on communication. In the high-speed, wide-area domain, network inefficiencies are caused by the combined effect of increased channel capacity, without a corresponding decrease in communication latency (due to finite propagation delays). Mirage proposes a view where latency can be compensated by accepting information imprecision (a controlled form of error), thus inverting the problem.

This research is based on suggestions derived from analogies in physics, using a model of state space volume transformations, in an attempt to incorporate the imprecision evident in quantum models into communication protocol analysis. It proposes to extend Shannon's communication theory by accounting for the effects of latency, just as Shannon's accounts for communication errors.

The dissertation we propose will consist of a three phase development of the formal model, providing for its synthesis and examples of its use. The first phase uses the description of a sample, existing protocol, clock synchronization via the Network Time Protocol, to assist in the development of the formal model. In the second phase, we will consider the application of the Mirage model principles towards the analysis of a new protocol, specifically a flow protocol, and the accumulation resetting mechanisms contained therein.

Finally, we will show how Mirage can be useful in the design of new protocols. In particular, we can apply this model toward the design of new distributed cache management protocols. Mirage suggests interesting tradeoffs and optimizations in the protocols used to maintain caches in a distributed shared memory.

MS-CIS-90-75 (LOGIC & COMPUTATION 25)

The Mixed Powerdomain

Carl A. Gunter

This paper introduces an operator M called the mixed powerdomain which generalizes the convex (Plotkin) powerdomain. The construction is based on the idea of representing partial information about a set of data items using a PAIR of sets, one representing partial information in the manner of the upper (Smyth) powerdomain and the other in the manner of the lower (Hoare) powerdomain where the components of such pairs are required to satisfy a consistency condition. This provides a richer family of meaningful partial descriptions than are available in the convex powerdomain and also makes it possible to include the empty set in a satisfactory way. The new construct is given a rigorous mathematical treatment like that which has been applied to the known powerdomains. It is proved that M is a continuous functor on bifinite domains which is left adjoint to the forgetful functor from a category of continuous structures called MIX ALGEBRAS. For a domain D with a coherent Scott topology, elements of M(D) can be represented as pairs (U,V) where U is a compact upper subset of D and V is a closed subset of D and the downward closure of U intersect V is equal to V. A Stone dual characterization of M is also provided.

MS-CIS-90-76 (LINC LAB 185)

Progressive Horizon Planning

Ron Rymon (University of Pennsylvania), Bonnie L. Webber (University of Pennsylvania), John R. Clarke (Medical College of Pennsylvania)

In an earlier paper [Rymon, 1989] we showed how domain localities and regularities can be used to reduce the complexity of finding a trauma management plan that satisfies a set of diagnostic and therapeutic goals. Here, we present another planning idea -- Progressive Horizon -- useful for optimizing such plans in domains where planning can be regarded as an incremental process, continuously interleaved with situation-goals analysis and plan execution. In such domains, planned action cannot be delayed until all essential information is available: A plan must include actions intended to gather information as well as ones intended to change the state of the world.

Interleaving planning with reasoning and execution, a progressive horizon planner constructs a plan that answers all currently known needs but has only its first few actions optimized (those within its planning horizon). As the executor carries out actions and reports back to the system, the current goals and the plan are updated based on actual performance and newly discovered goals and information. The new plan is then optimized within a newly set horizon.

In this paper, we describe those features of a domain that are salient for the use of a progressive horizon planning paradigm. Since we believe that the paradigm may be useful in other domains, we abstract from the exact techniques used by our program to discuss the merits of the general approach.

MS-CIS-90-77 (GRAPHICS LAB 35)

A Kinematic Model of The Human Spine and Torso

Gary Monheit, Norman I. Badler

In order to advance current human figure motion models, a more realistic model of the body must include a flexible torso and spine. The spinal column is a series of interdependent joints with three degrees of rotational freedom. A study of anatomical architecture supports the model's principal ideas, and indicates the parameters for spinal movement. By defining a database of spine attributes (obtained from medial data), and a small set of input parameters, inverse kinematic control of the spine may be achieved.

MS-CIS-90-78 (GRASP LAB 239)

Deciding No To Decide Using Resource-Bounded Sensing

Greg Hager

We view the problem of sensor-based decision-making in terms of two components: a sensor fusion component that isolates a set of models consistent with observed data, and an evaluation component that uses this information and task-related information to make model-based decisions. In previous work we have described a procedure for computing the solution set of parametric equations describing a sensor-object based decision-making methods.

In this paper, we investigate the implications of allowing one of the decision-making options to be ``no decision,'' whereupon a human might be called to aid or interact with the system In particular, this type of capability supports the construction of supervised or partially autonomous systems. We discuss how such situations might arise and give concrete examples of how a system might reach such a decision using our techniques.

MS-CIS-90-79 (GRASP LAB 240)

Real-Time Vision-Based Robot Localization

Sami Atiya (Universitat Karlsruhe), Greg Hager (University of Pennsylvania)

In this article we describe an algorithm for robot localization using visual landmarks. This algorithm determines both the correspondence between observed landmarks (in this case vertical edges in the environment) and a pre-loaded map, and the location of the robot from those correspondences. The primary advantages of this algorithm are its use of a single geometric tolerance to describe observation error, its ability to recognize ambiguous sets of correspondences, its ability to compute bounds on the error in localization, and fast performance. The current version of the algorithm has been implemented and tested on a mobile robot system. In several hundred trials the algorithm has never failed, and computes location accurate to within a centimeter in less than half a second.

MS-CIS-90-80 (GRASP LAB 241)

Interval-Based Techniques for Sensor Data Fusion

Greg Hager

We view the problem of sensor-based decision-making in terms of two components: a sensor fusion component that isolates a set of models consistent with observed data, and an evaluation component that uses this information and task-related information to make model-based decision. This paper describes a procedure for computing the solution set of parametric equations describing a sensor-object imaging relationship. Given a parametric form with s parameters, we show that this procedure can be implemented using a parallel array of 6_s² processors. We then describe an application of these techniques with demonstrates the use of task-related information and set-based decision-making methods.

MS-CIS-90-81 (LINC LAB 18)

Parallel Kalman Filtering On The Connection Machine

Michael A. Palis (University of Pennsylvania), Donald K. Krecker(General Electric Companies)

A parallel algorithm for square root Kalman filtering is developed and implemented on the Connection Machine (CM). The algorithm makes efficient use of parallel prefix or scan operations which are primitive instructions in the CM. Performance measurements show that the CM filter runs in time linear in the state vector size. This represents a great improvement over serial implementations which run in cubic time. A specific multiple target tracking application is also considered, in which several targets (e.g., satellites, aircrafts and missiles) are to be traced simultaneously, each requiring one or more filters. A parallel algorithm is developed which, for fixed size filters, runs in constant time, independent of the number of filters simultaneously processed.

MS-CIS-90-82 (LINC LAB 187)

Description Succinctness of Some Grammatical Formalisms for Natural Language

Michael A. Palis (University of Pennsylvania), Sunil Shende (University of Nebraska)

We investigate the problem of describing languages compactly in different grammatical formalisms for natural languages. In particular, the problem is studied from the point of view of some newly developed natural language formalisms like linear control grammars (LCGs) and tree adjoining grammars (TAGs); these formalisms not only generate non-context-free languages that capture a wide variety of syntactic phenomena found in natural language, but also have computationally efficient polynomial time recognition algorithms. We prove that the formalisms enjoy the property of unbounded succintness over the family of context-grammars, i.e. they are, in general, able of provide more compact representations of natural languages as compared to standard context-free grammars.

MS-CIS-90-83 (GRASP LAB 241)

Two-Handed Grasping With Two-Fingered Hands

Jose-Antonio N. Caraza, Xiaoping Yun

This paper analyzes two-handed grasping of a rigid object in the two-dimensional (2-D) space. The two hands under consideration have two fingers, and each finger is equipped with a tactile sensor. The hands are assumed to be respectively installed on two robotic manipulators capable of motion and force control.

MS-CIS-90-84 (LOGIC & COMPUTATION 26)

Decomposition Of Domains

Achim Jung, Leonid Libkin, Herman Puhlmann

The problem of decomposing domains into sensible factors is addressed an solved for the case of dI-domains. A decomposition theorem is proved which allows to represent an arbitrary dI-domain as a set of records with variants. The special case of direct product decompositions of Scott-domains is studied separately.

MS-CIS-90-85 (LOGIC & COMPUTATION 27)

Direct Product Decompositions Of Lattices, Closures and Relation Schemes

Leonid Libkin

In this paper we study direct product decompositions of closure operations and lattices of closed sets in terms of closure operations, and find those decompositions of lattices which correspond to the decompositions of closures. If a closure on a finite set is represented by its implication base (i.e. a binary relation on a powerset), we construct a polynomial algorithms to find its direct product decompositions. The main characterization theorem is also applied to define direct product decompositions of relational database schemes and to find out what properties of relational databases and schemes are preserved under decompositions.

MS-CIS-90-86 (LOGIC & COMPUTATION 28)

The Common Order-Theoretic Structure of Version Spaces And ATM's

Carl A. Gunter (University of Pennsylvania), Teow-Hin Ngair (University of Pennsylvania), Prakash Panangaden (McGill University), Devika Subramanian (Cornell University)

This paper exposes the common order-theoretic properties of the structures manipulated by the version space algorithm by recasting them in the framework of convex spaces. Our analysis of version spaces in this framework reveals necessary and sufficient conditions for ensuring the preservation of an essential finite representability property in version space merging. This analysis is used to formulate several sufficient conditions for when a language will allow version spaces to be represented by finite sets of concepts (even when the universe of concepts may be infinite). We provide a new convex space based formulation of computation performs by an ATMS which extends the expressiveness of disjunctions in the systems. This approach obviates the need for hyper-resolution in dealing with disjunction and results in simpler label-update algorithms.

MS-CIS-90-87 (DISTRIBUTED SYSTEMS LAB 4)

Analysis Of Error Control And Congestion Control Protocols

Amarnath Mukherjee

This thesis presents an analysis of a class of error control and congestion control protocols used in computer networks. We address two kinds of packet errors: (a) independent errors and (b) congestion-dependent errors. Our performance measure is the expected time and the standard deviation of the time to transmit a large message, consisting of N packets.

The analysis of error control protocols. Assuming independent packet errors gives an insight on how the error control protocols should really work if buffer overflows are minimal. Some pertinent results on the performance of go-back-n, selective repeat, blast with full retransmission on error (BFRE) and a variant of BFRE, the Optimal BFRE that we propose, are obtained.

We then analyze error control protocols in the presence of congestion-dependent errors. We study the selective repeat and go-back-n protocols and find that irrespective of retransmission strategy, the expected time as well as the standard deviation of the time to transmit N packets increases sharply the face of heavy congestion. However, if the congestion level is low, the two retransmission strategies perform similarly. We conclude that congestion control is a far more important issue when errors are caused by congestion.

We next study the performance of a queue with dynamically changing input rates that are based on implicit or explicit feedback. This is motivated by recent proposals for adaptive congestion control algorithms where the sender's window size is adjusted based on perceived congestion level of a bottleneck node. We develop a Fokker-Planck approximation 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, a linear increase/exponential decrease rate control algorithm is provably stable and fair. Delayed feedback, however, introduces cyclic behavior. This last result not only concurs with some recent simulation studies, it also expounds quantitatively on the real causes behind them.

MS-CIS-90-88 (GRAPHICS LAB 36)

Issues In Facial Animation

Catherine Pelachaud, Norman I. Badler, Mark Steedman

Our goal is to build a system of 3-D animation of facial expressions of emotion correlated with the intonation of the voice. Up till now, the existing systems did not take into account the link between these two features. Many linguists and psychologists have noted the importance of spoken intonation for conveying different emotions associated with speakers' messages. Moreover, some psychologists have found some universal facial expressions linked to emotions and attitudes. We will look at the rules that control these relations (intonation/emotions and facial expressions/emotions) as well as the coordination of these various modes of expressions. Given an utterance, we consider how the message (what is new/old information in the given context) transmitted through the choice of accents and their placement, are conveyed through the face. The facial model integrates the action of each muscle or group of muscles as well as the propagation of the muscles' movement. It is also adapted to the FACS notation (Facial Action Coding System) created by P. Ekman and W. Friesen to describe facial expressions. Our first step will be to enumerate and to differentiate facial movements linked to emotions from the ones linked to conversation. Then, we will examine what the rules are that drive them and how their different actions interact.

Key words: facial animation, emotion, intonation, coarticulation, conversational signals

MS-CIS-90-89 (GRASP LAB 242)

On The Convergence Time Of Simulated Annealing

Sanguthevar Rajasekaran

Simulated Annealing is a family of randomized algorithms used to solve many combinatorial optimization problems. In practice they have been applied to solve some presumably hard (e.g., NP-complete) problems. The level of performance obtained has been promised [5, 2, 6, 14]. The success of its heuristic technique has motivated analysis of this algorithm from a theoretical point of view. In particularly, people have looked at the convergence of this algorithm. They have show (see e.g., [10]) that this algorithm converges in the limit to a globally optimal solution with probability 1. However few of these convergence results specify a time limit within which the algorithm is guaranteed to converge(with some high probability, say). We present, for the first time, a simple analysis of SA that will provide a time bound for convergence with overwhelming probability. The analysis will hold no matter what annealing schedule is used. Convergence of Simulated Annealing in the limit will follow as a corollary to our time convergence proof.

In this paper we also look at optimization problems for which the cost function has some special properties. We prove that for these problems the convergence is much faster. In particular, we give a simpler and more general proof of convergence for Nested Annealing, a heuristic algorithm developed in [12]. Nested Annealing is based on defining a graph corresponding to the given optimization problem. If this graph is 'small separable', they [12] show that Nested Annealing will converge 'faster'.

For arbitrary optimization problem, we may not have any knowledge about the 'separability' of its graph. In this paper we give tight bounds for the 'separability' of a random graph. We then use these bounds to analyze the expected behavior of Nested Annealing on an arbitrary optimization problem. The 'separability' bounds we derive in this paper are of independent interest and have the potential of finding other applications.

MS-CIS-90-90 (GRASP LAB 243)

HEAP: A Sensory Driven Distributed Manipulation System

Sanjay Agrawal, Marcos Salganicoff, Michael Chan, Ruzena Bajcsy

We address the problems of locating, grasping, and removing one or more unknown objects from a given area. In order to accomplish the task we use HEAP, a system of coordinating the motions of the hand and arm. HEAP also includes a laser range finer, mounted at the end of a PUMA 560, allowing the system to obtain multiple views of the workspace.

We obtain volumetric information of the objects we locate by fitting superquadric surfaces on the raw range data. The volumetric information is used to ascertain the bust had configuration to enclose and constrain the object stably. The Penn Hand used to grasp the object, is fitted with 14 tactile sensors to determine the contact area and the normal components of the grasping forces. In addition the hand is used as a sensor to avoid any undesired collisions. The objective in grasping the objects is not to impart arbitrary forces on the object, but instead to be able to grasp a variety of objects using a simple grasping scheme assisted with a volumetric description and force and touch sensing.

MS-CIS-90-91 (LINC LAB 188)

Model-Based Penetration Path Calculations for The Diagnosis Of Multiple Trauma

Leonard J. Karpf

In order to enhance TraumAID, a system that provides decision support in the initial definitive management of multiple trauma, TSARR (TraumAID System for Anatomical Representation and Reasoning) has been designed to address the need for greater depth in TraumAID's understanding of anatomical reasoning. TSARR provides a framework for representing a three-dimensional model of relevant parts of the body; utilizing this model, TSARR is able to calculate three-dimensional representations of paths of injury, generated from wound locations input to the system. Using these paths, the system hypothesizes which anatomical structures in the patient might have been injured due to their location along a possible path of an injury. In the future, TraumAID will be able to utilize this information to focus its attention more accurately on specific areas of the body that have sustained injury.

This work has been done in conjunction with the TraumAID project being conducted by Professor Bonnie Webber of the University of Pennsylvania and by Dr. John R. Clarke, MD, of the Medical College of Pennsylvania.

MS-CIS-90-92 (GRASP LAB 244)

Robotic Exploration Of Surfaces With A Compliant Wrist Sensor

Pramath R. Sinha, Yangsheng Xu, Ruzena Bajcsy, Richard P. Paul

This paper presents some results of an ongoing research project to investigate the components and modules that are necessary to equip a robot with exploratory capabilities. Of particular interest is the recovery of certain material properties from a surface, given minimal p priori information, with the intent to use this information to enable a robot to stand and walk stably on a surface this is unknown and unconstrained. To this end, exploratory procedures (ep's) have been designed and implemented to recover penetrabil ity, material hardness and surface roughness by exploring the surface using a compliant wrist sensor. A six degree-of-freedom compliant wrist sensor, which combines passive compliance and active sensing, has been developed to provide the necessary flexibility for force and contact control, as well as to provide accurate position control. This paper describes the compliant wrist and sensing mechanism design along with a hybrid control algorithm that utilizes the sensed information from the wrist to adjust the apparent stiffness of the end-effector as desired.

MS-CIS-90-93 (GRASP LAB 245)

Active Exploration Of Surfaces For Legged Locomotion Of Robots

Pramath R. Sinha, Ruzena Bajcsy

This paper presents some results of an ongoing research project in the GRASP Lab in the area of active exploration and perception for the legged locomotion of robots. We propose an active perceptual scheme that is based on the ability of the robot to extract material properties from a surface during locomotion. This ability is provided to the robotic system through a compliant sensing device which is used to monitor the response of the surface when exploratory procedures are executed during the stepping and walking motions of the leg. Such a system will actively perceive changes in the surfaces properties and prevent the robot from slipping, falling, or sinking during locomotion. The paper describes the proposed perceptual scheme, the system set-up, and the implementation of the exploratory procedures.

MS-CIS-90-94 (LINC LAB 189)

Structure Unification Grammar: A Unifying Framework For Investigating Natur al Language (Masters' Thesis)

James Henderson

This thesis presents Structure Unification Grammar and demonstrates its suitability as a framework for investigating natural language from a variety of perspectives. Structure Unification Grammar is a linguistic formalism which represents grammatical information as partial descriptions of phrase structure trees, and combines these descriptions by equating their phrase structure tree nodes. This process can be depicted by taking a set of transparencies which each contain a picture of a tree fragment, and overlaying them so they form a picture of a complete phrase structure tree. The nodes which overlap in the resulting picture of a complete phrase structure tree. the nodes which overlap in the resulting picture are those which are equated. The flexibility with which information can be specified in the descriptions of trees and the generality of the combination operation allows a grammar writer or parser to specify exactly what is known where it is know. The specification of grammatical constraints is not restricted to any particular structural or informational domains. this property provides for a very perspicuous representation of grammatical information, and for the representations necessary for incremental parsing.

The perspicuity of SUG's representation is complemented by its high formal power. The formal power of SUG allows other linguistic formalisms to be expressed in it. By themselves these translations are not terribly interesting, but the perspicuity of SUG's representation often allows the central insights of the other investigations to be expressed perspicuously in SUG. Through this process it is possible to unify the insights form a diverse collection of investigations within a single framework, thus furthering our understanding of natural language as a whole. This thesis gives several examples of how insights from investigations into natural language can be captured in SUG. Since these investigations come from a variety of perspectives on natural language, these examples demonstrate that SUG can be used as a unifying framework for investigating natural language.

MS-CIS-90-95 (LINC LAB 190)

CLiFF Notes #1: Research in Natural Language Processing at the University of Pennsylvania Biannual Report: Fall 1990

Contributors: Students & Faculty, Editor: Elizabeth Levison

CLiFF is the Computational Linguists' Feedback Forum. This technical report is a collection of short abstracts by students and faculty in which they describe their work currently in progress. These presentations of the work being done in Natural Language Processing at the University of Pennsylvania should provide insight into the diversity of work at Penn, and the strong ties between the departments of Computer Science, Psychology and Linguistics.

MS-CIS-90-96 (GRASP LAB 246)

Object Retrieval Strategy In Unstructured Environments Using Active Vision and A Medium Complexity Gripper

Marcos Salganicoff, Michael Chan, Sanjay Agrawal, Ruzena Bajcsy

Depth information from a mobile laser stripe scanner mounted on a PUMA560 robot is used for simple thresholding by z-height and region growing. Superquadric surfaces are then fit to the regions segmented. This data reduction to three axis parameters, three Euler angles and two squareness parameters allows grasp planning using the PENN hand medium complexity end effector. Additionally, in order to take into account the spatial relationships between objects, they are grouped according to a nearest neighbor measure by distance between centroids in the x-y plane and also by height. The convex hull of the groups is then computed using Graham's method. The convex hull object list permits objects with the best clearance for grasp to be identified, thus reducing the possibility of unwanted collisions during the enclosure phase. The geometric properties of the object are then used to determine whether an approach parallel or normal to the plane of support is necessary. This list of candidate grasps for the object is checked for intersections with the bounding boxes of neighboring objects and the finger trajectories. The most stable collision free grasp preshape which passes the intersection testing is chosen. If no grasp is collision free the next best object in terms of topology is chosen. Height clustering information is used to determine a baseline height for transporting objects in a collision free fashion. By combining these simple strategies of favoring objects at the exterior of groups and tall objects for initial grasping and removal, the chances for successful task completion are increased with minimal computational burden.