Copy Link
Add to Bookmark
Report
AIList Digest Volume 4 Issue 099
AIList Digest Thursday, 24 Apr 1986 Volume 4 : Issue 99
Today's Topics:
Seminars - Run-Length Code for Geographical Information (SMU) &
Logic in Design (SU) &
A VLSI Architecture for Chess (SU) &
Minimal Entailment (SU) &
Chronological Ignorance (SU) &
Refutational Completeness in Theorem Proving (UTexas) &
Interpreting Logic Programs on an FFP Machine (UPenn) &
The Non-Von Project (UPenn) &
A Mathematical Theory of Plan Synthesis (SRI),
Conference - American Control Conference &
AAAI Workshop on AI and Simulation
----------------------------------------------------------------------
Date: WED, 23 APR 86 17:02:23 CDT
From: E1AR0002%SMUVM1.BITNET@WISCVM.WISC.EDU
Subject: Seminar - Run-Length Code for Geographical Information (SMU)
A Spatial Knowledge Structure Based on Run-Length-Code for a Geographical
Information System
Speaker: Erland Jungert
Illinois Institute of Technology
Location: 315SIC, Southern Methodist University, CS
Time: 3PM
Run-Length-Code (RLC) is an example of a simple data structure used
mainly for compacting images. A method where RLC is used as an object
oriented data structure for Geographical Information Systems (GIS) will be
presented. The usage of this object structure as a basis for spatial
reasoning while regarding the RLC-objects as part of a spatial knowledge
structure will be discussed.
------------------------------
Date: Mon 21 Apr 86 13:35:09-PST
From: Christine Pasley <pasley@SRI-KL>
Subject: Seminar - Logic in Design (SU)
CS529 - AI In Design & Manufacturing
Instructor: Dr. J. M. Tenenbaum
Title: Logic: Application to Design Debugging, Diagnosis, And Test
Speaker: Narinder Singh
From: Stanford University
Date: Wednesday, April 23, 1986
Time: 4:00 - 5:30
Place: Terman 556
Abstract:
Logic programming is a software engineering methodology based on techniques
from the field of Artificial Intelligence. One builds a logic program by
describing the application area of the program and its goal, rather than
specifying the actions necessary to achieve the goal. In this talk we will
examine the use of logic to represent and reason about digital devices for
simulation, test generation, and diagnosis. Describing designs in logic
permits capturing high level design descriptions, reasoning with a single
description for a collection of tasks, and reasoning with incomplete
descriptions. In addition, logic provides a flexible interpreter for reasoning
about a design, e.g., it permits reasoning forwards and backwards through a
design, and generating single or multiple answers to a goal.
Visitors welcome!
------------------------------
Date: Mon 21 Apr 86 09:49:49-PST
From: Sharon Gerlach <CSL.GERLACH@SU-SIERRA.ARPA>
Subject: Seminar - A VLSI Architecture for Chess (SU)
This Friday, April 25, at 1:30 in CIS 101:
All the Right Moves: A VLSI Architecture for Chess
Carl Ebeling
Carnegie Mellon University
Hitech, the Carnegie-Mellon chess program that recently won the ACM
computer chess championship and owns a USCF rating of 2340, owes its
success in large part to an architecture that is used for both
move generation and position evaluation. Previous programs have been
subject to a tradeoff between speed and knowledge: applying
more chess knowledge to position evaluation necessarily slows the
search. Although the previous computer chess champions, Belle and
Cray Blitz, have demonstrated the importance of deep search, it is
clear that better knowledge is required for first-rate chess. With
this new architecture, Hitech is able to search both deeply and
knowledgeably.
We will first describe the design and implementation of the move
generator which uses fine-grained parallelism to reduce the time to
produce and order moves. By generating all moves for both sides,
this move generator is able to order moves based both on capture
information and an estimate of the safety of the destination square.
This effort is rewarded by smaller search trees since the efficiency
of the alpha-beta search depends on the order in which moves are
examined. Experiments show that Hitech search trees are within a factor
of 1.5 of optimal. Although the amount of hardware required is
substantial, this architecture is eminently suited to VLSI.
We then describe the requirements of position evaluation and discuss
how this architecture can be adapted to perform evaluation. This
will include the description of a VLSI implementation that we
propose for position evaluation. Finally we will describe the other
components of the chess machine and present some performance results
that indicate how well the hardware supports the search.
------------------------------
Date: Tue 22 Apr 86 10:09:41-PST
From: Anne Richardson <RICHARDSON@SU-SCORE.ARPA>
Subject: Seminar - Minimal Entailment (SU)
DAY: April 28, 1986
EVENT: AI Seminar
PLACE: Jordan 050
TIME: 4:15
TITLE: "Minimal Entailment and Non-Monotonic Reasoning"
PERSON: David W. Etherington
FROM: University of British Columbia
Circumstances commonly require that conclusions be
drawn (conjectured) even though they are not strictly warranted
by the available evidence.
Various forms of minimal entailment have been suggested
as ways of generating appropriate conjectures.
Minimal entailment is a consequence relation in which those
facts which hold in minimal models of a theory are considered
to follow from that theory.
Thus minimal entailment is less restrictive than the standard logical
entailment relation, which strongly constrains what evidence
may be taken as supporting a conclusion.
Different definitions of minimality of models yield different
entailment relations.
The talk will outline a variety of such relations.
Domain, Predicate, and Formula Circumscription [McCarthy 1978,
1980, 1984] are syntactic formalisms intended to capture these
relations.
We examine each from a semantic viewpoint, in the hope of
clarifying their respective capabilities and weaknesses.
Results on the consistency, correctness, and adequacy of
these formalisms will be presented.
While minimal entailment corresponds most directly to the
Closed-World Assumption
that positive information
not implicit in what is known can be assumed false
McCarthy and others have suggested applications of
circumscription to more general default reasoning tasks.
With this in mind, connections between minimal entailment and
Reiter's Default Logic will be sketched, if time permits.
In this connection, we will consider positive and negative
results due to Grosof and Imielinski, respectively.
------------------------------
Date: 22 Apr 86 1306 PST
From: Vladimir Lifschitz <VAL@SU-AI.ARPA>
Subject: Seminar - Chronological Ignorance (SU)
CHRONOLOGICAL IGNORANCE:
time, knowledge, nonmonotonicity and causation
Yoav Shoham
Yale University
Thursday, May 1, 4pm
Room 380X, Mathematics Building
We are concerned with the problem of reasoning about change within a
formal system. We identify two problems that arise from practical
considerations of efficiency and naturalness of expression: the
persistence problem (otherwise known as the frame problem, and a new,
but no less evil, initiation problem. In this talk we concentrate on
the latter one.
We propose a new logic that allows efficient and natural reasoning
about change and which avoids the initiation problem. The logic,
called the logic of chronological ignorance, is a fusion of recent
ideas on temporal logic, modal logic of knowledge, and nonmonotonic
logic.
We identify a special class of theories, called causal theories, and
show these have elegant model-theoretic properties which make
reasoning about causal theories very easy.
Finally, we contrast our logic with previous work on nonmonotonic
logics in computer science, and discuss its connection to the
philosophical literature on causation.
------------------------------
Date: Tue 22 Apr 86 09:59:26-CST
From: Ellie Huck <AI.ELLIE@MCC.ARPA>
Subject: Seminar - Refutational Completeness in Theorem Proving (UTexas)
A New Method For Establishing
Refutational Completeness in Theorem Proving
Jieh Hsiang
SUNY at Stony Brook
April 25 - 10:00am
Echelon I, Room 409
In this talk we present a new technique for establishing completeness
of refutational theorem proving strategies. Our method employs
semantic trees and, in contrast to most of the semantic tree methods,
is based on proof-by-refutation as opposed to proof-by-induction.
Thus, it works well on transfinite semantic trees (to be introduced)
as well as on finite ones. This method is particularly useful for
proving the completeness of the following strategies (without the need
of the functionally reflexive axioms):
Resolution + oriented paramodulation
P1-resolution + oriented paramodulation
Resolution with ordered predicates + oriented paramodulation
using clauses only containing the equality predicate
A version of an unfailing Knuth-Bendix algorithm
The EN-Strategy, a complete refutational method for first
order theory with equality based on the term rewriting method
The Manna-Waldinger Tableau method with inference rules for
special relations, where oriented paramodulation is an
improvement of paramodulation.
------------------------------
Date: Tue, 22 Apr 86 11:44 EST
From: Tim Finin <Tim%upenn.csnet@CSNET-RELAY.ARPA>
Subject: Seminar - Interpreting Logic Programs on an FFP Machine (UPenn)
University of Pennsylvania Colloquium
11:00am April 23, 1986 - 216 Moore School
"INTERPRETING LOGIC PROGRAMS ON AN FFP MACHINE"
Bruce T. Smith
University of North Carolina - Chapel Hill
This talk describes a strategy for interpreting logic programs (e.g. Prolog) on
Gyula Mago's FFP Machine. The FFP Machine is a small-grain parallel computer
designed to interpret Backus' FFP language. The question is how to fit logic
programs into the FFP Machine's string reduction style of operation without
losing potential parallelism. In each machine cycle, the FFP Machine
partitions itself into a set of virtual MIMD computers-- one for each innermost
FFP application. These virtual computers work independently to re-write their
FFP expressions.
In constrast with the standard approach to parallelism in logic programming,
i.e. communicating processes cooperating to search an AND/OR tree, this
approach represents the search as an FFP sequence and searches by creating
appropriate reductions that re-write sub-trees. OR-parallelism is provided by
expanding different branches of the tree. AND-parallelism is provided by
creating virtual computers that perform unification (by a version of the
Martelli and Montanari algorithm) over sets of conjoined goals.
------------------------------
Date: Wed, 23 Apr 86 16:24 EST
From: Tim Finin <Tim%upenn.csnet@CSNET-RELAY.ARPA>
Subject: Seminar - The Non-Von Project (UPenn)
Colloquium - University of Pennsylvania
3:00pm 4-24-86, 216 Moore
THE NON-VON PROJECT: EXPERIMENTS WITH MASSIVELY PARALLEL MACHINES
David Elliott Shaw
Columbia University
NON-VON is a massively parallel non-von Neumann machine that has been shown to
support the extremely rapid execution of a wide range of computationally
intensive symbolic information processing tasks, including a number of
artificial intelligence applications. An early prototype called NON-VON 1,
which implements some, but not all of the features of the full architecture, is
presently operational at Columbia University.
Central to the NON-VON architecture is an active memory which is implemented
using custom VLSI chips, each containing eight 8-bit small processing elements.
A full-scale machine would contain hundreds of thousdands of small processing
elements, together with several hundred large processing elements, each based
on a conventional 32-bit microprocessor. NON-VON's processing elements are
physically interconnected in three ways, and can be dynamically reconfigured to
support a fourth logical communication topology. The machine is capable of
synchronous (SIMD), asynchronous (MIMD) and partitioned (multiple SIMD)
execution.
In this presentation, Professor Shaw will describe the organization of the
NON-VON programming techniques. Performance results in the areas of low-and
intermediate-level computer vision, database and knowledge base management, and
AI production systems will be presented.
------------------------------
Date: Wed 23 Apr 86 14:42:11-PST
From: LANSKY@SRI-AI.ARPA
Subject: Seminar - A Mathematical Theory of Plan Synthesis (SRI)
TOWARD A MATHEMATICAL THEORY OF PLAN SYNTHESIS
Edwin P.D. Pednault (PEDNAULT@SRI-AI)
Stanford University and SRI International, AI Center
11:00 AM, MONDAY, April 28
SRI International, Building E, Room EJ228 (new conference room)
Classical planning problems have the following form: given a set of
goals, a set of allowable actions, and a description of the current
state of the world, find a sequence of actions that will transform the
world from its current state to a state in which all of the goals are
satisfied. This talk is a presentation of my thesis research, which
examines the question of how to solve such problems automatically.
The question will be addressed from a rigorous, mathematical
standpoint, in contrast to the informal and highly experimental
treatments found in most previous work. By introducing mathematical
rigor, it has been possible to unify many existing ideas in automatic
planning, showing how they arise from first principles and how they
may be applied to solve a much broader class of problems than had
previously been considered. In addition, a number of theorems have
been proved that further our understanding of the synthesis problem,
and a language has been developed for describing actions that combines
the notational convenience of STRIPS with the expressive power of the
situation calculus.
This talk will concentrate on my techniques for plan synthesis with
only a brief summary of the other contributions of my research.
A mathematical framework will be introduced, along with a number of
theorems that form the basis for the synthesis techniques.
These theorems will then be combined with a least-commitment search strategy
to obtain a solution method that unifies and generalizes means-ends
analysis, opportunistic planning, goal protection, goal regression,
constraint posting/propagation, hierarchical planning, and nonlinear
planning.
------------------------------
Date: 23 Apr 1986 23:53:49 EST
From: ALSPACH@USC-ISI.ARPA
Subject: Conference - American Control Conference
Write to me at this address for registration and housing reservation forms
for the 1986 ACC (American Control Conference) described in a previous
message.
------------------------------
Date: 23 Apr 1986 1029-PST
From: STELZNER@ALADIN
Subject: Conference - AAAI Workshop on AI and Simulation
AAAI Workshop on AI and Simulation
Simulation shares with AI a concern for effective world modeling.
Currently, some computer scientists are trying to build systems that
integrate the strengths of simulation and AI---AI's ability to represent
complex system models and to reason over those models, and simulation's
ability to model dynamic behavior. This initial work is already
being realized in commercial products. We intend that this workshop
bring together researchers in knowledge-based simulation, tool builders
who are developing simulation systems that combine AI and classical
techniques, and system designers who have built AI-based simulation
applications.
Topics to be discussed
Expert reasoning in simulation
Scenario construction for expert systems
Integration of AI techniques with conventional simulations
Graphical representation for simulation
Application of new hardware architectures for simulation
AI-based simulation tools
Knowledge representation formalisms for simulation
Simulation at multiple levels of abstraction
Automatic analysis of simulation results
Organizers
The workshop organizers are Arthur Gerstenfeld (Worcester
Polytechnic Institute), Richard B. Modjeski (U.S. Army Concepts Analysis
Agency), Ramana Reddy (West Virginia University and the Robotics
Institute, Carnegie-Mellon University) and Marilyn Stelzner, Chair
(IntelliCorp)
Participation
The workshop will take place on Monday, August 11 at the University of
Pennsylvania. Participation in the workshop is by invitation, limited to 35
participants. People wishing to be invited should submit {\bf five} copies of
a 1000-word abstract describing their work in AI and simulation to the
workshop Chair, Marilyn Stelzner, IntelliCorp, 1975 El Camino Real West,
Mountain View, California 94040 by May 30, 1986. Invitations will be issued
by July 1.
------------------------------
End of AIList Digest
********************
