 |
2004 . 2003 . 2002 . 2001 . 2000 . 1999 . 1998 . 1997 . 1996 . 1995 . 1994 . 1993 . 1992 . 1991 . 1990
MS-CIS-93-01 (LOGIC & COMPUTATION 54)
On the Correspondence Between Proofs and l-Terms
Jean Gallier
The correspondence between natural deduction proofs and l-terms
is presented and discussed. A variant of the reducibility method
is presented, and a general theorem for establishing properties
of typed (first-order) l-terms is
proved. As a corollary, we obtain a simple proof of the Church-rosser
property, and of the strong normalization property, for the
typed l-calculus associated with
the systenm of (intuitionistic) first-order natural deduction,
including all the connectors ®, x, +, ",$ and ^ (falsity) (with or without h-like rules).
MS-CIS-93-02 (GRASP LAB 341)
Minimax Estimation Of A Bounded Location Parameter Using
Multilevel Loss (Dissertation)
Robert F. Kennedy
This dissertation considers minimax estimation under multilevel
loss of a bounded location parameter qÎ Q for
an arbitrary symmetric distribution F(z-q)
with monotone likelihood ratio. The parameter space is restricted
to a symmetric interval Q = [-d,d].
The multilevel loss function is a generalization of the zero-one
loss function, and can be represented by a linear combination
of component zero-one loss functions. The problem is considered
using two multilevel loss functions: zero-alpha-one loss; and
n-level loss. Minimax solutions under multilevel loss are shown
the be restricted to a class of monotone, antisymmetric decision
rules with range |d| £ [0,
d - e1]. The geometry of the zero-alpha-one problems
is analyzed to present the overall picture and categorize the
possible cases. From this analysis, the complete problem is
divided into three cases.
A solution technique is developed which allows the problem
to be represented by a finite-dimensional linear-algegraic
expression. The complete solution to the n-level loss problem
is presented for the simplest case (Case 1), which is defined
by d/2 £ e1 < en < d.
The truncated MLE is shown to be a global minimax rule for
a nondegenerate symmetric Case 1 problem when sufficient conditions
are satisfied. The solution is obtained by showing that the
truncated MLE is an almost equalizer rule which is Bayes with
respect to a least favorable peior. Thge truncated MLE is a
member of class \cal C of continuous peicewise-linear decision
rules with regions of either zero or unit slope. Rules from
this class are Bayes with respect to a corresponding class
of priors which have piecewise constnat densities. the equations
which determine a least favorable peior are derived and presented.
These results are shown to be valid for any symmetric distribution
with monotone likelihood ration.
The Case 2 problem, which is constrained by d/2 £ e1 < d £ e2 < 2d-
e1, is analyzed using zero-alpha-one loss. A solution
is obtained for a nominal Case 2 problem by modifying the technique
used for the Case 1 problem. A minimax rule is shown to be
discontinuous Bayes rule which equalizes the risk on a subset
ofQ. The Case 3 problem is analyzed
using a simplified form of multilevel loss which has minimax
solution in the class \cal C when certain constraints on the
loss function and distribution are satisfied. A method to approximate
a minimax rule for an arbitrary continuous bowl-shaped loss
function is developed using this same simplified form of multilevel
loss.
Finally, the behavior of minimax rules and least favorable
priors is examined for various shapes of loss functions and
sampling distributions. Evidence is presented which suggest
that when the scale parameter of the distribution approaches
zero, the minimax rules approach the truncated MLE, and the
envelope of theleast favorable priors approach the minimal
Fisher information prior independent of the shape of the loss
function and shope of the distribution.
MS-CIS-93-03 (GRAPHICS LAB 52)
A Gathering and Shooting Progressive Refinement Radiosity
Method
Min-Zhi Shao, Norman I. Badler
This paper presents a gathering and shooting progressive
refinement radiosity method. Our method integrates the iterative
process of light energy gathering used in the standard full
matrix method and the iterative process of light energy shooting
used in the conventional progressive refinement method. As
usual, in each iteration, the algorithm first selects the patch
which holds the maximum unprocessed light energy in the environment
as the shooting patch. But before the shooting process is activated,
a light energy gathering process takes place. In this gathering
process, the amount of the unprocessed light energy which is
supposed to be shot to the current shooting patch from the
rest of the environment in later iterations is pre-accumulated.
In general, this extra amount of gathered light energy is far
from trivial since it comes from every patch in the environment
from which the current shooting patch can be seen. However,
with the reciprocity relationship for form-factors, still only
one hemi-cube of the form-factors is needed in each iteration
step. Based on a concise record of the history of the unprocessed
light energy distribution in the environment, a new progressive
refinement algorithm with revised gathering and shooting procedures
is then proposed. With little additional computation and memory
usage compared to the conventional progressive refinement radiosity
method, a solid convergence speedup is achieved. This gathering
and shooting approach extends the capability of the radiosity
method in accurate and efficient simulation of the global illuminations
of complex environments.
MS-CIS-93-04 (LINC LAB 243)
VP Ellipsis and Semantic Identity
Daniel Hardt
While it is generally agreed that an elliptical Verb Phrase
must be identitical to its antecedent, the precise formulation
of the identity condition is controversial. I present a semantic
identity condition on VP ellipsis: the elided VP must have
the same meaning as its antecedent. I argue that a semantic
identity condition is superior to a syntactic condition on
both empirical and theoretical grounds. In addition, I show
that the proposed condition differs significantly from previously
proposed semantic conditions, in that other approaches do not
take into account the dynamic nature of semantic representation.
MS-CIS-93-05 (LINC 244)
An Algorithm for VP Ellipsis
Daniel Hardt
An algorithm is proposed to determine antecedents for VP
ellipsis. The algorithm eliminates impossible antecedents,
and then imposes a preference ordering on possible antecedents.
The algorithm performs with 94% accuracy on a set of 304 examples
of VP ellipsis collected from the Brown Corpus. The problem
of determining antecedents for VP ellipsis has received little
attention in the literature, and it is shown that the current
proposal is a significant improvement over alternative approaches.
MS-CIS-93-06 (LINC LAB 245)
VP Ellipsis and Contextual Interpretation
Daniel Hardt
A computational account of VP ellipsis is described, in which
VP's are represented in the discourse model as contextually
dependent semantic objects. It is argued that this approach
can handle examples that are not allowed by alternative accounts.
An implementation is defined in terms of extensions to the
Incremental Interpretation System. The treatment of VP ellipsis
is analogous to that of pronominal anaphora. It is suggested
that the recency and salience constraints commonly thought
to apply to pronominal anaphora might apply in a similar way
to VP ellipsis.
MS-CIS-93-07 (LOGIC & COMPUTATION 55) (DISTRIBUTED SYSTEMS
LAB 13)
A State Minimization Algorithm for Communicating State Machines
with Arbitrary Data Space
Inhye Kang, Insup Lee
A fundamental issue in the automated analysis of communicating
systems is the efficient generation of the reachable state
space. Since it is not possible to generate all the reachable
states of a system with an infinite number of states, we need
a way to combine sets of states. In this paper, we describe
communicating state machines with data variables, which we
use to specify concurrent systems. We then present an algorithm
that constructs the minimal reachability graph of a labeled
transition system with infinite data values. Our algorithm
clusters a set of states that are bisimilar into an equivalent
class. We include an example to illustrate our algorithm and
identify a set of sufficient conditions that guarantees the
termination of the algorithm.
MS-CIS-93-08 (LOGIC & COMPUTATION 56) (DISTRIBUTED SYSTEMS
LAB 14)
A Process Algebraic Approach To The Specification and Analysis
of Resource-Bound Real-time Systems
Insup Lee (University of Pennsylvania), Patrice Br 'e mond-Gr'e goire
(University of Pennsylvania), Richard Gerber (University
of Maryland)
There has recently been significant progress in the development
of timed process algebras for the specification and analysis
of real-time systems. This paper describes a timed process
algebra called ACSR. ACSR supports synchronous timed actions
and asynchronous instantaneous events. Timed actions are used
to represent the usage of resources and to model the passage
of time. Events are used to capture synchronization between
processes. To be able to accurately specify real systems, ACSR
supports a notion of priority that can be used to arbitrate
among timed actions competing for the use of resources and
among events that are ready for synchronization. The paper
also includes a brief overview of other timed process algebras
and discusses similarities and differences between them and
ACSR.
MS-CIS-93-09 (GRASP LAB 342)
Fast Parallel Deterministic and Randomized Algorithms for
Model Checking
Insup Lee, Sanguthevar Rajasekaran
Model checking is a powerful technique for verification of
concurrent systems. One of the potential problems with this
technique is state space explosion. There are two ways in which
one could cope with state explosion: reducing the search space
and searching less space. Most of the existing algorithms are
based on the first approach.
One of the sccuessful approach for reducing search space
uses Binary Decision Diagrames (BDDs) to represent the system.
Systems with a large number of states (of the order of 5 x
1020) have been thus verified. But there are limitations
to this heuristic approach. Even systems of reasonable complexity
have many more states. Also, the BDD apprach might fail even
on some simple systems. In this paper we propose the use of
parallelism to extend the applicability of BDDs in model checking.
In particular we present very fast algorithms for model checking
the employ BDDs. The algorithms presented are much faster than
the best known previous algorithms. We also describe searching
less space as an attractive approach to model checking. In
this paper we demonstrate the power of this approach. We also
suggest the use of randomization in the design of model checking
algorithms.
MS-CIS-93-10 (GRASP LAB 343)
Selection, Routing and Sorting On The Star Graph
Sanguthevar Rajasekaran, David S.L. Wei
We consider the problems of selection, routing and sorting
on an $n$-star graph (with n! nodes), an interconnection network
which has been proven to possess many special properties. We
identify a tree like subgraphc (which we call as a '(k, 1,
k) chain network') of the star graph which enables us to design
efficient algorithms for the above mentioned problems.
We present an algorithm that performs a sequence of n prefix
computations in O(n2) time. This algorithm is used
as a subroutine in our other algorithms. In additonal we offer
an efficient deterministic sorting algorithm that runs in O(n3 log
n)/2 steps. Though an algorithm with the same time bound has
been proposed before, our algorithm is very simple and is based
on a different approach. We also show that sorting can be performed
on the n star graph in time O(n3) and that selection
of a set of uniformaly distributed n keys can be performed
in O(n2) time with high probability. Finally, we
also present a deterministic (non oblivious) routing algorithm
that realizes any permutation in O(n3) steps on
the n-star graph.
There exists an algorithm in the literature that can perform
a single prefix computation in O(n logn) time. The best known
previous algorithm for sorting has a run time of O(n3 lg
n) and is deterministic. To our knowledge, the problem of selection
has not been considered before on the star graph.
MS-CIS-93-11 (GRASP LAB 344) (DISTRIBUTED SYSTEMS LAB 15)
Gigabit Telerobitcis: Applying Advanced Information Infrastructure
Ruzena Bajcsy, David J. Farber, Richard P. Paul, Jonathan
M. Smith
Advanced manufacturing concepts such as ``Virtual Factories''
use an information infrastructure to tie together changing
groups of specialized facilites to agile manufacturing systems.
A necessary element of such systems is the ability to teleoperate machines,
for example telerobotic systems with full-capability sensory
feeback loops. We have identified three network advances needed
for splitting robotic control from robotic function:
increased bandwidth, decreased error rates, and support for
isochronous traffic. These features are available in the Gigabit
networks under the development at Penn and elsewhere.
A number of key research questions are posed by gigabity
telerobotics. There are issues in network topology, robot control
and distributed system software, packaging and transport of
sensory data (including wide-area transport), and performance
implications of architectural choices using measures such as
cost, response time, and network utilization.
We propose the explore these question experimentally in
a joint research effort combining the Distributed Systems Laboratory
and the General Robotics and Sensory Perception (GRASP) Laboratory
at the University of Pennsylvania. The proposed experiments
should provide important early results. A detailed research
program is described.
MS-CIS-93-12 (GRAPHICS LAB 54)
A Kinematic Generalization of Rotoscoped Human Walking
Hyeongseok Ko, Norman I. Badler
The most prominent problems in utilizing the rotoscopy data
for human walking animation can be summarized as preservation
of the original motion characteristics in the generalization process
and constraint satisfaction. Generalization is the
process of producing the step of an arbitrary body and step
length from the original measured step 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 spatial motion characteristics as much as possible.
Two types of generalization are considered. One is the anthropometry
generalization, which handles the non-uniform segment
length ratio differences between the two bodies. The other
is the step length generalization, which changes
the steps to 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 within the generalization process.
MS-CIS-93-13 (GRAPHICS LAB 53)
Curved Path Human Locomotion that Handles Anthropometrical
Variety
Hyeongseok Ko, Norman I. Badler
Human locomotion simulation along a curved path is presented.
The process adds a small constant cost (O(1)) to any pre-existing
straight line walking algorithm. The input curve is processed
by the foot print generator to produce a foot print
sequence. The resulting sequence is scanned by the walking
motion generator that actually generates the poses of
the walking that realizes such foot prints. The two primitives INITIALISE_STEP and ADVANCE_STEP are
used for walking motion generation. INITIALIZE_STEP is
activated with the input parameters walker, next_foot_print , left_or_right,
and step_duration, just before each step to precompute
the trajectories of the center of the body and the ankles. ADVANCE_STEP
is called with a normalized time to generate the
actual pose at that moment. The normalized time is a logical
time, covering zero to one during a complete step.
MS-CIS-93-14 (LOGIC & COMPUTATION 57)
Inductive, Projective and Retractive Types
Brian T. Howard
We give an analysis of classes of recursive types by presenting
two extensions of the simply-typed lambda calculus. The first
language only allows recursive types with built-in principles
of well-founded induction, while the second allows more general
recursive types which permit non-terminating computations.
We discuss the expressive power of the languages, examine the
properties of reduction-based operational semantics for them,
and give examples of their use in expressing iteration over
large ordinals and in simulating both call-by-name and call-by-value
versions of the untyped lambda calculus. The motivations for
this work come from category theoretic models.
MS-CIS-93-15 (GRASP LAB 344)
Operator Interaction and Teleprogramming for Subsea Manipulation
Craig Sayers, Richard Paul, Max Mintz
The teleprogramming paradigm has been proposed as a means
to efficiently perform teleoperation in the subsea environment
via an acoustical link. In such a system the effects of both
limited bandwidth channels and delayed communications are overcome
by transmitting not Cartesian or joint level information but
rather symbolic, error-tolerant, program instructions to the
remote site. The operator interacts with a virtual reality
of the remote site which provides immediate visual and kinesthetic
feedback. The uncertainty in this model can be reduced based
on information received from the slave manipulator's tactile
contact with the environment. It is suggested that the current
state of the model be made available to the operator via a
graphical display which shows not only the position of objects
at the remote site but also, through the use of color clues,
the uncertainty associated with those positions. The provision
of uncertainty information is important since it allows the
operator to compromise between speed and accuracy. An additional
operator aid, which we term synthetic fixturing, is proposed.
Synthetic fixtures provide the operator of the teleprogramming
system with the teleoperation equivalent of the ``snap'' commands
common in computer aided design programs. By guiding the position
and/or orientation of the master manipulator toward specific
points, lines or planes the system is able to increase both
the speed and precision with which the operator can control
the slave arm without requiring sophisticated hardware.
MS-CIS-93-16 (LINC LAB 246)
The Relatedness and Comparative Utility of Various Approaches
To Operational Semantics
Raymond C. McDowell
We examine three approaches to operational semantics: transition
semantics, natural semantics, and reduction semantics. First
we compare the style and expressive power of the three forms
of semantics by using them to construct semantics for various
language features. Program abortion, interleaving, and block
structure particularly distinguish the three. Natural semantics
was very good at specifying ``large granularity'' features
such as blocks, but is apparently unable to capture interleaving
because of its ``small granularity''. On the other hand, transition
semantics and reduction semantics easily express ``small granularity''
features but have difficulty with ``large granularity'' features.
Reduction semantics provide especially concise specifications
of non-sequential control constructs such as abortion and interleaving.
We also analyze the utility of the different approaches for
two application areas: implementation correctness and type
soundness. For these two applications, natural semantics seems
to allow simpler proofs, although we do not generalize this
conclusion to other areas.
MS-CIS-93-17 (GRAPHICS LAB 54)
Intermittent Non-Rhythmic Human Stepping and Locomotion
Hyeongseok Ko, Norman I. Badler
There are many occasions where non-rhythmic stepping (NRS)
is more desirable than normal walking. This can be observed
in performing tasks in a narrow work space. For this purpose
NRS is considered as a variation of curved path walking. Four
types of local adjustment are dealt with: forward, backward,
lateral stepping, and turnaround. In the lower body motion,
the trajectory of the hip, angular trajectory of the feet,
and the trajectory of the swing ankle during the swing phase
determine the basic outline of an NRS. These trajectories are
precomputed in INITIALIZE_NRS before each NRS begins. ADVANCE_NRS is
called with a normalized time to generate
the actual pose of the NRS at that moment. The normalized time
is a logical time, covering zero to one during a complete step.
MS-CIS-93-18 (DISTRIBUTED SYSTEMS LAB 16)
Experimental Evaluation of an ATM Host Interface
C. Brendan S. Traw, Jonathan M. Smith
We have previously reported a design for a host interface
board intended to connect workstations to ATM networks, and
an implementation that was underway. Since then, we have
made some modifications to the hardware implementation, and
implemented software support. Our prototype connects an IBM
RS/6000 to a SONET-based ATM network carrying data at the
OC-3c rate of 155Mbps.
In this paper, we discuss an experimental evaluation
of the interface and supporting software. Our experiments
uncovered an unexpected bottleneck in providing high bandwidth
to application processes, and we suggest a number of possible
improvements to workstation architectures to address this
bottleneck.
MS-CIS-93-19 (DISTRIBUTED SYSTEMS LAB 17)
Cryptographic Support in A Gigabit Network
Jonathan M. Smith, C. Brendan S. Traw, David J. Farber
Many applications envisioned for ultra-high-speed networks
require cryptographic transformations for data in transit.
Security has often been an afterthought, and cryptographic
support has generally not kept pace with performance increases
in other network components. Two distinct experimental prototypes
of high-speed DES boards were built to understand architectural
issues in providing cryptographic support for the AURORA
gigabit testbed. Combining cryptographic support with the
host/network interface is indicated.
MS-CIS-93-20 (DISTRIBUTED SYSTEMS LAB 18)
An Overview of the Aurora Gigabit Testbed
David D. Clark, Bruce S. Davie, David J. Farber, Inder
S. Gopal, Bharath K. Kadaba, W. David Sincoskie, Jonathan
M. Smith, David L. Tennenhouse
AURORA is one of five U.S. testbeds charged with exploring
applications of, and technologies necessary for, networks
operating at gigabit per second or higher bandwidths. AURORA
is also an experiment in collaboration, where government
support (through the Corporation for National Research Initiatives,
which is in turn funded by DARPA and the NSF) has spurred
interaction among centers of excellence in industry, academia,
and government.
The emphasis of the AURORA testbed, distinct from the
other four testbeds, is research into the supporting technologies
for gigabit networking. Our targets include new software
architectures, network abstractions, hardware technologies,
and applications. This paper provides an overview of the
goals and methodologies employed in AURORA, and reports preliminary
results from our first year of research.
MS-CIS-93-21 (DISTRIBUTED SYSTEMS LAB 19)
The Software Design Laboratory
Jonathan M. Smith
Software Design Laboratory is an undergraduate practicum
in software design, which focuses on principles and practices
of large-scale software design. Concepts and examples borrowed
from elsewhere in Computer Science are applied to the construction
of a significant project, namely a command interpreter resembling
the Bourne shell. The course focus is on long-lived software
systems of a size requiring group effort. We therefore address
maintenance, testing, documentation, code readability, version
control, and group dynamics.
MS-CIS-93-22 (DISTRIBUTED SYSTEMS LAB 20)
Exploiting Parallelism in Hardware Implementation of
the DES
Albert G. Broscius, Jonathan M. Smith
The Data Encryption Standard algorithm has features which
may be used to advantage in parallelizing an implementation.
The kernel of the algorithm, a single round, may be decomposed
into several parallel computations resulting in a structure
with minimal delay. These rounds may also be computed in
a pipelined parallel structure for operations modes which
do not require cryptext feedback. Finally, system I/O may
be performed in parallel with the encryption computation
for further gain. Although several of these ideas have been
discussed before separately, the composite presentation is
novel.
MS-CIS-93-23 (DISTRIBUTED SYSTEMS LAB 21)
Reducing Host Load, Network Load, and Latency in a Distributed
Shared Memory
Ronald G. Minnich, David J. Farber
Mether is a Distributed Shared Memory (DSM) that runs
on Sun workstations under the SunOS 4.0 operating system.
User programs access the Mether address space in a way indistinguishable
from other memory. Mether had a number of performance problems
which we had also seen on a distributed shared memory called
Memnet. In this paper we discuss changes we made to Mether
and protocols we developed to use Mether that minimize host
load, network load, and latency. An interesting (and unexpected)
result was that for one problem we studied the same "best" protocol
for Mether is identical to the "best" protocol for MemNet.
The changes to Mether involve exposing an inconsistent
store to the application and making acdcess to the consistent
and inconsistent versions very convenient; providing both
demand-driven and data-driven semantics for updating pages;
and allowing the user to specify that only a small subset
of a page need be transferred. All of these operations are
encoded in a few address bits in the Mether virtual address.
MS-CIS-93-24 (DISTRIBUTED SYSTEMS LAB 22)
The Mether System: Distributed Shared Memory for SunOS
4.0
Ronald G. Minnich, David J. Farber
Mether is a Distributed Shared memory (DSM) that runs
on Sun workstations under the SunOS 4.0 operating system.
User programs access the Mether address space in a way indistinguishable
from other memory. Mether was inspired by the MemNet DSM,
but unlike MemNet Mether consists of software communicating
over a conventional Ethernet. The kernel part of Mether actually
does no data transmission over the network. Data transmission
is accomplished by a user-level server. The kernel driver
has no preference for a server, and indeed does not know
that servers exist. The kernel driver has been made very
safe, and in fact panic is not in its dictionary.
MS-CIS-93-25 (DISTRIBUTED SYSTEMS LAB 23)
Traffic Characteristics of A Distributed Memory System
Jonathan M. Smith, David J. Farber
We believe that many distributed computing systems of
the future will use distributed shared memory as a technique
for interprocess communication. Thus, traffic generated by
memory requests will be a major component of the traffic
for any networks which connect nodes in such a system. In
this paper, we study memory reference strings gathered with
a tracing program we devised. We study several models. First,
we look at raw reference data, as would be seen if the network
were a backplane. Second, we examine references in units
of "blocks", first using a one-block cache model and then
with an infinite cache. Finally, we study the effect of predictive
prepaging of these "blocks" on the traffic. We provide a
novel representation of memory reference data which can be
used to calculate interarrival distributions directly. Integrating
communication with computation can be used to control both
traffic and performance.
MS-CIS-93-26 (DISTRIBUTED SYSTEMS LAB 24)
Implementation and Performance of An ATM Host Interface
for Workstations
C. Brendan S. Traw, Jonathan M. Smith
This brief paper outlines our strategies for providing
a hardware and software solution to interfacing host to high-performance
networks. Our prototype implementation connects an IBM RS/6000
to a SONET-based ATM network carrying data at the OC-3c rate
of 155Mbps. We have measured application-to- network data
rates of up to 130 Mbps.
MS-CIS-93-27 (DISTRIBUTED SYSTEMS LAB 25)
Hardware/Software Organization of A High Performance
ATM Host Interface
C. Brendan S. Traw, Jonathan M. Smith
Concurrent increases in network bandwidths and processor
speeds have created a performance bottleneck at the workstation-to-network
host interface. This is especially true for BISDN networks
where the fixed length ATM cell is mismatched with application
requirements for data transfer; a successful hardware/software
architecture will resolve such differences and offer high
end-to-end performance.
The solution we report carefully splits protocol processing
functions into hardware and software implementations. The
interface hardware is highly parallel and performs all per-cell
functions with dedicated logic to maximize performance. Software
provides support for the transfer of data between the interface
and application memory, as well as the state management necessary
for virtual circuit setup and maintenance. In addition, all
higher level protocol processing is implemented with host
software.
The prototype connects an IBM RISC System/6000 to a SONET-based
ATM network carrying data at the OC-3c rate of 155 Mbps.
An experimental evaluation of the interface hardware and
software has been performed. Several conclusions about this
host interface architecture and the workstations it is connected
to are made.
MS-CIS-93-28 (DISTRIBUTED SYSTEMS LAB 26)
The AURORA Gigabit Testbed
David D. Clark, Bruce S. Davie, David J. Farber, Inder
S. Gopal, Bharath K. Kadaba, W. David Sincoskie, Jonathan
M. Smith, David L. Tennenhouse
AURORA is one of five U.S. networking testbeds charged
with exploring applications of, and technologies necessary
for, networks operating at gigabit per second or higher bandwidths.
The emphasis of the AURORA testbed, distinct from the other
four testbeds, BLANCA, CASA, NECTAR, and VISTANET, is research
into the supporting technologies for gigabit networking.
Like the other testbeds, AURORA itself is an experiment
in collaboration, where government initiative (in the form
of the Corporation for National Research Initiatives, which
is funded by DARPA and the National Science Foundation) has
spurred interaction among pre-existing centers of excellence
in industry, academia, and government.
AURORA has been charged with research into networking
technologies that will underpin future high-speed networks.
This paper provides an overview of the goals and methodologies
employed in AURORA, and points to some preliminary results
from our first year of research, ranging from analytic results
to experimental prototype hardware. This paper enunciates
our targets, which include new software architectures, network
abstractions, and hardware technologies, as well as applications
for our work.
MS-CIS-93-29 (DISTRIBUTED SYSTEMS LAB 27)
Developing Device Drivers for Character-Class MCA Adapters
in AIX, Version 3
Michael Massa
The purpose of this paper is to introduce the reader
to the concepts and techniques required to write a device
driver for a character class device on the Micro Channel
Architecture (MCA) bus in Version 3.xx of IBM's AIX operating
system (denoted by just AIX in this document). It attempts
to tie together the major pieces of development information
dispersed throughout the AIX manuals. It also includes some
information not found in the manuals which is crucial to
the development of a working device driver. This document
by no means provides complete coverage of the topic, and
references for further information will be made liberally
throughout. It may best be regarded as a road map to AIX
device driver development. The reader is assumed to be proficient
in UNIX/AIX applications programming and the C programming
language.
MS-CIS-93-30 (DISTRIBUTED SYSTEMS LAB 28)
A Host Interface Architecture and Implementation For
ATM Networks
Chandler Brendan Stanton Traw
The advent of high speed networks has increased demands
on processor architectures. These architectural demands are
due to the increase in network bandwidth relative to the
speeds of processor components. One important component for
a high-performance system is the workstation-to- network "host
interface". The solution presented in this thesis migrates
a carefully selected set of protocol processing functions
into hardware. The host interface is highly parallel and
all per cell functions are performed by dedicated logic to
maximize performance. There is a clean separation between
the interface functions, such as segmentation and reassembly,
and the interface/host communication. This architecture has
been realized in a prototype which connects an IBM RISC System/6000
workstation to a SONET-based ATM network carrying data at
the OC-3c rate of 155 Mbps.
MS-CIS-93-31 (DISTRIUBTED SYSTEMS LAB 29)
Experimental Evaluation Of A Video Capture Board For
Networked Workstations
Sanjay Kumar Udani
This thesis examines the architectural issues in the
design of a video capture board intended for use in multimedia
videoconferencing. The major issues examined are:
- Control of reception and transmission of multimedia
video streams
- Quality of service and service provision
- Compression requirements and solutions
- Data buffering and card connection strategies
- Handling multiple video streams
Results of measurements for prototype boards designed
and constructed at Penn are also given.
MS-CIS-93-32 (LOGIC & COMPUTATION 58)
Fixpoints and Bounded Fixpoints for Complex Objects
Dan Suciu
We investigate a query language for complex-object databases,
which is designed to (1) express only tractable queries,
and (2) be as expressive over flat relations as first order
logic with fixpoints. The language is obtained by extending
the nested relational algebra \cal NRA with a ``bounded fixpoint''
operator. As in the flat case, all PTime computable queries
over ordered databases are expressible in this language.
The main result consists in proving that this language is
a conservative extension of the first order logic with fixpoints,
or of the while-queries (depending on the interpretation
of the bounded fixpoint: inflationary or partial). The proof
technique uses indexes, to encode complex objects into flat
relations, and is strong enough to allow for the encoding
of \cal NRA with unbounded fixpoints into flat relations.
We also define a logic based language with fixpoints, the
``nested relational calculus'', and prove that its range
restricted version is equivalent to \cal NRA with bounded
fixpoints.
MS-CIS-93-33 (DISTRIBUTED SYSTEMS LAB 30)
Operating Systems Support for End-to-End Gbps Networking
Jonathan M. Smith, C. Brendan S. Traw
This paper argues that workstation host interfaces and
operating systems are a crucial element in achieving end-to-end
Gbps bandwidths for applications in distributed environments.
We describe several host interface architectures,discuss
the interaction between the interface and host operating
system, and report on an ATM host interface built at the
University of Pennsylvania.
Concurrently designing a host interface and software
support allows careful balancing of hardware and software
functions. Key ideas include use of buffer management techniques
to reduce copying and scheduling data transfers using clocked
interrupts. Clocked interrupts also aid with bandwidth allocation.
Our interface can deliver a sustained 130 Mbps bandwidth
to applications, roughly OC-3c link speed. Ninety-three percent
of the host hardware subsystem throughput is delivered to
the application with a small measured impact on other applications
processing.
MS-CIS-93-34 (DISTRIBUTED SYSTEMS LAB 31)
Revision of QoS Guarantees at the Application/Network
Interface
Klara Nahrstedt, Jonathan M. Smith
Connection management based on Quality of Service (QoS)
offers opportunities for better resource allocation in networks
providing service classes. "Negotiation" describes the process
of cooperatively configuring application and network resources
for an application's use. Complexx and long-running applications
can reduce the inefficiencies of static allocations by splitting
resource use into "eras" bounded by renegotiation of QoS
parameters. Renegotiation can be driven by either the application
or the network in order to best match application and network
dynamics. A key element in this process is a translation
between differing perspectives on QoS maintained by applications
and network service provision. We model translation with
an entity called a "broker".
MS-CIS-93-35 (DISTRIBUTED SYSTEMS LAB 32)
The Integrated Media Approach To Networked Multimedia
Systems
Klara Nahrstedt, Jonathan M. Smith
Applications which require real-time multimedia services[13]
face a number of difficult problems in the transmission of
multimedia information. Among the most difficult problems
are the heterogeneity of end nodes and the heterogeneity
of media Quality of Service (QoS) requirements. End nodes
typically consist of a computer and number of sensory input
and output devices, such as displays, microphones, and cameras.
QoS requirements[18] include degrees of reliability, jitter,
and delay.
We propose an intergrated approach to address these problems.
Multimedia input data comprise a sensory environment which
an application will make available; these data are packaged
together into an Integrated Multimedia Message (IMM). From
a received IMM, output data are selectively reproduced to
create another sensory environment. We propose an IMM format
and protocol behaviors for generation, presentation, and
synchronization of these messages.
While IMM's are aesthetically pleasing, well-suited to
proposed high- speed networks, and ease intramessage synchronization,
they are potentially plagued by the need to deliver QoS which
meets the worst-case requirements of all of their components[6].
We believe that this problem can be addressed, and are testing
that belief experimentally with the U. Penn Experimental
Multimedia Conferencing System, which will be embedded in
the AURORA Gigabit Testbed.
MS-CIS-93-36 (LOGIC & COMPUTATION 59)
Query Languages for Bags
Leonid Libkin, Limsoon Wong
MS-CIS-93-37 (LOGIC & COMPUTATION 60)
The Fast Fourier Transforms As A Database Query
Peter Buneman
By casting the discrete Fourier transform in comprehension
syntax and adding some primitives for ``array comprehensions'',
the fast Fourier transform may be derived by direct manipulation
of source code.
MS-CIS-93-38 (LOGIC & COMPUTATION 61)
DNA Workbench
James Tisdall
DNA WorkBench is a program for working with
DNA, RNA, and protein sequences. It is designed to solve
several problems that arise in two domains. The first domain
is that of the algorithm designer and implementor who is
working in the emerging field of computational biology. The
second domain is that of the worker in a genetics laboratory,
who needs frequently to turn to the computer to perform analysis
on existing or newly acquired nucleotide or protein sequences.
The problems encountered in these two domains overlap to
a considerable extent. The problems, and how they are addressed
by DNA WorkBench , are discussed within.
DNA WorkBench addresses both of these groups
with one program. In this way, new problems that require
new algorithms can be quickly brought from a theoretical
solution to an implementation and to the laboratory workbench.
This rapid transfer from research to development to the field
is essential in a fast moving area such as biotechnology,
by which term I mean to encompass such specialties as molecular
biology, genetics, human gene therapy, and the current large-scale
international sequencing and mapping of human DNA which has
been organized as the Human Genome Project in the United
States.
MS-CIS-93-39 (LINC LAB 247)
Generating Contextually Appropriate Intonation
Scott Prevost, Mark Steedman
One source of unnaturalness in the output of text-to-speech
systems stems from the involvement of algorithmically generated
default intonation contours, applied under minimal control
from syntax and semantics. It is a tribute both to the resilience
of human language understanding and to the ingenuity of the
inventors of these algorithms that the results are as intelligible
as they are. However, the result is very frequently unnatural,
and may on occasion mislead the hearer. This paper extends
earlier work on the relation between syntax and intonation
in language understanding in Combinatory Categorial Grammar
(CCG). A generator with a simple and domain-independent discourse
model can be used to direct synthesis of intonation contours
for responses to data-base queries, to convey distinctions
of contrast and emphasis determined by the discourse model.
MS-CIS-93-40 (GRASP LAB 345)
Model Based Teleoperation To Eliminate Feedback Delay
NSF Grant BCS89-01352 - 3rd Report
Richard P. Paul, Thomas Lindsay, Craig Sayers, Matthew
Stein, Desikachar Venkatesh
We are conducting research in the area of teleoperation
with feedback delay. Significant delays occur when performaing
space teleoperation from the earth as well as in subsea teleoperation
where the operator is typically on a surface vellel and communication
is via acoustic links. These delays make teleoperation extremely
difficult and lead to very low operator productivity.
We have combined computer graphics with manipulator programming
to provide a solution to the delay problem. A teleoperator
master arm is interfaced to a graphical simulation of the
remote environment. Synthetic fixtures are used to guid the
operators motions and to provide kinesthetic feedback. The
operator's actions are monitored and used to generate symbolic
motion commands for transmission to, and execution by, the
remote slave robot. While much of a task proceeds error free,
when an error does occur, the slave system transmits data
back to the master environment where the opertor can then
experience the motion of the slave manipulator in actural
task execution. We have also provided for the use of tools
such as an impact wrench and a winch at the slave site. In
all cases the tools are unencumbered by sensors; the slave
uses a compliant instrumented wrist to monitor tool operation
in terms of resulting motions and reaction forces.
MS-CIS-93-42 (LINC LAB 248)
An SE-tree based Characterization of the Induction Problem
Ron Rymon
Many induction programs use decision trees both as the
basis for their search, and as a representation of their
classifier solution. In this paper we propose a new structure,
called SE-tree, as a more general alternative.
MS-CIS-93-43 (DISTRIBUTED SYSTEMS LAB 33)
Host Interfacing at a Gigabit
C. Brendan S. Traw
A major goal of the host interface architecture which
has been developed at UPenn is to be sufficiently flexible
as to allow implementation using a range of technologies.
These technologies can provide the performace necessary for
operation in the emerging high bandwidth ATM networking environments.
This paper examines the feasibility of reimplementing the
current instantiation of the architecture which operates
at 160 Mbps to allow for operation in the 600+ Mbps domain.
MS-CIS-93-44 (LOGIC & COMPUTATION 63)
Sequentiality
Dan Suciu
This report contains an overview of concrete data structures,
sequential functions and sequential algorithms. We define
the notions of {\em concrete data structures} and prove the
representation theorem. Next, we present the notions of sequential
functions and of sequential algorithms, and show how the
latter can serve as a model for PCF. Finally, we present
the language CDS0, designed as a syntax for concrete data
structures and sequential algorithms
MS-CIS-93-45 (GRASP LAB 346)
Physics-Based Modeling, Analysis and Animation
Ioannis A. Kakadiaris
The idea of using physics-based models has received considerable
interest in computer graphics and computer vision research
the last ten years. The interest arises from the fact that
simple geometric primitives cannot accurately represent natural
objects. In computer graphics physics-based models are used
to generate and visualize constrained shapes, motions of
rigid and nonrigid objects and object interactions with the
environment for the purposes of animation. On the other hand,
in computer vision, the method applies to complex 3-D shape
representation, shape reconstruction and motion estimation.
In this paper we review two models that have been used
in computer graphics and two models that apply to both areas.
In the area of computer graphics, Miller uses a mass-spring
model to animate three forms of locomotion of snakes and
worms. To overcome the problem of the multitude of degrees
of freedom associated with the mass-spring lattices, Witkin
and Welch present a geometric method to model global deformations.
To achieve the same result Pentland and Horowitz in delineate
the object motion into rigid and nonrigid deformation modes.
To overcome problems of these two last approaches, Metaxas
and Terzopoulos in successfully combine local deformations
with global ones.
Modeling based on physical principles is a potent technique
for computer graphics and computer vision. It is a rich and
fruitful area for research in terms of both theory and applications.
It is important, though, to develop concepts, methodologies,
and techniques which will be widely applicable to many types
of applications.
MS-CIS-93-46 (LOGIC & COMPUTATION 64)
Realizability, Covers, and Sheaves I. Application to
the Simply-typed l -Calculus
Jean Gallier
We present a general method for proving properties of
typed l-terms. This method is
obtained by introducing a semantic notion of realizability
which uses the notion of a cover algebra (as in abstract
sheaf theory, a cover algebra being a Grothendieck topology
in the case of a preorder). For this, we introduce a new
class of semantic structures equipped with preorders, called
pre-applicative structures. These structures need not be
extensional. In this framework, a general realizability theorem
can be shown. Kleene's recursive realizability and a variant
of Kreisel's modified realizability both fit into this framework.
Applying this theorem to the special case of the term model,
yields a general theorem for proving properties of typed l,
in particular, strong normalization and confluence. This
approach clarifies the reducibility method by showing that
the closure conditions on candidates of reducibility can
be viewed as sheaf conditions. Part I of this paper applies
the above approach to the simply-typed l-calculus
(with types ®, ×, +, and ^). Part II of this paper deals with the second-order (polymorphic) l-calculus
(with types ® and ").
MS-CIS-93-47 (LOGIC & COMPUTATION 65)
Realizability, Covers and Sheaves II. Applications to
the Second-Order Typed $\lambda$-Calculus
Jean Gallier
We present a general method for proving properties of
typed l-terms. This method is
obtained by introducing a semantic notion of realizability
which uses the notion of a cover algebra (as in abstract
sheaf theory, a cover algebra being a Grothendieck topology
in the case of a preorder). For this, we introduce a new
class of semantic structures equipped with preorders, called
pre-applicative structures. These structures need not be
extensional. In this framework, a general realizability theorem
can be shown. Applying this theorem to the special case of
the term model, yields a general theorem for proving properties
of typed l-terms, in particular,
strong normalization and confluence. This approach clarifies
the reducibility method by showing that the closure conditions
on candidates of reducibility can be viewed as sheaf conditions.
Part II of this paper applies the above approach to the second-order
(polymorphic) l-calculus l®,"2 (with
types ® and ").
MS-CIS-93-48 (LOGIC & COMPUTATION 66)
Kripke Models for the Second-Orderl-Calculus
Jean Gallier
We define a new class of Kripke structures for the second-order l -calculus,
and investigate the soundness and completeness of some proof
systems for proving inequalities (rewrite rules) or equations.
The Kripke structures under consideration are equipped with
preorders that correspond to an abstract form of reduction,
and they are not necessarily extensional. A novelty of our
approach is that we define these structures directly as functors
A\colon\cal W® Preor equipped with certain natural transformations corresponding
to application and abstraction (where \cal W is a preorder,
the set of worlds, and Preor is the category of
preorders). We make use of an explicit construction of the
exponential of functors in the Cartesian-closed category Preor\cal
W, and we also define a kind of exponential ÕF(As)s Î T to
take care of type abstraction. We obtain soundness and completeness
theorems that generalize some results of Mitchell and Moggi
to the second-orderl -calculus,
and to sets of inequalities (rewrite rules).
MS-CIS-93-49 (LOGIC & COMPUTATION 67)
Reducibility Strikes Again, I!
Jean Gallier
In these notes, we prove some general theorems for establishing
properties of untyped l-terms,
using a variant of the reducibility method. These theorems
apply to (pure) l-terms typable
in the systems of conjunctive types \cal DO and \cal D. As
applications, we give simple proofs of the characterizations
of the terms having head-normal forms, of the normalizable
terms, and of the strongly normalizing terms. We also give
a characterization of the terms having weak head-normal forms.
This last result appears to be new.
MS-CIS-93-50 (GRASP LAB 347)
An Active Approach to Characterization and Recognition
of Functionality and Functional Properties
Luca Bogoni, Ruzena Bajcsy
Functionality in an object can be defined as its applicability
toward the accomplishment of a task. We emphasize and develop
an interactive and performatory approach to functionality
recovery from sensor data in the context of robotic manipulatory
tasks. By analyzing interaction of tool and target object
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. The representation of functionality allows us to
extend the recovery process to a hierarchy of functionalities
allowing complex ones to be composed from simpler ones.
A formal model, based on Discrete Event Dynamic System
Theory (DEDS), is introduced to define an interactive task
for recovering and describing functionality. To observe and
control the recovery process we introduce the notion of piecewise
observability of a task by different sensors. This allows
the description of a dynamic system in which not all events
nor the time of their occurrence may be predicted in advance.
An experimental system, with both vision and force sensors,
for carrying out the interactive functional recognition is
described.
MS-CIS-93-51 (LOGIC & COMPUTATION 68)
Feasible Computation Through Model Theory (Dissertation)
Anuj Dawar
The computational complexity of a problem is usually
defined in terms of the resources required on some machine
model of computation. An alternative view looks at the complexity
of describing the problem (seen as a collection of relational
structures) in a logic, measuring logical resources such
as the number of variables, quantifiers, operators, etc .
A close correspondence has been observed between these two,
with many natural logics corresponding exactly to independently
defined complexity classes. For the complexity classes that
are generally identified with feasible computation, such
characterizations require the presence of a linear order
on the domain of every structure, in which case the class
PTIME is characterized by an extension of first-order logic
by means of an inductive operator. No logical characterization
of feasible computation is known for unordered structures.
We approach this question from two directions. On the one
hand, we seek to accurately characterize the expressive power
of inductive logics over classes of structures where no linear
order is present. On the other hand, we study extensions
of inductive logic by means of generalized quantifiers to
determine if such extensions might exactly express the PTIME
properties. For the two investigations, we develop a common
set of tools and techniques, based on notions from model
theory. Basic notions, such as those of elementary equivalence
and element type are adapted to the context of finite relational
structures, in particular, by restricting the number of distinct
variables that can appear in any formula. We use these tools
to show that there is no extension of the inductive logic
be means of a finite number of generalized quantifiers that
exactly expresses the PTIME properties of finite relational
structures. We also show that, if there is any descriptive
characterization of the PTIME properties, indeed if the PTIME
properties are recursively indexable, then there is a characterization
by means of an extension of first-order logic by a uniform,
infinite sequence of generalized quantifiers. This is established
through a general result linking the recursive indexability
of a complexity class with the existence of complete problems
via weak logical reductions.
MS-CIS-93-52 (LINC LAB 249)
CLiff Notes: Research in the Language Information and
Computation Laboratory Annual Report--Spring 1993, No. 3
Faculty & Graduate Students
MS-CIS-93-53 (GRASP LAB 348)
Elastically Deforming A Three-Dimensional Atlas To Match
Anatomical Brain Images
Jim C. Gee, Martin Reivich, Ruzena Bajcsy
To evaluate our system for elastically deforming a three-dimensional
atlas to match anatomical brain images, six deformed versions
of an atlas were generated. The deformed atlases were created
by elastically mapping an anatomical brain atlas onto different
MRI brain image volumes. The mapping matches the edges of
the ventricles and the surface of the brain; the resultant
deformations are propagated through the atlas volume, deforming
the remainder of the structures in the process. The atlas
was then elastically matched to its deformed versions. The
accuracy of the resultant matches was evaluated by determining
the correspondence of 32 cortical and subcortical structures.
The system on average matched the centroid of a structure
to within 1 mm of its true position and fit a structure to
within 11% of its true volume. The overlap between the matched
and true structures, defined by the ratio between the volume
of their intersection and the volume of their union, averaged
66%. When the gray-white interface was included for matching,
the mean overlap improved to 78%; each structure was matched
to within 0.6 mm of its true position and fit to within 6%
of its true volume. Preliminary studies were also made to
determine the effect of the compliance of the atlas on the
resultant match.
MS-CIS-93-54 (GRAPHICS LAB 55)
Modeling Articulated Figure Motion With Physically-and
Physiologically-Based Constraints (Dissertation)
Philip L.Y. Lee
A methodology and algorithm are presented that generate
motions imitating the way humans complete a task under various
loading conditions. The path taken depends on ``natural''
parameters: the figure geometry, the given load, the final
destination, and, especially, the strength model of the agent.
Additional user controllable parameters of the motion are
the comfort of the action and the perceived exertion of the
agent. The algorithm uses this information to incrementally
compute a motion path of the end-effector moving the load.
It is therefore instantaneously adaptable to changing force,
loading, and strength conditions. Various strategies are
used to model human behavior (such as available torque, reducing
moment and pull back) that direct the trajectories. The strength
model dictates acceptable kinematic postures. The resulting
algorithm also offers torque control without the tedious
user expression of driving forces under a dynamics model.
The algorithm runs in near-real-time and offers an agent-dependent
toolkit for fast path prediction. Examples are presented
for various lifting tasks, including one- and two-handed
lifts, and raising the body from a seated posture.
MS-CIS-93-55 (GRAPHICS LAB 56)
Intermittent Non-Rhythmic Human Stepping and Locomotion
Hyeongseok Ko
When humans need to get from one location to another,
there are many occasions where non-rhythmic stepping (NRS)
is more desirable than normal walking. This can be observed
in performing tasks in a constricted work space. For the
purpose NRS is considered as a variation of curved path walking.
Four types of local adjustment are dealt with: forward, backward,
lateral stepping, and turnaround. Combined with curved path
walking, NRS provides a very useful tool for animating human
locomotion behaviors. In the lower body motion, the trajectory
of the hip, angular trajectory of the feet, and the trajectory
of the swing ankle during the swing phase determine the basic
outline of an NRS. These trajectories are precomputed at
the start of each step. The stepping process is called with
a {\em normalized time} to generate the actual pose of the
NRS at that moment. the normalized time is a logical time,
covering zero to one during a complete step.
MS-CIS-93-56 (LINC LAB 250)
Search Plans (Dissertation Proposal)
Michael Moore
People often do not know where things are and have to
look for them. This thesis presents a formal model suitable
for reasoning about how to find things and acting to find
them, which I will call ``search behavior''. Since not knowing
location of something can prevent an agent from reaching
its desired goal, the ability to plan and conduct a search
will be argued to increase the variety of situations in which
an agent can succeed at its chosen task.
Searching for things is a natural problem that arises
when the blocks world assumptions (which have been the problem
setting for most planning research) are modified by providing
the agent only partial knowledge of its environment. Since
the agent does not know the total world state, actions may
appear to have nondeterministic effects. The significant
aspects of the search problem which differ from previously
studied planning problems are the acquisition of information
and iteration of similar actions while exploring a search
space.
Since introduction of the situation calculus [McCarthy69],
various systems have been proposed for representing and reasoning
about actions which involve knowledge acquisition and iteration,
including Moore's work on the interaction between knowledge
and action [Moore80]. My concern with searching has to do
with a sense that Moore's knowledge preconditions are overly
restrictive. Morgenstern [Morgenstern88] examined ways to
weaken knowledge preconditions for an individual agent by
relying on the knowledge and abilities of other agents. Lesperance's
research [Lesperance91] on indexical knowledge is another
way of weakening the knowledge preconditions. I am trying
to reduce the {\em amount} of information an agent must know
(provided they can search a known search space). If you dial
the right combination to a safe it will open, whether or
not you knew in advance that it was the right combination.
Search is a way to guarantee you will eventually dial the
right combination. So what I am exploring is how to systematically
construct a search that will use available knowledge to accomplish
something the agent does not currently know enough to do
directly. Such systems can be used to infer properties of
plans which have already been constructed, but do not themselves
construct plans for complex actions.
I claim it is possible for automated agents to engage
in search behavior. Engaging in search behavior consists
in recognizing the need for a search, constructing an effective
plan, and then carrying out that plan. Expressing such a
plan and reasoning about its effectiveness requires a representation
language. I will select a representation language based on
criteria derived from analyzing the search planning problem.
Each of the three components of a system for engaging in
search behavior will be designed and implemented to demonstrate
that an automated agent can find things when it needs to.
MS-CIS-93-57 (LINC LAB 251)
Goal-Directed Diagnosis-Diagnostic Reasoning in Exploratory-Corrective
Domains
Ron Rymon
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-93-58 (GRASP LAB 349)
GRASP NEWS: Volume 9, Number 1
Faculty & Graduate Students
The past year at the GRASP Lab has been exciting and
productive period. As always, innovation and technical advancement
arising from past research has lead to unexpedcted questions
and fertile areas for new research. New robots, new mobile
platforsm, new sensors and cameras, and new personnel have
all contributed to the breathtaking pace of the change. Perhaps
the most significant change is the trend towards multi-disciplinary
projects, most notable the multi-agent project (see inside
for details on this, and all the other new and on-going project).
This issue of GRASP News covers the developments for the
year 1992 and the first quarter of 1993.
MS-CIS-93-59 (GRASP LAB 350)
The Soundness and Completeness of ACSR (Algebra of Communicating
Shared Resources)
Patrice Brémond-Grégoire
Recently, significant progress has been made in the development
of timed process algebras for the specification and analysis
of real-time systems; one of which is a timed process algebra
called ACSR supports synchronous timed actions and asynchronous
instantaneous events. Timed actions are used to represent
the usage of resources and to model the passage of time.
Events are used to capture synchronization between processes.
The be able to specify real systems accurately, ACSR supports
a notion of priority that can be used to arbitrate among
timed actions competing for the use of resources and among
events that are ready for synchronization. Equivalence between
ACSR terms is defined in terms of strong bisimulation. The
paper contains a set of algebraic laws that are proven sound
and complete for finite ACSR agents. This paper contains
the soundness and completeness proofs of the ACSR laws reported
in an earlier report (MS-CIS-93-08)
MS-CIS-93-60 (LOGIC & COMPUTATION 69)
Conservativity of Nested Relational Calculi with Internal
Generic Functions
Leonid Libkin, Limsoon Wong
It is known that queries in nexted relational calculus
are independent of the depth of set nesting in the intermediate
data and this remains true in the presence of aggregate functions.
We prove that this continues to be true if the calculus is
augmented with any internal generic family of functions.
MS-CIS-93-61 (LINC LAB 252)
Instructions, Intentions and Expectations
Bonnie Webber, Norman Badler, Barbara DiEugenio, Christopher
Geib, Libby Levison, Michael Moore
This is a short position paper on what we have learned
about the relationship between language and behavior from
an on-going attempt to enable people to use Natural Language
instructions to tell animated human figures what to do.
We view instructions as texts intended to be understood
in context, produced by an instructor who knows more than
the agent. (The latter means that instructions are worth
trusting, even if the world initially provides no corroborating
evidence.) With this view underlying the architecture of
our Animation from Natural Language ( AnimNL) system, the
paper discusses two main things we have learned about the
complex relationship between language and behavior:
- Intentions formed in response to instructions influence
agents' behavior at every level of decision-making, from
language understanding to motor control.
- Expectations formed in response to instructions influence
agents' behavior --- what they do and what they look for
--- over and beyond their current perceptions. As such,
expectations from instructions complement information from
the world in guiding an agent's behavior.
MS-CIS-93-62 (LOGIC & COMPUTATION 70)
Queries on Databases with User-Defined Functions
Dan Suciu
The notion of a database query is generalized for databases
with user-defined functions. Then, we can prove that the
computable queries coincide with those expressible by an
extension of the relational machine, with oracles ([4]).
This implies that any complete query language, extended with
user-defined function symbols in a ``reasonable'' way, is
still complete. We give an example of a complete query language
with user-defined functions, and discuss its connections
with object inventions.
MS-CIS-93-63 (GRAPHICS LAB 57)
SASS v.2.1: Anthropometric Spreadsheet and Database
for the IRIS
Francisco Azuola, Teo Kok Hoon, Sussana Wei
It describes the usage of SASS , a spreadsheet-like
system which allows flexible interactive access to all anthropometric
variables needed to size a computer-based human figure, described
structurally by a PEABODY file.
Data that may be accessed is organized into the following
``groups'': segment dimension (``girth''), joint limits,
center of mass, and strength, all of which work based on
statistical population data. SASS creates generic
computer-based human figures based on this data.
SASS also is an anthropometric database and
interactive query system that works upon anthropometric data
of real individuals. Scaled computer-based human figures
created by SASS can be displayed directly, and interactively
changed, within the Jack software.
MS-CIS-93-64 (LINC LAB 253)
A Model of Redundant Information in Dialogue: The Role
of Resource Bounds (Dissertation Proposal)
Marilyn A. Walker
The proposed thesis aims to contribute to current research
on cognitively and computationally accurate models of dialogue.
It investigates the use of informationally redundant utterances
(IRUs) in a corpus of problem-solving task-oriented dialogues.
An IRU is an utterance whose propositional content was already
added to the representation of the dialogue by the IRU's
antecedent, a previous utterance that realizes the same propositional
content as the IRU.
IRUs are clearly of linguistic interest since they appear
to be counter examples to the Gricean Maxim of Quantity.
Furthermore since communication is a subcase of action, the
existence of IRUs is a paradox because IRUs appear to be
actions whose effects have already been achieved.
An essential part of the proposed thesis is a distributional
analysis of IRUs in a large corpus of naturally occurring
problem solving dialogues. About 12% of the utterances in
the corpus are IRUs. The distributional analysis examines
the logical type of IRUs, the prosody of IRUs, and the co-occurrence
of IRUs with other indicators of discourse structure such
as cue words, and the location of the IRUS with respect to
its antecedent. IRUs include cases of presupposition affirmation,
and implicature reinforcement when the implicata is not said
by the same speaker in the same utterance.
I argue that IRUs can only be explained by a processing
model of dialogue that reflects agents' autonomy and limited
attentional and inferential capacity. IRUs can be classified
into three communicative functions and each of these functions
can be related to either agents' autonomy or limited processing
capacity:
- Attitude: to address the assumptions underlying the
inference of beliefs about mutual understanding and acceptance
- Consequence: to change the status of a belief from
an implicature to an entailment, or from an implicit belief
to an explicit one
- Attention: to manipulate the locus of attention of
the discourse participants by making or keeping a proposition
salient
Attitude is related to agent's autonomy. The treatment
of attitude has required the development of a model of mutual
beliefs based on Lewis's shared environment model of common
knowledge. The treatment of the communicative function of
Attention is based the interaction of this model of mutual
belief with Prince's taxonomy of information status and notions
such as given-s or salient. Finally the treatment of Consequence
also relies on developing the shared environment model of
mutual beliefs to capture aspects of agents' limited reasoning
ability. It isn't possible to use most existing semantics
models, based on possible world semantics, because they make
the simplifying assumption that agents are logically omniscient.
The explication of the paradox of IRUs has ramifications
for models of dialogue, the models of mutual belief that they
are based on and some basic tenets of the Gricean program. The
simulation experiments described here will provide an empirical
basis for the claim that discourse strategies that utilize IRUs
are more efficient than ones that don't when agents are modeled
as limited processors. Under these circumstances utterances that
are informationally redundant are not communicatively redundant,
demonstrating that the information exchange view of dialogue
is too narrow.
MS-CIS-93-65 (GRASP LAB 351)
Wide Bandwidth, Distributed, Digital Teleoperation
Venkatesh Desikachar, Matthew Stein, Richard Paul
Teleoperation means to perform a task at a distance.
The task is performed by a manipulator located at a remote
site, controlled by the master manipulator located in the
control room. The loop between the master and the slave manipulator
is closed by the human operator. the dexterity and manipulability
of the overall system has to be high such that the actions
can be easily carried out by the operator. A visual display
provides the operator a view of the slave arm and the task
environment, kinesthetic feedback provides a sense of physically
performing the task. Kinesthetic feedback is direct feedback
to the operator, while visual, audio, and other feedback
are indirect in nature. The displays generated from the video
data are very useful even when the quality of the image is
degraded. Changes in the camera position and orientation
can cause severe strain on the operator when interpreting
the viewed image. The corrections are applied to the position
and force transformations to reduce the strain on the operator.
The position and force data are communicated over a communication
channel from one station to the other. The use of communication
channel basically not designed for real time processes can
introduce significant delays leading to operator induced
instability of the teleoperator system. IN the presence of
such delays the force reflection as a non-reactive feedback
can help in maintaining the stability of the system. The
forces encountered by the slave manipulator is transformed
into audio range signals. The audio signal to the operator
is a reflection of force in a non-reactive manner. Advances
in high speed networks with increased bandwidth and decreased
error rates provide an opportunity to implement teleoperator
systems for long distance and distributed teleoperation.
A single operator from a control station can interact physically
with a system situated anywhere in the world and perform
the tasks as though he or she was present at the remote site.
A step by step implementation procedure of a direct teleoperator
system with communication between master and slave stations
through a computer network is described. the corrections
to the transforms to nullify the effect of change in viewing
parameters are discussed. The experimental results showing
the effectiveness of the change in camera orientations and
the comparison of active force reflection to the non-reactive
force reflection in the form of auditory signal is presented.
MS-CIS-93-66 (GRASP LAB 352)
Multiple Representation Approach To Geometric Model
Construction from Range Data
Visa Koivunen, Jean-Marc Vezien, Ruzena Bajcsy
A method is presented for constructing geometric design
data from noisy 3-D sensor measurements of physical parts.
In early processing phase, RLTS regression filters stemming
from robust estimation theory are used for separating the
desired part of the signal in contaminated sensor data from
undesired part. Strategies for producing a complete 3-D data
set from partial views are studied. Surface triangulation,
NURBS, and superellipsoids are employed in model construction
to be able to represent efficiently polygonal shapes, free
form surfaces and standard primitive solids. Multiple representations
are used because there is no single representation that would
be most appropriate in all situations. The size of the required
control point mesh for spline description is estimated using
a surface characterization process. Surfaces of arbitrary
topology are modeled using triangulation and trimmed NURBS.
A user given tolerance value is driving refinement of the
obtained surface model. The resulting model description is
a procedural CAD model which can convey structural information
in addition to low level geometric primitives. The model
is translated to IGES standard product data exchange format
to enable data sharing with other processes in concurrent
engineering environment. Preliminary results on view registration
and integration using simulated data are shown. Examples
of model construction using both real and simulated data
are also given.
MS-CIS-93-67 (LINC LAB 254)
Provability in TBLL: A Decision Procedure
Jawahar Chirimar (University of Pennsylvania), James
Lipton (Wesleyan University)
We prove the decidability of the Tensor-Bang fragment
of linear logic and establish upper (doubly exponential)
and lower (NP-hard) bounds.
MS-CIS-93-68 (GRASP LAB 353)
Simplifying Tool Usage In Teleoperative Tasks
Thomas Lindsay, Richard P. Paul
Modern robotic research has presented the opportunity
for enhanced teleoperative systems. Teleprogramming has been
developed for teleoperation in time-delayed environments,
but can also lead to increased productivity in non-delayed
teleoperation.
Powered tools are used to increase the abilities of the
remote manipulator. However, tools add to the complexity
of the system, both in terms of control and sensing. Teleprogramming
can be used to simplify the operators interaction with the
manipulator/tool system. Further, the adaptive sensing algorithm
of the remote site system (using an instrumented compliant
wrist for feedback) simplifies the sensory requirements of
the system. Current remote-site implementation of a teleprogramming
tool-usage strategy that simplifies tool use is described
in this document.
The use of powered tools in teleoperation tasks is illustrated
by two examples, ine using an air-powered impaced wrency,
and the other using an electric winch. both of these tools
are implemented at our remote site workcell, consisting of
a Puma 560 robot working on the task of removing the top
of a large box.
MS-CIS-93-69 (LINC LAB 255)
Verb Phrase Ellipsis: Form, Meaning and Processing (Dissertation)
Daniel Hardt
The central claim of this dissertation is that an elliptical
VP is a proform. This claim has two primary consequences:
first, the elliptical VP can have no internal syntactic structure.
Second, the interpretation of VP ellipsis must be governed
by the same general conditions governing other proforms,
such as pronouns. The basic condition governing the interpretation
of a proform is that it must be semantically identified with
its antecedent. A computational model is described in which
this identification is mediated by store and retrieve operations
defined with respect to a discourse model. Because VP ellipsis
is treated on a par with other proforms, the ambiguity arising
from ``sloppy identity'' becomes epiphenomenal, resulting
from the fact that the store and retrieve operations are
freely ordered.
A primary argument for the proform theory of VP ellipsis
concerns syntactic constraints on variables within the antecedent.
I examine many different types of variables, including reflexives,
reciprocals, negative polarity items, and wh-traces. In all
these cases, syntactic constraints are not respected under
ellipsis. This indicates that the relation governing VP ellipsis
is semantic rather than syntactic. In further support of
the proform theory, I show that there is a striking similarity
in the antecedence possibilities for VP ellipsis and those
for pronouns.
Two computer programs demonstrate the claims of this
dissertation. One program implements the semantic copying
required to resolve VP ellipsis, demonstrating the correct
set of possible readings for the examples of interest. The
second program selects the antecedent for a VP ellipsis occurrence.
This program has been tested on several hundred examples
of VP ellipsis, automatically collected from corpora.
MS-CIS-93-70 (LOGIC & COMPUTATION 71)
Algebraic Characterization of Edible Powerdomains
Leonid Libkin
Powerdomains like mixes, sandwiches, snacks and scones
are typically used to provide semantics of collections of
descriptions of partial data. In particular, they were used
to give semantics of databases with partial information.
In this paper we argue that to be able to put these constructions
into the context of a programming languages it is necessary
to characterize them as free (ordered) algebras. Two characterizations
-- for mixes and snacks -- are already known, and in the
first part of the paper we give characterizations for scones
and sandwiches and provide an alternative characterization
of snacks. The algebras involved have binary and unary operations
and relatively simple equational theories. We then define
a new construction, which is in essence all others put together
(hence called salad and give its algebraic characterization.
It is also shown how all algebras considered in the paper
are related in a natural way, that is, in a way that corresponds
to embeddings of their powerdomains. We also discuss some
semantic issues such as relationship between the orderings
and the semantics and justification for choosing the orderings.
Finally, we outline prospects for further research.
MS-CIS-93-71 (GRASP LAB 354)
Parallel Algorithms for Relational Coarsest Partition
Problems
Sanguthevar Rajasekaran, Insup Lee
Relational Coarsest Partition Problems (RCPPs) play a
vital role in verifying concurrent systems. It is known that
RCPPS are \cal P-complete and hence it may not be possible
to design polylog time parallel algorithms for these problems.
In this paper, we present two efficient parallel algorithms
for RCPP, in which its associated label transition system
is assumed to have m transitions and n states.
The first algorithm runs in O(n1+Î time
using [m/(n Î )] CREW
PRAAM processors, for any fixed Î < 1.
This algorithm is analogous and optimal with respect to the
sequential algorithm of Kanellakis and Smolka. the second
algorithm runs in O(n log n) time using [m/n] log n CREW
PRAM processor. this algorithm is analogous and nearly optimal
with respect to the sequential algorithm of Paige and Tarjan.
MS-CIS-93-72 (GRASP LAB 355)
Fast Parallel Routing and Computation On Interconnection
Networks (Dissertation)
David Shyue Liang Wei
Both parallel processing and artificial intelligence
play important roles in computer science. The application
of parallel processing in artificial intelligence is one
of the possible approaches to realize an efficient and intelligent
computer. This is a two-part thesis. The first part of this
thesis investigates routing problems, which are central to
parallel processing, for a class of interconnection networks
called leveled networks, while the second part of the thesis
makes use of these results to develop efficient parallel
algorithms for some communication intensive artificial intelligence
problems. Specifically, we look at the parsing problem for
natural language grammars which is a fundamental problem
in artificial intelligence. Our work goes beyond theoretical
study on routing and parallel algorithms in the we also develop
implementations of the algorithms on an actual parallel machine,
viz., the Connection Machine(CM). This allows us to verify
experimentally the performance predicted by theoretical analysis.
To date, much of the work on routing has virtually centered
on constant degree networks with logarithmic (or even larger)
diameter. In order to achieve faster communication, we initiate
the study of routing on some non-constant degree networks
in sublogarithmic diameter. We also give a universal randomized
optimal routing algorithm for a large class of interconnection
networks, viz., leveled networks. These leveled networks
can be of logarithmic, or sublogarithmic diameter. Further,
we present algorithms for emulating PRAMs, and ideal shared
memory model, on leveled networks. The emulation is optimal.
|