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