MS-CIS-91-01 (GRASP LAB 247)

Observing A Moving Agent

Ruzena Bajcsy, Tarek Sobh

We address the problem of observing a moving agent. In particular, we propose a system for observing a manipulation process, where a robot hand manipulates an object. A discrete event dynamic system (DEDS) from work is developed for the hand-object interaction over time and a stabilizing observer is constructed. Low-level modules are developed for recognizing the "events'' that causes state transitions within the dynamic manipulation system. The work examines closely the possibilities for errors, mistakes and uncertainties in the manipulation system, observer construction process and event identification mechanisms. The system utilizes different tracking techniques in order to observe the task in an active, adaptive and goal-directed manner.

MS-CIS-91-02 (GRASP LAB 248)

Model Based Teleoperation To Eliminate Feedback Delay NSF Grant BCS89-01352 First Report

Richard P. Paul, Janez Funda, Simeon Thierry, Thomas Lindsay, and Masahik o Hashimoto

We are conducting research in the area of teleoperation with feedback delay. Delay occurs with earth-based teleoperation in space and with surface-based teleoperation with untethered submersibles when acoustic communication links are involved. the delay in obtaining position and force feedback from remote slave arms makes teleoperation extremely difficult. We are proposing a novel combination of graphics and manipulator programming to solve the problem by interfacing a teleoperator master arm to a graphics based simulator of the remote environment coupled with a robot manipulator at the remote, delayed site. the operator's actions will be monitored to provide both kinesthetic and visual feedback and to generate symbolic motion commands to the remote slave. the slave robot will then execute these symbolic commands delayed in time. While much of a task will proceed error free, when an error does occur the slave system will transmit data back to the master and the master environment will be ``reset'' to the error state.

MS-CIS-91-03 (GRAPHICS LAB 37)

Interactive Behaviors For Bipedal Articulated Figures

Cary B. Phillips, Norman I. Badler

We describe techniques for interactively controlling bipedal articulated figures through kinematic constraints. These constraints model certain behavioral tendencies which capture some of the characteristics of human-like movement, and give us control over such elements as the figures' balance and stability. They operate in near real-time, so provide behavioral control for interactive manipulation. These constraints form the basis of an interactive motion-generation system that allows the active movement elements to be layered on top of the passive behavioral constraints.

MS-CIS-91-04 (GRASP LAB 249)

Hands: Human To Robotic

Sanjay Agrawal

Hands have for centuries been recognized as a fundamental tool for humans to gain an understanding of their environment and at the same time be able to manipulate it. In this presentation we will look at various studies made on the functionality and use of the human hand and examine the different approaches to analyzing and classifying human grasps and building a taxonomy of these grasps. We study the anatomy of the human hand, and examine experiments performed to understand the how gripping forces are applied when lifting objects, and the methods extraction of haptic information, by humans.

We discuss issues involved in the building of electro-mechanical manipulators and some of the mathematics used in analyzing the suitability of a design. We look at one of the earliest designs of a computer controlled articulated gripper, as well as two of the most prevalent designs in today's research world, the Stanford/JPL hand and the Utah/MIT had. Finally, we show why a more fundamental understanding of how human grasping works will help us design more useful manipulators.

MS-CIS-91-05 (GRASP LAB 250)

An Hand-Eye Arm Coordinated System

Sanjay Agrawal, Ruzena Bajcsy, Vijay Kumar

In this paper we present the description and experiments with a tightly coupled Hand-Eye-Arm manipulatory system. We explain the philosophy and the motivation for building a tightly coupled system that actually consists of very autonomous modules that communicate with each other via a central coordinator. We describe each of the modules in the system and their interactions with each other. We highlight the need for sensory driven manipulation, and explain how the above system, where the hand is equipped with multiple tactile sensors, is capable of both manipulating unknown objects, but also detecting and complying in the case of collisions. We explain the partition of the control of the system into various closed loops, representing coordination both at the level of gross manipulator motions as well as fine motions. We describe the various modes that the system can work in , as well as some of the experiments that are being currently performed using this system.

MS-CIS-91-06 (GRASP LAB 251)

Emulation Of A PRAM On Leveled Networks

David S. L. Wei

We present efficient emulations of the CRCW PRAM on a large class of processor interconnection networks called leveled networks. This class includes the star graph and the n-way shuffle, which have the interesting property that the network diameter is sub-logarithmic in the network size. We show that a CRCW PRAM can be emulated optimally on these networks (i.e., each emulation step takes time linear in the network diameter). this is the first result that demonstrates PRAM emulation in less than logarithmic time.

We also present an efficient emulation of the CRCW PRAM on an n x n mesh. Although an O(n)-time emulation algorithm for the mesh is known, the underlying constant in the run-time is large, making it impractical. We give an improved emulation algorithm whose time bound is only 4n + o(n).

MS-CIS-91-07 (GRASP LAB 252)

Symbolic Simulator/Debugger For The Systolic/Cellular Array Processor

Janez Funda

MS-CIS-91-08 (GRASP LAB 253)

Descriptive Complexity Approaches To Inductive Inference

Kevin Atteson

We present a critical review of descriptive complexity approaches to inductive inference. Inductive inference is defined as any process by which a model of the world is formed from observations. The descriptive complexity approach is a formalization of Occam's razor: choose the simplest model consistent with the data. Descriptive complexity as defined by Kolmogorov, Chaitin and Solomonoff is presented as a generalization of Shannon's entropy. We discuss its relationship with randomness and present examples. However, a major result of the theory is negative: descriptive complexity is uncomputable.

Rissanen's minimum description length (MDL) principle is presented as a restricted form of the descriptive complexity which avoids the uncomputability problem. We demonstrate the effectiveness of MDL through its application to AR processes. Lastly, we present and discuss LeClerc's application of MDL to the problem of image segmentation.

MS-CIS-91-09 (LINC LAB 191)

Investigating A Proof-Theoretic Meta-Language For Functional Programs (Dissertation)

John Hannan

In this dissertation we study a higher-order intuitionistic logic used as a specification language for a variety of tasks that treat functional programs as data objects. Such meta-programming tasks offer unique challenges including the representation of programs as data objects and the analysis of these objects. We present a technique, inspired by natural semantics and structural operational semantics, for specifying properties of programs. Specifications of this sort are presented as sets of inference rules and are encoded as clauses in a higher-order, intuitionistic meta-logic. Programs are represented by l-terms and many features of the language such as lexical scoping are enforced through the use of l-abstractions. Program properties are represented as propositions over these terms and are then proved by constructing proofs in our meta-logic. The meta-logic, based on natural deduction, includes inference rules for the introduction and discharge of both hypotheses and eigenvariables. We demonstrate how these rules provide simple and elegant manipulations of bound variables in functional programs. We also demonstrate how transforming proofs and proof systems in this setting provides a means for transforming meta-programs, producing new meta-programs that have certain properties or behaviors.

We argue the following points regarding these specifications and their proofs: (i)the specifications of numerous meta-programming tasks are clear, concise and well structured, providing them with simple explanations and correctness proofs; (ii)a wide variety of meta-programming tasks can be specified in a single unified framework, and thus we can investigate and understand the relationship between various tasks; (iii)proofs describing computations or other kinds of manipulations provide a structure that can be analyzed, using established techniques from proof theory; (iv)specification in our logic have a direct translation to programs in the logic programming language lProlog and this translation provides a mechanism for producing experimental implementations of our meta-programs.

MS-CIS-91-10 (GRASP LAB 254)

TRACS Users Manual and Software Reference Guide

Eric Paljug

The Two Robotic Arm Coordination System (TRACS) of the GRASP Lab is designed to perform experiments in dynamic two arm control. The system is comprised of two PUMA 250 robot arms with modified controllers, a PA-AT host computer and an AMD 29000 high speed floating point processor board. This manual describes the system software architecture and the software interfaces between the system elements. It is intended to aid in developing software for the system.

MS-CIS-91-11 (LINC LAB 192)

Type-Raising and Directionality In Combinatory Grammar

Mark Steedman

The form of rules in combinatory categorial grammars (CCG) is constrained by three principles, called ``adjacency'', ``consistency'' and ``inheritance''. These principles have been claimed elsewhere to constrain the combinatory rules of composition and type raising in such a way as to make certain linguistic universals concerning word order under coordination follow immediately. The present paper shows that the three principles have an extremely natural expression in a unification-based interpretation of CCG in which directional information is an attribute of the arguments of functions grounded in string position. The aforementioned universals can thereby be derived as consequences of more elementary assumptions. some desirable results follow, concerning type-raising and the parser.

MS-CIS-91-12 (LINC LAB 193)

Surface Structure, Intonation and Meaning In Spoken Language

Mark Steedman

The paper briefly reviews a theory of intonational prosody and its relation syntax, and to certain oppositions of discourse meaning that have variously been called ``topic and comment'' ``theme and rheme'', ``given and new'', or ``presupposition and focus''. The theory, which is based on Combinatory Categorial Grammar, is presented in full elsewhere. the present paper examines its consequences for the automatic synthesis and analysis of speech.

MS-CIS-91-13 (LINC LAB 194)

A Simple, Yet Probabilistically Tractable Algorithm For First Principles Diagnosis

Ron Rymon

There are three parts to this paper. First, I present what I hope is a conclusive, worst-case, complexity analysis of two well-known formulations of the Minimal Diagnosis problem -- those of [Reiter 87] and [Reggia et al 85]. I then show that Reiter's conflict-sets solution to the problem decomposes the single exponential problem into two problems, each exponential, that need be solved sequentially. From a worst case perspective, this only amounts to a factor of two, in which case I see no reason to prefer it over a simple generate-and-test approach. This is only emphasized with the results of the third part of the paper.

Here I argue for a different perspective on algorithms, that of expected, rather than worst-case performance. From that point of view, a sequence of two exponential algorithms has lesser probability to finish early than a single such algorithm. I show that the straightforward generate-and-test approach may in fact be somewhat attractive as it has high probability to conclude in a polynomial time, given a random problem instance.

MS-CIS-91-14 (LINC LAB 195)

Common Knowledge: A Survey

Marilyn A. Walker

This paper discusses the motivation behind common knowledge. Common knowledge has been argued to be necessary for joint action in general and for language use as a particular kind of joint action. However, this term has been broadly interpreted. Two major issues must be addressed: (1) What mental state corresponds to common knowledge, ie. is knowledge, belief or supposition the appropriate mental attitude? (2) What inference process allows agents to achieve common knowledge? Most generally, common knowledge is used to describe the knowledge that is evidenced in reflexive reasoning. The term has also been used to refer to facts or objects which are mutually salient. One of the main problems for a theory of common knowledge is whether knowledge is the appropriate mental attitude. It seems as though probabilistic beliefs might approximate the cognitive phenomenon of common knowledge more closely than knowledge. The main problem with a usable notion of common knowledge is that inference must play a critical role in what becomes common knowledge. I discuss the nature of conversational inference. It has a number of properties that distinguish it from other inferential systems, such as being apparently abductive and probabilistic, but a precise characterization of it is an unsolved problem. I suggest that in cases where ensuring common knowledge really matters, participants in dialogue accomplish this is by exploiting opportunities for redundancy in conversation.

MS-CIS-91-15 (GRAPHICS LAB 38)

Structure-Based Animation Of The Human Face

Stephen M. Platt, Aaron T. Smith, Francisco Azuola, Norman I. Badler, Catherine Pelachaud

The face is an interesting object to animate for several reasons: it is an important channel of communication and therefore important to an human body animation, and it is a complex object in that it is composed of many nonrigid interacting nonarticulated regions. In this paper, we examine the face, and present it as a hierarchically structured regionally defined object. Based on this regional decomposition, and a set of primitive actions, we describe an encoding of a large set of high level facial action descriptors. We also present an application which studies that interaction between intonation and facial expressions for a given emotion. It offers a higher level of representation of the action units by grouping them into specialized functions (lips shape for phonemes, eyebrow movements). An animation system linked to facial motion property is also presented.

MS-CIS-91-16 (LINC LAB 196)

Dynamic Binding Communication Mechanism

Jeffrey S. Aaronson

Shastri & Ajjanagadde have proposed a biologically plausible connectionist rule-based reasoning system (hereafter referred to as a knowledge base, or KB), that represents a dynamic binding as the simultaneous, or in-phase, activity of the appropriate nodes [9]. This paper makes the first attempt at designing a biologically plausible connectionist interface mechanism between 2 distinct phase-based KB, as the next step toward providing a computational account of common-sense reasoning. The Dynamic Binding Communication Mechanism (DBCM) extracts a dynamic binding from a source KB and incorporates the binding into a destination KB so that it is consistent with the knowledge already represented in the latter. DBCM consists of several distinct, special-purpose modules. The Binding Memory (BM) is made up of several identical banks of nodes. Each time a temporally-encoded dynamic binding is extracted from the source KB, it is transferred into on of the banks, where the binding is converted to a spatially-encoded representation. The Phase Database (PD) monitors the target KB. The Phase Allocator (PA) synthesizes information from the Phase Database and from the target KB to determine the phase in which to introduce the new dynamic binding into the target KB. In turn, the PA extracts a single binding from one of the banks in the BM and introduces it into the target KB. The interface also utilizes 2 searchlight mechanisms: the first governs which bank in the BM receives binding; the second mediates between the active banks (those which are currently representing bindings), and the Phase Allocator.

MS-CIS-91-17 (GRASP LAB 255)

The Hughes Array Co-Processor and Its Application To Robotics

Craig Sayers

This report describes the results of twelve months research involving the Hughes array co-processor. This work began with the testing and debugging of the existing system, continued with the development of software to interface the co-processor to a host machine and concluded with the implementation of a trajectory planning algorithm for redundant manipulators. A loader program has been developed which allows simple programs to be executed. A library of C-callable routines has also been created and this enables the fabrication of more complex systems which require a high level of interaction between the host and co-processor. Routines to perform square root, sine and cosine functions have been designed and these have been used successfully in the development of a trajectory planning algorithm. This algorithm uses the co-processor to compute in parallel a large number of forward kinematic solutions and by doing so is able to convert a cartesian space trajectory into a joint space path for a redundant manipulator. The performance of the processor has been analyzed and a number of recommendations have been made concerning future implementations.

MS-CIS-91-18 (DISTRIBUTED SYSTEMS LAB 5)

Analysis Of Dynamic Congestion Control Protocols: A Fokker-Planck Approximation

Amarnath Mukherjee, John C. Strikwerda

We present an approximate analysis of a queue with dynamically changing input rates that are based on implicit on explicit feedback. This is motivated by recent proposals for adaptive congestion control algorithms [RaJa 88, Jac 88], where the sender's window size at the transport level is adjusted based on perceived congestion level of a bottleneck node. We develop an analysis methodology for a simplified system; yet it is powerful enough to answer the important questions regarding stability, convergence (or oscillations), fairness and the significant effect that delayed feedback plays on performance. Specifically, we find that, in the absence of feedback delay, the linear increase/exponential decrease algorithm of Jacobson and Ramakrishnan-Jain [Jac 88, RaJa 88] is provably stable and fair. Delayed feedback on the other hand, introduces oscillations for every individual user as well as unfairness across those competing for the same resource. While the simulation study of Zhang [Zha 89] and the fluid-approximation study of Bolot and Shanker [BoSh 90] have observed the oscillations in cumulative queue length and measurements by Jacobson [Jac 88] have revealed some of the unfairness properties, the reasons for these have not been identified. We identify quantitatively the cause of these effects, via-a-vis the syst ems parameters and properties of the algorithm used. The model presented is fairly general and can be applied to evaluate the performance of a wide range of feedback control schemes. It is an extension of the classical Fokker-Planck equation. Therefore, it addresses traffic viability (to some extent) that fluid approximation techniques do not address.

MS-CIS-91-19 (GRAPHICS LAB 39)

Programming With Jack (Fourth Edition)

Cary B. Phillips

This manual describes the implementation of Jack with emphasis on how to extend it and modify it. the principle purpose of this manual is to describe what functions in the Jack libraries are available to be used in writing new features for Jack. the manual also gives an overview of how Jack works, for those interested in modifying its current behavior. This manual assumes that you already know how to use Jack, and are familiar with its basic terminology.

MS-CIS-91-20 (GRASP LAB 256)

GRASP NEWS, Volume 7, Number 1 Spring 1991

Various Contributors

Since its beginning in 1983, the GRASP News has chronicled the research efforts of the Grasp Laboratory. This edition, which covers developments for the year 1990, follows the format of previous editions. The Feature Article, however, in a departure from tradition does not highlight a particular research project. The research abstract summarize the progress of students, postdoctoral fellows, visiting researchers, and faculty. The abstracts are classified into three different areas -- Visions Research, Robotics Research and Distributed Real-Time Systems Research. There is also a section on laboratory Software and Hardware Developments. This edition comprises 40 articles from 45 contributors, which makes it the largest GRASP News ever!

MS-CIS-91-21 (LOGIC & COMPUTATION 28)

Representing Powerdomain Elements As Monadic Second Order Predicates

Carl A. Gunter

This report characterizes the powerdomain constructions which have been used in the semantics of programming languages in terms of formulas of first order logic under a preordering of provable implication. This provides an intuitive representation which suggests a new form of powerdomain---called the mixed powerdomain---which expresses data in a different way from the well-known constructions from programming semantics. It can be shown that the mixed powerdomain has many of the properties associated with the convex powerdomain such as the possibility of solving recursive equations and a simple algebraic characterization.

MS-CIS-91-22 (LINC LAB 197)

Tree-Adjoining Grammars and Lexicalized Grammars

Aravind K. Joshi, Yves Schabes

In this paper, we will describe a tree generating system called tree-adjoining grammar (TAG) and state some of the recent result about TAGs. The work on TAGs is motivated by linguistic considerations. However, a number of formal results have been established for TAGs, which we believe, would be of interest to researchers in tree grammars and tree automata. After giving a short introduction to TAG, we briefly state these result concerning both the properties of the string sets and tree sets. We will also describe the notion of lexicalization of grammars and investigate the relationship of lexicalization to context-free grammars (CFGs) and TAGs.

MS-CIS-91-23 (LOGIC & COMPUTATION 29)

An Abstract Interpretation For ML Equality Kinds

Carl A. Gunter (University of Pennsylvania) Elsa L. Gunter (AT&T Bell Laboratories) David B. MacQueen (AT&T Bell Laboratories)

The definition of Standard ML provides a form of generic equality which is inferred for certain types, called equality types, on which it is possible to define a computable equality relation. However, the standard definition is incomplete in the sense that there are interesting and useful types which are not inferred to be equality types but which nevertheless have a computable equality relation. In this paper we introduce a refinement of the Standard ML system of equality types and prove that our system is sound and complete} with respect to the existence of a computable equality. Our technique is based on an abstract interpretation of ML operators as monotone functions over a three point lattice. We show how the equality relation can be defined (as an ML program) from the definition of a type with our equality property. We then demonstrate a sound, efficient algorithm for inferring the equality property which corrects the limitations of the standard definition in all cases of practical interest.

MS-CIS-91-24 (LINC LAB 198)

Unification Of Simply Typed Lambda-Terms As Logic Programming

Dale Miller

The unification of simply typed lambda-terms modulo the rules of beta- and eta-conversions is often called ``higher-order'' unification because of the possible presence of variables of functional type. This kind of unification is undecidable in general and if unifiers exist, most general unifiers may not exist. In this paper, we show that such unification problems can be coded as a query of the logic programming language L-lambda in a natural and clear fashion. In a sense, the translation only involves explicitly axiomatizing in L-lambda the notions of equality and substitution of the simply typed lambda-calculus: the rest of the unification process can be viewed as simply an interpreter of L-lambda searching for proofs using those axioms. Appears in the Proceedings of the 1991 International Conference on Logic Progr amming, edited by Koichi Furukawa, June 1991.

MS-CIS-91-25 (LINC LAB 199)

Unification-Based Tree Adjoining Grammars

K. Vijay-Shanker (University of Delaware) Aravind K. Joshi (University of Pennsylvania)

Many current grammar formalisms used in computational linguistics take a unification-based approach that use structures (called feature structures) containing sets of feature-value pairs. In this paper, we describe a unification-based approach to Tree Adjoining Grammars (TAG). The resulting formalism (UTAG) retains the principle of factoring dependencies and recursion that is fundamental to TAGs (see Schabes, et. al., 1988). We give some l inguistic examples using UTAG and informally discuss the descriptive capacity of U TAG, comparing it with other unification-based formalisms. Finally, based on the linguistic theory underlying TAGs, we propose some stipulations that can be placed on UTAG grammars. In particular, we stipulate that the feature structures associated with the nodes in an elementary tree are bounded (there is an analogous stipulation on GPSG). Grammars that satisfy these stipulations are equivalent to TAG. Thus, even with these stipulations, UTAGs have more power than CFG-based unification grammars with the same stipulations. To Appear in Unification-Based Grammars'' (ed. Jurgen Wedekind), MIT PRESS, 1991.

MS-CIS-91-26 (LOGIC & COMPUTATION 30)

Relevant Consequence and Empirical Inquiry

Daniel N. Osherson (IDIAP) Scott Weinstein (University of Pennsylvania)

A criterion on adequacy is proposed for theories of relevant consequence. According to the criterion, scientists whose deductive reasoning is limited to some proposed subset of the standard consequence relation must not thereby suffer a reduction in scientific competence. A simple theory of relevant consequence is introduced and show to satisfy the criterion with respect to a formally defined paradigm of empirical inquiry.

MS-CIS-91-27 (GRASP LAB 257)

Occlusions As A Guide For Planning The Next View

Jasna Maver, Ruzena Bajcsy

The task of constructing a volumetric description of a scene from a single image is an underdetermined problem, whether it is a range or an intensity image. To resolve the ambiguities that are caused by occlusions in images, we need to take sensor measurements from several different views. We have limited ourselves to range images obtained by a laser scanning system. It is an actrive system which can encounter two types of occlusions. An occlusion arises either when the refelcted laser light does not reach the camera or when the direct laser light does not reach the scene surface. The task of 3-D data acquisition is divided into two subproblems: to acquire the depth information from one scanning plane and to select the proper scanning planes from which the direct laser light illuminates the entire scene. The first kind of occlusions (range shadows) are easily detected and can be used in designing an efficient algorithm. We develop a strategy to determine the sequence of different views using the information in a narrow zone around the occluded regions. Occluded regions are approximated by polygons. Based on the height information of the border of the occluded regions and geometry of the edges of the polygonal approximation, the next views in the same scanning plane the directions of the next scanning planes for further data acquisition are computed. A condensed and revised version of this technical report also appears as ``Occlusions as a Guide for Planning the Next View,'' University of Pennsylvania Technical Report, MS-CIS-92-40, GRASP LAB 318, 1991.

MS-CIS-91-28 (GRAPHICS LAB 40; LINC LAB 200)

Action Composition For The Animation Of Natural Language Instructions

Libby Levison

This report is an investigation of issues encountered in generating a short simulation from a set of instructions. A method for specifying simulations at a task-level, rather than by individual motion, is discussed. The research was conducted using a set of instructions that describe the removal of a Fuel Control Valve from an aircraft.

MS-CIS-91-29 LOGIC & COMPUTATION 31)

Logical And Computational Aspects Of Programming With Sets/Bags/Lists

Val Breazu-Tannen, Ramesh Subrahmanyam

We study issues that arise in programming with primitive recursion over non-free datatypes such as lists, bags and sets. Programs written in this style can lack a meaning in the sense that their outputs may be sensitive to the choice of input expression. We are, thus, naturally lead to a set-theoretic denotational semantics with partial functions. We set up a logic for reasoning about the definedness of terms and a deterministic and terminating evaluator. The logic is shown to be sound in the model, and its recursion free fragment is shown to be complete for proving definedness of recursion free programs. The logic is then shown to be as strong as the evaluator, and this implies that the evaluator is compatible with the provable equivalence between different set (or bag, or list) expressions . Oftentimes, the same non-free datatype may have different presentations, and it is not clear a priori whether programming and reasoning with the two presentations are equivalent. We formulate these ques tions, precisely, in the context of alternative presentations of the list, bag, an d set datatypes and study some aspects of these questions. In particular, we establish back-and-forth translations between the two presentations, from which it follows that they are equally expressive, and prove results relating proofs of program properties, in the two presentations. This paper has appeared in the Proceedings Of ICALP '91

MS-CIS-91-30 (GRASP LAB 258)

Design Of A Tool-Surrounding Compliant Instrumented Wrist

Thomas Lindsay, Richard P. Paul

Interaction between robot and environment is an extremely important aspect of robotic research. Compliance helps reduce the effects of impact when there is robot/environment interaction. To accomplish useful tasks, it is important to implement hybrid control; accurate position control is needed in unconstrained directions and accurate force control is needed in constrained direction. Force control can be more responsive with a compliant force/torque sensor [3], but positional accuracy is reduced with compliance. An instrumented compliant wrist device can be used to achieve both responsive force control and accurate position control. The wrist is connected in series between the end of the robot and the tool. The wrist device uses rubber elements for compliance and damping, and a serial linkage, with potentiometers at each joint, is used for sensing the defections produced in the wrist. Several major improvements are proposed for the Xu wrist. The wrist can be designed to surround the tool, thus reducing the distance between the end of the robot and the end of the tool, thus reducing the distance between the end of the robot and the end of the tool. The compliant structure is redesigned for more even compliance, and the sensing structure kinematics are simplified. In this over, the compliance, kinematics, and accuracy of the wrist will be presented. Also, software for finding the wrist transform, and plans for the wrist are given.

MS-CIS-91-31 (GRASP LAB 259)

Communicating Shared Resources: A Paradigm For Integrating Real-Time Specification And Implementation

Insup Lee, Susan Davidson, Richard Gerber

The timed behavior of distributed real-time systems can be specified using a formalism called Communicating Shared Resources, or CSR. The underlying computation model of CSR is resource-based in which multiple resources execute synchronously, while processes assigned to the same resource are interleaved according to their priorities. CSR bridges the gap between an abstract computation model and implementation environments, but is too complex to be treated as a process algebra. We therefore give a calculus for CSR (CCSR), that provides the ability to perform equivalence proofs by syntactic manipulation. We illustrate how a CSR specification can be translated into the CCSR formalism using a periodic timed producer-consumer example, and how a translated CSR specification can be shown correct using syntactic manipulations.

MS-CIS-91-32 (LOGIC & COMPUTATION 32)

Logic Programming In A Fragment Of Intuitionistic Linear Logic: Extended Abstract

Joshua Hodas, Dale Miller

Logic programming languages based on fragments of intuitionistic logic have recently been developed and studied by several researchers. In such languages, implications are permitted in goals and in the bodies of clauses. Attempting to prove a goal of the form D É G in a context G leads to an attempt to prove the goal G in the extended context G{D}. While an intuitionistic notion of context has many uses, it has turned out to be either too powerful or too limiting in several settings. We refine the intuitionistic notion of context by using a fragment of Girard's linear logic that includes additive and multiplicative conjunction, linear implication, universal quantification, the ``of course'' exponential, and the constants 1 (the empty context) and T (for ``erasing'' contexts). After presenting our fragment of linear logic, which contains the hereditary Harrop formulas, we show that the logic has a goal-directed interpretation. We also show that the non-determinism that results from the need to split contexts in order to prove a multiplicative conjunction can be handled by viewing proof search as a process that takes a context, consumes part of it, and returns the rest (to be consumed elsewhere). The complete specification of an interpreter for this logic is presented. Examples taken from theorem proving, natural language parsing, and data base programming are presented: each example requires a linear, rather than intuitionistic, notion of context to be modeled adequately.

MS-CIS-91-33 (LINC LAB 201)

Combining A Type Hierarchy With A Rule-Based Reasoner

Lokendra Shastri, D.R. Mani

This report describes an efficient connectionist knowledge representation and reasoning system that combines rule-based reasoning with inheritance and classification within an IS-A hierarchy. In addition to a type hierarchy, the proposed system can encode generic facts such as `Cats prey on birds' and rules such as `If x preys on y then y is scared of x' and use them to infer that Tweety (who is a Canary) is scared of Sylvester (who is a Cat). The system can also encode qualified rules such as if an animate agent walks into a solid object then the agent gets hurt'. The proposed system can answer queries in time that is only proportional to the length of the shortest derivation of the query and is independent of the size of the knowledge b ase. The system maintains and propagates variable bindings using temporally synchronous --- i.e., in-phase --- firing of appropriate nodes.

MS-CIS-91-34 (LOGIC & COMPUTATION 33)

Formal Models For Concurrent Communicating Systems

Anthony S. Kosky

This report was originally written to fulfill in part the requirements of the author's WPE examinations, part of the qualifying examinations for the University of Pennsylvania'a Computer Science Ph.D program. The report first introduces CCS and uses it to illustrate various features of established methods of modelling concurrent, communicating systems. The report then goes on to describe and investigate two new models for such systems: The Chemical Abstract Machine, a simple yet predominant in most models for such systems; and the p-calculus, a calculus similar in many respects to CCS, but able to model mobile processes and other, more difficult phenomena.

MS-CIS-91-35 (GRASP LAB 260)

RTC: Language Support For Real-Time Concurrency

Victor Wolfe, Susan Davidson, Insup Lee

This paper presents language constructs for the expression of timing and concurrency requirements in distributed real-time programs. Our programming paradigm combines an object-based paradigm for the specification of shared resources, and a distributed transaction-based paradigm for the specification of application processes. Resources provide abstract views of shared system entities, such as devices and data structures. Each resource has a state and defines a set of actions that can be invoked by processes to examine or change its state. A resource also specifies scheduling constraints on the execution of its actions to ensure the maintenance of its state's consistency. Processes access resources by invoking actions and express precedence, consistency. Processes access resources by invoking actions and express precedence, consistency and timing constraints on action invocations. The implementation of our language constructs with real-time scheduling and locking for concurrency control is also described.

MS-CIS-91-36 (GRASP LAB 261)

A Framework For Visual Observation (Dissertation Proposal)

Tarek M. Sobh

We address the problem of observing a moving agent. In particular, we propose a system for observing a manipulation process, where a robot hand manipulates an object. A discrete event dynamic systems (DEDS) frame work is developed for the hand/object interaction over time and a stabilizing overserver is constructed. Low-level modules are developed for recognizing the ``events'' that causes state transitions within the dynamic manipulation system. The work examines closely the possibilities for errors, mistakes and uncertainties in the manipulation system, observer construction process and event identification mechanisms. The system utilizes different tracking techniques in order to observe and recognize the task in an active, adaptive and goal-directed manner.

MS-CIS-91-37 (GRASP LAB 262)

The Role Of Vergence Micromovements On Depth Perception

Antônio Francisco Júnio

A new approach in stereo vision is proposed which recovers 3D depth information using continuous vergence angle control with simultaneous local correspondence response. This technique relates elements with the same relative position in the left and right images for a continuous sequence of vergence angles. the approach considers the extremely fine vergence movements about a given fixation point within the depth of field boundaries. It allows the recovery of 3D depth information given the knowledge of the system's geometry and a sequence of pairs [a_I, C_i], wherea_i is the i^th vergence angle and C_i is the i^th matrix of correspondence responses. The approach has several advantages over the current ones. First, due to its local operation characteristics, the resulting algorithms can be implemented in a modular hardware scheme. Second, unlike currently use algorithms, there is no need to compute depth from disparity values; at the cost of the acquisition of a sequence of images during the micromovements. the approach also greatly reduces the errors in stereo due to the sensor quantization. Last, and most important of all, the approach is supported by experimental results from physiology and psychophysics. Physiological results show that the human eye performs fine movements during the process of fixation on a single point, which are collectively called physiological nystagmus. One such movement, called binocular flicks, happens in opposing directions and produces convergence/divergence of the eyes. These are the micromovements that we suppose are the basis for depth perception. Therefore, the approach proposes a functional correlation between these vergence micromovements, depth perception, stereo acuity and stereo fusion.

MS-CIS-91-38 (GRASP LAB 263)

Performance Evaluation via Perturbation Analysis

Tarek M. Sobh

In this paper we present an overview for the development of a theory for analyzing and predicting the behavior if discrete event dynamic systems (DEDS). DEDS are dynamic systems in which state transitions are caused by internal, discrete events in the system. DEDS are attracting considerable interest, current applications are found in manufacturing systems, communications and air traffic systems, future applications will include robotics, computer vision and artificial intelligence. We will discuss the perturbation analysis technique (PA) for evaluation the performance of DEDS.

MS-CIS-91-39 (GRASP LAB 264)

Discrete Event Dynamic Systems: An Overview

Tarek M. Sobh

In this report we present an overview for the development of a theory for discrete event dynamic systems (DEDS). Dynamic systems are usually modeled by finite state automata with partially overservable events together with a mechanism for enabling and disabling a subset of state transitions. DEDS are attracting considerable interests, current applications are found in manufacturing systems, communications and air traffic systems, future applications will include robotics, computer vision and AI. We will discuss notions of modeling, stability issues, observability, feedback and invertibility. We will also discuss the perturbation analysis technique (PA) for analyzing and describing the behavior of DEDs.

MS-CIS-91-40 (GRASP LAB 265)

Teleprogramming: Towards Delay-Invariant Remote Manipulation (Dissertation)

Janez Funda

This dissertation addresses the problem of remote manipulation in the presence of communication delays. Delays occur with earth-based control of a robotic system in space or when an untethered submersible system is controlled from the surface via an acoustic communication channel. The resulting delay in obtaining position and force feedback from the remote slave arm(s) makes direct teleoperation infeasible. We propose a new control methodology, called teleprogramming, which allows for efficient control for a robotic system in the presence of significant feedback delays without substantial degradation in the overall system performance. A teleprogramming system allows the operator to kinesthethically, as well as visually, interact with a graphical simulation of the remote environment and to interactively, on-line teleprogram the remote manipulator through a sequence of elementary symbolic instructions. These instructions are generated automatically by the operator's station software in real time as the task progresses. The slave robot executes these symbolic commands delayed in time and, should an error occur, allows the operator to specify the necessary corrective actions and continue with the task. Teleprogramming offers a practical compromise between the ultimate and the feasible, and provides an effective and time-efficient approach to remote manipulation. Advantages of teleprogramming over existing control methodologies include a relatively modest required level of remote site autonomy, and the absence of the need of complex automatic task planners and preprogrammed error recovery modules. This document describes the overall conceptual architecture of teleprogramming and presents a detailed treatment of all major components of teleprogramming system. An operational prototype system is described an preliminary experimental results are reported. Experimental results have confirmed the validity and feasibility of the teleprogramming control methodology. Sustained and efficient remote control of a robot manipulator in the presence of a five second feedback delay was successfully accomplished for simple contact tasks.

MS-CIS-91-41 (GRASP LAB 266)

A Comparison Of Compressed and Uncompressed Transmission Modes

Tarek M. Sobh, Jaffar Rehman

In this paper we address the problem of host to host communication. In particular, we discuss the issue of efficient and adaptive transmission mechanisms over possible physical links. We develop a tool for making decisions regarding the flow of control sequences and data from and to a host. This issue of compression is discussed in details, a decision box and an optimizing tool for finding the appropriate thresholds for a decision are developed. Physical parameters like the data rate, bandwidth of the communication medium, distance between the hosts, abaud rate, levels of discretization, signal to noise ration and propagation speed of the signal are taken into consideration while developing our decision system. Theoretical analysis is performed to develop mathematical models for the optimization algorithm. Simulation models are also developed for testing both the optimization and the decision tool box.

MS-CIS-91-42 (LINC LAB 202)

Generation and Synchronous Tree-Adjoining Grammars

Stuart M. Sheiber (Harvard University) Yves Schabes (University of Pennsylvania)

MS-CIS-91-43 (LINC LAB 203)

Synchronous Tree-Adjoining Grammars

Stuart M. Sheiber (Harvard University) Yves Schabes (University of Pennsylvania)

The unique properties of tree-adjoining grammars (TAG) present a challenge for the application of TAGs beyond the limited confines of syntax, for instance, to the task of semantic interpretation or automatic translation of natural language. We present a variant of TAGs, called synchronous TAGs, which characterize correspondences between languages. The formalism's intended usage is to relate expressions of natural languages to their associated semantics represented in a logical form language, or to their translates in another natural language; in summary, we intend it to allow TAGs to be used beyond their role in syntax proper. We discuss the application of synchronous TAGs to concrete examples, mentioning primarily in passing some computational issues that arise in its interpretation.

MS-CIS-91-44 (LINC LAB 204)

Using Lexicalized Tags For Machine Translation

Anne Abeillé(University of Paris) Yves Schabes (University of Pennsylvania) Aravind K. Joshi (University of Pennsylvania)

Lexicalized Tree Adjoining Grammar (LTAG) is an attractive formalism for linguistic description mainly because of its extended domain of locality and its factoring recursion out from the domain of local dependencies (Joshi, 1984, Kroch and Joshi, 1985, Abeille, 1988). LTAG's extended domain of locality enables on to localize syntactic dependencies (such as filler-gap), as well as semantic dependencies (such as predicate-arguments). The aim of this paper is to show that these properties combined with the lexicalized property of LTAG are especially attractive for machine translation. The transfer between two languages, such as French and English, can be done by putting directly into correspondence large elementary universe without going through some interlingual representation and without major changes to the source and target grammars. The underlying formalism fro the transfer is ``synchronous Tree Adjoining Grammars'' (Sheiber and Schabes [1990]). Transfer rules are stated as correspondences between nodes of trees of large domain of locality which are associated with words. We can thus define lexical transfer rules that avoid the defects of a mere word-to-word approach but still benefit from the simplicity and elegance of a lexical approach. We rely on the French and English LTAG grammars (Abeillé [1988], Abeillé [1990(b)], Abeillé et al. [1990], Abeillé and Schabes [1989, 1990]) that have been designed over the past two years jointly at University of Pennsylvania and University of Paris 7-Jussieu.

MS-CIS-91-45 (GRASP LAB 267)

Surface and Volumetric Segmentation Of Complex 3-D Objects Using Parametric Shape Models (Dissertation)

Alok Gupta

The problem of part definition, description, and decomposition is central to the shape recognition systems. In this dissertation, we develop an integrated framework for segmenting dense range data of complex 3-D scenes into their constituent parts in terms of surface and volumetric primitives. Unlike previous approaches, we use geometric properties derived from surface, as well as volumetric models, to recover structured descriptions of complex objects without a priori domain knowledge or stored models. To recover shape descriptions, we use bi-quadric models for surface representation and superquadric models for object-centered volumetric representation. The surface segmentation uses a novel approach of searching for the best piecewise description of the image in terms of bi-quadric (z = f(x,y)) models. It is used to generate the region adjacency graphs, to localize surface discontinuities, and to derive global shape properties of the surfaces. A superquadric model is recovered for the entire data set and residuals are computed to evaluate the fit. The goodness-of-fit value based on the inside-outside function, and the mean-squared distance of data from the model provide quantitative evaluation of the model. The qualitative evaluation criteria check the local consistency of the model in the form of residual maps of overestimated and underestimated data regions. The control structure invokes the models in a systematic manner, evaluates the intermediate descriptions, and integrates them to achieve final segmentation. Superquadric and bi-quadric models are recovered in parallel to incorporate the best of the coarse-to-fine and fine-to-coarse segmentation strategies. The model evaluation criteria determine the dimensionality of the scene, and decide whether to terminate the procedure, or selectively refine the segmentation by following a global-to-local part segmentation approach. The control module generates hypotheses about superquadric models at clusters of underestimated data and performs controlled extrapolation of the part-model by shrinking the global model. As the global model shrinks and the local models grow, they are evaluated and tested for termination or further segmentation. We present results on real range images of scenes of varying complexity, including objects with occluding parts, and scenes where surface segmentation is not sufficient to guide the volumetric segmentation. We analyze the issue of segmentation of complex scenes thoroughly by studying the effect of missing data on volumetric model recovery, generating object-centered descriptions, and presenting a complete set of criteria for the evaluation of the superquadric models. We conclude by discussing the applications of our approach in data reduction, 3-D object recognition, geometric modeling, automatic model generation, object manipulation, and active vision.

MS-CIS-91-46 (GRASP LAB 268)

Self Organizing Feature Maps and Their Applications To Robotics

Craig Sayers

The self-organizing feature maps developed by Kohonen appear to capture some of the advantages of the natural systems on which they are based. A summary of the operation of this form of artificial neural network is presented. It was concluded that the primary benefits of using self-organizing feature maps result from their adaptability and plasticity while most problems are largely caused by the lack of a rigorous mathematical foundation. Two different robotics applications are described. In the first, developed by Martinez and Schulten, a hierarchical structure composed of many self-organizing feature maps is used to control a five degree of freedom robot arm. While it was noted that there may be some practical problems, the general idea of using a hierarchical structure appears sound and may be applicable to a wider range of problems. The second robotics application was developed by Saxon and Mukherjee. They used a single self-organizing feature map to learn the motion map of a two degree of freedom arm. The use of such a system should simplify path planning by combining multiple constraints into a 2-D structure.

MS-CIS-91-47 (GRASP LAB 269)

Optimal Randomized Algorithms For Multipacket and Wormhole Routing On the Mesh

Sanguthevar Rajasekaran, Mukund Raghavachari

In this paper, we present a randomnized algorithm for the multipacket (i.e., k - k) routing problem on an n x n mesh. The algorithm competes with high probability in at most kn + O(k log n) parallel communication steps, with a constant queue size of O(k). The previous best known algorithm [4] takes [5/4] kn + O([kn/f(n)]) steps with a queue size of O(k f(n)) (for any 1 £n). We will also present a randomnized algorithm for the wormhold model permutation routing problem for the mesh that completes in at the most kn + O(k log n) steps, with a constant queue size of O(k), where k is the number of flits that each packet is divided into. The previous best result [6] was also randomnized and had a time bound of kn +O ([kn/f(n)]) with a queue size of O(k f(n)) for any 1 £ f(n). The two algorithms that we will present are optimal with respect to queue size. The time bounds are within a factor of two of the only known lower bound.

MS-CIS-91-48 (GRASP LAB 270)

Analysis and Simulation Of Mechanical Systems With Multiple Frictional Contacts

Yin Tien Wang, Vijay R. Kumar

In many engineering applications such as assembly of mechanical components, robot manipulation, gripping, fixturing and part feeding, there are situations in which a rigid body is subject to multiple frictional contacts with other bodies. It is proposed to develop a systematic method for the analysis and simulation of such systems. A detailed study is presented on rigid body impact laws, and the assumption of contact compliance is investigated.

MS-CIS-91-49 (LOGIC & COMPUTATION 34)

Theoretical Aspects Of Schema Merging

Peter Buneman, Susan Davidson, Anthony Kosky

A general technique for merging database schemas is developed that has a number of advantages over existing techniques, the most important of which is that schemas are placed in a partial order that has bounded joins. This means that the merging operation, when it succeeds, is both associative and commutative, i.e., that the merge of schemas is independent of the order in which they are considered -- a property not possessed by existing methods. The technique is interactive in that users made assertions about the relationships between the nodes of the schemas to be merged. These assertions are then considered to be elementary schemas, and are combined with the schemas using precisely the same merging operation. The technique is general and can be applied to a variety of data models. It can also deal with certain cardinality constraints that arise through the imposition of keys. A prototype implementation, together with a graphical interface, has been developed.

MS-CIS-91-50 (GRAPHICS LAB 41)

Natural Language Control Of Animation Of Task Performance In A Physical Domain (Dissertation)

Jugal Kumar Kalita

We establish a link from natural language statements describing actions to be performed by an agent to a semantic representation suitable for achieving effective control of a computer-driven graphical animation system. A representation scheme based on decompositional analysis is developed emphasizing the requirement that algorithmic implementability of the underlying semantic primitives is our primary concern. Our primitives pertain to mechanical characteristics of the ``kernel'' tasks denoted by a class of action verbs (verbs whose underlying tasks deal with an agent manipulating one or more objects); they refer to geometric constraints and goals that need to be achieved, kinematic and dynamic characteristics, and certain aspectual characteristics such as repetitiveness of one or more sub-actions, definedness of termination points, etc. We provide lexical entries for a few verbs in terms of such primitives. We also analyze the manner in which prepositional and adverbial modifiers affect the representation as well as the execution of the basic actions denoted by the verbs. Such modifiers either provide values of arguments for the verbs' internal representations, modify default argument values, or provide values of non-obligatory arguments. We obtain semantic representations for a few prepositions and adverbs in a fashion integrable into the scheme for verbal meaning representation. We have developed a system to demonstrate the validity of the results obtained; such a system establishes channels of communication with existing animation software developed at the Graphics Laboratory at the University of Pennsylvania.

MS-CIS-91-51 (DISTRIBUTED SYSTEMS LAB 6)

On Call Migration

Ming Chit Tam

In an environment where network resources are reserved e.g, telephone networks, the path with smallest number of hops is prefered and other alternate paths are used only when there the shortest path is full. However if the alternate path is longer more network resources are devoted to the circuit and this in turn could worsen the situation. Circuit migration is a solution to reduce the amount of resources inefficiently used due to alternate routing in connection oriented networks. By rerouting a circuit when its shortest path becomes available, one can smooth out the congestion and increases the utilization of the network. The overhead of circuit migration is comparable to call set up and the tradeoff of circuit migration is improvement in performance vs. some additional call processing capacity. In this report we will focus on the above tradeoff, evaluating it analytically and by simulation on a completely connected topology. Our initial results indicate that migration could improve the performance of the network at high load but it has to be done very often. Such a large amount of overhead could be expensive enough to offset the gain in performance. On further investigation, we discover that threshing can also occur in circuit migration. We proposed two solutions to the problem. The first solution is to migrate only when the shortest path is no longer highly utilized. The second solution migrates a circuit only if its path is congested. A hybrid solution using the two above is also examined. We will also address the reordering problem that could occur when a circuit is transferred to a new path.

MS-CIS-91-52 (GRASP LAB 271)

Fast Algorithms For Generating Discrete Random Variates With Changing Distribu tion

Sanguthevar Rajasekaran, Keith W. Ross

One of the most fundamental and frequently used operations in the process of simulating a stochastic discrete event system is the generation of a nonuniform discrete random variate. The simplest form of this operation can be stated as follows: Generate a random variable X which is distributed over the integers 1,2, ¼ such that P(X = i) = p_i. A more difficult problem is to generate X when the p_i's change with time. For this case, there is a well-known algorithm which takes O( log n) time to generate each variate. Recently Fox [4] presented an algorithm that takes an expected o( log n) time to generate each variate under assumptions restricting the way the p_i's can change. In this paper we present algorithm for discrete random variate generation that take an expected O(1) time to generate each variate. Furthermore, our assumptions on how the p_i 's change are less restrictive than those of Fox. The algorithms are quite simple and can be fine-tuned to suit a wide variety of application. The application to the simulation of queueing networks is discussed in some detail.

MS-CIS-91-53 (DISTRIBUTED SYSTEMS LAB 7)

Dynamic Time Windows and Generalized Closed-Loop/Open-Loop Mechanisms For Congestion Control Of Data Traffic In High Speed Wide Area Networks

Amarnath Mukherjee (University of Pennsylvania) Lawrence H. Landweber (University of Wisconsin) Theodore Faber (University of Wisconsin)

This paper presents a set of mechanisms for congestion control of data traffic in high speed wide area networks (HSWANs) along with preliminary performance results. The model of the network assumes reservation of resources based on average requirements. The mechanisms address (a) the different network time constants (short term and medium-term), (b) admission control that allows controlled variance of traffic as a function of medium-term congestion, and (c) prioritized scheduling which is based on a new fairness criterion. This latter criterion is perceived as the appropriate fairness measure for HSWANs. Preliminary performance studies show that the queue length statistics at switching nodes (mean, variance and max) are approximately proportional to the end-point 'time window' size. Further,

• when network utilization approaches unity, the time window mechanism can protect the network from buffer overruns and excessive queueing delays, and
• when network utilization level is smaller, the time window may be increased to allow a controlled amount of variance that attempts to simultaneously meet the performance goals of the end-user and that of the network.

• necessary and sufficient conditions for accomplishing desired fairness,
• simulation and (limited analytical results for expected waiting times,
• ability to protect against misbehaving users, and
• relationship between end-point admission control (Time-Window) and internal scheduling ('Pulse' and Virtual Clock) at the switch.

MS-CIS-91-54 (LINC LAB 205)

Flexible Support For Trauma Management Through Goal-Directed Reasoning and Planning

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

We describe a system, TraumAID, which has been designed to provide decision support throughout the initial definitive management of severely injured patients (i.e., after their initial evaluation, resuscitation, and stabilization). Over the course of initial definitive management, TraumAID recommends appropriate procedures to be carried out, based on currently available evidence and on the complexity and urgency of the situation. TraumAID's ability to deal flexibly with complex and often urgent situations comes from its ability to reason separately about the management goals that should be achieved and about the means that are situationally appropriate for achieving them. In this paper, we describe TraumAID's approach to trauma management in more detail, showing in particular how it enables TraumAID to adapt its reasoning and recommendations to the urgency with which a patient's condition must be addressed.

MS-CIS-91-55 (GRASP LAB 272; DISTRIBUTED SYSTEMS LAB 8)

Supporting Real-Time Concurrency

Victor Wolfe

Concurrent real-time applications are complicated since both timing and consistency constraints must be met for correct performance. Furthermore, techniques to enforce these two forms of constraints are often incompatible. For instance, priority-driven preemptive scheduling, which is optimal for meeting timing constraints in some systems, may leave a shared resource's state inconsistent. On the other hand, mutual exclusion techniques that ensure the consistency of shared resources are not well-suited to meeting timing constraints. This dissertation develops concepts and programming language constructs for facilitating the enforcement of both real-time and consistency constraints in applications with concurrency. Our programming paradigm combines an object-based paradigm for the specification of shared resources, and a distributed transaction-based paradigm for the specification of application processes. Resources provide abstract views of shared system entities, such as devices and data structures. Each resource has a state and defines a set of actions that can be invoked by processes to examine or change its state. A resource also specifies scheduling constraints on the execution of its actions to ensure the maintenance of its state's consistency. Processes access resources by invoking actions and express precedence, consistency and timing constraints on action invocations. The implementation of our language constructs with real-time scheduling and locking for concurrency control is also described, including a novel deadlock prevention technique. The utility of the constructs are demonstrated in two ways. First, we describe their use to solve a general concurrent real-time problem called timed atomic commitment . We then describe how they were used to program a graphic simulation of two robot arms coordinating to pick up a moving object under timing constraints.

MS-CIS-91-56 (GRAPHICS LAB 42)

Three Dimensional Workspace Visualization For Redundant Articulated Chains

This thesis deals with the problem of the 3D workspace visualization for anthropomorphic linkages, not only those with redundant degrees of freedom but also those with joint limits. Although the workspace problem has important applications in a variety of fields such as computer-aided design, ergonomic studies, and robotics, the problem's computational complexity has never been analyzed. In addition, previous techniques suffer from one or more of the following drawbacks: high computational cost, computing 2D workspace cross sections, dealing with manipulators that have specialized geometry, or sensitivity to geometrical and numerical errors or approximations. We analyze the computational complexity of the problem and prove that it is NP-hard. Then, we decompose it into three major subproblems: workspace point generation, visualization, and criteria selection. We describe and compare different techniques for computing workspace points: direct kinematics based algorithms, nonlinear programming based algorithms, and force application based algorithms. Each class of these algorithms has advantages and disadvantages, and none of them supersedes the others in all applications. Instead of debating the merits of these algorithms, we integrate them into ``Hybrid algorithms'' that are capable of generating workspace points efficiently. The visualization module can be built by either surface-based or volume-based algorithms. Each class of these algorithms is more suitable than the others for certain applications. The criteria selection module interacts with the user and tailors the most appropriate techniques, from the workspace point generation and the visualization modules, based on the application requirements.

MS-CIS-91-57 (GRASP LAB 273)

Communicating Shared Resources: A Model For Distributed Real-Time Systems

Richard Gerber

The timing behavior of a real-time system depends not only on delays due to process synchronization, but also on the availability of shared resources. Most current real-time models capture delays due to process synchronization; however, they abstract out resource-specific details by assuming idealistic operating environments. On the other hand, scheduling and resource allocation algorithms used for real-time systems ignore the effect of process synchronization except for simple precedence relations between processes. To bridge the gap between these two disciplines, we have developed a methodology called Communicating Shared Resources, or CSR. In this dissertation we describe our approach to the specification and verification of real-time systems. Application processes are specified in the CSR application language, which includes language constructs that are essential in real-time settings, such as timeouts, deadlines, periodic processes, interrupts and exception-handling. Then, a configuration schema is used to map the processes to system resources, and to specify the physical communication links between them. To analyze and execute the entire system, we automatically translate the result of the mapping into the CCSR process algebra. CCSR characterizes CSR's resource-based computation model by a priority-sensitive, operational semantics. To do this, we have formulated a natural treatment of preemption, which is based not only on priority, but also on resource utilization and inter-resource synchronization. The preemption ordering leads to a compositional proof system, which allows the syntactic manipulation of CCSR terms. Using this proof system, we perform the algebraic verification of our original real-time system.

MS-CIS-91-58 (LOGIC & COMPUTATION 35)

Data Abstraction and General Recursion

Ramesh Subrahmanyam

Existing approaches to semantics of algebraically specified data types such as Initial Algebra Semantics and Final Algebra Semantics do not take into account the possibility of general recursion and hence non-termination in the ambient programming language. Any technical development of this problem needs to be in the setting of domain theory. In this paper we present extensions of initial and final algebra semantics to algebras with an underlying domain structure. Four possibilities for specification methodologies arise: two each in the Initial and Final algebra paradigms. We demonstrate that the initial/final objects (as appropriate) exist in all four situations. The final part of the paper attempts to explicate the notion of abstractness of ADT's by defining a notion of operational semantics for ADT's, and then studying the relationship between the various algebraic-semantics proposed and the operational semantics.

MS-CIS-91-59 (LOGIC & COMPUTATION 36)

Bounded Linear Logic

Jean-Yves Girard, Andre Scedrov, Philip J. Scott

A typed, modular paradigm for polynomial time computation is proposed.

MS-CIS-91-60

Equational and Rule-Based Programming: Visualization, Reliability, and Knowledge Base Generation

Jee-In Kim

This document describes developing an environment for effective use of functional/equational programs and rule-based expert systems. There are significant advantages in using these paradigms for reliability, parallelism, and accumulation of expertise in knowledge bases. The environment will make it easier to understand and use these paradigms, construct more reliable systems, and automatically enrich rule-based knowledge bases with the expertise. It will consist of the following components: (1) Visualization: for composing systems using a graphical interface and for understanding of algorithms. (2) Consistency Checking: for an equational and a rule-based languages in accordance with the semantics of the languages. (3) Knowledge Base Generation and Testing: a translator that extracts expertise from existing programs and accumulates it as rules in knowledge bases; the rules are tested to enhance reliability. (4) Verification: interactive heterogeneous reasoning that consists of equational reasoning based on visual and textual information. These tools will be integrated in the proposed environment. The environment will greatly reduce the costs and increase the reliability of functional/equational and rule-based systems.

MS-CIS-91-61 (LOGIC & COMPUTATION 37)

Forms of Semantic Specification

Carl A. Gunter

The way to specify a programming language has been a topic of heated debate for some decades and at present there is no consensus on how this is best done. Real languages are almost always specified informally; nevertheless, precision is often enough lacking that more formal approaches could benefit both programmers and language implementors. My purpose is to look at a few of these formal approaches in hope of establishing some distinctions or at least stirring some discussion.

MS-CIS-91-62 (GRASP LAB 274)

Efficient Simulation of Large-Scale Loss Networks

Mark Prindiville, Sanguthevar Rajasekaran, Keith W. Ross

Recently Rajasekaran and Ross [1] presented an algorithm that takes an expected 0(1) time to generate a nonuniform discrete random variate. In this paper we discuss how this algorithm can be employed in the efficient simulation of large-scale telephone networks. In a simulation based upon a standard event-list approach, the generation of a new event in the systems take 0(log n) time. With this new algorithm, event generation becomes an 0(1) process, and simulation times for large networks can be reduced.

MS-CIS-91-63 (LINC LAB 206)

Surface Structure, Intonation, and ``Focus''

Mark Steedman

The paper briefly reviews a theory of intonational prosody and its relation syntax, and to certain oppositions of discourse meaning that have variously been called ``topic and comment'', ``theme and rheme'', ``given and new'', or ``presupposition and focus.'' The theory, which is based on Combinatory Categorial Grammar, is presented in full elsewhere. The present paper examines its implications for the semantics of ``focus''.

MS-CIS-91-64 (LOGIC & COMPUTATION 38)

Fully Abstract Translations Between Functional Languages

Jon G. Riecke

We examine the problem of finding fully abstract translations between programming languages, i.e., translations that preserve code equivalence and nonequivalence. We present three examples of fully abstract translations: one from call-by-value to lazy PCF, one from call-by-name to call-by-value PCF, and one from lazy to call-by-value PCF. The translations yield upper and lower bounds on decision procedures for proving equivalences of code. We finally define a notion of ``functional translation'' that captures the essence of the proofs of full abstraction, and show that some languages cannot be translated into others.

MS-CIS-91-65 (LOGIC & COMPUTATION 39)

Modeling and Merging Database Schemas

Anthony S. Kosky

MS-CIS-91-66 (LINC LAB 207)

Computational Accounts of Music Understanding

Daniel Hardt

We examine various computational accounts of aspects of music understanding. These accounts involve programs which can notate melodies based on pitch and duration information. It is argued that this task involves significant musical intelligence. In particular, it requires an understanding of basic metric and harmonic relations implicit in the melody. We deal only with single-voice, tonal melodies. While the task is a limited one, and the programs give only partial solutions to this task, we argue that this represents a first step towards a computational realization of significant aspects of musical intelligence.

MS-CIS-91-67 (LINC LAB 208)

Towards Goal-Directed Diagnosis (Preliminary Report)

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

Recent research has abstracted diagnosis away from the activity needed to acquire information and to act on diagnosed disorders. In some problem domains, however, such abstraction is counter-productive and does not reflect real-life practice, which integrates diagnostic and therapeutic activity. Trauma management is a case in point. Here, we discuss a formalization of the integrated approach taken in TraumAID, a system we have developed to serve as an artificial aide to residents and physicians dealing with multiple trauma. Among other things, the active pursuit of information raises the question of what is and what is not worth pursuing. In TraumAID 2.0, we take the view that the process of diagnosis should continue only as long as it is likely to make a difference to future actions. That view is formalized in the goal-directed diagnostic paradigm (GDD). Unlike other diagnostic paradigms, goal-directed diagnosis is first and foremost concerned with setting goals based on its conclusions. It regards the traditional construction of an explanation for the faulty behavior as secondary.

In order to explicitly represent goal-directedness, the diagnostic process is viewed as search in a space of attitude-beliefs. From this, we derive a high-level algorithm that produces appropriate requests for action while searching for an explanation. A complete explanation, however, is not the criterion for terminating action. Such a criterion, we argue, is better treated in terms of goal-means tradeoffs. TraumAID's architecture, in so far as it embodies this goal-directed approach, assigns to a complementary planner the resolution of such tradeoffs.

MS-CIS-91-68 (GRASP LAB 275)

Contact Operations Using An Instrumented Compliant Wrist

Thomas Lindsay, Janez Funda, Richard Paul

Teleprogramming was developed as a solution to problems of teleoperation systems with significant time delays [5]. In teleprogramming, the human operator interacts in real time with a graphical model of the remote site, which provides for real time visual and force feedback. The master system automatically generates symbolic commands based on the motions of the master arm and the manipulator/model interactions, given predefined criteria of what types of motions are to be expected. These commands are then sent via a communication link, which may delay the signals, to the remote site. Based upon a remote world model, predefined and possibly refined as more information is obtained, the slave carries out commanded operations in the remote world and decides whether each step has been executed correctly. Contact operations involve the remote site manipulator interacting with the environment, including planned collisions, and motion with contact with the environment. A hybrid position/force control scheme using a instrumented compliant wrist has been demonstrated to be very effective for these types of operations. In particular, switching between position and force modes (when contacting a surface, for example) does not present problems for the system. A brief introduction of teleprogramming and contact operations is presented, including a model of sliding motions and early experimental results. Problems with these early experiments are presented, and solutions discussed. The criteria for an object to slide rather than tip over are presented, relating to the geometry of the object and the applied forces. Finally, methods are presented to match the experimental results to a simple model, to help the remote manipulator to quickly and robustly sense collisions.

MS-CIS-91-69

Investigating Logics For Feasible Computation

Anuj Dawar

MS-CIS-91-70 (GRASP LAB 276)

Dynamics Of Rigid Bodies Undergoing Multiple Frictional Contacts

Yin-Tien Wang, Vijay Kumar, Jacob Abel

There are several applications in robotics and manufacturing in which nominally rigid objects are subject to multiple frictional contacts with other objects. In most previous work, rigid body models have been used to analyze such systems. There are two fundamental problems with such an approach. Firstly, the use of frictional laws, such as Coulomb's law, introduce inconsistencies and ambiguities when used in conjunction with the principles of rigid body dynamics. Secondly, hypotheses traditionally used to model frictional impacts can lead to solutions which violate principles of energy conservation. In this paper these problems are explained with the help of examples. A new approach to the simulation of mechanical systems with multiple, frictional constraints is proposed which is free of inconsistencies.

MS-CIS-91-71

Parallel Algorithms For Depth-First Search

Jon Freeman

In this paper we examine parallel algorithms for performing a depth-first search (DFS) of a directed or undirected graph in sub-linear time. this subject is interesting in part because DFS seemed at first to be an inherently sequential process, and for a long time many researcher believed that no such algorithms existed. We survey three seminal papers on the subject. The first one proves that a special case of DFS is (in all likelihood) inherently sequential; the second shows that DFS for planar undirected graphs is in NC; and the third shows that DFS for general undirected graphs is in RNC. We also discuss randomnized algorithms, P-completeness and matching, three topics that a re essential for understanding and appreciating the results in these papers

MS-CIS-91-72 (LINC LAB 209)

Abstract Syntax and Logic Programming

Dale Miller

When writing programs to manipulate structures such as algebraic expressions, logical formulas, proofs, and programs, it is highly desirable to take the linear, human-oriented, concrete syntax of these structures and parse them into a more computation-oriented syntax. For a wide variety of manipulations, concrete syntax contains too much useless information (e.g., keywords and white space) while important information is not explicitly represented (e.g., function-argument relations and the scope of operators). In parse trees, much of the semantically useless information is removed while other relationships, such as between function and argument, are made more explicit. Unfortunately, parse trees do not adequately address important notions of object-level syntax, such as bound and free object-variables, scopes, alphabetic changes of bound variables, and object-level substitution. I will argue here that the abstract syntax of such objects should be organized around a-equivalence classes ofl -terms instead of parse trees. Incorporating this notion of abstract syntax into programming languages is an interesting challenge. This paper briefly describes a logic programming language is presented to illustrate its approach to handling object-level syntax. A model theoretic semantics for this logic programming language is also presented.

MS-CIS-91-73 (GRASP LAB 277)

Descriptive Complexity Approaches To Inductive Inference: A Critical Review

Kevin Atteson

We present a general introduction and critical review of descriptive complexity approaches to inductive inference, that is, the problem of determining a model from observation. Descriptive complexity, as defined by Kolmogogov, Chaitin and Solomonoff is presented as a generalization of Shannons entropy. Its relations with randomness is discussed and examples are presented. the practicability of descriptive complexity theory is discussed. We then present Rissanen's MDL principle as a restriction of descriptive complexity. We demonstrate the effectiveness of MDL by applying it it AR processes. Lastly, we present and discuss LeClerc's application of MDL to image segmentation.

MS-CIS-91-74 (LOGIC & COMPUTATION 40)

Constructive Logics Part I: A Tutorial On Proof Systems and Typed l-Calculi

Jean Gallier

The purpose of this paper is to give an exposition of material dealing with constructive logic, typed l-calculi, and linear logic. The emergence in the past ten years of a coherent field of research often named ``logic and computation'' has had two major (and related) effects: firstly, it has rocked vigorously the world of mathematical logic; secondly, it has created a new computer science discipline, which spans from what is traditionally called theory of computation, to programming language design. Remarkably, this new body of work relies heavily on some ``old'' concepts found in mathematical logic, like natural deduction, sequent calculus, and l-calculus (but often viewed in a different light), and also on some newer concepts. Thus, it may be quite a challenge to become initiated to this new body of work (but the situation is improving, there are now some excellent texts on this subject matter). This paper attempts to provide a coherent and hopefully ``gentle'' initiation to this new body of work. We have attempted to cover the basic material on natural deduction, sequent calculus, and typed l -calculus, but also to provide an introduction to Girard's linear logic, one of the most exciting developments in logic these past five years. The first part of these notes gives an exposition of background material (with the exception of the Girard-translation of classical logic into intuitionistic logic, which is new). The second part is devoted to linear logic and proof nets.

MS-CIS-91-75 (LOGIC & COMPUTATION 41)

Constructive Logics Part II: Linear Logic and Proof Nets

Jean Gallier

The purpose of this paper is to give an exposition of material dealing with constructive logics, typed l-calculi, and linear logic. The first part of this paper gives an exposition of background material (with the exception of the Girard-translation of classical logic into intuitionistic logic, which is new). This second part is devoted to linear logic and proof nets. Particular attention is given to the algebraic semantics (in Girard's terminology, phase semantics) of linear logic. We show how phase spaces arise as an instance of a Galois connection. We also give a direct proof of the correctness of the Danos-Regnier criterion for proof nets. This proof is based on a purely graph-theoretic decomposition lemma. As a corollary, we give an O(n²)-time algorithm for testing whether a proof net is correct. Although the existence of such an algorithm has been announced by Girard, our algorithm appears to be original.

MS-CIS-91-76 (LOGIC & COMPUTATION 42)

Unification Procedures In Automated Deduction Methods Based On Matings: A Survey

Jean Gallier

Unification procedures arising in methods for automated theorem proving based on matings are surveyed. We begin by reviewing some fundamentals of automated deduction, including the Skolem form and the Skolem-Herbrand-Godel theorem. Next, the method of matings for first-order languages without equality due to Andrews and Bibel is presented. Standard unification is described in terms of transformations on systems (following the approach of Martelli and Montanari, anticipated by Herbrand). Some fast unification algorithms are also sketched, in particular, a unification closure algorithm inspired by Paterson and Wegman's method. The method of matings is then extended to languages with equality. This extention leads naturally to a generalization of standard unification called rigid E-unification (due to Gallier, Narendran, Plaisted, and Snyder). The main properties