Van Harmelen F., Lifschitz V., Porter B. Handbook of Knowledge Representation

Подождите немного. Документ загружается.

FOUNDATIONS OF

ARTIFICIAL INTELLIGENCE

Foundations of Artiﬁcial Intelligence

Series Editors

J. Hendler

H. Kitano

B. Nebel

AMSTERDAM–BOSTON–HEIDELBERG–LONDON–NEW YORK–OXFORD

PARIS–SAN DIEGO–SAN FRANCISCO–SINGAPORE–SYDNEY–TOKYO

Handbook of Knowledge Representation

Edited by

Frank van Harmelen

Vrije Universiteit Amsterdam

The Netherlands

Vladimir Lifschitz

University of Texas at Austin

USA

Bruce Porter

University of Texas at Austin

USA

AMSTERDAM–BOSTON–HEIDELBERG–LONDON–NEW YORK–OXFORD

PARIS–SAN DIEGO–SAN FRANCISCO–SINGAPORE–SYDNEY–TOKYO

Elsevier

Radarweg 29, PO Box 211, 1000 AE Amsterdam, The Netherlands

The Boulevard, Langford Lane, Kidlington, Oxford OX5 1GB, UK

First edition 2008

No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form

or by any means electronic, mechanical, photocopying, recording or otherwise without the prior written

permission of the publisher

Permissions may be sought directly from Elsevier’s Science & Technology Rights Department in Oxford,

UK: phone (+44) (0) 1865 843830; fax (+44) (0) 1865 853333; email: permissions@elsevier.com. Alter-

natively you can submit your request online by visiting the Elsevier web site at http://elsevier.com/locate/

permissions, and selecting Obtaining permission to use Elsevier material

Notice

No responsibility is assumed by the publisher for any injury and/or damage to persons or property as a

matter of products liability, negligence or otherwise, or from any use or operation of any methods, products,

instructions or ideas contained in the material herein. Because of rapid advances in the medical sciences, in

particular, independent veriﬁcation of diagnoses and drug dosages should be made

Library of Congress Cataloging-in-Publication Data

A catalog record for this book is available from the Library of Congress

British Library Cataloguing in Publication Data

A catalogue record for this book is available from the British Library

ISBN: 978-0-444-52211-5

For information on all Elsevier publications

visit our website at books.elsevier.com

Printed and bound in United Kingdom

0809101112 10987654321

We dedicate this book

to the memory of Ray Reiter (1939–2002)

This page intentionally left blank

Preface

Knowledge Representation and Reasoning is at the heart of the great challenge of

Artiﬁcial Intelligence: to understand the nature of intelligence and cognition so well

that computers can be made to exhibit human-like abilities. As early as 1958, John

McCarthy contemplated Artiﬁcial Intelligence systems that could exercise common

sense. From this and other early work, researchers gained the conviction that (artiﬁcial)

intelligence could be formalized as symbolic reasoning with explicit representations

of knowledge, and that the core research challenge is to ﬁgure out how to represent

knowledge in computers and to use it algorithmically to solve problems.

Fifty years later, this book surveys the substantial body of scientiﬁc and engineer-

ing insights that constitute the ﬁeld of Knowledge Representation and Reasoning.

Advances have been made on three fronts. First, researchers have explored general

methods of knowledge representation and reasoning, addressing fundamental issues

that cut across application domains. Second, researchers have developed specialized

methods of knowledge representation and reasoning to handle core domains, such as

time, space, causation and action. Third, researchers have tackled important applica-

tions of knowledge representation and reasoning, including query answering, planning

and the Semantic Web. Accordingly, the book is divided into three sections to cover

these themes.

Part I focuses on general methods for representing knowledge in Artiﬁcial Intelli-

gence systems. It begins with background on classical logic and theorem proving, then

turns to new approaches that extend classical logic—for example, to handle qualitative

or uncertain information—and to improve its computational tractability.

• Chapter 1 provides background for many of the subsequent chapters by survey-

ing classical logic and methods of automated reasoning.

• Chapter 2 describes the remarkable success of satisﬁability (SAT) solvers. Re-

searchers have found that this type of automated reasoning can be used for an

ever increasing set of practical applications and that it can be made surprisingly

efﬁcient.

• Chapter 3 reviews research in Description Logics, which provides methods for

representing and reasoning with terminological knowledge. Description logics

are the core of the representation language of the Semantic Web.

• Chapter 4 describes constraint programming, a powerful paradigm for solving

combinatorial search problems. This style of knowledge representation and rea-

soning draws together a wide range of techniques from artiﬁcial intelligence,

operations research, algorithms and graph theory.

vii

viii Preface

• Chapter 5 reviews the inﬂuential work on Conceptual Graphs. This structured

representation provides an expressive language and powerful reasoning methods

that are essential for applications such as Natural Language Understanding.

• Chapter 6 introduces nonmonotonic logics, which deal with complications re-

lated to handling exceptions to general rules. These logics are called “non-

monotonic” because they describe the retraction of information from a knowl-

edge base when additional exceptions are taken into account.

• Chapter 7 builds on the previous one by describing Answer Set logic, which

neatly handles default rules and exceptions, along with the nonmonotonic rea-

soning that they engender. This form of logic also supports reasoning about the

causal effects of actions—another key feature of common sense.

• Chapter 8 continues this theme with a survey of techniques for Belief Revision,

that is, how an agent changes its knowledge base in light of new information

that contradicts a previous belief.

• Chapter 9 explains the role of qualitative models of continuous systems. These

models enable another key feature of common sense: reasoning with incomplete

information. This form of reasoning can compute, for example, the possible fu-

ture states of a system, which is important for numerous tasks, such as diagnosis

and tutoring.

• Chapter 10 demonstrates that these theories and techniques establish the basis

for problem solvers that exploit an explicit model of the behavior of systems

for tasks such as design, testing, and diagnosis. Being based on ﬁrst principles

knowledge and inference engines with a formal logical foundation, rather than

experience tied to speciﬁc instances and situations, such model-based problem

solversachieve the competence and robustness needed for industrial applications

of knowledge representation and reasoning techniques.

• Chapter 11 confronts the unavoidable problem of uncertainty in real world do-

mains, and surveys the extensive research on Bayesian networks as a method for

modeling and reasoning with uncertain beliefs.

Part II delves into the special challenges of representing and reasoning with some

core domains of knowledge, including time, space, causation and action. These chal-

lenges are ubiquitous across application areas, so solutions must be general and com-

posable.

• Chapter 12 discusses ways to represent the temporal aspects of an ever-changing

world. In a theme that recurs throughout this section, this raises a variety of

interesting ontological issues—such as whether time should be modeled with

points or intervals, and at what level of granularity—along with the pragmatic

consequences of these decisions.

• Chapter 13 surveys qualitative representations of space—including topology,

orientation, shape, size and distance—as well as reasoning methods appropri-

Preface ix

ate to each. Although no single theory covers these topics comprehensively,

researchers have produced a powerful tool kit.

• Chapter 14 builds on the two previous chapters, and also on research on qualita-

tive modeling, to tackle the general problem of physical reasoning. Two impor-

tant domain theories are developed (for liquids and solid objects), and the key

issue of shifting between alternative models is explored.

• Chapter 15 surveys representations of an agent’s knowledge and beliefs, includ-

ing propositions about the knowledge state of other agents (e.g., “Tom believes

that Mary knows...”). This work nicely extends to handle common knowledge

and distributed knowledge within a community of agents.

• Chapter 16 surveys the long history of the “situation calculus”—a knowledge

representation designed to handle dynamic worlds. As ﬁrst deﬁned by McCarthy

and Hayes, a situation is “a complete state of the universe at an instance of

time”. Because situations are ﬁrst-order objects that can be quantiﬁed over, this

framework has proven to be a strong foundation for reasoning about change.

• Chapter 17 describes the Event Calculus as an alternative to the Situation Calcu-

lus with some additional nice features. In particular, the event calculus facilitates

representing continuous events, nondeterministic effects, events with duration,

triggered events, and more.

• Chapter 18 continues the development of representation languages designed for

dynamic worlds by introducing Temporal Action Logics. This family of lan-

guages is especially well suited for reasoning about persistence, i.e., features of

the world that carry forward through time, unchanged, until an action affects

them. It facilitates the representation of nondeterministic actions, actions with

duration, concurrent actions and delayed effects of actions, partly due to its use

of explicit time, and it tightly couples an automated planner to the formalism.

• Chapter 19 focuses on Nonmonotonic Causal Logic, which handles dynamic

worlds using a strong solution to the frame problem. This logic starts with

assumption that everything has a cause: either a previous action or inertia (per-

sistence). This results in nice formalizations for key issues such as ramiﬁcations,

implied action preconditions, and concurrent interacting effects of actions.

Part III surveys important applications of knowledge representation and reasoning.

The application areas span the breadth of Artiﬁcial Intelligence to include question

answering, the Semantic Web, planning, robotics and multi-agent systems. Each ap-

plication draws extensively on the research results described in Parts I and II.

• Chapter 20 surveys research in question answering systems. These systems

answer questions given a corpus of relevant documents and, in some cases,

a knowledge base of common sense information. The system’s challenge is to

select relevant passages of text (an information retrieval task), interpret them

(a natural language understanding task) and infer an answer to the question

(a reasoning task).