IJCAI 1989-volume-2

Proceedings of the

Eleventh International Joint Conference

on Artificial Intelligence

Volume-2

August 20-25 1989

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 5. 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 Wermtcr         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