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 rep