Copy Link
Add to Bookmark
Report
AIList Digest Volume 4 Issue 193
AIList Digest Sunday, 21 Sep 1986 Volume 4 : Issue 193
Today's Topics:
Seminars - Backtrach Search for Constraint Satisfaction (SRI) &
Minisupercomputers and AI Machines (CMU) &
Equal Opportunity Interactive Systems (SU),
Seminars (Past) - AI in Communication Networks (Rutgers) &
Goal Integration in Heuristic Algorithm Design (Rutgers) &
Long-Term Planning Systems (TI) &
Learning by Understanding Analogies (SRI) &
Belief Revision (SRI) &
Factorization in Experiment Generation (SRI)
----------------------------------------------------------------------
Date: Wed 17 Sep 86 13:39:03-PDT
From: Amy Lansky <LANSKY@SRI-VENICE.ARPA>
Subject: Seminar - Backtrach Search for Constraint Satisfaction (SRI)
IMPROVING BACKTRACK SEARCH ALGORITHMS
FOR CONSTRAINT-SATISFACTION PROBLEMS
Rina Dechter (DECHTER@CS.UCLA.EDU)
Cognitive System Laboratory, Computer Science Department, U.C.L.A.
and
Artificial Intelligence Center, Hughes Aircraft Company
11:00 AM, TUESDAY, September 23
SRI International, Building E, Room EJ228
The subject of improving search efficiency has been on the agenda of
researchers in the area of Constraint-Satisfaction- Problems (CSPs)
for quite some time. A recent increase of interest in this subject,
concentrating on backtrack search, can be attributed to its use as the
control strategy in PROLOG, and in Truth-Maintenance-Systems (TMS).
The terms ``intelligent backtracking'', ``selective backtracking'',
and ``dependency- directed backtracking'' describe various efforts for
producing improved dialects of backtrack search in these systems. In
this talk I will review the common features of these attempts and will
present two schemes for enhancing backtrack search in solving CSPs.
The first scheme, a version of "look-back", guides the decision of
what to do in dead-end situations. Specifically, we concentrate on
the idea of constraint recording, namely, analyzing and storing the
reasons for the dead-ends, and using them to guide future decisions,
so that the same conflicts will not arise again. We view constraint
recording as a process of learning, and examine several possible
learning schemes studying the tradeoffs between the amount of learning
and the improvement in search efficiency.
The second improvement scheme exploits the fact that CSPs whose
constraint graph is a tree can be solved easily, i.e., in linear time.
This leads to the following observation: If, in the course of a
backtrack search, the subgraph resulting from removing all nodes
corresponding to the instantiated variables is a tree, then the rest
of the search can be completed in linear time. Consequently, the aim
of ordering the variables should be to instantiate as quickly as
possible a set of variables that cut all cycles in the
constraint-graph (cycle-cutset). This use of cycle-cutsets can be
incorporated in any given "intelligent" backtrack and is guaranteed to
improve it (subject to minor qualifications).
The performance of these two schemes is evaluated both theoretically
and experimentally using randomly generated problems as well as
several "classical" problems described in the literature.
VISITORS: Please arrive 5 minutes early so that you can be escorted up
from the E-building receptionist's desk. Thanks!
ALSO: NOTE DAY CHANGE!!! (Tuesday -- this week only)
------------------------------
Date: 17 Sep 86 14:53:24 EDT
From: Barbara.Grandillo@n.sp.cs.cmu.edu
Subject: Seminar - Minisupercomputers and AI Machines (CMU)
Special Computer Science Seminar
Speaker: Professor Kai Hwang
University of Southern California
Title: Design Issues of Minisupercomputers and AI Machines
Date: Monday, September 22, 1986
Time: 12:00 noon
Place: Wean Hall 4605
In this seminar, Dr. Hwang will address the fundamental issues in
designing efficient multiprocessor/multicomputer minisupercomputers or
AI machines. The talk covers the systems architectural choices,
interprocessor communication mechanisms, resource allocation methods,
I/O and OS functions, mapping of parallel algorithms, and the creation
of parallel programming environment for these machines.
These design issues and their possible solutions are drawn from the
following commercial or exploratory systems: Alliant FX/8, FPS
T-Series and M64 Series,Flex/32, Encore Multimax, Flex/32, Elxsi 6400,
Sequent 8000, Connection Machine, BBN Butterfly, FAIM-1, Alice, Dado,
Soar, and Redfiflow, etc.
Dr. Hwang will also assess the technological basis and future trends in
low-cost supercomputing and AI processing.
------------------------------
Date: 19 Sep 86 0845 PDT
From: Rosemary Napier <RFN@SAIL.STANFORD.EDU>
Subject: Seminar - Equal Opportunity Interactive Systems (SU)
Computer Science Colloquium
Tuesday, October 7, 1986, 4:15PM, Terman Auditorium
"Equal Opportunity Interactive Systems and Innovative Design"
Harold Thimbleby
Dept. of Computer Science
University of York
Heslington, York
United Kingdom YO1 5DD
Most interactive systems distinguish between the input and output
of information. Equal opportunity is a design heuristic that
discards these distinctions; it was inspired by polymodality
in logic programming and a well-known problem solving heuristic.
The seminar makes the case for equal opportunity, and shows how
several user engineering principles, techniques and systems can
be reappraised under equal opportunity.
By way of illustration, equal opportunity is used to guide the
design of a calculator and spreadsheet. The resulting systems
have declarative user interfaces and are arguably easier to
use despite complex operational models.
About the speaker: Harold Thimbleby did his doctoral research in
user interface design. He joined the Computer Science department
at York in 1982 and is currently on sabbatical at the Knowledge
Sciences Institute, Calgary. He is currently writing a book on
the application of formal methods as heuristics for user interface
design.
------------------------------
Date: 8 Sep 86 23:50:47 EDT
From: Tom Fawcett <FAWCETT@RED.RUTGERS.EDU>
Subject: Seminar - AI in Communication Networks (Rutgers)
The first speaker of this year's Machine Learning Seminar series at Rutgers
will be Andrew Jennings of Telecom Australia, speaking on "AI in
Communication Networks". Dr. Andrews will speak in Hill-423 at 11 AM on
THURSDAY, September 18th (NB: this is NOT the standard day for the ML
series). The abstract follows:
Andrew Jennings
(Arpanet address: munnari!trlamct.oz!andrew@seismo.CSS.GOV)
Telecom Australia
AI in Communication Networks
Expert systems are gaining wide application in communication
systems, especially in the areas of maintenance, design and planning. Where
there are large bodies of existing expertise, expert systems are a useful
programming technology for capturing and making use of that expertise.
However will AI techniques be limited to retrospective capturing of
expertise or can they be of use for next generation communication systems?
This talk will present several projects that aim to make use of AI
techniques in next-generation communication networks. An important aspect
of these systems is their ability to learn from experience.
This talk will discuss some of the difficulties in developing
learning in practical problem domains, and the value of addressing these
difficulties now. In particular the problems of learning in intractable
problem domains is of great importance for these problems and some ongoing
work on this problem will be presented. The projects discussed include a
system for capacity assignment in networks, a project to develop AI systems
for routing in fast packet networks and a system for VLSI design from a high
level specification.
------------------------------
Date: 9 Sep 86 12:43:20 EDT
From: Tom Fawcett <FAWCETT@RED.RUTGERS.EDU>
Subject: Seminar - Goal Integration in Heuristic Algorithm Design
(Rutgers)
Next week, on Tuesday, September 16th in Hill 423 at 11 AM, Jack
Mostow will give a talk based on his work with Kerstin Voigt, entitled
"A Case Study of Goal Integration in Heuristic Algorithm Design".
This a joint ML/III seminar, and is a dry run for a talk being given at the
Knowledge Compilation Workshop. There's no paper for the talk, but Jack
recommends his AAAI86 article with Bill Swartout as good background reading.
The abstract follows:
Jack Mostow
Rutgers University
(Arpanet address: MOSTOW@RED.RUTGERS.EDU)
A Case Study of Goal Integration in Heuristic Algorithm Design:
A Transformational Rederivation of MYCIN's Therapy Selection Algorithm
An important but little-studied aspect of compiling knowledge into
efficient procedures has to do with integrating multiple, sometimes
conflicting goals expressed as part of that knowledge. We are
developing an artificial intelligence model of heuristic algorithm
design that makes explicit the interactions among multiple goals. The
model will represent intermediate states and goals in the design
process, transformations that get from one state to the next, and
control mechanisms that govern the selection of which transformation
to apply next. It will explicitly model the multiple goals that
motivate and are affected by each design choice.
We are currently testing and refining the model by using it to explain
the design of the algorithm used for therapy selection in the medical
expert system MYCIN. Previously we analyzed how this algorithm
derives from the informal specification "Find the set of drugs that
best satisfies the medical goals of maximizing effectiveness,
minimizing number of drugs, giving priority to treating likelier
organisms, [etcetera]." The reformulation and integration of these
goals is discussed in Mostow & Swartout's AAAI86 paper. Doctoral
student Kerstin Voigt is implementing a complete derivation that will
address additional goals important in the design of the algorithm,
such as efficient use of time, space, and experts.
------------------------------
Date: Mon 18 Aug 86 16:28:02-CDT
From: Rajini <Rajini%ti-csl.csnet@CSNET-RELAY.ARPA>
Subject: Seminar - Long-Term Planning Systems (TI)
Dr. Jim Hendler, Assistant Professor at Univ of Maryland, is a giving a
special seminar at 10:00 am on August 28th. Abstract of his talk follows.
It will be held in Conference room #2, Computer Science Center, Texas
Instruments, Dallas.
--Rajini
rajini@ti-csl
(214) 995-0779
Long-term planning systems
James Hendler
Computer Science Dept.
University of Maryland
College Park, Md. 20903
Most present day planning systems work in domains where a single goal is
planned for a single user. Further, the only object changing the world is
the planner itself. The few systems that go beyond this, for example Vere's
DEVISER system, tend to work in domains where the world, although changing,
behaves according to a set of well-defined rules. In this talk we describe
on-going research directed at extending planning systems to function in the
dynamic environments necessary for such tasks as job-shop scheduling,
process control, and autonomous vehicle missions.
The talk starts by describing the inadequacies of present-day systems for
working in such tasks. We focus on two, necessity of a static domain and
inability to handle large numbers of interacting goals, and show some of the
extensions needed to handle these systems. We describe an extension to
marker-passing, a parallel, spreading activation system, which can be used
for handling the goal interaction problems, and we discuss representational
issues necessary to handling dynamic worlds. We end by describing work on
a system which is being implemented to deal with these problems.
------------------------------
Date: Tue 19 Aug 86 19:55:33-PDT
From: Margaret Olender <OLENDER@SRI-WARBUCKS.ARPA>
Subject: Seminar - Learning by Understanding Analogies (SRI)
Russell Greiner, Toronto, will be guest speaker at the RR Group's
PlanLunch (August 20, EJ228, 11:00am).
LEARNING BY UNDERSTANDING ANALOGIES
This research describes a method for learning by analogy---i.e., for
proposing new conjectures about a target analogue based on facts known
about a source analogue. After formally defining this process, we
present heuristics which efficiently guide it to the conjectures which
can help solve a given problem. These rules are based on the view
that a useful analogy is one which provides the information needed to
solve the problem, and no more. Experimental data confirms the
effectiveness of this approach.
------------------------------
Date: Wed 20 Aug 86 16:02:46-PDT
From: Amy Lansky <LANSKY@SRI-WARBUCKS.ARPA>
Subject: Seminar - Belief Revision (SRI)
IS BELIEF REVISION HARDER THAN YOU THOUGHT?
Marianne Winslett (WINSLETT@SCORE)
Stanford University, Computer Science Department
11:00 AM, MONDAY, Aug. 25
SRI International, Building E, Room EJ228
Suppose one wishes to construct, use, and maintain a database of
knowledge about the real world, even though the facts about that world
are only partially known. In the AI domain, this problem arises when
an agent has a base set of extensional beliefs that reflect partial
knowledge about the world, and then tries to incorporate new, possibly
contradictory extensional knowledge into the old set of beliefs. We
choose to represent such an extensional knowledge base as a logical
theory, and view the models of the theory as possible states of the
world that are consistent with the agent's extensional beliefs.
How can new information be incorporated into the extensional knowledge
base? For example, given the new information that "b or c is true,"
how can we get rid of all outdated information about b and c, add the
new information, and yet in the process not disturb any other
extensional information in the extensional knowledge base? The burden
may be placed on the user or other omniscient authority to determine
exactly which changes in the theory will bring about the desired set
of models. But what's really needed is a way to specify the update
intensionally, by stating some well-formed formula that the state of
the world is now known to satisfy and letting internal knowledge base
mechanisms automatically figure out how to accomplish that update. In
this talk we present semantics and algorithms for an operation to add
new information to extensional knowledge bases, and demonstrate that
this action of extensional belief revision is separate from, and
in practice must occur prior to, the traditional belief revision
processes associated with truth maintenance systems.
------------------------------
Date: Wed 3 Sep 86 14:51:36-PDT
From: Amy Lansky <LANSKY@SRI-WARBUCKS.ARPA>
Subject: Seminar - Factorization in Experiment Generation (SRI)
FACTORIZATION IN EXPERIMENT GENERATION
Devika Subramanian
Stanford University, Computer Science Department
11:00 AM, MONDAY, September 8
SRI International, Building E, Room EJ228
Experiment Generation is an important part of incremental concept
learning. One basic function of experimentation is to gather data
to refine an existing space of hypotheses. In this talk, we examine
the class of experiments that accomplish this, called discrimination
experiments, and propose factoring as a technique for generating
them efficiently.
------------------------------
End of AIList Digest
********************
