MS-CIS-92-01 (GRASP LAB 298)

Teleprogramming: Remote Site Research Issues: (Dissertation Proposal)

Thomas Lindsay

This document proposes the development of the remote site workcell for teleoperation with significant communication delays (on the order of one to 20 seconds). In these situations, direct teleoperation becomes difficult to impossible due to the delays in visual and force feedback. Teleprogramming has been developed in order to overcome this problem. 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 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 models, 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.

The remote site receives commands sent via the delayed communication link. These commands must be parsed and translated into the local robot control language, which includes insertion of dynamic parameters that are not generated the master system. The commands are then executed by the hybrid position/force controller, and the resulting motions monitored for errors.

This proposal addresses the following remote site issues: low level manipulator control using an instrumented compliant wrist for sensory feedback, higher level command execution implementing dynamic parameters, and remote manipulator tool usage and control.

MS-CIS-92-02 (GRAPHICS LAB 46)

Curved Path Walking

Hyeongseok Ko, Norman I. Badler

Research on biped locomotion has focused on sagittal plane walking in which the stepping path is a straight line. Because a walking path is often curved in a three dimensional environment, a 3D locomotion subsystem is required to provide general walking animation. In building a 3D locomotion subsystem, we tried to utilize pre-existing straight path (2D) systems. The movement of the center of the body is important in determining the amount of banking and turning. The center site is defined to be the midpoint between the two hip joints. An algorithm to obtain the center site trajectory that realizes the given curved walking path is presented. From the position and orientation of the center site, we compute stance and swing leg configuration as well as the upper body configuration, based on the underlying 2D system.

MS-CIS-92-03 (LOGIC & COMPUTATION 46)

Statman's 1-Section Theorem

Jon G. Riecke

Statman's 1-Section Theorem [17] is an important but little-known result in the model theory of the simply-typed l-calculus. The 1-Section Theorem states a necessary and sufficient condition on models of the simply-typed l-calculus for determining whether bh-equational reasoning is complete for proving equations that hold in a model. We review the statement of the theorem, give a detailed proof, and discuss its significance.

MS-CIS-92-04 (GRASP LAB 299)

Interactive Image Display For The X Window System

John Bradley

This report describes the program XV, which is an interactive color image display program for workstations and terminals running the X Window System. The program displays images saved in a variety of popular formats. It lets you arbitrarily stretch or compress the size of the image, rotate the image in 90-degree steps, flip the image around horizontal or vertical axes, crop off unwanted portions of the image, and measure pixel values and coordinates. Modified images can be saved in a variety of formats, or sent to a PostScript printer.

The program also features extensive color manipulation functions, including a colormap editor, hue remapping, brightness and contrast adjustment, and individual mapping functions for the Red, Green, and Blue video channels, to correct for device-dependent non-linear color response.

MS-CIS-92-05 (LINC LAB 212)

Multiple Instantiation Of Predicates In A Connectionist Rule-Based Reasoner

D.R. Mani, Lokendra Shastri

Shastri and Ajjanagadde have described a neurally plausible system for knowledge representation and reasoning that can represent systematic knowledge involving n-ary predicates and variables, and perform a broad class of reasoning with extreme efficiency. The system maintains and propagates variable bindings using temporally synchronous --- i.e., in-phase --- firing of appropriate nodes. This paper extends the reasoning system to incorporate multiple instantiation of predicates, so that any predicate can now be instantiated with up to k dynamic facts, k being a system constant. The ability to accommodate multiple instantiations of a predicate allows the system to handle a much broader class of rules; the system can even handle limited recursion (up to k levels). Though the time and space requirements increase by a constant factor, the extended system can still answer queries in time proportional to the length of the shortest derivation of the query and is independent of the size of the knowledge base.

MS-CIS-92-06 (GRAPHICS LAB 47)

Generating Human Motion By Symbolic Reasoning

Moon Ryul Jung, Norman I. Badler

This paper describes work on applying AI planning methods to generate human body motion for the purpose of animation. It is based on the fact that although we do not know how the body actually controls massively redundant degrees of freedom of its joints and moves in given situations, the appropriateness of specific behavior for particular conditions can be axiomatized at a gross level using commonsensical observations. Given the motion axioms (rules), the task of the planner is to find a discrete sequence of intermediate postures of the body via goal reduction reasoning based on the rules along with a procedure to discover specific collision-avoidance constraints, such that any two consecutive postures are related via primitive motions of the feet, the pelvis, the torso, the head, the hands, or other body parts. Our planner also takes account of the fact that body motions are continuous by taking advantage of execution-time feedback. Planning decisions are made in the task space where our elementary spatial intuition is preserved as far as possible, only dropping down to a joint space formulation typical in robot motion planning when absolutely necessary. We claim that our work is the first serious attempt to use an AI planning paradigm for animation of human body motion.

MS-CIS-92-07 (LINC LAB 213)

Goals and Actions In Natural Language Instructions (Dissertation Proposal)

Barbara Di Eugenio

Human agents are extremely flexible in dealing with Natural Language instructions: they are able both to adapt the plan they are developing to the input instructions, and vice versa, to adapt the input instructions to the plan they are developing. Borrowing the term from [Lewis 79], I call this two-way adaptation process accommodation.

In this proposal, I first define accommodation in the context of processing instructions. I then provide evidence for the particular inferences I advocate, and for the further claim that such inferences are directed by the goal to achieve which a certain action is performed. The evidence I provide comes from my analysis of naturally occurring instructions, and in particular of purpose clauses and of negative imperatives.

Finally, I propose a computational model of instructions able to support accommodation inferences. Such model is composed of: a speaker / hearer model of imperatives, based on the one presented in [Cohen and Levesque 90]; an action representation formalism based on a hybrid system, a' la KRYPTON [Brachman et al. 83], whose primitives are those proposed in [Jackendoff 90]; and inference mechanisms that contribute to building the structure of the intentions that the agent develops while interpreting instructions.

MS-CIS-92-08 (DISTRIBUTED SYSTEMS LAB 10)

New Algorithms For Capacity Allocation and Scheduling Of Multiplexed Variable Bit Rate Video Sources

Amarnath Mukherjee, Jaffar Rehman

This study presents simple and accurate heuristics for determining the equivalent bandwidth for multiplexed variable bit rate (VBR) video sources. The results are based on empirical studies of measurement data of various classes of VBR video sources. They are also validated through extensive simulation. The principal result is that the equivalent bandwidth per source for n independent and identically distributed VBR video sources may be approximated by a hyperbolic function of the form: a coth ^-1n + b where a and b are independent of n. Further, assuming Î is the acceptable loss tolerance, statistical regression shows that b is a linear function of mean and log ( Î ), while a is a polynomial in log( Î ).

The capacity assignment problem is further augmented with a scheduling algorithm that is an extension of the Virtual Clock Algorithm. The new algorithm belongs to a class of algorithms which we refer to as Generalized Virtual Clock (GVC) algorithms. The particular GVC algorithm investigated in this paper estimates the instantaneous rate of transmission of each source, and uses the estimate instead of the static average rates, for prioritizing packets. In so doing, it attempts to synchronize the switch scheduling rates and the packet arrival rates of each source, and improves upon the spatial loss distribution characteristics of Virtual Clock. The combined allocation and scheduling algorithms are proposed as means for guaranteeing Quality of Service in high speed networks.

MS-CIS-92-09 (GRAPHICS LAB 48)

Collision-Free Path and Motion Planning For Anthropometric Figures

Wallace Ching, Norman I. Badler

This paper describes a collision free path planning and animation system for anthropometric figures. It can also take into consideration the strength limit of human figures and plan the motion accordingly. The algorithm breaks down the degrees of freedom of the figure into Cspace groups and computes the free motion for each of these groups in a sequential fashion. It traverses the tree in a depth first order to compute the motion for all the branches. A special playback routine is then used to traverse the tree in a reverse order to playback the final motion. Strength value measures are incorporated directly into the searching function so that path computed will obey strength availability criteria. The planner runs in linear time with respect to the total number of Cspace groups. The planner can interface with other simulation techniques to simulate complex human motions. We believe that the planner would find a path in most cases and is fast enough for practical use in a wide range of computer graphics applications.

MS-CIS-92-10 (GRAPHICS LAB 49)

The Reality of Virtual Environments WPE II Paper

Rebecca T. Mercuri

Recent advances in computer technology have made it now possible to create and display three-dimensional virtual environments for real-time exploration and interaction by a user. This paper surveys some of the research done in this field at such places as: NASA's Ames Research Center, MIT's Media Laboratory, The University of North Carolina at Chapel Hill, and the University of New Brunswick. Limitations to the "reality" of these simulations will be examined, focusing on input and output devices, computational complexity, as well as tactile and visual feedback.

MS-CIS-92-11 (GRASP LAB 300)

Superquadric Library, User Manual and Utility Programs

Luca Bogoni

Superquadrics are a family of parametric shapes that have been used as primitives for shape representation in computer vision and computer graphics. They can be used for modeling tapering and bending deformations and are recovered efficiently by a stable numerical procedure.

This document introduces the superquadric library, SQ_lib , developed at the GRASP Lab at the University of Pennsylvania.

The manual is organized into three parts. The first part provides the reader with a description of superquadrics models and deformations that can be performed. Furthermore, it introduces the coordinate systems conventions which are used in the library.

The second part presents some examples of applications on how one can use the functions defined in the library. It also lists utility programs which have been developed while conducting research. They provide a good source of examples for the application of the library.

Finally, the last part describes the datatypes and each of the functions which are supported in the library. The library itself is organized in two sets Fundamental and Auxiliary functions. A quick reference to all the functions and an index is provided.

Some of the functions and examples supplied perform data preprocessing and are connected to the PM image description also available from the GRASP Lab. These functions are provided in isolation from the remaining body of the library and can easily be excluded in the actual compilation of the library. Furthermore, routines for the visualization of the data, using X11, are also provided.

MS-CIS-92-12 (GRASP LAB 301)

Robotic Exploration Of Surfaces and Its Application To Legged Locomotion

Pramath Raj Sinha

Material properties like penetrability, compliance, and surface roughness are important in the characterization of the environment. While concentrating on issues of geometry and shape, researchers in perceptual robotics, until recently, have not quite addressed the issue of the extraction of material properties from the environment. the goal of this research is to design and implement a robotic system that will actively explore a surface to extract its material characteristics. Further, the relevance of material properties in the legged locomotion of robots is also recognized and our research objectives are extended towards building a robotic system for exploration such that it actively perceives material properties during the process of legged locomotion. The chosen approach to the design and implementation of such a robotic system is to first select an appropriate environment model and then to design exploratory procedures salient to each attribute of interest. These exploratory procedures are then implemented through an experimental setup and the results show that material properties can be reliably measured. The design, implementation, and results of a framework for surface exploration to recover material properties are presented.

Further, the exploratory procedures for exploration are integrated into an active perceptual scheme for legged locomotion. The perceptual scheme is designed around creating the ability for the robot to sense variations in terrain properties while it is walking, so that is may be able to avoid sinking, slipping, and falling due to unexpected changes in the terrain properties, and make suitable changes in its foot forces to continue locomotion. Finite element simulations of the foot--terrain interaction are used to justify some of the strategies used in this active perceptula scheme. the active perceptual scheme is implemented by simulating a leg-ankle-foot system with a PUMA arm-compliant wrist-foot system and an accelerometer mounted on the foot to detect slip. Details of implementation and experimental results are presented.

MS-CIS-92-13 (GRASP LAB 301)

Understanding Of Surface Reflections In Computer Vision By Color and Multiple Views (Dissertation)

Sang Wook Lee

This thesis addresses problems and presents models for the detection and separation of specularities from Lambertian reflections using color and multiple images with different viewing direction. From the models, three algorithms are proposed and experimental results are presented. The first algorithms uses only color information for the separation of diffuse as well as sharp specularities and inter-reflections from Lambertian reflections through image segmentation. A computational model based on the dichromatic model is presented for interpretation of various surface reflections in a spectral space with three orthogonal basis functions. The established model is used for arranging color data for segmentation and separation. Applicable objects and illumination for the algorithm are limited to uniformly colored dielectrics under singly colored scene illumination. Use of multiple views for understanding reflection properties is proposed with the second and the third algorithms called spectral differencing and view sampling, respectively. Both use multiple views in different viewing directions, and are based on the Lambertian consistency that image irradiance from Lambertian reflection does not vary depending on viewing directions, while image irradiance from specular reflection or from the mixture of Lambertian and specular reflections can change. Spectral differencing is a detection algorithm that detects specularities by color difference between two images without relying on any geometric feature correspondence. The object and illumination domain for detection is extended to nonuniformly colored dielectrics and metals under multiply colored scene illumination. With densely sampled views in wide angle and with known viewing directions, the view sampling algorithm reconstructs object structure as well as separates specularities from Lambertian reflections. The view sampling algorithm does not require color information, and is applicable to dielectrics and metals. Experimental results conform to the models and algorithms within the limitations discussed.

MS-CIS-92-15 (GRASP LAB 302)

Grasp Laboratory News, Volume 8, Number 1

Faculty & Graduate Students

The GRASP laboratory has undertaken a research project to develop a multiagent robotic system for intelligent material handling. This article outlines the organization of the system. The goal of this research project is to investigate the architecture, coordination, and monitoring of a {\em multiagent robotic system} employed in the task of material handling, in an unstructured, indoor environment. In this research, manipulators, observers, vehicles, sensors, and human operators(s) are considered to be agents. Alternatively, an agent can be a general-purpose agent (for example, a six degree of freedom manipulator on a mobile platform and visual, force, touch and position sensors). Possible applications for such a system includes handling of waste and hazardous materials, decontamination of nuclear plants, and interfacing between special purpose material handling devices in warehouse. The fundamental research problems that are being studied are organization, or the decomposition of the task into subtasks and configuring the multiple agents with appropriate human interaction, exploration, or the process of exploring geometric, material and other properties about the environment and other agents, and coordination, or the dynamic control of multiple agents for manipulation and transportation of objects to a desired destination.

MS-CIS-92-16 (GRASP LAB 303)

Simulation Of Mechanical Systems With Multiple Frictional Contacts

Yin-Tien Wang, Vijay Kumar

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-92-17 (LOGIC & COMPUTATION 46)

Structural Recursion As A Query Language

Val-Breazu-Tannen (University of Pennsylvania), Peter Buneman (University of Pennsylvania), Shamim Naqvi (BELLCORE)

We propose a programming paradigm that tries to get close to both the semantic simplicity of relational algebra, and the expressive power of unrestricted programming languages. Its main computational engine is structural recursion on sets. All programming is done within a ``nicely'' typed lambda calculus, as in Machiavelli [OBB89]. A guiding principle is that how queries are implemented is as important as whether they can be implemented. As in relational algebra, the meaning of any relation transformer is guaranteed to be a total map taking finite relations to finite relations. A naturally restricted class of programs written with structural recursion has precisely the expressive power of the relational algebra. The same programming paradigm scales up, yielding query languages for the complex-object model [AB89]. Beyond that, there are, for example, efficient programs for transitive closure and we are also able to write programs that move out of sets, and then perhaps back to sets, as long as we stay within a (quite flexible) type system. The uniform paradigm of the language suggests positive expectations for the optimization problem. In fact, structural recursion yields finer grain programming therefore we expect that lower-level, and therefore better optimizations will be feasible.

MS-CIS-92-18 (GRASP LAB 304)

Coordinating Locomotion and Manipulation Of A Mobile Manipulator

Yoshio Yamamoto, Xiaoping Yun

A mobile manipulator in this study is a manipulator mounted on a mobile platform. Assuming the end point of the manipulator is guided, e.g., by a human operator to follow an arbitrary trajectory, it is desirable that the mobile platform is able to move as to position the manipulator in certain preferred configurations. Since the motion of the manipulator is unknown a priori, the platform has to use the measured joint position information of the manipulator for motion planning. This paper presents a planning and control algorithm for the platform so that the manipulator is always positioned at the preferred configurations measured by its manipulability. Simulation results are presented to illustrate the efficacy of the algorithm. The use of the resulting algorithm in a number of applications is also discussed.

MS-CIS-92-19 (GRASP LAB 305)

Multi-Arm Manipulation Of Large Objects With Rolling Contacts (Dissertation Proposal)

Eric D. Paljug

We investigate the task of manipulating large objects relative to the size of the robot. In general, this task requires the use of more than one manipulator. The proposed approach is to use two robot arms, and to permit the robots to use any link surface for manipulation. Neither robot arm has a fixed grasp of the object. Its surface merely contacts the object surface. These contact points are capable of rolling, sliding and separation. The analysis begins by developing the equations that govern the system. Rolling at the contact points is included in the system model. Contact separation is avoid by enforcing the unilateral constraints that each arm must push at the contact point. Sliding is avoided by constraining the applied force to fall within the contact friction cone. A control algorithm is developed by employing nonlinear feedback obtained by applying techniques from differential geometry. The controller dynamically regulates force and motion simultaneously. A motion and force planner is also developed which incorporates the unilateral constraints into the system. The planner specifies a rolling motion for each contact which improves the system's ability to avoid slipping by repositioning the contact points such that forces are applied along the surface normals. The rolling motion is calculated based on the object dynamics and the desired critical contact force. Extensions to the theory are investigated by relaxing certain key assumptions. Simulations and experiments of the theoretical results are proposed to investigate the issues of practical implementation.

MS-CIS-92-20 (GRASP LAB 306)

Proving Properties of Real-Time Distributed Systems: A Comparison of Three Approaches

Insup Lee

Three formal methods for specifying properties of real-time systems are reviewed and used in a common example. Two of them offer a graphical representation and the third is an algebraic language. The example is that of an automatic railroad system with sensors to detect the train position and controls for the gate mechanism. Associated with each formalism is a proof methodology which is described and used to prove a safety property about the example. A comparison is made between the three formalisms according to various criteria including the expressiveness, readability, maintainability of the language, support for real-time concepts, method for expressing properties and proof mechanisms.

MS-CIS-92-21 (LINC LAB 216)

Ellipsis and Discourse (Dissertation Proposal)

Daniel Hardt

MS-CIS-92-22 (LINC LAB 217)

CLiFF Notes: Research In Natural Natural Processing at the University of Pennsylvania

Facutly & Graduate Students

The computational linguistics feedback forum (CLiFF) is a group of students and faculty who gather once a week to discuss the member's current research. As the work ``feedback'' suggest, the group's purpose is the sharing of ideas. The group also promotes interdiscipinary contacts between researchers who share an interest in Cognitive Science.

There is no single theme describing the research in Natural Language Processing at Penn. There is work done in CCG, Tree adjoining grammars, intonation, statistical methods, plan inference, instruction understanding, incremental interpretation, language acquisition, syntactic parsing, causal reasoning, free word order languages, and many other areas. With this in mind, rather than trying to summarize the varied work currently underway here at Penn, we suggest reading the following abstracts to see how the students and faculty themselves describe their work. Their abstract illustrate the diversity of interest amount the researchers, explain the areas of common interest, and describe some very interesting work in Cognitive Science.

This report is a collection of abstracts for both faculty and graduate students in Computer Science, Psychology and Linguistics. We pride ourselves on the close working relations between these groups, as we believe that the communication among the different departments and the ongoing inter-departmental research not only improves the quality of our work, but makes much of that work possible.

MS-CIS-92-23 (LINC LAB 218)

Progressive Horizon Planning--Planning Exploratory-Corrective Behavior

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

Much planning research assumes that the goals for which one plans are known in advance. That is not true of trauma management, which involves both a search for relevant goals and reasoning about how to achieve them.

TraumAID is a consultation system for the diagnosis and treatment of multiple trauma. It has been under development jointly at the University of Pennsylvania and the Medical College of Pennsylvania for the past eight years. TraumAID integrates diagnostic reasoning, planning and action. Its reasoner identifies diagnostic and therapeutic goals appropriate to the physician's knowledge of the patient's state, while its planner advises on beneficial actions to next perform. The physician's lack of complete knowledge of the situation and the time limitations of emergency medicine constrain the ability of any planner to identify what would be the best thing to do. Nevertheless, TraumAID's Progressive Horizon Planner has been designed to create a plan for patient care that is in keeping with the standards of managing trauma.

MS-CIS-92-24 (LINC LAB 219)

Character Recognition Using A Modular Spatiotemporal Connectionist Model

Thomas Fontaine, Lokendra Shastri

We describe a connectionist model for recognizing handprinted characters. Instead of treating the input as a static signal, the image is scanned over time and converted into a time-varying signal. The temporalized image is processed by a spatiotemporal connectionist network suitable for dealing with time-varying signals. The resulting system offers several attractive features, including shift-invariance and inherent retention of local spatial relationships along the temporalized axis, a reduction in the number of free parameters, and the ability to process images of arbitrary length.

connectionist networks were chosen as they offer learnability, rapid recognition, and attractive commercial possibilities. A modular and structured approach was taken in order to simplify network construction, optimization and analysis.

Results on the task of handprinted digit recognition are among the best report to date on a set of real-world ZIP code digit images, provided by the United States Postal Service. The system achieved a 99.1% recognition rate on the training set and a 96.0% recognition rate on the test set with no rejections. A 99.0% recognition rate on the test set was achieved when 14.6% of the images.

MS-CIS-92-25

Self-Annihilating Sentences: Saul Gorn's Compendium of Rarely Used Cliches

Saul Gorn

This report was originally issued January 1985. Due to the sudden and untimely loss of Dr. Saul Gorn, the department (CIS) has reissued this paper for it's 1992 series of reports.

MS-CIS-92-26 (GRASP LAB 307)

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

Robert Bruce King, II

Modern robotics applications are becoming more complex due to greater numbers of sensors and actuators. The control of such systems may require multiple processor to meet the computational demands and to support the physical distribution 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. Our research is the design and evaluation of a real-time kernel, called Timix V2, for distributed robotics applications.

Timix V2 provides threads with dynamic timing constraints, execution environments as basic units for resource allocation and memory management context, and events to signal message arrival, device interrupts, alarms, and exceptions. The salient features of Timix V2 are support for uniform scheduling and timely communication. Timix V2 uses the notion of consistent scheduling to uniformly schedule both application and kernel threads to guarantee that the applications' real-time constraints are met. All device interrupt handlers, except the periodic clock interrupt, are converted to threads that are scheduled like any other thread. Timix V2's port-based message passing primitives support real-time communication by allowing individual message priorities to be used to order messages on a queue and by propagating scheduling information from a message to the associated thread on message arrival.

The kernel has been implemented on a distributed test-bed and evaluated with respect to distributed real-time robotics applications.

MS-CIS-92-27 (GRASP LAB 308)

A Robotic System for Learning Visually-Driven Grasp Planning (Dissertation Proposal)

Marcos Salganicoff

We use findings in machine learning, developmental psychology, and neurophysiology to guide a robotic learning system's level of representation both for actions and for percepts. Visually-driven grasping is chosen as the experimental task since it has general applicability and it has been extensively researched from several perspectives. An implementation of a robotic system with a gripper, compliant instrumented wrist, arm and vision is used to test these ideas. Several sensorimotor primitives (vision segmentation and manipulatory reflexes) are implemented in this system and may be thought of as the ``innate'' perceptual and motor abilities of the system.

Applying empirical learning techniques to real situations brings up such important issues as observation sparsity in high-dimensional spaces, arbitrary underlying functional forms of the reinforcement distribution and robustness to noise in exemplars. The well-established technique of non-parametric projection pursuit regression (PPR) is used to accomplish reinforcement learning by searching for projections of high-dimensional data sets that capture task invariants.

We also pursue the following problem: how can we use human expertise and insight into grasping to train a system to select both appropriate hand preshapes and approaches for a wide variety of objects, and then have it verify and refine its skills through trial and error. To accomplish this learning we propose a new class of Density Adaptive reinforcement learning algorithms. These algorithms use statistical tests to identify possibly ``interesting'' regions of the attribute space in which the dynamics of the task change. They automatically concentrate the building of high resolution descriptions of the reinforcement in those areas, and build low resolution representations in regions that are either not populated in the given task or are highly uniform in outcome.

MS-CIS-92-28 (GRASP LAB 309)

Robust Location Estimation for MLR and Non-MLR Distributions (Dissertation Proposal)

Gerda L. Kamberova

We address the problem of minimax location parameter estimation under zero-one loss. Consider the location data model Z - q + V. We observe the random variable Z and based on our observations(s), we want to estimate the value of the parameterq, where we know a priori that | q| £ d. The random noise V has a CDF F, F is independent of q. The sampling distribution (the CDF of Z) is F (z -q). The distribution f may be known, or it may be unknown. In the latter case, there is a known class of distributions \cal F, to which F belongs. The locations data model is a starting point for considering more complex models, like Z = h(q) + V, where h is a nonlinear functions ofq, or more general Z = h(q + V). The minimax criterion with zero-one loss is suitable for modeling problems in which it is desirable to minimize the maximum probability of getting unacceptable errors. Using this approach, as a consequence, we obtain fixed size confidence intervals, for the parameter, with highest probability of coverage.

There is a substantial difference in treating MLR and non-MLR distributions. When the sampling distribution is MLR, we obtain globally minimax decision procedures. They are monotone nondecreasing, continuous functions with very simple structures. When the sampling distribution is non-MLR, these monotone procedures are minimax within the class of all monotone decision rules. but they are not necessarily globally minimax. We explore the structure on non-monotone equalizer rules for non-MLR sampling distributions. We also explore the structure of Bayes rules. We believe that understanding of the structure of both equalizer and Bayes rules is a necessary step towards the delineation of global minimax decision procedures.

When the underlying distribution F is imprecisely known we consider the robust minimax decision problems. We study different sets of distributions (uncertainty classes) to which the CDF F may belong.

We use our results to address problems in sensor fusion. Many tasks in active perception require that we be able to combine different information from a variety of sensors which relate to one or more features of the environment. Prior to combining these data, we must test our observations for consistency. We examine sensor fusion problems for linear location data models. Our goal is 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 which 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.

MS-CIS-92-29 (GRASP LAB 310)

Markov Random Field Models: A Bayesian Approach To Computer Vision Problems

Gerda L. Kamberova

The object of our study is the Bayesian approach in solving computer vision problems. We examine in particular: (i) applications of Markov random field (MRF) models to modeling spatial images; (ii) MRF based statistical methods for image restoration, segmentation, texture modeling and integration of different visual cues.

MS-CIS-92-30 (GRASP LAB 311)

Convergence of Stochastic Processes

Robert Mandelbaum

MS-CIS-92-31 (GRASP LAB 312)

Multivariate Data Fusion Based On Fixed-Geometry Confidence Sets

Gerda Kamberova, Ray McKendall, Max Mintz

MS-CIS-92-32 (LINC LAB 220)

Japanese Discourse and the Process of Centering

Marilyn Walker (University of Pennsylvania), Masayo Iida (Hewlett Packard Laboratories), Sharon Cote (University of Pennsylvania)

This paper has two aims: (1) to generalize a computational account of discourse processing called CENTERING and apply it to discourse processing in Japanese, and (2) to provide some insights on the effect of syntactic factors in Japanese on discourse interpretation. We argue that while discourse interpretation is an inferential process, the syntactic cues constrain this process, and demonstrate this argument with respect to the interpretation of ZEROS, unexpressed arguments of the verb, in Japanese. The syntactic cues in Japanese discourse that we investigate are the morphological markers for grammatical TOPIC, the post-position wa , as well as those for grammatical functions such as SUBJECT, ga OBJECT, o and OBJECT2, ni. In addition, we investigate the role of speakers' EMPATHY, which is the perspective from which an event is described. This is morphologically indicated through the use of verbal compounding, i.e. that auxiliary use of verbs such as kureta, kita. Our results are based on a survey of native speakers of their interpretation of short discourses, consisting of minimal pairs, varied by one of the above factors. We demonstrate that these syntactic cues do indeed affect the interpretation of ZEROS, but that having previously been the TOPIC and being realized as a ZERO also contribute to an entity being interpreted as the TOPIC. We propose a new notion of TOPIC AMBIGUITY, and show that CENTERING provides constraints on when a ZERO can be interpreted as the TOPIC.

MS-CIS-92-33 (LINC LAB 221)

Logic Programming In A Fragment Of Intuitionistic Linear Logic

Joshua S. Hodas, Dale Miller

When logic programming is based on the proof theory of intuitionistic logic, it is natural to allow implications in goals and the bodies of clauses. Attempting to prove a goal of the form D É G from the context (set of formulas) G leads to an attempt to prove the goal G in the extended context GÈ{D}. Thus during the bottom-up search for a cut-free proof contexts, represented as the left-hand side of intuitionistic sequents, grow as stacks. While such an intuitionistic notion of context provides for elegant specifications of many computations, contexts can be made more expressive and flexible if they are based on linear logic. After presenting two equivalent formulations of a fragment of linear logic, we show that the fragment has a goal-directed interpretation, thereby partially justifying calling it a logic programming language. Logic programs based on the intuitionistic theory of hereditary Harrop formulas can be modularly embedded into this linear logic setting. Programming 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. An interpreter for this logic programming language must address the problem of splitting context; that is, when attempting to prove a multiplicative conjunction (tensor), say G₁ Ä G₂, from the context D the latter must be split into disjoint contexts, D₁ and ]Delta₂for which G₁ follows from D ₁ and G₂ follows from D₂. Since there is an exponential number of such splits, it is important to delay the choice of a split as much as possible. A mechanism for the lazy splitting of contexts is presented based on viewing proof search as a process that takes a context, consumes part of it, and returns the rest (to be consumed elsewhere). In addition, we use collections of Kripke interpretations indexed by a commutative monoid to provide models for this logic programming language and show that logic programs admit a canonical model.

MS-CIS-92-34 (LINC LAB 222)

Conceptual Structures and CCG: Linking Theory and Incorporated Argument Adjuncts

Michael White

In Combinatory Categorial Grammar (CCG) [Steedman90,SteedmanLanguage91], semantic function-argument structures are compositionally produced through the course of a derivation. These structures identify, inter alia, which entities play the same roles in different events for expressions involving a wide range of coordinate constructs. This sameness of role (i.e. thematic) information is not identified, however, across cases of verbal diathesis. To handle these cases as well, the present paper demonstrates how to adapt the solution developed in Conceptual Semantics [Jackendoff90,Jackendoff91] to fit the CCG paradigm.

The essence of the approach is to redefine the Linking Theory component of Conceptual Semantics in terms of CCG categories, so that derivations yield conceptual structures representing the desired thematic information; in this way no changes are required on the CCG side. While this redefinition is largely straightforward, an interesting problem arises in the case of Conceptual Semantics' Incorporated Argument Adjuncts. In examining these, the paper shows that they cannot be treated as adjuncts in the CCG sense without introducing new machinery, nor without compromising the independence of the two theories. For this reason, the paper instead adopts the more traditional approach of treating them as oblique arguments.

MS-CIS-92-35 (GRASP LAB 313)

Control of Discrete Event Systems

Jana Koecká

Discrete Event Systems (DES) are a special type of dynamic systems. The ``state'' of these systems changes only at discrete instants of time and the term "event" is used to represent the occurrence of discontinuous changes (at possibly unknown intervals). Different Discrete Event Systems models are currently used for specification, verification, synthesis as well as for analysis and evaluation of different qualitative and quantitative properties of existing physical systems.

The main focus of this paper is the presentation of the automata and formal language model for DES introduced by Ramadge and Wonham in 1985. This model is suitable for the examination of some important control theoretic issues, such as controllability and observability from the qualitative point of view, and provides a good basis for modular synthesis of controllers. We will also discuss an Extended State Machine and Real-Time Temporal Logic model introduced by Ostroff and Wonham in [Ostroff-ESM87]. It incorporates an explicit notion of time and means for specification and verification of discrete event systems using a temporal logic approach. An attempt is made to compare this model of DES with other ones.

MS-CIS-92-36 (GRASP LAB 314)

Randomized Routing and Sorting On The Reconfigurable Mesh

Sanguthevar Rajasekaran, Theodore McKendall

In this paper we demonstrate the power of reconfiguration by presenting efficient randomized algorithms for both packet routing and sorting on a reconfigurable mesh connected computer (referred to simply as the mesh from hereon). The run times of these algorithms are better than the best achievable time bounds on a conventional mesh.

In particular, we show that permutation routing problem can be solved on a linear array of size n in [3/4]n steps, whereas n-1 is the best possible run time without reconfiguration. We also show that permutation routing on an n×n reconfigurable mesh can be done in time n+o(n). In contrast, 2n-2 is the diameter of a conventional mesh and hence routing and sorting will need at least 2n-2 steps on a conventional mesh. In addition we show that the problem of sorting can be solved in time n+o(n). All these time bounds hold with high probability. The bisection lower bound for both sorting and routing on the mesh is [n/2], and hence our algorithms have nearly optimal time bounds.

MS-CIS-92-37 (GRASP LAB 315)

An Active Approach To Functionality Characterization and Recognition

Luca Bogoni, Ruzena Bajcsy

In this paper we focus on understanding and defining a methodology for object description and recognition both in terms of its geometrical, material and functional specifications. We define functionality in an object as its applicability toward the achievement of a task. We emphasize and develop an interactive and performatory approach to functionality recovery. Furthermore, we introduce the distinction between Inherent, Intended and Imposed functionality.

By analyzing interaction and manipulation tasks as goal--oriented recognition processes we propose to identify and characterize functionalities of objects. This interaction is not only a means of verification of the hypothesized presence of functionality in objects but also a way to actively and purposively recognize the object.

In order to accomplish our goal, we introduce a formal model, based on Discrete Event Dynamic System Theory, to define a task for recovering and describing functionality. We extend the recovery process to an algebra of tasks. We describe how a more complex task can be composed from a set of primitive ones. This constructive approach allows a task to be built from simpler ones in an stepwise fashion.

Once the manipulatory task has been described in the formal model, it must be instantiated in a context. In such a context, the behavior of the system in which the interaction between a Manipulator, a Tool and a Target object must be observed. Thus, the description of tasks themselves provide must for means of addressing observability through different sensor modalities. For this purpose, we introduce the notion of Partial Observability of a task. This allows the description of a plant in which not all events and the time of their occurrence might be modelled and therefore predictable in advance.

MS-CIS-92-38 (GRASP LAB 316)

Robotic Exploration Of Material and Kinematic Properties Of Objects (Dissertation)

Mario Fernando Montenegro Campos

The physical interaction with unstructured environments requires that robotic systems have the ability to extract material and kinematic properties of objects around them. The goal of this research is to design a robotic systems that actively explores and extracts the material properties, including thermal, hardness and mass properties and of kinematic properties, such as mobility and geometric parameters of objects and their parts. to accomplish this objective, we invoke the paradigms of active perception and exploratory procedures. We develop methodologies for the design of such procedures as well as sensors which support their use in the robotic domain and demonstrate their effectiveness. The system is composed of a control module which coordinates the visual and the haptic sub-modules. Vision is implemented via an agile laser range-scanner which is able to acquire different views of the desired object. Global volumetric models of the object are recovered by fitting super-ellipsoids to the 2[1/2]D range image. The haptic module uses the geometric information of the object to perform several tests based on non-destructive techniques. For exploring thermal properties, a new approach for the design and modeling of thermal sensors for robotics is presented. A model of this sensor is developed and its validity is experimentally verified with different materials. Mass density is estimated by the weight evaluation procedure. Hardness is evaluated by means of stress vs. strain tests. Compression and tension tests are performed to determine this property. The kinematic characteristics of the object are explored by the mobility procedure. We describe a novel methodology, based on screw theoretic results which enables the identification of the mobility of the object. This is accomplished by forming a closed kinematic chain with the manipulator and the unknown object. The number of degrees of freedom present in the object as well as the geometric parameters of its links are then extracted. The design and implementation of the robotic haptic architecture testbed where all of the above concepts were smoothly integrated into a working system is also described. The architecture controls and coordinates the two robot manipulators, the instrumented parallel-jaw gripper and the mobile laser range-scanner.

MS-CIS-92-39 (GRASP LAB 317) (LINC LAB 223)

Parallel Evidence-Based Indexing of Complex Three-Dimensional Models Using Prototypical Parts and Relations (Dissertation Proposal)

Ron Katriel

This proposal is concerned with three-dimensional object recognition from range data using superquadric primitives. Superquadrics are a family of parametric shape models which represent objects at the part level and can account for a wide variety of natural and man-made forms. We propose a vision architecture that scales well as the size of its model database grows. Following the recovery of superquadric primitives from the input depth map, we split the computation into two concurrent processing streams. One is concerned with the classification of individual parts using viewpoint-invariant shape information while the other classifies pairwise part relationships using their relative size, orientation and type of joint. The major contribution of this proposal lies in a principled solution to the very difficult problems of superquadric part classification and model indexing. The problem is how to retrieve the best matched models without exploring all possible object matches. Our approach is to cluster together similar model parts to create a reasonable number of prototypical part classes (protoparts). Each superquadric part recovered from the input is paired with the best matching protopart using precomputed class statistics. A parallel, theoretically-well grounded evidential recognition algorithm quickly selects models consistent with the classified parts. Classified part relations (protorelations) are used to further reduce the number of consistent models and remaining ambiguities are resolved using sequential top-down search.

MS-CIS-92-40 (GRASP LAB 318)

Occlusions As A Guide For Planning The Next View

Jasna Maver, Ruzena Bajcsy

To resolve the ambiguities that are caused by occlusions in images, we need to take sensor measurements from several different views. The task addressed in this paper deals with a strategy for acquiring 3-D data of an unknown scene. We must first answer the question: What knowledge is adequate to perform a specific task? Thinking in the spirit of purposive vision, to accomplish its task, a system does not need to understand the complete scene but must be able to recognize patterns and situations that are necessary for accomplishing the task.

We have limited ourselves to range images obtained by a light stripe range finder. A priori knowledge given to the system is the knowledge of the sensor geometry. The foci of attention are occluded regions, i.e., only the scene at the borders of the occlusions is modeled to compute the next move. Since the system has knowledge of the sensor geometry, it can resolve the appearance of occlusions by analyzing them.

The problem of 3-D data acquisition is divided in two subproblems due to two types of occlusions. An occlusion arises either when the reflected laser light does not reach the camera or when the directed laser light does not reach the scene surface. After taking the range image of a scene the regions of no data due to the first kind of occlusion are extracted. The missing data are acquired by rotating the sensor system in the scanning plane, which is defined by the first scan. After a complete image of the surface illuminated from the first scanning plane has been built, the regions of missing data which are due to the second kind of occlusions are located. Then the directions of the next scanning planes for further 3-D data acquisition are computed.

For more detailed proofs and theorems of the computation of the next scanning plane (Section 5.3) please see ``Occlusions as a Guide for Planning the Next View,'' University of Pennsylvania Technical Report, MS-CIS-91-27, GRASP LAB 257, 1991.

MS-CIS-92-41 (GRASP LAB 319)

Analysis and Simulation of Mechanical Systems with Multiple Frictional Contacts (Dissertation)

Yin-Tien Wang

There are several applications in robotics and manufacturing in which nominally rigid objects are subject to multiple frictional contacts. Since such a system is characterized by unilateral constraints, the topology of the mechanical system varies with time. that is, each time when a contact is formed or broken, or when a rolling contact changes to a sliding contact, the mobility of the mechanical system and the structure of the differential equations that characterize the system change. The research in this dissertation focuses on a systematic method for the analysis and simulation of such systems.

In most previous work, rigid body models and empirical models for friction have been used to analyze the dynamics of such systems. It is shown here that the use of frictional laws, such a Coulomb's law, introduce inconsistencies and ambiguities when used in conjunction with the principles of rigid body dynamics. Further, the static indeterminacy makes it impossible to determine the contact forces.

A new approach to the simulation of mechanical systems with multiple, frictional constraints is proposed which is free of inconsistencies. Compliant contact models are used to model the deformation of the contact surface and the energy dissipation during impacts. The method involves the integration of rigid body models with the compliant contact models - the rigid body models are used for predicting gross motion in the absence of unilateral constraints, and the contact models are used, when frictional contacts occur, for analyzing small motions. This method is compared with previous hypotheses and models and is shown to overcome their limitations.

The general method developed in this dissertation has applications in a wide range of problems in manufacturing and robotics. In this dissertation, we address the dynamic analysis and simulation of nonlinear control algorithms for multiarm manipulation, control of enveloping grasps and the parts-feeding processing manufacturing.

MS-CIS-92-42 (DISTRIBUTED SYSTEMS LAB 11)

MIRAGE: A Model for Latency In Communication (Dissertation)

Joseph Dean Touch

Mirage is an abstract model for the design and analysis of high speed wide area network (WAN) protocols. It examines the effects of latency on communication, and indicates the information separation is the distinguishing characteristic of gagabit WANs. Existing protocols will exhibit performance failures du to an inability to accommodate imprecision in the remote state. The name Mirage denotes the difficulty with latent communication, namely nodes never really ``see'' each other precisely; rather, they work with (and around) the mirages which high speed and fixed latency conjure before them .

This dissertation describes the Mirage abstract model as an extended finite state machine that accommodates imprecision through the use of multiple simultaneous states and state space volume transformation. We introduce guarded messages , to accommodate nondeterministic data streams, and communicability, the upper bound on communication, given fixed latency and state predictability. Mirage demonstrates how excess bandwidth can be used to accommodate latency, and shows the bounds on latency constrained communication. Supplemental discussions includes consider Mirage as an extension of Shannon's communication theory, and compare it to physics analogs.

Mirage was applied to the Network Time Protocol (NTP), to demonstrate its use and exemplify its abstract components. We show the equivalence between variation in state space imprecision and variation in transmission latency. Several 'optional' components of the NTP specification are shown to be required, and layering is violated in permitting sender anticipation.

To show the models advantages, Mirage was applied to processor - memory interaction as a protocol, calling the result m-Net (MicroNet). Using anticipation, we develop a novel interface which achieves a hit rate equivalent to that of a 50K byte cache, using 400 bytes of storage.m -Net complements conventional cache techniques, especially where communication latency is the limiting factor in code execution, and where excess communication bandwidth is available. Dynamic traces measured the latency accommodation possible by the various implementation versions.

MS-CIS-92-43 (LINC LAB 224)

Pronominal Reference To Events and Actions: Computational Foundations (Dissertation)

Ethel Schuster

When a pronoun appears in discourse, it can refer to a specific event, to various types of events, as well as to sets of events. It is not always possible to identify a one-to-one correspondence between the pronoun and its referent. This thesis presents an approach whereby such a correspondence can be identified. Two types of relationships among referents are identified: (i) a generalization relationship, which establishes the relationship between a specific event, described in the discourse, and a general class of events, and (ii) three compounding relationships, sequence, causation, and generation. These compounding relationships connect various events as compound unit as a whole or to parts of it, depending on the particular compounding relationships that hold within the compound.

This thesis also presents a set of rules that guide the choice of the referents of the pronouns it and that. This set of rules leads to an algorithm that generates pronouns referring to individual or compound events. By using one pronoun over the other, it is possible to indicate whether the pronoun refers to a compound referent or to parts of that compound.

MS-CIS-92-44 (GRASP LAB 320)

Control of Mechanical Systems with Rolling Constraints: Application To Dynamic Control of Mobile Robots

Nilanjan Sarkar, Xiaoping Yun, Vijay Kumar

There are many examples of mechanical systems which require rolling contacts between two or more rigid bodies. Rolling contacts engender nonholonomic constraints in an otherwise holonomic system. In this paper, we develop a unified approach to the control of mechanical systems subject to both holonomic and nonholonomic constraints. We first present a state space realization of a constrained system and show that it is not input-state linearizable. We then discuss the input-output linearization and zero dynamics of the system. This approach is applied to the dynamic control of mobile robots. Two types of control algorithms for mobile robots are investigated: (a) trajectory tracking, and (b) path following. In each case, a smooth nonlinear feedback is obtained to achieve asymptotical input-output stability, and Lagrange stability of the overall system. Simulation results are presented to demonstrate the effectiveness of the control algorithms and to compare the performance of trajectory tracking and path following algorithms.

MS-CIS-92-45 (GRASP LAB 321)

On Feedback Linearization of Mobile Robots

Xiaoping Yun, Yoshio Yamamoto

A wheeled mobile robot is subject to both holonomic and nonholonomic constraints. Representing the motion and constraint equations in the state space, this paper studies the feedback linearization of the dynamic system of a wheeled mobile robot. The main results of the paper are: (1) It is shown that the system is not input-state linearizable. (2) If the coordinates of a point on the wheel axis are taken as the output equation, the system is not input-output linearizable by using a static state feedback; (3) but is input-output linearizable by using a dynamic state feedback. (4) If the coordinates of a reference point in front of the mobile robot are chosen as the output equation, the system is input-output linearizable by using a static state feedback. (5) The internal motion of the mobile robot when the reference point moves forward is asymptotically stable whereas the internal motion when the reference point moves backward is unstable. A nonlinear feedback is derived for each case where the feedback linearization is possible.

MS-CIS-92-46 (LINC LAB 225)

From Operational Semantics To Abstract Machines

John Hannan (University of Copenhagen), Dale Miller (University of Pennsylvania)

We consider the problem of mechanically constructing abstract machines from operational semantics, producing intermediate-level specifications of evaluators guaranteed to be correct with respect to the operational semantics. We construct these machines by repeatedly applying correctness-preserving transformations to operational semantics until the resulting specifications have the form of abstract machines. Though not automatable in general, this approach to constructing machine implementations can be mechanized, providing machine-verified correctness proofs. As examples we present the transformation of specifications for both call-by-name and call-by-value evaluation of the untyped $\lambda$-calculus into abstract machines that implement such evaluation strategies. We also present extensions to the call-by-value machine for a language containing constructs for recursion, conditionals, concrete data types, and built-in functions. In all cases, the correctness of the derived abstract machines follows from the (generally transparent) correctness of the initial operational semantic specification and the correctness of the transformations applied.

MS-CIS-92-47 (LOGIC & COMPUTATION 47)

Naturally Embedded Query Languages

Val Breazu-Tannen, Peter Buneman, Limsoon Wong

We investigate the properties of a simple programming language whose main computational engine is structural recursion on sets. We describe a progression of sublanguages in this paradigm that (1) have increasing expressive power, and (2) illustrate robust conceptual restrictions thus exhibiting interesting additional properties. These properties suggest that we consider our sublanguages as candidates of ``query languages''. Viewing query languages as restrictions of our more general programming language has several advantages. First, there is no ``impedance mismatch'' problem; the query languages are already there, so they share common semantic foundation with the general language. Second, we suggest a uniform characterization of nested relational and complex-object algebras in terms of some surprisingly simple operators; and we can make comparisons of expressiveness in a general framework. Third, we exhibit differences in expressive power that are not always based on complexity arguments, but use the idea that a query in one language may not be polymorphically expressible in another. Fourth, ideas of category theory can be profitably used to organize semantics and syntax, in particular our minimal (core) language is a well-understood categorical construction: a cartesian category with a strong monad on it. Finally, we bring out an algebraic perspective, that is, our languages come with equational theories, and categorical ideas can be used to derive a number of rather general identities that may serve as optimizations or as techniques for discovering optimizations.

MS-CIS-92-48 (LINC LAB 226)

p-Calculus As A Theory In Linear Logic: Preliminary Results

Dale Miller

The agent expressions of the p-calculus can be translated into a theory of linear logic in such a way that the reflective and transitive closure of p-calculus (unlabeled) reduction is identified with ``entailed-by''. Under this translation, parallel composition is mapped to the multiplicative disjunct (``par'') and restriction is mapped to universal quantification. Prefixing, non-deterministic choice (+), replication (!), and the match guard are all represented using non-logical constants, which are specified using a simple form of axiom, called here a process clause. These process clauses resemble Horn clauses except that they may have multiple conclusions; that is, their heads may be the par of atomic formulas. Such multiple conclusion clauses are used to axiomize communications among agents. Given this translation, it is nature to ask to what extent proof theory can be used to understand the meta-theory of thep-calculus. We present some preliminary results along this line for p₀, the ``propositional'' fragment of the p-calculus, which lacks restriction and value passing (p₀ is a subset of CCS). Using ideas from proof-theory, we introduce co-agent and show that they can specify some testing equivalences forp₀ . If negation-as-failure-to-prove is permitted as a co-agent combinator, then testing equivalence based on co-agents yields observational equivalence for p₀. This latter result follows from observing that co-agents are isomorphic to formulas in the Hennessy-Milner modal logic.

MS-CIS-92-49 (LINC LAB 227)

A Structural Interpretation of Combinatory Combinatory Categorial Grammar

James Henderson

This paper gives an interpretation of Combinatory Categorial Grammar derivations in terms of the construction of traditional phrase structure trees. This structural level of representation not only shows how CCG is related to other grammatical investigations, but this paper also uses it to extend CCG in ways which are useful for analyzing and parsing natural language, including a better analysis of coordination.

MS-CIS-92-50 (LINC LAB 228)

A Reconsideration of Preconditions

Christopher W. Geib

This paper is part of an attempt to introduce intentionality of the actor to planning decisions. As a first step in this process the usual representations for actions used by planning systems must be reevaluated. this paper argues for the elimination of preconditions and qualification conditions from action representation in favor of explicit representation of intention, situated reasoning about the results of the action and reactive failure mechanisms. The paper then describes a planning system that has explicit representation and use of intentions and uses action representation that do not have preconditions.

MS-CIS-92-51 (LINC LAB 229)

Surface Structure

Mark Steedman

The purpose of this paper is to show how binding and control can be captured straightforwardly in Combinatory Categorial Grammar (CCG), and to examine the interaction of the binding theory with the CCG account of long-range dependencies including ``parasitic gaps'' (Steedman 1987, Szabolcsi 1987a). Part I shows that a simple theory of binding and control is compatible with CCG. Part II shows that the Binding Theory interacts correctly with the combinatory account of long range dependency, correctly imposing certain constraints, including a number of asymmetries with respect to extraction between subjects and other arguments, such as ``strong crossover'', and the equivalent of an ``anti-c-command'' restriction on parasitic gaps (cf. Taraldsen (Taraldsen 1979). Them conclusion suggests a simplifying reorganisation of the theory of grammar, via a single level of derivational syntax and a reallocation of responsibilities among the modules of the theory.

MS-CIS-92-52 (LINC LAB 230)

Categorial Grammar

Mark Steedman

The paper is a review article comparing a number of approaches to natural language syntax and semantics that have been developed using categorial frameworks.

It distinguishes two related but distinct varieties of categorial theory, one related to Natural Deduction systems and the axiomatic calculi of Lambek, and another which involves more specialized combinatory operations.

MS-CIS-92-53 (LINC LAB 231)

Grammars and Processors

Mark Steedman

The paper discusses the role of grammars in sentence processing, and explores some consequences of the ``Strong Competence Hypothesis'' of Bresnan and Kaplan for combinatory theories of grammar.

MS-CIS-92-54 (GRASP LAB 322)

Multi-Arm Manipulation Of Large Objects With Rolling Contacts (Dissertation)

Eric David Paljug

The problem of manipulating objects which are relatively larger than the size of the manipulators is investigated. Large objects without special features such as handles can not be grasped easily by the conventional end effectors such as parallel-jaw grippers or multi-fingered hands. This work focuses on the manipulation of large objects in the plane and analyzes the contact interactions. The flat surface effectors of planar three link manipulators interact with the object. The dynamics of the object and the manipulators are included in the equations of motion that govern the planar manipulation system. The contacts between the link surface and the object can be characterized by rolling, sliding, and separation. This study focuses on rolling which is explicitly included in the dynamic model of the system. Contact separation is avoided by enforcing the unilateral constraint that each manipulator must push at the contact point. Sliding is avoided by constraining the applied force to fall within the contact friction cone. The dynamic coordination between multiple manipulators is achieved by simultaneously regulating the motion of the object and the critical contact force. Control algorithms are developed that employ nonlinear feedback to linearize and decouple the system. A motion and force planner is developed which incorporates the unilateral constraints into the system. The motion planner also specifies the rolling motion for each contact. Rolling enables the system to avoid slipping by repositioning the contact points such that forces are applied along the surface normals. The calculations of the rolling motion planner are based on the dynamics of the object, the measured external disturbance forces, and desired critical contact force. Extensions of the analysis are investigated by relaxing certain key assumptions. Results from simulation and experimentation are presented to verify the efficacy of the theory and to provide insight into the issues of practical implementation.

MS-CIS-92-55 (LINC LAB 232)

GRAD-CM2: A Data-Parallel Connectionist Network Simulator

Thomas Fontaine

A data-parallel simulator capable of training recurrent time-delay connectionist networks is described. The simulator, GRAD-CM2, is written in the C^*programming language and runs on a Connection Machine CM-2. GRAD-CM2 is an extension of the serial simulator, GRADSIM [8], and offers ismular features. Timing performances of GRAD-CM2 and GRADSIM on a series of spatiotemporal discrimination tasks are presented to emphasize the efficacy of data-parallelism.

MS-CIS-92-56 (GRASP LAB 323)

Mesh Connected Computers With Multiple Fixed Buses: Packet Routing, Sorting and Selection

Sanguthevar Rajasekaran

Mesh connected computers have become attractive models of computing because of their varied special features. In this paper we consider two variations of the mesh model: 1) a mesh with fixed buses, and 2) a mesh with reconfigurable buses. Both these models have been the subject matter of extensive previous research. We solve numerous important problems related to packet routing, sorting, and selection on these models. In particular, we provide lower bounds and very nearly matching upper bounds for the following problems on both these models: 1) Routing on a linear array; and 2) k-k routing, k-k sorting, and cut through routing on a 2D mesh for any k ³ 12. We provide an improved algorithm for 1-1 routing and a matching sorting algorithm. In addition we present greedy algorithms for 1-1 routing, k-k routing, cut through routing, and k-k sorting that are better on average and supply matching lower bounds. We also show that sorting can be performed in logarithmic time on a mesh with fixed buses. As a consequence we present an optimal randomized selection algorithm. In addition we provide a selection algorithm for the mesh with reconfigurable buses whose time bound is significantly better than the existing ones. Our algorithms have considerably better time bounds than many existing best known algorithms.

MS-CIS-92-57 (GRASP LAB 324)

Optimal Mesh Algorithms For The Voronoi Diagram Of Line Segments, Visibility Graphs and Motion Planning In The Plane

Sanguthevar Rajasekaran, Suneeta Ramaswami

The movion planning problem for an object with two degrees of freedom moving in the plane can be stated as follows: Given a set of polygonal obstacles in the plane, and a two-dimensional mobile object B with two degrees of freedom determine if it is possible to move B from a start position to a final position while avoiding the obstacles. If so, plan a path for such a motion. Techniques from computational geometry have been used to develop exact algorithms for this fundamental case of motion planning. In this paper we obtain optimal mesh implementations of two different methods for planning motion in the plane. We do this by first presenting optimal mesh algorithms for some geometric problems that, in addition to being important substeps in motion planning, have numerous independent applications in computational geometry.

In particular, we first show that the Voronoi diagram of a set of n nonintersecting (exceptpossibly at endpoints) line segments in the plane can be constructed in O (Ön) time on a Ön mesh, which is optimal for the mesh. Consequently, we objtain an optimal mesh implementation of the sequential motion planning algorithm described in [14]; in other words, given a disc B and a polygonal obstacle set of size n, we can plan a path (if it exists) for the motion of B from a start position to a final position in O(Ön) time on a mesh size n. Next we show that given a set of n line segments and a point p, the set of segment endpoints that are visible from p can be computed in O (Ön) mesh-optimal time on a Ön x Ön mesh. As a result, the visibility graph of a set of n line segments can be computed in O(n) time on an n x n mesh. This result leads to an O(n) algorithm on an n x n mesh for planning the shortest path motion between a start position and a final position for a convex object B (of constant size) moving amont convext polygonal obstacles of total size n.

MS-CIS-92-58 (GRASP LAB 325)

A Comparison Of Meshes With Static Buses and Unidirectional Wrap-Arounds

Danny Krizanc (University of Rochester), Sanguthevar Rajasekaran (University of Pennsylvania), Sunil M. Shende (University of Nebraska)

We investigate the relative computational powers of a mesh with static buses and a mesh with unidirectional wrap-arounds. A mesh with unidirectional wrap-arounds is a torus with the restriction that any wrap-around link of the architecture can only transmit data in one of the two directions at any clock tick. We show that the problem of packet routing can be solved as efficiently on a linear array with unidirectional wrap-around link as on a linear array with a broadcast bus. We also present a routing algorithm for a two-dimensional torus with unidirectional wrap-around links whose run time is close to that of the best known algorithm for routing on a mesh with broadcast buses in each dimension. In addition, we show that on a mesh with broadcast buses, sorting can be done in time that is essentially the same as the time needed for packet routing.

MS-CIS-92-59 (LOGIC & COMPUTATION 48)

A Conservative Property of A Nested Relational Query Language

Limsoon Wong

MS-CIS-92-60

Convex Spaces As An Order-Theoretic Basis For Problem Solving (Dissertation)

Teow-Hin Ngair

The ability to represent and use a body of knowledge or information is fundamental to all problem solvers. It is well recognized that different problems require different representations so that the corresponding algorithms can be implemented efficiently. This thesis advocates that ordered structures play an important role in many problem domains. In particular, we focus on the study of an ordered structure called a convex space. We demonstrate that this particular ordered structure helps answer some of the important questions concerning problem solving tasks in the fields of Artificial Intelligence and Database Systems that are of major interest from both theoretical and practical points of view.

Specifically, we study how convex spaces can be used to formulate the algorithms related to version spaces, querying independent databases, Assumption-based Truth Maintenance Systems (ATMS), and the generation of prime implicates. This results in a unifying framework for studying and understanding the representation used in these seemingly unrelated areas. Consequently, we derive general admissibility criteria for version space learning, a semantics for describing a useful database merging procedure in addition to some standard relational database operations, and a consistent semantics for the basic and extended ATMS's.

Moreover, the order-theoretic study leads to the derivation and implementation of better algorithms to replace some of the existing algorithms. Most noteworthy are a more general prime implicate generation algorithm that can also function as very efficient abductive reasoner and theorem prover, an ordered-theoretic based extended ATMS algorithm which eliminates the necessity of inefficient resolution procedures, and a focused ATMS algorithm that supports an efficient diagnostic system. The complexity issues of various algorithms are discussed and some empirical results are presented.

MS-CIS-92-61 (GRASP LAB 326)

Focusing ATMS Problem-Solving: A Formal Approach

Teow-Hin Ngair, Gregory Provan

The Assumption-based Truth Maintenance System (ATMS) is a general and powerful problem-solving tool in AI. Unfortunately, its generality usually entails a high computational cost. In this paper, we study how a general notion of cost function can be incorporated into the design of an algorithm for focusing the ATMS, called BF-ATMS. The BF-ATMS algorithm explores a search space of size polynomial in the number of assumptions, even for problems which are proven to have exponential size labels. Experimental results indicate significant speedups over the standard ATMS for such problems. In addition to its improved efficiency, the BF-ATMS algorithm retains the multiple-context capability of an ATMS, and the important properties of consistency, minimality, soundness, as well as the property of bounded completeness.

The usefulness of the new algorithm is demonstrated by its application to the task of consistency-based diagnosis, where dramatic efficiency improvements, with respect to the standard solution technique, are obtained.

MS-CIS-92-62 (LINC LAB 233)

Specifying Filler-Gap Dependency Parsers In A Linear-Logic Programming Language

Joshua S. Hodas

An aspect of the Generalized Phrase Structure Grammar formalism proposed by Gazdar, et al. is the introduction of the notion of ``slased categories'' to handle the parsing of structures, such as relative clauses, which involve unbounded dependencies. This has been implemented in Definite Clause Grammars through the technique of gap threading, in which a difference list of extracted noun phrases (gaps) is maintained. However, this technique is cumbersome, and can result in subtle soundness problems in the implemented grammars. Miller and Pareschi have proposed a method immplementing gap threading at the logical level in intuitionistic logic. Unfortunately that implementation itself suffered from serious problems, which the authors recognized. This paper builds on work first presented with Miller in which we developed a filler-gap dependency parser in Girard's linear logic. This implementation suffers from non of the pitfalls of either the tradition implemention, or the intuitionistic one. It serves as further demonstration of the usefulness of sub-structural logic in natural language applications.

MS-CIS-92-63 (GRASP LAB 327)

Design and Control Of An In-Parallel Pneumatically-Actuated Manipulator

Thomas G. Sugar

The design and control of an in-parallel, pneumatically actuated manipulator is presented. In-parallel manipulators offer superior dynamic characteristics because of their high stiffness, low inertia, and potential for direct drive actuation. In this thesis, the three degree of freedom tripod manipulator is studied. The three degrees of freedom of the manipulator are exactly those that are required for force control perpendicular to a surface. These degrees of freedom are translations along the approach direction and rotations about the axes perpendicular to the approach direction. This body os research can be grouped into three parts. First the area of force control is examined with two purposes in mind, improving pneumatic force control, and understanding how force control has been traditionally implemented and the reasons for its limitations. Next, the improvement of the response of the mechanism and the implementation of different force control schemes are investigated. To improve the response of the system, shorter transmission lengths and an inner pressure feedback loop are added. Position control, force control, stiffness/compliance control, and impedance control, are all investigated, Lastly, a discussion of the advantages and possible uses of this mechanism is presented. The advantage of the parallel mechanism is the ability to regualte the force perpendicular to the surface. Thus, the mechanism can control the force perpendicular to the surface, while an arm attached to the mechanism can control the position of the end effector. This mechanism thus allows the hybrid position and force control problem to be decoupled. Obvious uses for applying a force perpendicular to a surface are tasks such as deburring or polishing. Another possible use could be peg insertion; a new design for peg insertion will be discussed. Lastly, this mechanism could be used as an ankly for a walking machine or a writ for a serial robot. The mechanism can adjust for unforeseen impacts and allow the system to be used in an unstructured. environment.

MS-CIS-92-64

Teleprogramming: Remote Site Robot Task Execution (Dissertation)

Thomas S. Lindsay

This dissertation describes a remote site robot workcell for teleoperation with communication delays on the order of 20 seconds. In these situations, direct teleoperation becomes impossible due to the delays in visual and force feedback. Teleprogramming has been developed in order to overcome this problem.

An integral part of teleprogramming is a semi-autonomous remote site robot system. The remote system is composed of a robot manipulator, sensors, controlling computer, and manipulator tools. The constraints on the remote site system and the amount of autonomy needed are defined partially by the teleprogramming system, and partially by the needs of the remote system. Development of the remote site system for teleoprogramming evokes some pertinent research issues: low level manipulator control, semi-autonomous Vcommand execution, and remote site tool usage.

Low level manipulator control is based on a hybrid control scheme using wrist-based sensory feedback. Implementation of this control is presented and problems related to controlling the manipulator in an arbitrary frame are investigated.

High level commands are executed at the remote site in small autonomous steps. Implementation of tolerance checks and guarded moves are presented, including error detection and the detection of motion termination conditions in a partially known environment.

Power tools introduce redundant degrees of freedom into the manipulator/tool system. To control this redundant system, the tool is actively controlled in its natural degree of freedome and the corresponding degree of freedom in the manipulator become passive. Feedback for the manipulator/tool system is supplied by the wrist-based sensor. Two examples of sensing and control for tools are presented.

This research has resulted in the development of a remote site system for teleprogramming. The remote system, however, is both time-delay and input independent. The characteristics of the system, including the compliance, flexibility, and semi-autonomity, are useful to a wide variety of robotics applications, including manufacturing and direct teleoperation.

MS-CIS-92-65 (GRASP LAB 329)

Control of Rolling Contacts In Multi-Arm Manipulation

Eric Plajug, Xiaoping Yun, Vijay Kumar

When multiple arms are used to manipulate a large object, it is beneficial and sometimes necessary to maintain and control contacts between the object and the effector (the contacting surface of an arm) through force closure. Rolling and/or sliding can occur at these contacts, and the system is characterized by holonomic as well as nonholonomic (including unilateral) constraints. In this paper, the control of planar rolling contacts is investigated. Multi-arm manipulation systems are typically redundant. In our approach, a minimal set of inputs is employed to control the trajectory of the system while the surplus inputs control the contact condition. The trajectory includes the gross motion of the object as well as the rolling motion at the contacts. A nonlinear feedback scheme for simultaneous control of motion as well as contact conditions is presented. A new algorithm which adapts a two-effector grasp with rolling contacts to external loads and the trajectory is developed. Simulations and experimental results are used to illustrate the salient features in control and planning.

MS-CIS-92-66 (LINC LAB 234)

Search Through Systematic Set Enumeration

Ron Rymon

In many problem domains, solutions take the form of unordered sets. We present the Set-Enumerations (SE)-tree - a vehicle for representing sets and/or enumerating them in a best-first tfashion. We demonstrate its usefulness as the basis for a unifying search-based framework for domains where minimal (maximal) elements of a power set are targeted, where minimal (maximal) partial instantiations of a set of variables are sought, or where a composite decision is not dependent on the order in which its primitive component-decisions are taken. Particular instantiations of SE-tree-based algorithms for some AI paroblem domains are used to demonstrate the general features of the approach. These algorithms are compared theoretically and empirically with cureent algorithms.

MS-CIS-92-67 (LOGIC & COMPUTATION 50)

Data Abstraction In Programming Language Semantics (Dissertation)

Ramesh Subrahmanyam

Most modern programming languages allow the user to define abstract data types, thereby creating an extended language. While the programming language without the definition of ADT's is completely described by its operational semantics, the new constants in the extended language need to be specified in some appropriate formalism. Algebraic equations are one such formalism; such a specification of an ADT constrains the class of valid implementations of the ADT by requiring that the equations be observational equivalences in the extended language. To reason about the extended language it is useful to have a denotational semantics. This thesis studies the denotational semantics of languages with algebraically specified ADT's.

For a natural class of models for the extended language we give a necessary and sufficient condition for a model to be computationally adequate with respect to the extended language. This is shown in a variety of language settings to show the general nature of the ideas. We consider the implementation language PCF_n, which is a call-by-name variant of PCF . We define a class of algebras called fully abstract algebras, and exhibit a general construction that for a given algebraic specification of an ADT and any fully abstract algebra satisfying the specification constructs a fully abstract model of PCF_n extended with the ADT. This construction is rather syntactic, and so we consider some special cases where a ``semantic'' construction of a fully abstract model can be carried out. We then show the construction of two fully abstract algebras satisfying the specification. Both these algebras have appealing categorical descriptions that can be used to define paradigms of specification semantics, similar to initial and final algebra semantics.

For any programming language, there is the problem of reasoning about its models. Mechanization of such reasoning is intractable, in general, and therefore it is useful to consider specific fragments. We consider a fragment of PCF_n extended with ADT's that consists of simply typed lambda terms with algebraic constants. We study certain natural axiomatizations of specific environment models, which are models of call by name lambda calculi, and derive sufficient conditions for their completeness.

MS-CIS-92-68 (GRASP LAB 330)

Dynamic Network Construction and Updating Techniques For The Diagnoses Of Acute Abdominal Pain

Gregory M. Provan, John R. Clarke

Computing diagnoses in domains with continuously changing data is a difficult, but essential aspect of solving many problems. To address this task, this paper describes a dynamic influence diagram (ID) construction and updating system, DYNASTY, and its application to constructing a decision-theoretic model to diagnose acute abdominal pain, a domain in whch the finding evolve during the diagnostic process.

For a system which evolves over time, DYNASTY constructs a parsimonious ID, and then dynamically updates the ID, rather than constructing a new network from scratch for every time interval. In addition, DYNASTY contains algorithms for testing the sensitivity of the constructed network's system parameters. The main constributions of this paper are: (1) presenting an efficient temporal influence diagram technique based on parsimonious model construction; and (2) formalizing the principles underlying a diagnostic tool for acute abdominal pain which explicityly models time-varying findings.

MS-CIS-92-70 (GRASP LAB 332)

Rapid Prototyping Using Three-Dimensional Computer Vision

Visa Koivunen, Ruzena Bajcsy

A method for building model data for CAD and CAM purposes from physical instances using three-dimensional sensor data is presented. These techniques are suitable for Reverse Engineering of industrial parts, and can be used as a design aid as well. The nature of the reverse engineering task is quantitative, and the emphasis is on accurate recovery of the geometry of the part, whereas the object recognition task is qualitative, and aims to recognize similar shapes. The proposed method employs multiple representations to build a CAD model for the part, and to produce useful information for part analysis and process planning. The model building strategy is selected based on the obtained surface and volumetric data descriptions and their quality. A novel, robust non-linear filtering method is presented to attenuate noise from sensor data. Volumetric description is obtained by recovering a superquadric model for the whole data set. A surface characterization process is used to determine the complexity of the underlying surface. A substantial data compression can be obtained by approximating huge amount sensor data by B-spline surfaces. As a result a Boundary Representation model for Alpha_1 solid modeling system is constructed. The model data is represented both in Alpha_1 modeling language and IGES product data exchange format. Experimental results for standard geometric shapes and for sculptured free-form surfaces are presented using both real and synthetic range data.

MS-CIS-92-71 (LOGIC & COMPUTATION 51)

$n$-distributivity, dimension and Carath\'{e}odory's theorem

Leonid Libkin

A. Huhn proved that the dimension of Euclidean spaces can be characterized through algebraic properties of the lattices of convex sets. In fact, the lattice of convex sets of Eⁿ is n+1-distributive but not n-distributive. In this paper his result is generalized for a class of algebraic lattices generated by their completely join-irreducible elements. The lattice theoretic form of Carathédory's theorem characterizes n-distributivity in such lattices. Several consequences of this result are studies. First, it is shown how infinite n-distributivity and Carathédory's theorem are related. Then the main result is applied to prove that for a large class of lattices being n-distributive means being in a variety generated by the finite n-distributive lattices. Finally, n-distributivity is studied for various classes of lattices, with particular attention being paid to convexity lattices of Birkhoff and Bennett for which a Helly type result is also proved.

MS-CIS-92-72 (LOGIC & COMPUTATION 52)

Polymorphism and Inference In Database Programming

Peter Buneman (University of Pennsylvania), Atsushi Ohori (Oki Electric)

The polymorphic typee system of ML can be extended in two ways to make it the appropriate 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 relation database 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 program that involving field selection and generalized relational operators.

These extensions may also be used to provide static polymorphic typechecking in object-oriented languages and databases. A problem that arises with object oriented databses is the apprarent need for the dynamic typechecking when dealing with queries on heterogeneous collections of objects. An extension of the type system needed for generalized relational operations can also be used for manipulating collections of dynamically typed values in a statically typed language. A prototype language based on these ideas has been implemented. While it lacks a proper treatment of persistent data, it demonstrates that a wide variety of database structures can be cleanly represented in a polymorphic programming language.

MS-CIS-92-73

Intentions In Means-End Planning (Dissertation Proposal)

Christopher W. Geib

This proposal discusses the use of the intentions of the actor in performing means-end reasoning. In doing so, it will show that preconditions and applicability conditions in existing systems are ill-defined and intrinscially encode situaltional information that prevents intentions from playing a role in the planning process. While the former problem can be fixed, the latter cannot. Therefore, I argue that preconditions should be eliminated from action representation. In their place, I suggest explicit representation of intention, situalted reasoning about the results of action, and robust failure mechanisms. I then describe a system, the Intentional Planning System (ItPlanS), which embodies these ideas, compare ItPlanS to other systems, and propose future directions for this work.

MS-CIS-92-74 (LINC LAB 236)

Doing What You're Told: Following Task Instruction In Changing, but Hospitable Environments

Bonnie Webber, Norman Badler, F. Breckenridge Baldwin, Welton Becket, Barbara Di Eugenio, Christopher Geib Moon Jung, Libby Levison, Michael Moore, Michael White

The AnimNL project ( Anim ation from N atural L anguage) has as its goal the automatic creation of animated task simulationsfrom natural-language instructions. The question addressed in this paper is how agents can perform tasks in environments about which they have only partial relevant knowledge. The solution we describe involves enabling such agents to

• develop expectations through instruction understanding and plan inference, and use those expectations in deciding how to act;
• exploit generalized abilities in order to deal with novel geometric situations.

The AnimNL project builds on an animation system, Jack ^TM, that has been developed at the Computer Graphics Research Lab at the University of Pennsylvania, and draws upon a range of recent work in Natural Language semantics, planning and plan inference, philosophical studies of intention, reasoning about knowledge and action, and subsumption architectures for autonomous agents.

MS-CIS-92-75 (GRASP LAB 333)

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

Richard P. Paul, Janez Funda, Thomas Lindsay, Masahiko Hashimoto, Craig Sayers

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 leading to very low productivity.

We have combined computer graphics with manipulator programming to provide a solution to the problem. A teleoperator master arm is interfaced to a graphics based simulator of the remote environment. The system is then coupled with a robot manipulator at the remote, delayed site. The operator's actions are monitored to provide both kinesthetic and visual feedback and to generate symbolic motion commands to the remote slave. The slave robot then executes these symbolic commands delayed in time. While much of a task proceeds error free, when an error does occur, the slave system transmits data back to the master environment which is then ``reset'' to the error state from which the operator continues the task.

MS-CIS-92-76 (LINC LAB 237)

Acquisition Of Verb Categories

Mark Steedman

The paper was delivered as a commentary upon Michael Brent's presentation ``Acquisition of Subcategorization Frames Using Aggregated Evidence from Local Syntactic Cues'' to the Conference on Acquisition of the Mental Lexicon, IRCS, University of Pennsylvania, January 1992. It argues in support of using statistical techniques like Brent's to minimise the consequences of errors and misanalyses, but concludes that the case for believing that children acquire subcategorisations and other aspects of syntax on the basis of semantic and contextual cues remains strong.

MS-CIS-92-77 (GRASP LAB 334)

Improved Instrumented Compliant Wrist Design

Thomas Lindsay Richard P. Paul

Interaction between robot and environment is an extremely important aspect of robotic research. Compliance helps reduce the impact effects of robot/environment interaction. Hybrid position/force control is important in most robotic tasks; accurate position control is needed in unconstrained directioins, and accurate fore control is needed in constrained directions. Force control can be more responsive with a compliant force/torque sensor, 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 connect in series between the end of the robot and the tool, and is designed to partially surround the tool, thus reducing the distance between the end of the robot and the end of 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 deflections produced in the wrist.

This document describes the newest version of the instrumented compliant wrist, including modifications and improvements to the wrist described in ``Design of a Tool Surrounding compliant Instrumented Wrist'', available as tech report MS-CIS-91-30, GRASP LAB 258 from the University of Pennsylvania. Changes include a more protective sensing linkage structure and improved electronics. The compliance, kinematcis, and accuracy of the wrist are presented. Also, software for determining the wrist transform, and plans for the wrist are given.

MS-CIS-92-78 (GRASP LAB 335)

A Proposal Concerning The Analysis Of Shadows In Images By An Active Observer (Dissertation Proposal)

Gareth D. Funka-Lea

Shadows occur frequently in indoor scenes and outdoors on sunny days. Despite the information inherent in shadows about a scene's geometry and lighting conditions, relatively little work in image understanding has addressed the important problem of recognizing shadows. This is an even more serious failing when one considers the problems shadows pose for many visual techniques such as object recognition and shape from shading. Shadows are difficult to identify because they cannot be infallibly recognized until a scene's geometry and lighting are known. However, there are a number of cues which together strongly suggest the identification of a shadow. We present a list of these cues and methods which can be used by an active observer to detect shadows. By an active observer, we mean an observer that is not only mobile, but can extend a probe into its environment. The proposed approach should allow the extraction of shadows in real time. Furthermore, the identification of a shadow should improve with observing time. In order to be able to identify shadows without or prior to obtaining information about the arrangement of objects or information about the spectral properties of materials in the scene, we provide the observer with a probe with which to cast its own shadows. Any visible shadows cast by the probe can be easily identified because they will be new to the scene. These actively obtained shadows allow the observer to experimentally determine the number and location of light sources in the scene, to locate the cast shadows, and to gain information about the likely spectral changes due to shadows. We present a novel method for locating a light source and the surface on which a shadow is cast. It takes into account errors in imaging and image processing and, furthermore, it takes special advantage of the benefits of an active observer. The information gained from the probe is of particular importance in effectively using the various shadow cues. In the course of identifying shadows, we also present a new modification on an image segmentation algorithm. Our modification provides a general description of color images in terms of regions that is particularly amenable to the analysis of shadows.

MS-CIS-92-79 (GRAPHICS LAB 50)

Striaght Line Walking AnimNLation Based On Kinematic Generalization That Preserves The Original Characteristics

Kyeongseok Ko, Norman I. Badler

The most prominent problems in utilizing the rotoscopy data for human walking animation can be summarized into two: Preservation of the original motion characteristics in the generalization process and the Constraint Satisfaction.

Generalization is the process of producing the step of an arbitrary body and step length out of the original measured step which is of one particular subject and step length. If we lose much of the original style in the generalization, it would be meaningless to use the measured data. We present a generalization technique that keeps the original motion characteristics as much as possible.

Two types of generalization are considered. The one is the body condition generalization, which handles the differences between the two bodies. The ratio between the corresponding segments of the two bodies may not be uniform, which makes this generalization complicated. The other one is the step length generalization, which provides the steps with different step lengths of the same subject. These two generalizations are combined together to generate a step of arbitrary subject and step length.

The constraint satisfaction is enforced inside of our generalization process. Therefore the only thing that concerns us is the {\em quality} of the generalization. In our work, the preservation of the original characteristics is considered as the criteria determining the quality of the generalization. We prove that our generalization scheme actually preserves the characteristics of the original walk.

MS-CIS-92-80 (LINC LAB 238)

Proceedings of the Workshop on Linear Logic and Logic Programming (Washington, DC)

Edited by Dale Miller

Declarative programming languages often fail to effectively address many aspects of control and resource management. Linear logic provides a framework for increasing the strength of declarative programming languages to embrace these aspects. Linear logic has been used to provide new analyses of Prolog's operational semantics, including left-to-right/depth-first search and negation-as-failure. It has also been used to design new logic programming languages for handling concurrency and for viewing program clauses as (possibly) limited resources. Such logic programming languages have proved useful in areas such as databases, object-oriented programming, theorem proving, and natural language parsing.

This workshop is intended to bring together researchers involved in all aspects of relating linear logic and logic programming. The proceedings includes two high-level overviews of linear logic, and six contributed papers.

Workshop organizers: Jean-Yves Girard (CNRS and University of Paris VII), Dale Miller (chair, University of Pennsylvania, Philadelphia), and Remo Pareschi, (ECRC, Munich).

MS-CIS-92-81 (LINC LAB 239)

More On Goal-Directed Diagnosis

Ron Rymon

**THIS PAPER HAS BEEN REPLACED BY MS-CIS-93-57/LINC LAB 251**

In many diagnosis-and-repair domains, diagnostic reasoning cannot be abstracted from repair actions, nor from actions necessary to obtain diagnostic information. We call these exploratory-corrective domains. In TraumAID 2.0, a consultation system for multiple trauma management, we have developed and implemented a framework for reasoning in such domains which integrates diagnostic reasoning with planning and action. In this paper, we present Goal-Directed Diagnosis (GDD), the diagnostic reasoning component of this framework. Taking the view that a diagnosis is only worthwhile to the extent that it can affect subsequent decisions, GDD focuses on the formation of appropriate goals for its complementary planner.

MS-CIS-92-82 (GRASP LAB 336)

Active Color Image Analysis For Recognizing Shadows

Gareth Funka-Lea, Ruzena Bajcsy

Many existing computer vision modules assume that shadows in an image have been accounted for prior to their application. In spite of this, relatively little work has been done on recognizing shadows or on recognizing a single surface material when directly lit and in shadow. This is in part because shadows cannot be infallible recognized until a scene's lighting and geometry are known. However, color is a strong cue to the presence of shadows. We present a general color image segmentation algorithm whose output is amenable to the recovery of shadows as determined by an analysis of the physics of shadow radiance. Then, we show how an observer that can cast its own shadows can infer enough information about a scene's illumination to refine the segmentation results to determine where the shadows in the scene are with reasonable confidence. Having an observer that can actively cast shadows frees us from restrictive assumptions about the scene illumination or the reliance on high level scene knowledge. We present results of our methods on images of complex indoor and outdoor scenes.

MS-CIS-92-83 (DISTRIBUTED SYSTEMS LAB 12)

On The Dynamics and Significance of Low Frequency Components of Internet Load

Dynamics of Internet load are investigated using statistics of round-trip delays, packet losses and out-of-order sequence of acknowledgments. Several segments of the Internet are studied. They include a regional network (the Jon von Neumann Center Network), a segment of the NSFNet backbone and a cross-country network consisting of regional and backbone segments.

Issues addressed include:
(a) dominant time scales in network workload;
(b) the relationship between packet loss and different statistics of round-trip delay (average, minimum, maximum and standard-deviation);
(c) the relationship between out of sequence acknowledgments and different statistics of delay;
(d) the distribution of delay;
(e) a comparison of results across different network segments (regional, backbone and cross-country); and
(f) a comparison of results across time for a specific network segment.

This study attempts to characterize the dynamics of Internet workload from an end-point perspective. A key conclusion from the data is that efficient congestion control is still a very difficult problem in large internetworks. Nevertheless, there are interesting signals of congestion that may be inferred from the data. Examples include (a) presence of slow oscillation components in smoothed network delay, (b) increase in conditional expected loss and conditional out-of-sequence acknowledgments as a function of various statistics of delay, (c) change in delay distribution parameters as a function of load, while the distribution itself remains the same, etc. The results have potential application in heuristic algorithms and analytical approximations for congestion control.

MS-CIS-92-84 (GRASP LAB 337)

Learning for Coordination of Vision and Action

Marcos Salganicoff (University of Pennsylvania), Ruzena Bajcsy (University of Pennsylvania), Tom Mitchell (Carnegie Mellon University)

We define the problem of visuomotor coordination and identify bottleneck problems in the implementation of general purpose vision and action systems. We conjecture that machine learning methods provide a general purpose mechanism for combining specific visual and action modules in a task-independent way. We also maintain that successful learning systems reflect realities of the environment, exploit context information, and identify limitations in perceptua l algorithms which cannot be captured by the designer. We then propose a multi-step find-and-fetch mobile robot search and retrieval task. This task illustrates where current learning approaches provide solutions and where future research opportunities exist.

MS-CIS-92-85 (LINC LAB 240)

Generalized Quantifiers and Logical Reducibilities

Anuj Dawar

We consider extensions of first order logic (FO) and least fixed point logic (LFP) with generalized quantifiers in the sense of Lindström [Lin66]. We show that adding a finite set of such quantifiers to LFP fails to capture all polynomial time properties of structures, even over a fixed signature. We show that this strengthens results in [Hel92] and [KV92a]. We also consider certain regular infinite sets of Lindström quantifiers, which correspond to a natural notion of logical reducibility. We show that if there is any recursively enumerable set of quantifiers that can be added to FO (or LFP) to capture P, then there is one with strong uniformity conditions. This is established through a general result, linking the existence of complete problems for complexity classes with respect to the first order translations of [Imm87] or the elementary reductions of [LG77] with the existence of recursive index sets for these classes.

MS-CIS-92-86

Proceedings of the Workshop on thelProlog Programming Language (University of Pennsylvania)

Edited by Dale Miller

MS-CIS-92-87 (GRASP LAB 338)

Learning and Forgetting for Perception-Action: A Projection Pursuit and Density Adaptive Approach (Dissertation)

Marcos Salganicoff

We study learning of perception-action relations using visually-driven grasping as an example task. The well-established technique of non-parametric Projection Pursuit Regression (PPR) is used to accomplish reinforcement learning by searching for projections of high-dimensional data sets that capture invariants in the distribution of reinforcement in the parameter-space. The variable resolution 2^k-tree, a generalized quadtree, is used to represent perception-action maps based on the resulting reinforcement regression function.

We also pursue the following problem: how can we use human expertise and insight into grasping to train a system to select gripper approach directions and orientations for grasping, and then have it verify and adapt its skills through trial and error? To accomplish this learning we develop a new Density Adaptive Reinforcement Learning algorithm. This algorithm uses statistical tests to identify regions of the attribute space in which the dynamics of the task change and the density of exemplars is high. It concentrates the building of high-resolution descriptions in those areas.

In order to adapt the default rules to those necessary for the robot, it is necessary for the system to be able to forget previous experiences that no longer reflect the behavior of the world. A general purpose Density Adaptive forgetting algorithm has been developed that can be used as a front-end for a variety of learning methods. Additionally, by setting the forgetting parameters appropriately, an upper bound on the number of exemplars stored in the system may also be selected. This is important since all memory-based learning systems have finite memory in practice.

The approach is verified through simulation and experimentation. A robotic system incorporating two robots with a gripper, compliant instrumented wrist, arm, camera and laser scanner is used for experimentation. Since trial and error learning processes imply that failures will occur, the mechanics of the untrained robotic system must be able to tolerate mistakes during learning and not be damaged by excessive forces. We address this by the use of an instrumented, compliant robot wrist that controls impact forces.

MS-CIS-92-88 (LOGIC & COMPUTATION 53)

Semantic Representations and Query Languages for Or-sets

Leonid Libkin, Limsoon Wong

Or-sets were introduced by Imielinski, Naqvi and Vadaparty for dealing with liimited forms of disjunctive information in database queries. Independently, Rounds used a similar notion for representing disjunctive and conjunctive information in the context of situation theory. In this paper we formulate a query language with adequate expressive power for or-sets. Using the notion of normalization of or-sets, queries at the ``structural'' and ``conceptual'' levels are distinguished. Losslessness of normalization is established for a large class of queries. We have obtained upper bounds for the cost of normalization. An approach related to that of rounds is used to provide semantics for or-sets.

MS-CIS-92-89 (LINC LAB 241)

Syntactic Locality and Tree Adjoining Grammar: Grammatical, Acquisition and Processing Perspectives (Dissertation)

Robert Evan Frank

It has been widely recognized that the relations huuman grammar exploits are sensitive to constraints on structural locality. Indeed, much research in generative syntax has forcused on the precise characterization of the locality conditions that grammatical processes respect. In this dissertation, I propose that locality reflects the underlying formal system with which grammars are represented. In particular, I argue that the formalism of Tree Adjoining Grammar (TAG) is the appropriate meta-language for grammatical principles. TAG privdes a mechanism for composing phrase structure representations from small structural domains, and in so doing, restricts the class of possible grammatical principles to those expressible over these domains. Under this view, the existence of locality conditions is not directly stipulated, but instead follows from the representational machinery which the formal grammar makes available. I consider evidence from three domains of linguistic inquiry which provide convergent support for this view.

I first address the problem of constructing a grammatical theory in the principles and parameters fromaework in the context of the TAG formalism. I develop a substantive theory of the atomic objects of TAG, elementary trees, and argue for a Condition on Elementary Tree Minimality (CETM) which restricts the domain of an elementary tree. the CETM combined with TAG versions of the Projection Principle and the Empty Category Principle yields elegant analyses of a range of contructions including raising, copular sentences, wh-movement and gerunds.

Next, I turn to the domain of parsing and demonstrate how a TAG-based theory of grammar resolves the apparently incompatible demands of grammatical transparency and computational efficiency. The model I develop operates incrementally by processing in elementary tree-sized chunk,s as determined by the CETM. This view of incrementality is supported by psycholinguistic evidence concerning the closure points of syntactic processing.

Finally, in the domain of acquisitions, I argue that the assumption that children cannot perform the more complex operations of TAG, adjoining, explains relative difficulties in the acquisition of seemingly disparate constructions including wh-movement, control, raising, and relative clauses. This represents a new kind of explanation for the time course of acquisition through properties of formal and computational complexity.

MS-CIS-92-90 (GRAPHICS LAB 51)

Physics-Based Modeling Of Nonrigid Objects For Vision and Graphics (Dissertation)

Dimitri N. Metaxas

This thesis develops a physics-based framework for 3D shape and nonrigid motion modeling for computer vision and computer graphics. In computer vision it addresses the problems of complex 3D shape representation, shape reconstruction, quantitative model extraction from biomedical data for analysis and visualization, shape estimation, and motion tracking. In computer graphics it demonstrates the generative power of our framework to synthesize constrained shapes, nonrigid object motions and object interactions for the purposes of computer animation.

Our framework is based on the use of a new class of dynamically deformable primitives which allow the combination of global and local deformations. It incorporates physical constraints to compose articulated models from deformable primitives and provides force-based techniques for fitting such models to sparse, noise-corrupted 2D and 3D visual data. The framework leads to shape and nonrigid motion estimators that exploit dynamically deformable models to track moving 3D objects from time-varying observations.

We develop models with global deformation parameters which represent the salient shape features of natural parts, and local deformation parameters which capture shape details. In the context of computer graphics, these models represent the physics-based marriage of the parameterized and free-form modeling paradigms. An important benefit of their global/local descriptive power in the context of computer vision is that it can potentially satisfy the often conflicting requirements of shape reconstruction and shape recognition.

The Lagrange equations of motion that govern our models, augmented by constraints, make them responsive to externally applied forces derived from input data or applied by the user. This system of differential equations is discretized using finite element methods and simulated through time using standard numerical techniques. We employ these equations to formulate a shape and nonrigid motion estimator. The estimator is a continuous extended Kalman filter that recursively transforms the discrepancy between the sensory data and the estimated model state into generalized forces. These adjust the translational, rotational, and deformational degrees of freedom such that the model evolves in a consistent fashion with the noisy data.

We demonstrate the interactive time performance of our techniques in a series of experiments in computer vision, graphics, and visualization.

MS-CIS-92-91 (LINC LAB 242)

Negotiation, Feedback, and Perspective Within Natural Language Generation (Dissertation)

Robert Rubinoff

This thesis is an investigation of how natrual language generation can take advantage of the ways that language use goes beyond simple, straightforward transmission of information. The two main constributions of the work are the use of annotations to relate linguistic choice to text planning and the use of perspective to model dependence and effects on attitude and context. Placing annotations on linguistic options allow the text planner to detect and respond to interactions between linguistic choices and the communicative plan driving those choices, without conflating the planning and linguistic levels of decision-making. The explicit modeling of perspective and perspective shifts allows the perspective to influence the generator's choices; in particular, the generator can take into account the ways that particular linguistic choices can affect or alter the subsequent perspective. The use of these techniques has been demonstrated in the IGEN implementation, resulting in a generator that can take advantage of the flexibility of natural language to frame its output in a way that reinforces the underlying goals driving the generation.

MS-CIS-92-92 (GRASP LAB 339)

Robust Signal Restoration and Local Estimation of Image Structure

Visa Koivunen

A class of nonlinear regression filters based on robust theory is introduced. the goal of the filtering is to restore the shape and preserve the details of the original noise-free signal, while effectively attenuating both impulsive and nonimpulsive noise. The proposed filters are based on robust Least Trimmed Squares estimation, where very deviating samples do not contribute to the final output. Furthermore, if there is more than one statistical population present in the processing windown the filter is very likely to select adaptively the samples that represent the majority and uses them for computing the output. We apply the regression filters on geometric signal shapes which can be found, for example, in range images. The proposed methods are also useful for extracting the trend of the signal without loosing important amplitutde information. We show experimental results on restroation of the original signal shape using real and synthetic data and both impulsive and nonimpulsive noise.

In addition, we apply the robust approach for describing local image structure. We sue the method for estimating spatial properties of the image in a local neighborhood. Such properties can be used for example, as auniformity predicate in the segmentation phase of an image understanding task. the emphasis is on producing reliable results even if the assumptions on noise, data and model are not completely valid. The experimental results provide information about the validity of those assumptions. Image describption results are shown using synthetic and real data, various signal shapes and impulsive and nonimpulsive noise.

MS-CIS-92-93 (GRASP LAB 340)

Robust Location Estimation for MLR and Non-MLR Distributions (Dissertation)

Gerda L. Kamberova

We study the problem of estimating an unknown parameter q from an observation of random variable Z = q + V. This is the location data model' V is random noise with absolutely continuous distribution F, independent of q. The distribution F belongs to a given uncertainty class of distributions \cal F,| \cal F|³. We seek robust minimax decision rules for estimating the location parameter q. The parameter space is restricted - a known compact interval. The minimax risk is evaluated with respect to a zero-one loss function with a given error-tolerance e. The zero-one loss uniformly penalizes estimates which differ from the true parameter by more than the threshold e (these are unacceptable errors). The minimax criterion with zero-one loss is suitable for modeling problems for which it is desirable to minimize the maximum probability of getting unacceptable errors. As a consequence of this approach we obtain fixed size confidence intervals with highest probability of coverage.

We consider the distribution-dependent function [((x+2e))/f(x)], where e is the error-tolerance and f is the noise density. We distinguish two different types of problems (involving two different types of distributions) based on behavior of this ratio: (I). Type \cal M-problems (\cal M-distributions) are characterized by a strictly monotone decreasing ratio; the minimax rules for \cal M-problems are admissible. They are monotone nondecreasing with a very simple structure -- continuous, piecewise-linear. the class of \cal M-problems includes, but is not limited to, the distributions with monotone likelihood ratio (MLR) and non-MLR mixtures of normal distributions. (II). Type \cal N M-problems (\cal N M-distributions) are characterized by nonmonotone ratios; the minimax rules for these problems are in general nonmonotone.