E1AR0002@SMUVM1.BITNET (10/29/86)
\documentstyle{article}
\textwidth 6in
\textheight 8.5in
\topmargin -24pt
\oddsidemargin 18pt
\begin{document}
\noindent TECHNICAL NOTE: 73\hfill PRICE: \$40.00\\[0.01in]
\noindent TITLE: QA4: A PROCEDURAL CALCULUS FOR INTUITIVE REASONING\\
AUTHORS: J. F. RULIFSON, J. A. DERKSEN, and R. J. WALDINGER\\
DATE: NOVEMBER 1972\\[0.01in]
ABSTRACT: This report presents a language, called QA4, designed
to facilitate the construction of problem-solving systems used for
robot planning, theorem proving, and automatic program synthesis and
verification. QA4 integrates an omega-order logic language with
canonical composition, associative retrieval, and pattern matching of
expressions; process-structure programming; goal-directed searching;
and demons. Thus it provides many useful programming aids. More
importantly, however, it provides a semantic framework for common
sense reasoning about these problem domains. The interpreter for the
language is extraordinary general, and is therefore an adaptable tool
for developing the specialized techniques of intuitive, symbolic
reasoning used by the intelligence system.
Chapter One is an informal introduction to the unusual
programming concepts available in the QA4 language. Chapter Two is a
primer for the language. It informally presents the language through
the use of examples. Most of the unusual or complicated features of
the language are not discussed. The chapter concludes with a
presentation of a small robot planning system that uses only the
language features presented in the chapter. Chapter Three presents a
series of examples chosen to illustrate solutions to automatic
programming problems. The QA4 programs used in Chapter Three rely on
language features not presented in the primer. They are, however,
explained as they occur. These programs illustrate most of the
programming concepts just discussed. Chapter Four is a complete
reference guide to the language. It provides the semantics of all the
features of the language together with many implementation notes and
design rationale. Chapter Five discusses extensions to the language
that will probably be done during the next year.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
\noindent TECHNICAL NOTE: 86\hfill PRICE: \$20.00\\[0.01in]
\noindent TITLE: REASONING ABOUT PROGRAMS\\
AUTHORS: R. J. WALDINGER and K. N. LEVITT\\
DATE: OCTOBER 1973\\[0.01in]
ABSTRACT: This paper describes a theorem prover that embodies
knowledge about programming constructs, such as numbers, arrays,
lists, and expressions. The program can reason about these concepts
and is used as part of a program verification system that uses the
Floyd-Naur explication of program semantics. It is implemented in the
QA4 language; the QA4 system allows many pieces of strategic
knowledge, each expressed as a small program, to be coordinated so
that a program stands forward when it is relevant to the problem at
hand. The language allows clear, concise representation of this sort
of knowledge. The QA4 system also has special facilities for dealing
with commutative functions, ordering relations, and equivalence
relations; these features are heavily used in this deductive system.
The program interrogates the user and asks his advice in the course of
a proof. Verifications have been found for Hoare's FIND program a
real-number division algorithm, and some sort programs, as well as for
many simpler algorithms. Additional theorems have been proved about a
pattern matcher and a version of Robinson's unification algorithm.
The appendix contains a complete, annotated listing of the deductive
system and annotated traces of several of the deductions performed by
the system.\\
\pagebreak
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 98\hfill PRICE: \$10.00\\[0.01in]
\noindent TITLE: KNOWLEDGE AND REASONING IN PROGRAM SYNTHESIS\\
AUTHORS: ZOHAR MANNA and R. J. WALDINGER\\
DATE: NOVEMBER 1974\\[0.01in]
ABSTRACT: Program synthesis is the construction of a computer
program from given specifications. An automatic program synthesis
system must combine reasoning and programming ability with a good deal
of knowledge about the subject matter of the program. This ability
and knowledge must be manifested both procedurally (by programs) and
structurally (by choice of representation).
We describe some of the reasoning and programming capabilities of
a projected synthesis system. Special attention is paid to the
introduction of conditional tests, loops, and instructions with wide
effects in the program being constructed. The ability to satisfy
several interacting goals simultaneously proves to be important in
many contexts. The modification of an already existing program to
solve a somewhat different problem has been found to be a powerful
approach.
We illustrate these concepts with hand simulations of the
synthesis of a number of pattern-matching programs. Some of these
techniques have already been implemented, some are in the course of
implementation, while others seem equivalent to well-known unsolved
problems in artificial intelligence.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 107\hfill PRICE: \$10.00\\[0.01in]
\noindent TITLE: ACHIEVING SEVERAL GOALS SIMULTANEOUSLY\\
AUTHOR: RICHARD WALDINGER\\
DATE: JULY 1975\\[0.01in]
ABSTRACT: In the synthesis of a plan or computer program, the
problem of achieving several goals simultaneously presents special
difficulties, since a plan to achieve one goal may interfere with
attaining the others. This paper develops the following strategy: to
achieve two goals simultaneously, develop a plan to achieve one of
them and then modify that plan to achieve the second as well. A
systematic program modification technique is presented to support this
strategy. The technique requires the introduction of a special
skeleton model to represent a changing world that can accommodate
modifications in the plan. This skeleton model also provides a novel
approach to the frame problem.
The strategy is illustrated by its application to three examples.
Two examples involve synthesizing the following programs:
interchanging the values of two variables and sorting three variables.
The third entails formulating a tricky blocks world plan. The
strategy has been implemented in a simple QLISP program.
It is argued that skeleton modeling is valuable as a planning
technique apart from its use in plan modification, particularly
because it facilitates the representation of influential actions
whose effects may be far reaching.
The second part of the paper is a critical survey of contemporary
planning literature, which compares our approach with other techniques
for facing the same problems.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 109\hfill PRICE: \$20.00\\[0.01in]
\noindent TITLE: A STRUCTURE FOR PLANS AND BEHAVIOR\\
AUTHOR: EARL D. SACERDOTI\\
DATE: AUGUST 1975\\[0.01in]
\pagebreak
ABSTRACT: This report describes progress that has been made in
the ability of a computer system to understand and reason actions. A
new method for representing actions within a computer memory has been
developed, and this new representation, called the procedural net, has
been employed in developing new strategies for solving problems and
monitoring the execution of the resulting solutions.
A set of running computer programs, called the NOAH (Nets of
Action Hierarchies) systems, embodies the representation and
strategies discussed above. Its major goal is to provide a framework
for storing expertise about the actions of a particular task domain
and to impart that expertise to a human in the cooperative achievement
of nontrivial tasks.
A problem is presented to NOAH as a statement that is to be made
true by applying a sequence of actions in an initial state of the
world. The actions are drawn from a set of actions previously defined
to the system. NOAH first creates a one-step solution to the problem
(essentially Solve the given goal). Then it progressively expands
the level of detail of the solution, filling in ever more detailed
actions. All the individual actions, composed into plans at differing
levels of detail, are stored in a data structure called the procedural
net. The system avoids imposing unnecessary constraints on the order
of the actions, rather than as linear sequences.
The same data structure is used to guide the human user through a
task. Since the system has planned the task at varying levels of
detail, it can issue requests for action to the user at varying levels
of detail, depending on his competence and understanding of the
higher-level actions. If more detail should be needed than was
originally planned for, or if an unexpected event causes the plan to
go awry, the system can continue to plan from any point during
execution.
The key ideas that are explored include:
\begin{enumerate}
\item Planning at many levels of detail
\item Representing a plan as a partial ordering of actions with respect to
time.
\item Execution monitoring and error recovery usig hierarchial plans.
\item Using procedures that represent a task domain to generate
declartive (frame-like) structures that represent individual actions.
\item Using abstract actions to model iterative operators.
\end{enumerate}
The major point of the report is that the structure of a plan of
actions is as important for problem solving and execution monitoring
as the nature of the actions themselves.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 112\hfill PRICE: \$10.00\\[0.01in]
\noindent TITLE: A TUNEABLE PERFORMANCE GRAMMAR\\
AUTHOR: JANE J. ROBINSON\\
DATE: SEPTEMBER 1975\\[0.01in]
ABSTRACT: This paper describes a tuneable performance grammar
currently being developed for speech understanding. It shows how
attributes of words are defined and propagated to successively larger
phrases, how other attributes are acquired, how factors reference
them to help the parser choose among competing definitions in order to
interpret the utterance correctly, and how these factors can easily be
changed to adapt the grammar to other discourses and contexts. Factors
that might be classified as syntactic are emphasized, but the
attributes they reference need not be, and seldom are, purely
syntactic.\\
\pagebreak
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 113\hfill PRICE: \$10.00\\[0.01in]
\noindent TITLE: SEMANTIC PROCESSING FOR SPEECH UNDERSTANDING\\
AUTHOR: GARY G. HENDRIX\\
DATE: SEPTEMBER 1975\\[0.01in]
ABSTRACT: The semantic component of the speech understanding
system being developed jointly by SRI and SDC rules out phrase
combinations that are not meaningful and produces semantic
interpretations for combination that are. The system consists of a
semantic network model and routines that interact with it. The net is
partitioned into a set of hierarchically ordered subnets, facilitating
the encoding of higher-order predicates and the maintenance of
multiple parsing hypotheses. Composition routines, combining
utterance components into phrases, consult network descriptions of
prototype situations and surface-to-deep-case maps. Outputs from
these routines are network fragments consisting of several subnets
that in aggregate capture the interrelationships between a phrase's
syntax and semantics.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 117\hfill PRICE: \$25.00\\[0.005in]
\noindent TITLE: PERCEPTUAL STRATEGIES FOR PURPOSIVE VISION\\
AUTHOR: THOMAS D. GARVEY\\
DATE: SEPTEMBER 1976\\
ABSTRACT: This report describes a computer program that
approaches perception as a problem-solving task. The system
uses information about the appearances of objects, about their
interrelationships, and about available sensors to produce a plan for
locating specified objects in images of room scenes. The strategies
produced allow for cost-effective processing by utilizing cheap
features in the early stages, reserving more complex operations for
later in the process, when the content has been sufficiently
restricted.
The general strategy paradigm used by the system is to acquire
image samples expected to belong to the target object; validate the
hypothesis that the acquired samples do belong to the target; and
finally to bound the image of the object by outlining it in a display
picture.
Sensors used by the system include a vidicon with three color
filters and a master-scanned, laser-rangefinder capable of producing a
range image. In addition, the range-finder measures the
reflectivity at the laser wavelength, at each post, producing a
gray-scale image in perfect registration with the range image. The
primitive attributes of brightness, line, saturation, height, and
local surface orientation at specified range locations can be computed
from these images. These attributes represent the new data available
to the system for recognizing and identifying objects. Object
descriptions are provided initially by indicating the object to the
system, and allowing the system to measure attributes. Other data,
such as typical object relationships, are provided interactively by
the user.
When required to locate an object, the system computes a
distinguishing features representation that will serve to separate
parts of the target from those of other objects. These distinguishing
features are combined into a strategy represented as a planning graph.
This graph contains optimal subgoals for achieving the goal of
locating the object. An execution routine selects the best subgoal,
executes it, rates its effect, and selects the next best goal,
continuing with the progress until either the object is located, or
there are no options remaining.
This approach offers several contributions to perception
research. By capitalizing on the goal-directed aspects of the
problem, the system is able to select relevant information from a mass
of irrelevant data. The system is able to organize its processing in
such a way as to optimize the use of sensor data. By generating
strategies when needed, the program allows for the easy introduction
of new objects and new sensors. The system allows for the logical
introduction of new information deriving algorithms.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 120\hfill PRICE: \$10.00\\[-0.15in]
\begin{tabbing}
\noindent TITLE: \= QLISP: A LANGUAGE FOR THE INTERACTIVE DEVELOPMENT\\
\> OF COMPLEX SYSTEMS\\
AUTHORS: \= EARL SACERDOTI, RICHARD FIKES, RENE REBOH, DANIEL SAGALOWICZ, \\
\> RICHARD WALDINGER and B. MICHAEL WILBER\\
DATE: MARCH 1976\\[-0.15in]
\end{tabbing}
ABSTRACT: This paper presents a functional overview of the
features and capabilities of QLISP, one of the newest of the current
generation of very high level languages developed for use in
artificial intelligence (AI) research.
QLISP is both a programming language and an interactive
programming environment. It embeds an extended version of QA4, an
earlier AI language, in INTERLISP, a widely available version of LISP
with a variety of sophisticated programming aids.
The language features provided by QLISP include a variety of
useful data types, an associative data base for the storage and
retrieval of expressions, a powerful pattern matcher based on a
unification algorithm, pattern-directed function invocation, teams
of pattern involved functions, a sophisticated mechanism for breaking
a data base into contexts, generators for associative data retrieval,
and easy extensibility. System features available in QLISP include a
very smooth interaction with the underlying INTERLISP language, a
facility for aggregating multiple pattern matches, and features for
interactive control of programs.
A number of the implemented applications of QLISP are briefly
discussed, and some directions for future development are presented.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
-------