Proceedings of the Eleventh International Joint Conference on Artificial Intelligence (II)

IJCAI-89 Contents Vol2

Proceedings of the Eleventh International Joint Conference

Volume 2

August 20-25 1989

sponsored by International Joint Conferences on Artificial Intelligence, Inc. (IJCAII)

cosponsored and hosted by American Association for Artificial Intelligence (AAAI)

In cooperation with A consortium of Michigan companieson

Artificial Intelligence

PLANNING, SCHEDULING, REASONING ABOUT ACTIONS

Sometimes Updates Are Circumscription

Marianne Winslett  859

Things That Change by Themselves

Vladimir Lifschitz and Arkady Rabinov  864

A Formal Account of Self-Knowledge and Action

Yves Lesperance  868

Constraint Satisfaction with Delayed Evaluation

Monte Zweben and Megan Eskey  875

Constraint Posting for Verifying VLSI Circuits

Daniel Weise  881

Temporally Coarse Representation of Behavior for Model-based Troubleshooting of Digital Circuits

Waiter Hamscher  887

Filter Preferential Entailment for the Logic of Action in Almost Continuous Worlds

Erik Sandewall  894

A Parallel Algorithm for Statistical Belief Refinement and its use in Causal Reasoning

Jay C. Weber  900

Temporal Projection and Explanation

Andrew B. Baker and Matthew L. Ginsberg  906

Negotiation and Task Sharing Among Autonomous Agents in Cooperative Domains

Gilad Zlotkin and Jeffrey S. Rosenschein  912

On Cooperation in a Multi-Entity Model

Moshe Tennenholtz and Yoram Moses  918

Ascribing Plans to Agents

Kurt Konolige and Martha E. Pollack  924

Ordering Problem Subgoals

jie Cheng and Keki B. Irani  931

Towards a Theory of Conflict Detection and Resolution in Nonlinear Plans

Joachim Hertzberg and Alexander Hoz  937

Control of Refitting during Plan Reuse

Subbarao Kambhampati and James A. Hendler  943

A Model of Planning for Plan Efficiency: Taking Advantage of Operator Overlap

Caroline Clarke Hayes  949

Time for Action: On the Relation Between Time, Knowledge and Action

Yoav Shoham.  954

Coal Ordering in Partially Ordered Plans

Mark Drummond and Ken Carrie  960

Minimal Change and Maximal Coherence: A Basis for Belief Revision and Reasoning about Actions

An and S. Rao and Norman Y.Foo  966

Decision-Making in an Embedded Reasoning System

Michael P. Georgeff and Francois Felix Ingrand  972

Solving Time-Dependent Planning Problems

Mark Boddy and Thomas Dean  979

A Model for Projection and Action

Keiji Kanazawa and Thomas Dean  985

The Dynamics of Action Selection

PattieMaes  991

A Planning/Scheduling Methodology for the Constrained Resource Problem

Naiping Keng and David Y. Y. Yun  998

A Reactive Scheduling Agent

Patrick Prosser  1004

Constraint Satisfiability Algorithms for Interactive Student Scheduling

Roncn Feldman and Martin Charles Golumbic  1010

A Maneuvering-Board Approach to Path Planning with Moving Obstacles

Lou Tychonievich, David Zaret, John Mantegna,

Robert Evans, Eric Muehle and Scott Martin  1017

Neuroplanners and Their Application to Eyes/Head/Neck Coordination

Daryl H. Graf and Wilf R. LaLonde  1022

Motion Planning of Multi-Joint Robotic Arm with Topological Dimension Reduction Method

Bo Zhang, Ling Zhang and Tian Zhang  1029

Representations of Assembly Sequences

L. S. Homem de Mello and A. C. Sanderson  1035

COMMONSENSE REASONING

Preferred Subtheories: An Extended Logical Framework for Default Reasoning

Gerhard Brewka  1043

A Correct Non-Monotonic ATMS

Ulrich Junker  1049

Prediction is Deduction but Explanation is Abduction

Murray Shanahan  1055

A Knowledge-Level Account of Abduction Hector

J. Lcvcsquc  7067

Outline of A Naive Semantics for Reasoning with Qualitative Linguistic Information

Daniel G. Schwartz  1068

A Semantics for Probabilistic Quantifier-Free First-Order Languages, with ParticularApplication to Story Understanding 

Eugene Charniak and Robert Goldman  1074

HUGIN— A Shell for Building Bayesian Belief Universes for Expert Systems

Stig K. Andersen,Kristian G. Olesen, Finn V.Jensen and Frank Jensen   1080

Negative Reasoning Using Inheritance

LinPadgham   1086

An Evidence-based Framework for a Theory of Inheritance

T. Krishnaprasad and Michael Kifer   1093

On the Declarative Semantics of Inheritance Networks

T. Krishnaprasad, Michael Kifer and David S.Warren   1099

A Modest, but Semantically Well Founded, Inheritance Reasoner

Fahiem Bacchus  1104

Measure-Free Conditioning, Probability and Non-Monotonic Reasoning

Didier Dubois and Henri Pradc  1110

An Analysis of ATMS-Based Techniques for Computing

Dempster-Shafcr Belief Functions Gregory M. Provan  1115

Reflection and Action Under Scarce Resources: Theoretical Principles and Empirical Study

Eric J. Horvitz, Gregory F. Cooper and David E. Heckerman  1121

Qualitative Reasoning of Bayesian Belief Using Meta-knowledge

Bon K. Sy   1128

A Semantical Approach to Stable Inheritance Reasoning

Craig Boutilier   1134

The Tractability of Path-Based Inheritance

Bart Sclman and Hector J. Levcsque   1140

Vivid Knowledge and Tractable Reasoning:

David W. Etherington, Alex Borgida, Ronald). Brachman and Henry Kautz  1146

Skeptical Inheritance: Computing the Intersection of Credulous Extensions

Lynn Andrea Stein  1153

KNOWLEDGE REPRESENTATION

Uncertainty, Belief, and Probability Ronald

F agin and Joseph Y. Halpern  1161

Belief as Defeasible Knowledge

Yoav Shoham and Yoram Moses  1168

Using Global Properties for Qualitative Reasoning: A Qualitative SystemTheory

Yoshitcru Ishida   1174

Perturbation Analysis with Qualitative Models

Renato De Mori and Robert Prager  1180

Stochastic Analysis of Qualitative Dynamics

Jon Doyle and Elisha P. Sacks  1187

Constraint Reasoning Based on Interval Arithmetic

Eero Hyvonen  1193

Relating the TMS to Autoepistemic Logic

Yasushi Fujiwara andShinichi Honiden   1199

On the Relation Between Truth Maintenance and Autoepistemic Logic

MichaelReinfrank, Oskar Dressier and Gerd Brewka  1206

On the Relation Between Autoepistemic Logic and Circumscription

KurtKonolige  1213

Using a Feature Algebra for Reasoning about Geometric Feature Interactions

Raghu R. Karinthi and Dana 5. Nau  1219

Automated Physical Modeling

Andrew Gelsey  1225

A Focused, Context-Sensitive Approach to Monitoring

Richard J. Doyle, Suzanne M. Sellers and David J. Atkinson  1231

Model-Based Monitoring of Dynamic Systems

Daniel Dvorak and Benjamin Kuipers  1238

Approximation of Indistinct Concepts

Zhang Mingyi  1244

ANASTASIL: A Hybrid Know ledge-Based System for Document Layout Analysis

Andreas Dengel and Gerhard Barth  1249

Temporal Matching: Recognizing Dynamic Situations from Discrete Measurements

Klaus Nokel  1255

The Orders of Magnitude Models as Qualitative Algebras

L. Travd-Massuyds and N. Piera  1261

Processes at Discontinuities

Patrick J. Hayes and Michael Ley ton  1267

Introducing Actions into Qualitative Simulation

Kenneth D. Forbus  1273

The Thought Experiment Approach to Qualitative Physics

David L. Hibler and Gautam Biswas  1279

The Logic of Time Structures: Temporal and Nonmonotonic Features

Mira Balaban and Neil V. Murray  1285

Approximation Algorithms for Temporal Reasoning

Peter van Beek  1291

Managing Efficiently Temporal Relations Through Indexed Spanning Trees

Malik Ghallab and Amine Mounir Alaoui  1297

Normality and Faults in Logic-Based Diagnosis

David Poole  1304

A Theory of Diagnosis for Incomplete Causal Models

Luca Console, Danielc Theseider Dupr£ and Pictro Torasso  1311

"Physical Negation"—Integrating Fault Models into the General Diagnostic Engine

Peter Struss and Oskar Dressier  1318

Diagnosis with Behavioral Modes

Johan de Kleer and Brian C. Williams  1324

Reasoning about Kinematic Topology

Boi Faltings, Emmanuel Baechler and Jeff Primus  1331

Simplification and Abstraction of Kinematic Behaviors

Leo Joskowicz  1337

Reasoning About Hidden Mechanisms

Richard J. Doyle  1343

A Diagnostic Algorithm based on Models at Different Level of Abstraction

MassimoGallanti, Marco Roncato, Alberto Stcfanini, Georgio Tornielli  1350

Experience Learning in Model-Based Diagnostic Systems

Yoshiyuki Koseki  1356

Candidate Ordering and Elimination in Model-Based Fault Diagnosis

Jiah-shing Chen and Sargur N. Srihari  1363

An Integrated Knowledge Based Assembly Control System for Automobile Manufacturing

B. Frcitag, B. Huber and W. Womann  1369

An Analysis of First-Order Logics of Probability

Joseph Y. Halpcrn  1375

On the Semantics of Counterfactuals

Peter Jackson  1382

Functional Representation of Designs and Redesign Problem Solving

Ashok Goel and B. Chandrasckaran  1388

Towards a Generic Model of Configuraton Tasks

Sanjay Mittal and Felix Frayman  1395

A Case-Based Mechanical Redesign System

Francois Daube and Barbara Hayes-Roth  1402

Design Optimization Using Dynamic Evaluation

Witold Paluszynski and Ira Kalet  1408

A Unified View of Propositional Knowledge Base Updates

Hirofum i Ka tsuno and A Iberto O. Mendelzon  1413

Plausible Infercncing Using Extended Composition

Michael N. Huhns and Larry M. Stephens  1420

Storing and Generalizing Multiple Instances While Maintaining Knowledge-Level Parallelism 

Ronald A. Sumida and Michael G. Dyer  1426

Reasoning About Assumptions in Graphs of Models

Sanjaya Addanki, Roberto Cremonini and J. Scott Penberthy  1432

Tuning a Knowledge Base of Refinement Rules To Create Good Circuit Designs

Chris Jong and Phil Franklin  1439

Automating the Construction of Patchers That Satisfy Global Constraints

Kerst'm Voigt and Chris Jong  1446

Extending the Constraint Propagation of Intervals

Allen C. Ward, Tonics Lozano-Pe*rez and Warren P. Seering  1453

SPEECH AND NATURAL LANGUAGE

A Schema-Based Approach to Understanding Subjunctive Conditionals Wayne Wobcke  1461

Semantic Interpretation Based on the Multi-World Model

Katashi Nagao  1467

Semantics of Perspectival Utterances

Yasuhiro Katagiri  1474

Formal Properties and Implementation of Bidirectional Charts

Giorgio Satta and Oliviero Stock  1480

Integration of Semantic and Syntactic Constraints for Structural Noun Phrase Disambiguation

Stefan Wermter  1486

Bidirectional Use of Knowledge in the Multi-modal NL Access System XTRA

Jurgen AWgayer, Roman Jansen-Winkeln, Carola Rcddig and Norbert Reithingcr.  1492

Computing Pronoun Antecedents in an English Query System

KurtGoddcn  1498

A Reactive Approach to Explanation

Johanna D. Moore and William R. Swartout  1504

Phrasing a Text in Terms the User Can Understand

John A. Bateman and C6cile L Paris  1511

POPEL-HOW: A Distributed Parallel Model for Incremental Natural Language Production with Feedback

Wolfgang Finklerand Guntcr Neumann  1518

Controlling a Language Generation Planner

Sergei Nirenburg, Victor Lesser and Eric Nybcrg  1524

On the Generalization Capability of Multi-Layered Networks in the Extraction of Speech Properties

Renato De Mori, Yoshua Bengio and Piero Cosi  1531

A Parallel Parser for Spoken Natural Language

Egidio P. Giachin and Claudio Rullent  1537

Layering Predictions: Flexible Use of Dialog Expectation in Speech Recognition

Shcryl R. Young, Wayne H. Ward and Alexander G. Hauptmann  1543

Computer-Aided Grammar Acquisition in the Chinese Understanding System CUSAGA

Lu Ruqian, Liu Yinghui and Li Xiaobin  1550

Lexicon Acquisition: Learning from Corpus by Capitalizing on Lexical Categories

UriZemilc  1556

VISION AND ROBOTICS

Perception of Non-Rigid Motion: Inference of Shape, Material and Force

Alex Pentland and John Williams  1565

The Complexity of Perceptual Search Tasks

John K. Tsotsos  1571

A Homogeneous Framework for Visual Recognition

Rick Kjcldsen, Ruud M. Bolle, Andrea Califano and Russell W. Taylor  1578

A "Small Leakage" Model for Diffusion Smoothing of Image Data

Li-Dong Cai  1585

Can Early Stage Vision Detect Topology

Lifu Liu, Nanyuan Zhao and Zhaoqi Bian  1591

Objective Functions for Feature Discrimination

Pascal Fua and Andrew J. Hanson  1596

Some Experiments in Applying Inductive Inference Principles to Surface Reconstruction

Edwin P. D. PednaulL  1603

Three-Dimensional Interpretation of Quadrilaterals

Gang Xu and Saburo Tsuji  1610

Visual Reasoning in Geometry Theorem Proving

Michelle Y. Kim  1617

Experiments with a Network-Based Geometric Reasoning Engine

Robert B. Fisher and Mark J. L. Orr  1623

Building a World Model for a Mobile Robot Using Dynamic Semantic Constraints

Minoru Asada and Yoshiaki Shirai  1629

Reference Frames for Animate Vision

Dana H. Ballard  1635

Using Generic Knowledge in Analysis of Aerial Scenes: A Case Study

Andres Huertas, William Cole and Ramakant Nevada  1642

Chromatic Stereopsis

John R. Jordan III, Alan C Bovik and Wilson S. Geisler  1649

Using Line Correspondence Stereo to Measure Surface Orientation

Lawrence B. Wolff and Terrance E. Boult  1655

A Region-Based Stereo Algorithm

Gang Xu, Hideki Kondo and Saburo Tsuji  1661

PANELS

The Challenge of Neural Darwinism

Stephen W. Smoliar  1669

Robot Navigation

David P. Miller  1672

High-Impact Future Research Directions for Artificial Intelligence

Perry W. Thorndyke  1675

Artificial Intelligence and Space Exploration

PeterFriedland  1676

(How) Is Al Impacting Manufacturing?

Mark S. Fox  1679

DISCLAIMER: Please note that IJCAI Organization is the sole copyright owner of all materials published in the Proceedings of its conferences. All rights are reserved. No part of any IJCAI conference Proceedings may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher, which is also the IJCAI Organization. Contact information for obtaining written permission can be found here.