LAWS@SRI-AI.ARPA (02/10/85)
From: AIList Moderator Kenneth Laws <AIList-REQUEST@SRI-AI.ARPA>
AIList Digest Sunday, 10 Feb 1985 Volume 3 : Issue 18
Today's Topics:
Seminars - The Bertrand Constraint Language (Oregon) &
Insights on Searching (CMU) &
Motion Planning Algorithms (SU) &
Triangle Tables for Robot Actions (SU) &
Robot Mind-Body Synapse (CSLI),
Conferences - Genetic Algorithms &
Mathematical Foundations of Programming Semantics
----------------------------------------------------------------------
Date: Thursday, 7 Feb 85 15:03:05 PST
From: wm@tekchips
Subject: Seminar - The Bertrand Constraint Language (Oregon)
Oregon Graduate Center
Department of Computer Science and Engineering
Colloquium
February 22, 3:30 pm, Main Seminar Room
Bertrand, a General Purpose Constraint Language
Wm Leler
Computer Research Laboratory
Tektronix, Inc.
Constraint languages and constraint satisfaction
techniques are making the problem solving abilities of
the computer available to a wider audience. For
example, simple spread-sheet languages such as VisiCalc
allow many different financial modeling problems to be
solved without resorting to programming. In a
conventional language the programmer must specify a
step-by-step procedure for the language interpreter to
follow. In a constraint language, programming is a
descriptive task. The user specifies a set of
relationships, called constraints, and it is up to the
constraint satisfaction system to satisfy these
constraints. Unfortunately, constraint satisfaction
systems have been very difficult to build.
Bertrand is a general purpose language designed for
building constraint satisfaction systems. Constraints
are solved using rewrite rules, which are invoked by
pattern matching. Bertrand is similar in expressive
power to relational languages such as Prolog, but
without any procedural semantics. Its lack of
procedural semantics makes Bertrand especially
attractive for execution on parallel processors.
This talk will review several example constraint
satisfaction systems built using Bertrand with
applications in graphics, design, and modeling. There
will also be some discussion of the language issues
involved in the design of Bertrand.
------------------------------
Date: 8 Feb 85 18:49:38 EST
From: Steven.Shafer@CMU-CS-IUS
Subject: Seminar - Insights on Searching (CMU)
[Forwarded from the CMU bboard by Tyson@SRI-AI.]
Type: AI Seminar
Speaker: Hans Berliner
Topic: Superpuzz and Some Insights on Searching
Dates: 12-Feb-85
Time: 3:30 pm
Place: WeH 5409
Most solutions in any complex domain require some non-intuitive
moves that violate good heuristic rules. When a combination of search
procedure and evaluation function requires that the search keep finding
"good" moves or else abandon the current branch, the search takes on
an undesirable breadth-first character. This research indicates that
it is possible to define evaluation functions that allow continuing a
branch that encounters some non-intuitive moves by giving credit for
earlier "good" moves. We define an "adventurousness coefficient"
that determines the ratio of acceptance of non-intuitive moves to
"good" moves, and show that greater adventurousness is desirable as
the depth of solution increases. Further, adventurousness has an
even greater payoff when a constraint satisfaction method exists that
can terminate unsolvable branches.
Our domain for this study was Superpuzz, a very difficult solitaire
puzzle. Four search paradigms, each the best of its kind for
non-adversary problems, were investigated. These are: Depth-first
with branch and bound and iterative deepening (DF), A*, Best-first
with a simple evaluation function (BF1), and Best-first with a
complex evaluation function (BF2). All methods except BF2 use the
same knowledge, and each of these methods is tested with and without
the use of a constraint satisfaction procedure, all on the same sets
of progressively more difficult solitaire problems.
As expected, the most informed search (BF2) does better than the
less informed as the problems get more difficult. Constraint
satisfaction is found to have a pronouncedly greater effect when
coupled with the most informed algorithm (BF2). BF1, which uses the
same knowledge as A* and DF but has a greater adventurousness
coefficient, far outperforms these paradigms in terms of work required
at about a 5% reduction in the quality of the (otherwise) optimal
solution.
Adventurousness can be thought of as a primitive form of planning,
in which no specific goal is enunciated but the cohesion of a set of
moves in "making progress" is being measured. The desired degree
of adventurousness appears to depend on the domain, evaluation
function, and constraint satisfaction method used.
------------------------------
Date: Mon 4 Feb 85 15:13:05-PST
From: Andrei Broder <Broder@SU-SCORE.ARPA>
Subject: Seminar - Motion Planning Algorithms (SU)
[Forwarded from the SRI-AI bboard by Laws@SRI-AI.]
AFLB Seminar
2/14/85 - Prof. Micha Sharir (Tel Aviv)
"Motion planning algorithms - a survey"
We discuss the problem of planning automatically a continuous motion
of a given robot system B having k degrees of freedom, from an initial
position to a final desired position. During the required motion B has
to avoid certain obstacles whose geometry is known. In abstract
terms, the problem is reduced to that of calculating the connected
components of the (k-dimensional) manifold FP of all free positions of
B, and is thus a problem in "computational topology". In the talk we
will survey the main results in this area as developed during the last
four years. Some of the topics of the talk (as time will permit) will
be:
(1) We show that the problem is solvable in time polynomial in the
geometric complexity n of the obstacles, provided that k is fixed.
(2) The problem is PSPACE-hard if k is arbitrary, even for very simple
systems.
(3) Efficient solutions exist for several simple systems. We will
describe some of them.
(4) Review of the main solution techniques.
(5) Spin-off problems in computational geometry.
(6) Variants of the problem: motion planning with a gripped object,
motion planning in the presence of moving obstacles, optimal motion
planning, etc.
***** Time and place: February 14, 12:30 pm in MJ352 (Bldg. 460) ******
------------------------------
Date: Wed 6 Feb 85 21:19:30-PST
From: Gio Wiederhold <WIEDERHOLD@SU-SCORE.ARPA>
Subject: Seminar - Triangle Tables for Robot Actions (SU)
[Forwarded from the Stanford bboard by Laws@SRI-AI.]
Tuesday, February 12, 1985
at 4:15 in Terman Auditorium
Nils J. NILSSON
Chairman, Stanford Computer Science Department
will present:
TRIANGLE TABLES:
A Proposal for a Language for Programming Robot Actions
Structures called ``triangle tables'' were used in connection with the
SRI robot SHAKEY for storing sequences of robot actions. Since the
original motivation for triangle tables still seems relevant, I have
recently elaborated the original concept and have begun to consider
how the expanded formalism can be used as a general robot programming
language. This talk will describe this new view of triangle tables
and how they might be used in a language that supports asynchronous
and concurrent action computations.
------------------------------
Date: Wed 6 Feb 85 17:20:59-PST
From: Emma Pease <Emma@SU-CSLI.ARPA>
Subject: Seminar Summary - Robot Mind-Body Synapse (CSLI)
[Excerpted from the CSLI Newsletter by Laws@SRI-AI.]
SUMMARY OF F-4 MEETING
``Robot Design: In Search of the Mind-Body Synapse''
Stan Rosenschein, CSLI
For purposes of the discussion, the term ``robot'' was taken refer to a
collection of (man-made) sensors and effectors connected through a computer
controller. To lend an air of reality to the discussion, a ``hands-on''
display was given of an ultrasonic rangefinder, a small CCD camera, a
battery-operated robotics kit including a motorized gripper, and a small
computer. The challenge facing the robot designer is how to assemble these
(or similar) components to build a device capable of complex and
interesting behaviors. The most complex and difficult part of the robot
design task is programming the controller. Many AI researchers have sought
to manage this complexity by developing computational abstractions based on
some version of commonsense belief-desire-intention (BDI) psychology--the
``folk'' theory of mind. In addition, they have tended to adopt a
``representationalist'' tactic in which the components of mental state
(beliefs, desires, intentions) are realized as symbolic structures to be
manipulated by the program. Another approach, one based on an abstract
correlational theory of information-bearing states in automata, was put
forward as an alternative. There was much discussion on the utility of
belief-desire-intention psychology, especially in its
``representationalist'' form, as a framework for building robots.
------------------------------
Date: 7 Feb 85 13:44:23-CST (Thu)
From: "John J. Grefenstette" <jjg%vanderbilt.csnet@csnet-relay.arpa>
Subject: Conference on Genetic Algorithms
Call for Papers
International Conference on Genetic Algorithms
and Their Applications
An International Conference on Genetic Algorithms and Their
Applications, sponsored by Texas Instruments and the U.S.
Navy Center for Applied Research in AI (NCARAI), will be
held on July 24-26, 1985 at Carnegie-Mellon University in
Pittsburgh. Authors are invited to submit papers on all as-
pects of Genetic Algorithms, including the following topics:
theoretical foundations of Genetic Algorithms; machine
learning using Genetic Algorithms; classifier systems; ap-
portionment of credit; Genetic Algorithms in function optim-
ization and search; experimental applications.
Authors are requested to submit three copies (hard copy
only) of a full paper by May 1, 1985 to the program chair-
man:
Dr. John J. Grefenstette
Computer Science Department
Vanderbilt University
Box 73 Station B
Nashville, TN 37235
Papers will be refereed by the Program Committee, and au-
thors will be notified of acceptance or rejection by May 20,
1985. Camera ready copies are due by June 21, 1985. Ac-
cepted papers will be published in the Conference Proceed-
ings.
Morning sessions of the conference will be devoted to
presentations of the accepted papers. Afternoon sessions
will be devoted to panel discussions of the general themes
raised in the morning sessions.
There will be no registration fee, but for planning purposes
all attendees are asked to register by June 1, 1985. Regis-
tration information may be obtained from:
Dr. Stephen F. Smith
Robotics Institute
Carnegie-Mellon University
Pittsburgh, PA 15213
sfs@CMU-RI-ISL1
(412) 578-8811
Conference Committee
---------- ---------
John H. Holland University of Michigan (Conference Chair)
Lashon B. Booker NCARAI
Kenneth A. De Jong NCARAI and George Mason University
John J. Grefenstette Vanderbilt University (Program Chair)
Stephen F. Smith C-MU Robotics Institute (Local Arrangements)
------------------------------
Date: Sat, 2 Feb 85 16:26:43 cst
From: Austin Melton <austin%kansas-state.csnet@csnet-relay.arpa>
Subject: Conference - Mathematical Foundations of Programming Semantics
[Forwarded from the SRI-AI bboard by Laws@SRI-AI.]
CALL FOR PAPERS AND CONFERENCE ANNOUNCEMENT
CONFERENCE ON
THE MATHEMATICAL FOUNDATIONS OF PROGRAMMING SEMANTICS
DATE AND SITE SPONSORS
Iowa State University
April 11 and 12, 1985 Kansas State University
Kansas State University The University of Kansas
Manhattan, Kansas 66506 The University of Nebraska
Wichita State University
The conference will be a forum for computer scientists and mathematicians
jointly to discuss current research and possible directions for future research
in both programming language semantics in general and the mathematics used
in programming semantics in particular. From these discussions the computer
scientists will have first-hand exposure to the mathematical ideas which
might prove fruitful for future work, and the mathematicians will gain insight
for future work by seeing how their results can be applied and by seeing what
types of mathematical results are needed for future work in programming
language semantics.
Suggested topics include, but are not limited to, the following:
theory of complete partial orders and continuous lattices,
topological and categorical approaches to semantics,
formal and descriptive aspects of semantics notations
The following computer scientists and mathematicians will be speaking at the
conference:
Dr. Dana Scott, Carnegie-Mellon University
Dr. Horst Herrlich, University of Bremen, West Germany
Dr. Adrian Tang, The University of Kansas
Dr. George Strecker, Kansas State University
Dr. Stephen Brookes, Carnegie-Mellon University
Dr. Carl Gunter, Carnegie-Mellon University
Authors are invited to submit five copies of extended abstracts (approximately
two pages double spaced) describing recent advances in programming semantics
or related mathematics. The first page of the abstract should include
all authors' names, mailing addresses, and telephone numbers. Graduate
students are also encouraged to submit abstracts. The submission deadline
is March 11, 1985. Authors will be notified of acceptance by March 22, 1985.
Five copies of the extended abstracts should be submitted to:
Prof. Austin Melton or Prof. Robert Wherritt
Computer Science Department Department of Mathematics and Statistics
Fairchild Hall, 121 Box 33
Kansas State University Wichita State University
Manhattan, Kansas 66506 Wichita, Kansas 67208
USA USA
or via CSNET
austin%kansas-state@csnet-relay
Abstracts of the accepted papers and the invited addresses will be available
to all conference participants at the start of the conference.
The conference proceedings will be published after the conference and
mailed to all the participants.
...
FOR MORE INFORMATION about the conference or accommodations please contact
Professor Austin Melton or Ms. Robin Niederee:
Kansas State University
Computer Science Department
Fairchild Hall, 121
Manhattan, Kansas 66506
913-532-6350
CSNET austin%kansas-state@csnet-relay or robin%kansas-state@csnet-relay
The registration fee is $35 (students $5).
Meals are included in the $35.00 registration fee. Students may purchase
meals for an additional $20.00.
PLEASE REGISTER AND MAKE MEAL RESERVATIONS BY APRIL 8, 1985. Registration and
meal reservations may be made via CSNET (austin%kansas-state@csnet-relay or
robin%kansas-state@csnet-relay) with payments being made at the conference.
------------------------------
End of AIList Digest
********************