IJCAI 1995- volume 1

Proceedings of the Fourteenth International

Joint Conference on Artificial Intelligence

Montreal, Quebec, Canada August 20-25,1995

ACTION AND PERCEPTION

VISION: EARLY VISION

Fitting Models to Distributed Representations of Vision

Sourabh A. Niyogi     3

Natural Basis Functions and Topographic Memory for Face Recognition

Rajesh P N. Rao and Dana H. Ballard         10

VISION: ACTIVE VISION

Representations for Active Vision

Cornelia Eermuller and Yiannis Aloimonos         20

Animate Vision in a Rich Environment

Tomas Uhlin and Jan-Olof Eklundh         27

VISION: QUALITATIVE METHODS

A Qualitative Approach to Sensor Data Fusion for Mobile Robot Navigation

Steven Reece and Hugh Durrant- Whyte         36

Qualitative Interpretation of Spectral Images: Reasoning with Uncertain Evidence

Qi Zhao and Toyoaki Nishida         42

VISION: SYSTEMS AND ARCHITECTURES         1

Control Structures for Incorporating Picture-Specific Context in Image Interpretation

 Rajiv Chopra and Rohini K. Srihari         50

Visual routines and visual search: a real-time implementation and an automata-theoretic analysis

Ian Horswill         56

VISION: SYSTEMS AND ARCHITECTURES     2

Adaptable Planner Primitives for Real-World Robotic Applications

Robert W. Wisniewski and Christopher M. Brown         64

An Architecture for Vision and Action

 R. James Firby, Roger E. Kahn, Peter N. Prokopowicz, and Michael J. Swain         72

VISION: VISION AND OTHER PERCEPTION

Active Agent Oriented Multimodal Interface System

 Osamu Hasegawa, Katsunobu Itou, Takio Kurita, Satoru Hayamizu, Kazuyo lanaka, Kazuhiko Yamamoto, and Nobuyuki Otsu   82      

Robotic Perception of Material

 Eric Krotkov         88

ROBOTICS: MULTI-AGENT SYSTEMS

Knowledge Considerations in Robotics and Distribution of Robotic Tasks

 Ronen I. Brafinan and Yoav Shoham         96

RESC: An Approach for Real-time, Dynamic Agent Tracking

 Milind Tambe and Paul S. Rosenbloom         103

ROBOTICS: NAVIGATION

Self-Organi/ation of Symbolic Processes through Interaction with the Physical World

 Jun Tami         112

Using Knowledge to Isolate Search in Route Finding

BingLiu         119

ROBOTICS: LEARNING

Motion Sketch: Acquisition of Visual Motion Guided Behaviors

 Takayuki Nakamura and Minora Asada         126

Using the Representation in a Neural Network's Hidden Layer for Task-Specific Focus of Attention

Shumeet Baluja and Dean A. Pomerleau         133

ROBOTICS: FORMAL METHODS

Formalizing Behavior-based Planning for Nonholonomic Robots

 Vikram Manikonda, JamesHendler, and P. S. Krishnaprasad         142

Logic Programming for Robot Control

 David Poole         150

AUDITORY SCENE ANALYSIS

Organization of Hierarchical Perceptual Sounds

: Music Scene Analysis with Autonomous Processing Modules  and a  Quantitative Information Integration Mechanism Kunio Kashino, Kazuhiro   158 Nakadai,Tomoyoshi  Kinoshita, and Hidehiko lanaka       

Residue-Driven Architecture for Computational Auditory Scene Analysis

  Tomohiro Nakatani, Hiroshi G. Okuno, and Takeshi Kawabata         165

AUTOMATED REASONING

PROOF PLANNING

Relational Rippling: A Ceneral Approach

  Alan Bundy and Vincent Lombart         175

A Model of Analogy-Driven Proof-Plan Construction

Erica Melis         182

ANALOGY AND ABSTRACTION

Second-Order Matching modulo Evaluation A Technique for Reusing Proofs

Thomas Kolbe and Christoph Walther         190

A Semantic Theory of Abstractions

P. Pandurang Nayak and Alan Y Levy         196

ABDUCTION

Abductive Framework for Nonmonotonic Theory Change

Katsumi Inoue and Chiaki Sakama         204

Model-Based Diagnosis using Causal Networks

  Adna n Da rwiche         211

SEARCH  1

Deadline Compliance, Predictability, and On-line Optimization in Real-Time Problem Solving 

Babak Hamidzadeh and Shashi Shekhar         220

Best: A New Method for Real-Time Decision Making

  Joseph C. Pemherton         227

SEARCH  2

How to Use Limited Memory in Heuristic Search

  Hermann Kaindl Gerhard Kainz, Angelika Leeb, and Harald Smetana         236

Experimenting with Revisits in Game Tree Search

  Subir Bhattacharya         243

SEARCH  3

On Bootstrapping Local Search with Trail-Markers 

Pang C Chen         252

The Trailblazcr Search with a Hierarchical Abstract Map

Takahiro Sasaki, Fumihiko Chimura, and Mario Tokoro         259

SEARCH 4

From Approximate to Optimal Solutions: A Case Study of Number Partitioning

  Richard  Korf         266

Best-First Fixed-Depth Game-Tree Search in Practice 

Aske Plaat, Jonathan Schaeffer, Wim Pijls, and Arie de Bruin         273

SATISFIABILITY 1

Theoretical Analysis of Davis-Putnam Procedure and Propositional Satisfiability

Nobuhiro Yugam          282

On the Complexity of Extending Ground Resolution with Symmetry Rules

  Thierry Boy de la Tour and Stiphane Demri         289

SATISFIABILITY         2

SEM: a System for Enumerating Models

 jian Zhang and Hantao Zhang         298

Performance Test of Local Search Algorithms Using New Types of Random CNF Formulas

Byungki Cha and Kazuo lwama         304

DEFAULTS

Towards Efficient Default Reasoning

  Ilkka Niemela         312

Default-Reasoning with Models 

Roni Khardon and Dan Roth         319

THEOREM PROVING 1

Extending Semantic Resolution via Automated Model Building: applications 

Ricardo Caferra and Nicolas Peltier         328

Model Elimination, Logic Programming and Computing Answers 

Peter Baumgartner, Ulrich Furbach, and Frieder Stolzcnburg         335

THEOREM PROVING         2

Equality Elimination for the Inverse Method and Extension Procedures

  Anatoli Degtyarev and Andrei Voronkov         342

Experiments with Associative-Commutative Discrimination Nets 

Leo Bachmair, la Chen, I. V Ramakrishnaru Siva Anantharaman, and Jacques Chabin         348

REASONING ABOUT PROGRAMS

A Methodology for Proving Termination of Genera] Logic Programs 

Elena Marchiori         356

Unique Normal Forms and Confluence of Rewrite Systems: Persistence 

Rakesh M. Verm a         362

CASE BASED REASONING

CASE BASED REASONING         1

Improving System Performance in Case-Based Iterative Optimization through Knowledge Filtering

Kazuo Miyashita and Katia Sycara         371

Remembering To Forget: A Competence-Preserving Case Deletion Policy for Case-Based Reasoning Systems 

Barry Smyth and Mark T. Keane         377

CASE BASED REASONING         2

Stratified Case-Based Reasoning: Reusing Hierarchical Problem Solving Episodes 

L. Karl Branting and David W. Aba         384

Using Introspective Reasoning to Refine Indexing 

Susan Fox and David B. Leake         391

CASE BASED REASONING         3

Using CBR to Drive IR

  Edwina L. Rissland and Jody J. Daniels         400

Within the Letter of the Law: open-textured planning 

Kathryn E. Sanders         408

COGNITIVE MODELLING

COGNITIVE MODELLING         1

Optional Deep Case Filling and Focus Control with Mental Images:  ANTLIMA-KOREF 

Anselm Blocker and /org R. J. Schirra         417

A Microfeature Based Approach Towards Metaphor Interpretation 

Ron Sun 424

COGNITIVE MODELLING 2

Forgetting and Compacting data in Concept Learning

  Gunther Sablon and Luc De Raedt         432

Determining what to learn through component-task modeling

  Bruce Krulwich, Larry Birnbaum, and Gregg Collins         439

COGNITIVE MODELLING         3

Using Information Content to Evaluate Semantic Similarity in a Taxonomy

Philip Resnik         448

On Heuristic Reasoning, Reactivity, and Search 

Susan L Epstein         454

COGNITIVE MODELLING     4

Action and Perception in Man-Made Environments 

Daniel D. Fu, KristianJ. Hammond, and Michael]. Swain         464

CONNECTIONIST MODELS

CONNECTIONS MODELS         1

Kanerva's Sparse Distributed Memory: An Object-Oriented Implementation on the Connection Machine

Andreas Turk and Gunther Gorz         473

Understanding Neural Networks via Rule Extraction 

Rudy Setiono and Huan Liu         480

CONNECTIONIST MODELS         2

GR2A Hybrid Knowledge-based System Using General Rules

  Zhe Ma, Robert F. Harrison, and R. Lee Kennedy         488

A Hybrid Fuzzy-Neural Expert System for Diagnosis 

Christoph S. Herrmann         494

CONNECTIONIST MODELS         3

A Hybrid Rule-based System: How Variables are Involved in Connectionist Rule-based Systems

Fukumi Kozato         502

Learning Distributed Representations for the Classification of Terms

 Alessandro Sperduti, Antonina  Starita, and Christoph Goller         509

CONNECTIONIST MODELS     4

A Novelty Detection Approach to Classification

 Nathalie Japkowicz, Catherine Myers, and Mark Gluck         518

Combining the Predictions of Multiple Classifiers: Using Competitive Learning to Initialize Neural Networks

Richard Maclin and Jude W Shavlik     524

CONNECTIONIST MODELS   5

A Model for Hormonal Modulation of Learning

Hiroaki Kitano         532

CONSTRAINT SATISFACTION

CONSTRAINT SATISFACTION  1

A Theoretical Evaluation of Selected Backtracking Algorithms

Grzegorz Kondrak and Peter van Beek         541

Extracting Constraint Satisfaction Subproblems

Eugene C. Freuder and Paul D. Hubbe         548

CONSTRAINT SATISFACTI

On the Space-Time Trade-orT in Solving Constraint Satisfaction Problems

Roberto J. Bayardo, Jr. and Daniel P. Miranker 558

Generalizing Inconsistency Learning for Constraint Satisfaction

Eugene C. Freuder and Richard J. Wallace         563

CONSTRAINT SATISFACTION  3

Look-ahead value ordering for constraint satisfaction problems

 Daniel Frost and Rina Dechter         572

Constraint Satisfaction as Global Optimization

Pedro Meseguer and Javier Larrosa         579

CONSTRAINT SATISFACTION   4

Increasing Functional Constraints Need to Be Checked Only Once

Bing Liu         586

Using Inference to Reduce Arc Consistency Computation

Christian Bessiere, Eugene C. Freuder, and Jean-Charles Rtgin         592

CONSTRAINT SATISFACTION  5

A Theoretical and Experimental Comparison of Constraint Propagation Techniques for Disjunctive  Scheduling

Philippe Baptiste and Claude Le Pape         600

Limited Discrepancy Search

William D. Harvey and Matthew L. Ginsberg         607

CONSTRAINT SATISFACTION  6

GSAT and Local Consistency

Kalev Kask and Rina Dechter         616

CONSTRAINT SATISFACTION  7

Constraint Solving over Semirings

Stefano Bistarelli, Ugo Montanari, and Francesca Rossi         624

Valued Constraint Satisfaction Problems: Hard and Easy Problems

Thomas Schiex, Helene Fargier, and Gtrard Verfaillie         631

CONSTRAINT SATISFACTION  8

Composition in Hierarchical CLP

Michael Jampel and Sebastian Hunt         640

Sparse Constraint Graphs and Exceptionally Hard Problems

Barbara M. Smith and Stuart A. Grant         646

DISTRIBUTED Al

COALITIONS

Task allocation via coalition formation among autonomous agents

 Onn Shehory and Sarit Kraus         655

Coalition Formation among Bounded Rational Agents

Tuomas W. Sandholm and Victor R Lesser         662

MULTIPLE AGENTS 1

Matchmaking for Information Agents

Daniel Kuokka and Larry Harada         672

Deriving Multi-Agent Coordination through Filtering Strategies

Eithan Ephrati, Martha E. Pollack, and Sigalit Ur         679

MULTIPLE AGENTS 2

Flexible social laws

Will Briggs and Diane Cook         688

Equilibrium Analysis of the Possibilities of Unenforced Exchange in Multiagent Systems

Tuomas W Sandholm and Victor R Lesser         694

DISTRIBUTED PLANNING

The Semantics of Intention Maintenance for Rational Agents

 Michael P Georgeffand Anand S. Rao         704

Social Dilemmas in Computational Ecosystems

 Tad Hogg         711

GENETIC ALGORITHMS

GENETIC ALGORITHMS  1

Hybrid Learning Using Genetic Algorithms and Decision Trees for Pattern Classification

/. Bala, J. Huang, H. Vafaie, K Dejong, and H Wechsler         719

A genetic prototype learner

Sandip Sen and Leslie Knight         725

GENETIC ALGORITHMS 2

Gene Duplication to Enable Genetic Programming to Concurrently Evolve Both the Architecture

and Work-Performing Steps of a Computer Program

 John R. Koza         734

The Automatic Programming of Agents that Learn Mental Models and Create Simple Plans of Action

David Andre         741

KNOWLEDGE BASE TECHNOLOGY

KNOWLEDGE BASE TECHNOLOGY 1

Knowledge Representation in the Large

 Peter D. Karp and Suzanne M. Paley         751

Efficient Algorithms and Performance Results for Multi-User Knowledge Bases

Vinay K. Chaudhri and John Mylopoulos         759

KNOWLEDGE BASE TECHNOLOGY 2

The Generic Frame Protocol

Peter D. Karp, Karen L. Myers, and Tom Gruber         768

Knowledge-Based Anytime Computation

AbdeUillah Mouaddib and Shlomo Zilberstein         775

PLANNING, MONITORING, AND CONTROL

Proposing Measurements in Dynamic Systems

Johann Gamper and Wolfgang Nejdl         784

Synthesizing Plant Controllers Using Real-time Goals

M. Barbeau, F Kabanza, and R. St-Denis         791

KNOWLEDGE REPRESENTATION

DESCRIPTION LOGICS

What's in an Aggregate: Foundations for Description Logics with Tuples and Sets

Giuseppe De Giacomo and Maurizio Lenzerini         801

Terminological Logics with Modal Operators

Franz Baader and Armin Laux         808

EXPLANATION

Explaining Subsumption in Description Logics Deborah

L. McGuinness and Alexander T Borgida         816

Determining Explanations using Transmutations

Mary-Anne Williams, Maurice Pagnucco, Norman Foo, and Brailey Sims         822

KNOWLEDGE COMPILATION

An Analysis of Approximate Knowledge Compilation

Alvaro del Val         830

Knowledge Compilation Using Theory Prime Implicates

 Pierre Marquis         837

COMMONSENSE KNOWLEDGE

Toward a Geometry of Common Sense: A Semantics and a Complete Axiomatization of Mcreotopology

Nicholas Asher and Laure Vieu         846

A Logical Account of Relevance

Gerhard Lakemeyer         853

COMPLEXITY

The Comparative Linguistics of Knowledge Representation

Goran Gogic, Henry Kautz, Christos Papadimitriou, and Bart Selrnan         862

Semantics and Complexity of Abduction from Default Theories

Thomas Titer, Georg Gottlob, and Nicola Leone         870

DIAGRAMS

Inter-diagrammatic Reasoning

Michael Anderson and Robert McCartney         878

Qualitative Structural Analysis Using Diagrammatic Reasoning

Shirley Tessler, Yumi Iwasaki, and Kincho Law         885

SPATIAL REASONING

An algebraic approach to granularity in qualitative time and space representation

Jerome Euzenat         894

Topological Inference

Michelangelo Grigni, Dimitris Papadias, and Christos Papadimitriou         901

SHAPE AND SPACE

Utilizing Moment Invariants and Grobner Bases to Reason About Shapes

Haim Schweitzer  andjanell Straach         908

A Qualitative Discretization for Two-Body Contacts

Amitabha Mukerjee, Manish Agarwal, and Praveen Bhatia         915

INFORMATION GATHERING

Letizia: An Agent That Assists Web Browsing

Henry Lieberman         924

Category Translation: Learning to understand information on the Internet

Mike Perkowitz and Oren Etzioni         930

AWARDS

RESEARCH EXCELLENCE AWARD

Explaining the Ineffable: AI on the Topics of Intuition, Insight and Inspiration

Herbert A. Simon, Carnegie Mellon University         939

COMPUTERS AND THOUGHT AWARD

Rationality and Intelligence

Stuart Russell, University of California, Berkeley         950

INVITED SPEAKERS

Profiling Communication in Distributed Genetic Algorithms

Jonathan Maresky, Yuval Davidor, Daniel Gitler, Gad Aharoni, and Amnon Barak, The Hebrew University of Jerusalem         961

Agents on Stage: Advancing the State of the Art of AI Barbara

Hayes-Roth, Stanford University         967

Turing Test Considered Harmful

Patrick Hayes, Beckman Institute, and Kenneth Ford, University of West Florida         972

Vive la difference! Individualised interaction with users

 Judy Kay, University oj Sydney         978

Biologically Inspired Defenses Against Computer Viruses

Jeffrey O. Kephart, Gregory B. Sorkin, William C Arnold, David M. Chess, Gerald J. Tesauro, and Steve R. White, IBM Thomas J. Watson Research Center         985

Inductive Logic Programming: Inverse Resolution and Beyond

Stephen Muggleton, Oxford University Computing Laboratory         997

Stochastic Search and Phase Transitions: AI Meets Physics

Bart Selrnan, AT&T Bell Laboratories         998

Modeling Living Systems for Computer Vision

 Demetri Terzopoulos, University of Toronto         1003