clarke@csri.toronto.edu (Jim Clarke) (10/28/88)
(MP = McLennan Physical Labs., 60 St. George Street)
(RS = Rosebrugh Building, 81 Taddle Creek Road)
SUMMARY:
AI SEMINAR - Tuesday, November 8, 2:00 p.m. in MP 134 -- David Smith:
"A Decision-Theoretic Approach to the Control of Planning Search"
NUMERICAL ANALYSIS SEMINAR - Fri., Nov. 11, 10 a.m. in RS310 -- Nicholas Higham:
"Fast Polar Decomposition of an Arbitrary Matrix"
---------------
AI SEMINAR - Tuesday, November 8, 2:00 p.m. in MP 134
David Smith
Rockwell International Science Centre, Palo Alto
"A Decision-Theoretic Approach to the Control of Planning Search"
Abstract. One impediment to the realization of effective planning systems
is the problem of controlling search. For a typical planning problem,
there are usually many partial plans that will achieve the desired goal.
Few of these turn out to be realizable, and fewer yet result in efficient
plans. To make planning tractable a system must be able to focus its at-
tention on only the most promising alternatives. In this talk I advocate a
decision-theoretic approach to the control of planning search. I assume
that the planner has models available of the cost of achieving atomic goals
and their negations. I also assume that it has models of the likelihood of
being able to achieve such goals. Using this information, I will show how
a planner can choose between alternative actions for achieving goals and
subgoals, can choose the order in which to plan for conjuncts in a conjunc-
tive goal or subgoal, can decide when to make assumptions or insert condi-
tionals into a plan, and can decide when to interleave planning with execu-
tion.
NUMERICAL ANALYSIS SEMINAR - Friday, November 11, 10:00 a.m. in RS310
Nicholas J. Higham
Department of Computer Science, Cornell University
(Joint work with Robert S. Schreiber, RIACS, NASA Ames Research Center, Moffet Field, CA)
"Fast Polar Decomposition of an Arbitrary Matrix"
The polar decomposition of an m x n matrix A of full rank, where m >= n,
can be computed using a quadratically convergent algorithm of Higham
[SIAM. J. Sci. Stat. Comput., 7 (1986), pp.1160--1174]. The algorithm is
based on a Newton iteration involving a matrix inverse. We show how with
the use of a preliminary complete orthogonal decomposition the algorithm
can be extended to arbitrary A. We also describe how to use the algo-
rithm to compute the positive semi-definite square root of a Hermitian po-
sitive semi-definite matrix. We formulate a hybrid algorithm which adap-
tively switches from the matrix inversion based iteration to a matrix mul-
tiplication based iteration due to Kovarik, and to Bjorck and Bowie. The
decision when to switch is made using a condition estimator. This ``matrix
multiplication rich'' algorithm is shown to be more efficient on machines
for which matrix multiplication can be executed 1.5 times faster than ma-
trix inversion.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
BITNET,CSNET: clarke@csri.toronto.edu CDNNET: clarke@csri.toronto.cdn
UUCP: {allegra,cornell,decvax,linus,utzoo}!utcsri!clarke