Copy Link
Add to Bookmark
Report
AIList Digest Volume 5 Issue 061
AIList Digest Monday, 2 Mar 1987 Volume 5 : Issue 61
Today's Topics:
Seminars - Motion Planning in Time-Varying Environment (UPenn) &
A Step Toward a Logic Machine (SMU) &
VLSI Approach to the ELIS Lisp Machine (SU),
Conference - Columbia AI Symposium
----------------------------------------------------------------------
Date: Sat, 28 Feb 87 14:01:15 EST
From: tim@linc.cis.upenn.edu (Tim Finin)
Subject: Seminar - Motion Planning in Time-Varying Environment (UPenn)
COLLOQUIUM
Computer and Information Science
University of Pennsylvania
Philadelphia PA
10:30am 3/2/87, 307 Towne Bldg.
Motion Planning in Time-varying Environment
Kamal Kant Gupta
Computer Vision and Robotics Lab
McGill University
Motion Planning Problem is to determine the motion of an object,
from a start position to a goal position, while avoiding collision
with other objects (obstacles) in its enviroment. Most Motion Planning
research, up until very recently, has considered static obstacles, i.e.,
plan the path to avoid the static obstacles, called the path planning
problem, or, the PPP. We consider the problems of planning collision-
free trajectories (path as a function of time) for an object among
moving as well as static obstacles. We call it the Trajectory Planning
Problem (TPP) in time-varying enviroments.
Our approach to formulating the TPP is to consider space-time, where
time is represented explicitly. Such a representation leads to a
geometric view of trajectory - as a curve in space-time-and lends itself
to use of computational geometric techniques in space-time. Such techniques
are quite novel in the sense that they do not occur in the case of only
static obstacles.
We propose a heuristic but natural decomposition of the TPP into two
sub-problems: (i) plan a path to avoid the static obstacles, i.e.
solve the PPP, and (ii) plan the velocity of the robot along the
path to avoid collision with the moving obstacles. We call the
second sub-problem the velocity planning problem, the VPP. The
main motivation behind the decomposition is to reduce the
complexity of the full problem, and present efficient algorithms
for collision-free trajectories.
Standard algorithms may be used to sovle the PPP. We then present
fast, efficient and complete algorithms to solve the VPP. The essence
of these algorithms lies in forulating the VPP in 2-dimensional path-
time. In the process, we also explore some properties of the path-
time space.
These algorithms have applications in several domains of robotics. In
particular, we shall illustrate the use of these algorithms in two
domains: i) for autonomous navigation of a mobile robot, and ii)
for motion co-ordination of multiple robots.
------------------------------
Date: Sat, 28 Feb 1987 13:19 CST
From: Leff (Southern Methodist University)
<E1AR0002%SMUVM1.BITNET@wiscvm.wisc.edu>
Subject: Seminar - A Step Toward a Logic Machine (SMU)
Seminar Announcement, Computer Science and Engineering, Southern
Methodist University, MOnday, March 2, 1987, Room 315 SIC, 1:30PM
A Step Toward a Logic Machine, C. S. Tang, Carnegie-Mellon University
XYZ is a software development support system to unify various ways
of programming programming [sic] with HLL (Pascal, Ada, Fortran etc.),
programming with abstract specification (temporal logic, production systems,
Prolog, pre-post condition specification, etc.) and programming with graphics
(structured flow chart, Petri Nets, Data Flow Diagrams, etc.) It is based on
a linear-time temporal logic language with a uniform framework of programs,
to combine the abstract behavior description with dynamic state transition.
It could be used to represent the dynamic semantics of HLLs, which
could serve as the basis of a semantics-directed compiler generation and source
to source transformation system, and also to represent different layers of
abstract specification, from the very abstract level down to the assembly
like efficiently executable level, such that a method is introduced for
programming by decompositional specification and verification
within this identical famework. And on this basis, related with programming
with Dataflow Diagram, an approach to connect the informal methodology of
sytem design with the fomral method of programming such as specification,
verification, program decomposition and transformation are suggested. It
is considered as a step toward a model of an architecture really based
on logic, which could do logic reasoning and abstract specification
conveniently and is still able to execute conventional programs as
efficiently as on conventional Von Neumann computers.
This "uniform program framework" appraoch is different from those to
express program state transition by introducing new logic variants
such as interval logic or branching logic in that: 1) This approach
can avoid the task of building new metamathematical foundations and is
easier to understand to use; 2) It could be implemented efficiently;
3) Prolog-like production systems are its sublanguage, so it is
different from those systems to extend Prolog with temporal logics.
The latter could not execute algorithmic programs efficiently; 4) It is
even more expressive.
------------------------------
Date: 28 Feb 87 1027 PST
From: Carolyn Talcott <CLT@SAIL.STANFORD.EDU>
Subject: Seminar - VLSI Approach to the ELIS Lisp Machine (SU)
Title: VLSI approach to the ELIS Lisp machine
Speaker: Yasushi Hibino
Director of Second Research Section
NTT Basic Research Laboratories
Nippon Telegraph and Telephone
Time: Monday March 2, 3:30pm
Place: 352 Margaret Jacks
Abstract:
The LISP Machine ELIS was designed to achieve a comfortable
interactive programming environment by a fast microcoded LISP
interpreter. ELIS is a microprogram control machine with a 32k
64-bits-words writable control store. ELIS also has a 32K word
hardware stack and special memory interface registers. VLSI ELIS chip
is developed by two-micron double metal layer CMOS technology. The
VLSI ELIS is compatible with an ELIS breadboard machine in the level
of microcodes. Therefore, TAO Lisp, which is a dialect of CommonLisp
and assimilates object oriented programming, logic programming and
concurrent programming within the Lisp world, is running on the VLIS
ELIS. The speed of interpreted codes in TAO is comparable to that of
compiled codes of MIT's Lisp machines. THis good performance is
attained by a simple internal bus structure and a design of fucntion
blocks with iterative circuit structures.
In my talk, the architecture of ELIS is briefly introduced and a VLSI
approach for it is discussed. The approach is not like Meed and
Conway's. It is rather orthodox approach, because in the case of a
dedicated machine it is not desirable that VLSI design methodology
restricts an architecture of the machine.
[CLT -- Sorry for the short notice, please pass this on to anyone
you think might be interested.]
------------------------------
Date: Sun 1 Mar 87 18:46:18-EST
From: Michael Lebowitz <LEBOWITZ@CS.COLUMBIA.EDU>
Subject: Conference - Columbia AI Symposium
ARTIFICIAL INTELLIGENCE DAY
SPONSORED BY DEPT. OF COMPUTER SCIENCE
COLUMBIA UNIVERSITY
MARCH 6, 1987
DAG ROOM, SCHOOL OF INTERNATIONAL AFFAIRS
10:00 Brian Reiser "An Intelligent Tutoring Systems"
Princeton Univ.
11:00 Coffee Break
11:30 Edward H. Shortliffe "Graphical Access to an Expert System:
Stanford Univ.
2:00 Carl Hewitt "Due Process"
MIT
3:00 Ruzena Bajcsy "Errors and Mistakes in Sensory
Univ. of Pennsylvania Programming"
4:00 Reception Computer Science Lounge
------------------------------
End of AIList Digest
********************
