E1AR0002@SMUVM1.BITNET (03/02/86)
:pages 90
:keywords causal reasoning, VLSI, qualitative physics, design
automation, qualitative circuit simulation, representation of
knowledge, circuit theory, problem solving, expert systems
:abstract
With the push towards sub-micron technology, transistor models have
become increasingly complex. The number of components in integrated
circuits has forced designer's efforts and skills towards higher
levels of design. This has created a gap between design expertise and
the performance demands increasingly imposed by the technology. To
alleviate this problem, software tools must be developed that provide
the designer with expert advice on circuit performance and design.
This requires a theory that links the intuitions of an expert circuit
analyst with the corresponding principles of formal theory (i.e.,
algebra, calculus, feedback anaylsis, network theory, and
electrodynamics), and that makes each underlying assumption explicit.
Temporal Qualitative Analysis is a technique for analyzing the
qualitative large signal behavior of MOS circuits that straddle the
line between the digital and analog domains. Temporal Qualitative
Analysis is based on the following four components: First, a
qualitative representation is composed of a set of open regions
separated by boundaries. These boundaries are chosen at the
appropriate level of detail for the analysis. This concept is used in
modeling time, space, circuit state variables, and device operating
regions. Second, constraints between circuit state variables are
established by circuit theory. At a finer time scale, the designer's
intuition of electrodynamics is used to impose a causal relationship
among these constraints. Third, large signal behavior is modeled by
Transition Analysis, using continuity and theorems of calculus to
determine how quantities pass between regions over time. Finally,
Feedback Analysis uses knowledge about the structure of equations and
the properties of structure classes to resolve ambiguities.
:tr 789
:author Kenneth D. Forbus
:asort Forbus, K.D.
:title Qualitative Process Theory
:date July 1984
:cost $7.00
:pages 179
:keywords qualitative reasoning, common sense reasoning, naive
physics, artificial intelligence, problem solving, mathematical
reasoning
:abstract
Objects move, collide, flow, bend, heat up, cool down, stretch,
compress, and boil. These and other things that cause changes in
objects over time are intuitively characterized as {\it processes}.
To understand common sense physical reasoning and make programs that
interact with the physical world as well as people do we must
understand qualitative reasoning about processes, when they will
occur, their effects, and when they will stop. Qualitative Process
theory defines a simple notion of physical process that appears useful
as a language in which to write dynamical theories. Reasoning about
processes also motivates a new qualitative representation for quantity
in terms of inequalities, called the {\it quantity space}. This report
describes the basic concepts of Qualitative Process theory, several
different kinds of reasoning that can be performed with them, and
discusses its impact on other issues in common sense reasoning about
the physical world, such as causal reasoning and measurement
interpretation. Several extended examples illustrate the utility of
the theory, including figuring out that a boiler can blow up, that an
oscillator with friction wil eventually stop, and how to say that you
can pull with a string, but not push with it. This report also
describes GIZMO, an implemented computer program which uses
Qualitative Process theory to make predictions and interpret simple
measurements. The representations and algorithms used in GIZMO are
described in detail, and illustrated using several examples.
:tr 791
:author Bruce R. Donald
:asort Donald, B.R.
:title Motion Planning with Six Degrees of Freedom
:date May 1984
:cost $7.00
:pages 261
:ADnum AD-A150312g
:keywords motion planning, robotics, path planning, configuration
space, obstacle avoidance, spatial reasoning, geometric modelling,
piano mover's problem, computational geometry, applied differential
topology, Voronoi diagram
:abstract
The motion planning problem is of central importance to the fields of
robotics, spatial planning, and automated design. In robotics we are
interested in the automatic synthesis of robot motions, given
high-level specifications of tasks and geometric models of the robot
and obstacles. The "Mover's" problem is to find a continuous,
collision-free path for a moving object through an environment
containing obstacles. We present an implemented algorithm for the
"classical" formulation of the three-dimensional Mover's problem:
Given an arbitrary rigid polyhedral moving object "P" with three
translational and three rotational degrees of freedom, find a
continuous, collision-free path taking "P" from some initial
configuration to a desired goal configuration. This thesis describes
the first known implementation of a complete algorithm (at a given
resolution) for the full six degree of freedom Mover's problem. The
algorithm transforms the six degree of freedom planning problem into a
point navigation problem in a six-dimensional configuration space
(called C-space). The C-space obstacles, which characterize the
physically unachievable configurations, are directly represented by
six-dimensional manifolds whose boundaries are five dimensional C-surfaces.
:tr 793
:author Daniel Sabey Weld
:asort Weld, D.S.
:title Switching Between Discrete and Continuous Process Models to Predict Genet
ic Activity
:date May 1984
:cost $5.00
:pages 83
:keywords QP theory, simulation, aggregation, multiple representations
:abstract
Two kinds of process models have been used in programs that reason
about change: discrete and continuous models. We describe the design
and implementation of a qualitative simulator, PEPTIDE, which uses
both kinds of process models to predict the behavior of molecular
genetic systems. The program uses a discrete process model to simulate
both situations involving abrupt changes in quantities and the actions
of small numbers of molecules. It uses a continuous process model to
predict gradual changes in quantities. A novel technique, called
aggregation, allows the simulator to switch between these models
through the recognition and summary of cycles. The flexibility of
PEPTIDE's aggregator allows the program to detect cycles within cycles
and predict the behavior of complex situations.
:tr 794
:author Eugene C. Ciccarelli IV
:asort Ciccarelli, E.
:title Presentation Based User Interfaces
:date August 1984
:cost $7.00
:pages 196
:keywords user interfaces, presentation systems, programming tools,
display, editor
:abstract
A prototype {\it presentation system base} is described. It offers
mechanisms, tools, and ready-made parts for building user interfaces. A
general user interface mode underlies the base, organized around the
concept of a {\it presentation}: a visible text or graphic form
conveying information. The base and model emphasize domain
independence and style independence, to apply to the widest possible
range of interfaces. The {\it primitive presentation system model}
treats the interface as a system of processes maintaining a semantic
relation between an {\it application data base} and a {\it
presentation data base}, the symbolic screen description containing
presentations. A {\it presenter} continually updates the presentation
data base from the application data base. The user manipulates
presentations with a {\it presentation editor}. A {\it recognizer}
translates the user's presentation manipulation into application data
base commands. The primitive presentation system can be extended to
model more complex systems by attaching additional presentation
systems. In order to illustrate the model's generality and descriptive
capabilities, extended model structures for several existing user
interfaces are discussed. The base provides support for building the
application and presentation data bases, linked together into a
single, uniform network, including descriptions of classes of objects
as well as the objects themselves. The base provides an initial
presentation data base network, graphics to continuously display it,
and editing functions. A variety of tools and mechanisms help create
and control presenters and recognizers. To demonstrate the base's
utility, three interfaces to an operating system were constructed,
embodying different styles: icon, menu, and graphical annotation.
:tr 807
:author Andrew Lewis Ressler
:asort Ressler, A.L.
:title A Circuit Grammar for Operational Amplifier Design
:date January 1984
:cost $6.00
:pages 92
:keywords artificial intelligence, computer aided design, grammar,
operational amplifier, circuit, design, language
:abstract
Electrical circuit designers seldom create really new topologies or use
old ones in a novel way. Most designs are known combinations of
common configurations tailored for the particular problem at hand. In
this thesis I show that much of the behavior of a designer engaged in
such ordinary design can be modelled by a clearly defined
computational mechanism executing a set of stylized rules. Each of my
rules embodies a particular piece of the designer's knowledge. A
circuit is represented as a hierarchy of abstract objects, each of
which is composed of other objects. The leaves of this tree represent
the physical devices from which physical circuits are fabricated. By
analogy with context-free languages, a class of circuits is generated
by a phrase-structure grammar of which each rule describes how one
type of abstract object can be expanded into a combination of more
concrete parts. Circuits are designed by first postulating an abstract
object which meets the particular design requirements. This object is
then expanded into a concrete circuit by successive refinement using
rules of my grammar. There are in general many rules which can be used
to expand a given abstract component. Analysis must be done at each
level of the expansion to constrain the search to a reasonable set.
Thus the rules of my circuit grammar provide constraints which allow
the approximate qualitative analysis of partially instantiated
circuits. Later, more careful analysis in terms of more concrete
components may lead to the rejection of a line of expansion which at
first looked promising. I provide special failure rules to direct the
repair in this case. As part of this research I have developed a
computer program , CIROP, which implements my theory in the domain of
operational amplifier design.
:tr 810
:author Michael Andreas Erdmann
:asort Erdmann, M.A.
:title On Motion Planning with Uncertainty
:date August 1984
:cost $7.00
:pages 261
:keywords motion planning, mechanical assembly, parts mating,
robotics, configuration space, friction, compliance, uncertainty
:abstract
Robots must successfully plan and execute tasks in the presence of
uncertainty. Uncertainty arises from errors in modelling, sensing, and
control. Planning in the presence of uncertainty constitutes one facet
of the general motion planning problem in robotics. This problem is
concerned with the automatic synthesis of motion strategies from high
level task specifications and geometric models of environments. In
order to develop successful motion strategies, it is necessary to
understand the effect of uncertainty on the geometry of object
interactions. Object interactions, both static and dynamic, may be
represented in geometrical terms. This thesis investigates geometrical
tools for modelling and overcoming uncertainty. The thesis describes
an algorithm for computing backprojections of desired task
configurations. Task goals and motion states are specified in terms of
a moving object's configuration space. Backprojections specify regions
in configuration space from which particular motions are guaranteed to
accomplish a desired task. The back projection algorithm considers
surfaces in configuration space that facilitate sliding towards the
goal, while avoiding surfaces on which motions may prematurely halt.
In executing a motion from a backprojection region, a plan executor
must be able to recognize that a desired task has been accomplished.
Since sensors are subject to uncertainty, recognition of task success
is not always possible. The thesis considers the structure of
backprojection regions and of task goals that ensures goal
recognizability. The thesis also develops a representation of friction
in configuration space, in terms of a friction cone analogous to the
real space friction cone. The friction cone provides the
backprojection algorithm with a geometrical tool for determining
points at which motions may halt.
:tr 834
:author Peter Merrett Andreae
:asort Andreae, P.M.
:title Justified Generalization: Acquiring Procedures From Examples
:date January,1985
:cost $6.00
:pages 161
:adnum AD-A156408
:keywords machine learning, constraining generalization, justification of
generalization.
:abstract
This thesis describes an implemented system called NODDY for
acquiring procedures from examples presented by a teacher. Acquiring
procedures from examples involves several different generalization
tasks. Generalization is an underconstrained task, and the main issue
of machine learning is how to deal with this underconstraint. The
thesis presents two principles for constraining generalization on
which NODDY is based. The first principle is to exploit domain based
constraints. NODDY demonstrates how such constraints can be used both
to reduce the space of possible generalizations to manageable size,
and how to generate negative examples out of positive examples to
further constrain the generalization. The second principle is to avoid
spurious generalizations by requiring justification before adopting a
generalization. NODDY demonstrates several different ways of
justifying a generalization and proposes a way of ordering and
searching a space of candidate generalizations based on how much
evidence would be required to justify each generalization. Acquiring
procedures also involves three types of constructive generalization:
inferring loops (a kind of group), inferring complex relations and
state variables, and inferring predicates. NODDY demonstrates three
constructive generalization methods for these kinds of generalization.
:tr 844
:unavailable
:author Gul Agha
:asort Agha, G.
:title Actors: A Model of Concurrent Computation In Distributed Systems
:date June,1985
:pages 198
:keywords distributed systems, concurrency, programming languages,
object-oriented programming, deadlock, semantics of programs, process
architectures, functional programming
:tr 852
:title Local Rotational Symmetries
:author Margaret Morrison Fleck
:asort Fleck, M.M.
:date August 1985
:pages 156
:cost $6.00
:keywords shape representation, computer vision, artificial intelligence,
smoothed local symmetries, local symmetries, multiple-scale representations,
hierarchical representations, rotational symmetries, round regions
:abstract
This thesis describes a representation for the two-dimensional round
regions called Local Rotational Symmetries. Local Rotational
Symmetries are intended as a companion to Brady's Smoothed Local
Symmetry Representation for elongated shapes. An algorithm for
computing Local Rotational Symmetry representations at multiple scales
of resolution has been implemented and results of this implementation
are presented. These results suggest that Local Rotational Symmetries
provide a more robustly computable and perceptually accurate
description of round regions than the previous proposed
representations. In the course of developing this representation, it
has been necessary to modify the way both Smoothed Local Symmetries
and Local Rotational Symmetries are computed. First, grey scale image
smoothing proves to be better than boundary smoothing for creating
representations at multiple scales of resolution, because it is more
robust and it allows qualitative changes in representation between
scales. Secondly, it is proposed that shape representations at
different scales be explicitly related, so that information can be
passed between scales and computation at each scale can be kept local.
Such a model for multi-scale computation is desirable both to allow
efficient computation and to accurately model human perceptions.
:tr 859
:author Anita M. Flynn
:asort Flynn, A.M.
:title Redundant Sensors for Mobile Robot Navigation
:date September 1985
:pages 70
:cost $5.00
:adnum AD-A161087
:keywords mobile robot, sensors, path planning, navigation, map making
:abstract
Redundant sensors are needed on a moblie robot so that the accuracy
with which it perceives its surroundings can be increased. Sonar and
infrared sensors are used here in tandem, each compensating for
deficiencies in the other. The robot combines the data from both
sensors to build a representation which is more accurate than if
either sensor were used alone. Another representation, the curvature
primal sketch, is extracted from this perceived workspace and is used
as the input to two path planning programs: one based on configuration
space and one based on a generalized cone formulation of free space.
:tr 860
:author Jose Luis Marroquin
:asort Marroquin, J.L.
:title Probabilistic Solution of Inverse Problems
:date September 1985
:pages 206
:cost $7.00
:adnum AD-A161130
:keywords inverse problems, computer vision, surface interpolation,
image restoration, Markov random fields, optimal estimation, simulated
annealing
:abstract
In this thesis we study the general problem of reconstructing a
function, defined on a finite lattice, from a set of incomplete, noisy
and/or ambiguous observations. The goal of this work is to demonstrate
the generality and practical value of a probabilistic (in particular,
Bayesian) approach to this problem, particularly in the context of
Computer Vision. In this approach, the prior knowledge about the
solution is expressed in the form of a Gibbsian probability
distribution on the space of all possible functions, so that the
reconstruction task is formulated as an estimation problem.
------------------------
Books and Manuals
------------------------
= These items are available from the publishers =
Abelson, Harold, and Gerald Jay Sussman. {Structure and Interpretation
of Computer Programs}. Cambridge, MA.: MIT Press, 1984.
{Barriers to Equality in Academia: Women in Computer Science at MIT}.
Prepared by female graduate students and research staff in the
Laboratory for Computer Science and the Artificial Intelligence
Laboratory at MIT. February, 1983. Available from MIT Lab for
Computer Science.
Berwick, Robert C.. {The Acquisition of Syntactic Knowledge}. Cambridge,
MA.: MIT Press, 1985.
Berwick, Robert C., and Amy Weinberg. {The Grammatical Basis of
Linguistic Performance: Language Use and Acquisition}. Cambridge, MA.:
MIT Press, 1984.
Brady, J. Michael, and Robert C. Berwick. {Computational Models of
Discourse}. Cambridge, MA.: MIT Press, 1983.
Brady, J. Michael, ed. {Computer Vision}. Amsterdam: North-Holland, 1982.
Brady, J. Michael, John Hollerbach, Timothy Johnson, Tomas
Lozano-Perez, and Matthew T. Mason, eds. {Robot Motion: Planning and
Control}. Cambridge, MA.: MIT Press, 1982.
Brady, J. Michael. {The Theory of Computer Science: A Programming
Approach}. London: Chapman and Hall, 1977.
Brooks, Rodney A. {Programming in Common Lisp}. New York: John Wiley
and Sons, 1985.
Davis, Randall, and Douglas B. Lenat. {Knowledge-Based Systems in
Artificial Intelligence}. New York: McGraw-Hill, 1982.
DiSessa, Andrea, and Harold Abelson. {Turtle Geometry: The Computer as
a Medium for Exploring Mathematics}. Cambridge, MA.: MIT Press, 1981.
Fahlman, Scott E. {NETL: A System for Representing and Using
Real-World Knowledge}. Cambridge, MA.: MIT Press, 1979.
Grimson, W.E.L. {From Images to Surfaces: A Computational Study of the
Human Early Visual System}. Cambridge, MA.: MIT Press, 1981.
Hildreth, Ellen C. {The Measurement of Visual Motion}. (ACM
Distinguished Dissertation Series.) Cambridge, MA.: MIT Press, 1984.
Hillis, W. Daniel. {The Connection Machine}. Cambridge, MA.: MIT Press,
1985.
Marcus, Mitchell P. {A Theory of Syntactic Recognition for Natural
Language}. Cambridge, MA.: MIT Press, 1980.
Mason, Matthew T., and J. Kenneth Salisbury, Jr. {Robot Hands and the
Mechanics of Manipulation}. Cambridge, MA.: MIT Press, 1985.
Mason, Matthew T., and J. Kenneth Salisbury, Jr. {Dextrous Robot Hand
Videotape}. Cambridge, MA.: MIT Press, 1985.
Minsky, Marvin. {Computation}. Englewood Cliffs, NJ.: Prentice Hall,
1967.
Minsky, Marvin. {Robotics}. New York: Anchor Press Doubleday, 1985.
Minsky, Marvin, and Seymour Papert. {Perceptrons}. Cambridge, MA.: MIT
Press, 1968.
Minsky, Marvin, ed. {Semantic Information Processing}. Cambridge, MA.:
MIT Press, 1968.
Moore, Robert C. {Reasoning from Incomplete Knowledge in a Procedural
Deduction System}. New York: Garland Publishing, 1979.
Papert, Seymour, and Robert McNaughton. {Counter-Free Automata}.
Cambridge, MA.: MIT Press, 1971.
Stallman, Richard M. {EMACS Manual}, (AIM 555). MIT Artificial
Intelligence Laboratory, March 1983. Available from the AI Laboratory
Publications Office at a cost of $3.50, prepaid.
Stallman, Richard M., David Moon, and Daniel Weinreb. {Window System
Manual}. MIT Artificial Intelligence Laboratory, August 1983, Edition
1.1, System Version 95. Available from the AI Laboratory Publications
Office at a cost of $7.00, prepaid.
Stallman, Richard M. {ZMail Manual}. MIT Artificial Intelligence
Laboratory, Zmail Version, April 1983, First Edition. Available from
the AI Laboratory at a cost of $6.00, prepaid.
Sussman, Gerald. {A Computer Model of Skill Acquisition}. New
York: Elsevier Science, February 1975. (Out of print).
Ullman, Shimon. {The Interpretation of Visual Motion}. Cambridge,
MA.: MIT Press, 1979.
Weinreb, Daniel, David Moon, and Richard Stallman. {LISP Machine
Manual}. MIT Aritificial Intelligence Laboratory, revised, June,
1984. Sixth Edition. Available from the AI Laboratory at a cost of
$20.00, prepaid.
Winograd, Terry. {Understanding Natural Language}. New York: Academic
Press, 1972.
Winston, Patrick H., and Karen Prendergast. {The A.I. Business: The
Commercial Uses of Artificial Intelligence}. Cambridge, MA.: MIT
Press, 1984.
Winston, Patrick H. {Artificial Intelligence}, 2nd ed. Reading, MA.:
Addison-Wesley, 1984.
Winston, Patrick H., and Richard H. Brown, eds. {Artificial
Intelligence: An MIT Perspective}. 2 volumes. Cambridge, MA.: MIT
Press, 1979.
Winston, Patrick H., and Berthold K.P. Horn. {LISP}, 2nd ed. Reading,
MA.: Addison-Wesley, 1984.
Winston, Patrick H., ed. {The Psychology of Computer Vision}. New
York: McGraw-Hill, 1975. (Out of print).
-------