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

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

592 13. Qualitative Spatial Representation and Reasoning

[138] D. Mark, D. Comas, M. Egenhofer, S. Freundschuh, J. Gould, and J. Nunes.

Evaluatingand reﬁning computational models of spatial relations through cross-

linguistic human-subjects testing. In A. Frank and W. Kuhn, editors. Spatial

Information Theory: A Theoretical Basis for GIS, Lecture Notes in Computer

Science, vol. 988, pages 553–568. Springer-Verlag, Berlin, 1995.

[139] C. Masolo and L. Vieu. Atomicity vs. inﬁnite divisibility of space. In Spatial

Information Theory—Cognitive and Computational Foundations of Geographic

Information Science, Lecture Notes in Computer Science, vol. 1661, pages 235–

250. Springer, 1999.

[140] M. Mavrovouniotis and G. Stephanopoulos. Formal order-of-magnitude reason-

ing in process engineering. Computers and Chemical Engineering, 12:867–881,

1988.

[141] R.C. Meathrel and A.P. Galton. A hierarchy of boundary-based shape descrip-

tors. In Proceedings of the 17th International Joint Conference on Artiﬁcial

Intelligence (IJCAI-01), pages 1359–1364, 2001.

[142] A. Mukerjee. Neat vs. scruffy: A survey of computational models for spatial

expressions. In P. Oliver and K.-P. G app, editors. Representation and Processing

of Spatial Expressions. Kluwer, 1998.

[143] A. Mukerjee and G. Joe. A qualitative model for space. In Proceedings of the

8th National Conference on Artiﬁcial Intelligence (AAAI-90), pages 721–727.

Morgan Kaufmann, Los Altos, CA, 1990.

[144] P. Muller. Topological spatio-temporal reasoning and representation. Computa-

tional Intelligence, 18(3):420–450, 2002.

[145] B. Nebel. Computational properties of qualitativespatial reasoning: First results.

In I. Wachsmuth, R. Rollinger, and W. Brauer, editors. Proceedings of the 19th

German AI Conference (KI-95), Lecture Notes in Computer Science, vol. 981,

pages 233–244. Springer-Verlag, 1995.

[146] B. Nebel. Reasoning about temporal relations: a maximal tractable subset of

Allen’s interval algebra. Journal of the ACM, 42(1):43–66, January 1995.

[147] B. Nebel. Solving hard qualitative temporal reasoning problems: Evaluating the

efﬁciency of using the ORD-Horn class. CONSTRAINTS, 3(1):175–190, 1997.

[148] J. Nicod. Geometry in the sensible world. Doctoral thesis, Sorbonne, 1924;

English translation in Geometry and Induction. Routledge and Kegan Paul,

1969.

[149] W. Nutt. On the translation of qualitative spatial reasoning problems into

modal logics. In Proceedings of KI-99, Lecture Notes in Artiﬁcial Intelligence,

vol. 1701, pages 113–124. Springer, 1999.

[150] J. Pacheco, M.T. Escrig, and F. Toledo. Representing and reasoning on three-

dimensional qualitative orientation point objects. In P. Brazdil and A. Jorge,

editors. Progress in Artiﬁcial Intelligence, Knowledge Extraction, Multi-agent

Systems, Logic Programming and Constraint Solving, 10th Portuguese Confer-

ence on Artiﬁcial Intelligence, Lecture Notes in Computer Science, vol. 2258,

pages 298–305. Springer, 2001.

[151] D. Papadias and M.J. Egenhofer. Algorithms for hierarchical spatial reasoning.

GeoInformatica, 1(3):251–273, 1997.

[152] D. Papadias and Y. Theodoridis. Spatial relations, minimum bounding rectan-

gles, and spatial data structures. International Journal of Geographic Informa-

tion Systems, 11(2):111–138, 1997.

A.G. Cohn, J. Renz 593

[153] D.N. Pham, J.R. Thornton, and A. Sattar. Modelling and solving temporal rea-

soning as propositional satisﬁability. In Proceeding of the 4th International

Workshop on Modelling and Reformulating, Sitges, Spain, 2005.

[154] L. Polkowski and A.Skowron.Rough mereology in information systems. A case

study: qualitative spatial reasoning. In Rough Set Methods and Applications:

New Developments in Knowledge Discovery in Information Systems, pages 89–

135. Physica-Verlag GmbH, Heidelberg, Germany, 2000.

[155] I. Pratt and O. Lemon. Ontologies for plane, polygonal mereotopology. Notre

Dame Journal of Formal Logic, 38(2):225–245, 1997.

[156] I. Pratt and D. Schoop. A complete axiom system for polygonal mereotopology

of the real plane. Journal of Philosophical Logic, 27:621–658, 1998.

[157] I. Pratt-Hartmann. Empiricism and rationalism in region-based theories of

space. Fundamenta Informaticae, 46(1–2):159–186, 2001.

[158] O. Raiman. Order of magnitude reasoning. In Proceedings of the 5th National

Conference on Artiﬁcial Intelligence (AAAI-86), pages 100–104, 1986.

[159] R. Rajagopalan. A model for integrated qualitative spatial and dynamic reason-

ing about physical systems. In Proceedings of the 12th National Conference on

Artiﬁcial Intelligence (AAAI-94), pages 1411–1417, 1994.

[160] C.G. Ralha. A framework for dynamic structuring of information. PhD thesis,

University of Leeds, 1996.

[161] D. Randell and A. Cohn. Modelling topological and metrical properties of physi-

cal processes. In R. Brachman, H. Levesque, and R. Reiter, editors. Proceedings

1st International Conference on the Principles of Knowledge Representation

and Reasoning (KR-89), pages 55–66. Morgan Kaufmann, Los Altos, CA, 1989.

[162] D.A. Randell, A.G. Cohn, and Z. Cui. Computing transitivity tables: A challenge

for automated theorem provers. In Proceedings of the 11th International Con-

ference on Automated Deduction (CADE-92). Springer-Verlag, Berlin, 1992.

[163] D.A. Randell, Z. Cui, and A.G. Cohn. A spatial logic based on regions and con-

nection. In Proc. 3rd Int. Conf. on Knowledge Representation and Reasoning,

pages 165–176. Morgan Kaufmann, San Mateo, CA, 1992.

[164] D.A. Randell, M. Witkowski, and M. Shanahan. From images to bodies: Mod-

elling and exploiting spatial occlusion and motion parallax. In Proceedings of

the 17th International Joint Conference on Artiﬁcial Intelligence (IJCAI-01),

pages 57–66. Morgan Kaufmann, 2001.

[165] E. Remolina and B. Kuipers. Towards a general theory of topological maps.

Artiﬁcial Intelligence, 152(1):47–104, 2004.

[166] J. Renz. A canonical model of the region connection calculus. In A.G. Cohn,

L.K. Schubert, and S. Shapiro, editors. Principles of Knowledge Representa-

tion and Reasoning: Proceedings of the 6th International Conference (KR-98),

pages 330–341. Morgan Kaufman, 1998.

[167] J. Renz. Maximal tractable fragments of the region connection calculus: A com-

plete analysis. In Proceedings of the Sixteenth International Joint Conference

on Artiﬁcial Intelligence (IJCAI-99), pages 448–455, 1999.

[168] J. Renz. A spatial odyssey of the interval algebra: 1. Directed intervals. In

B. Nebel, editor. Proceedings of the 17th International Joint Conference on

Artiﬁcial Intelligence (IJCAI-01), pages 51–56. Morgan Kaufmann, 2001.

594 13. Qualitative Spatial Representation and Reasoning

[169] J. Renz. Qualitative spatial and temporal reasoning: Efﬁcient algorithms for

everyone. In M.M. Veloso, editor. Proceedings of the 20th International Joint

Conference on Artiﬁcial Intelligence (IJCAI-07), pages 526–531, 2007.

[170] J. Renz and G. Ligozat. Weak composition for qualitative spatial and temporal

reasoning. In Principles and Practice of Constraint Programming—CP 2005,

11th International Conference, pages 534–548, 2005.

[171] J. Renz and D. Mitra. Qualitative direction calculi with arbitrary granularity.

In Proceedings of the 8th Paciﬁc Rim International Conference on Artiﬁcial

Intelligence, pages 65–74, 2004.

[172] J. Renz and B. Nebel.On the complexity of qualitativespatial reasoning: A max-

imal tractable fragment of the region connection calculus. Artiﬁcial Intelligence,

108(1–2):69–123, 1999.

[173] J. Renz and B. Nebel. Efﬁcient methods for qualitative spatial reasoning. Jour-

nal of Artiﬁcial Intelligence Research, 15:289–318, 2001.

[174] J. Renz and B. Nebel. Qualitative spatial reasoning using constraint calculi. In

M. Aiello, I. Pratt-Hartmann, and J. van Benthem, editors. Handbook of Spatial

Logics. Springer-Verlag, Berlin, 2007.

[175] J. Renz, R. Rauh, and M. Knauff. Towards cognitive adequacy of topological

spatial relations. In C. Freksa, W. Brauer, C. Habel, and K.F. Wender, editors.

Spatial Cognition, Lecture Notes in Computer Science, vol. 1849, pages 184–

197. Springer, 2000.

[176] R. Röhrig. A theory for qualitative spatial reasoning based on order relations. In

Proceedings of the 12th National Conference on Artiﬁcial Intelligence (AAAI-

94), vol. 2, pages 1418–1423, Seattle, 1994.

[177] A.J.O. Roy and J.G. Stell. A qualitative account of discrete space. In M.J. Egen-

hofer and D.M. Mark, editors. Proceedings of GIScience 2002, Lecture Notes in

Computer Science, vol. 2478, pages 276–290. Springer, 2002.

[178] P. Sablayrolles. Spatio-temporal semantics in natural language: the case of mo-

tion. In Semantics of Time, Space, Movement and Spatio-Temporal Reasoning,

pages 69–88, 1992. Working Papers of the 4th International Workshop.

[179] P. Santos, B. Bennett, and G. Sakellariou. Supervaluation semantics for an

inland water feature ontology. In L.P. Kaelbling and A. Safﬁotti, editors. Pro-

ceedings of the 19th International Joint Conference on Artiﬁcial Intelligence

(IJCAI-05), pages 564–569. Professional Book Center, Edinburgh, 2005.

[180] P. Santos and M. Shanahan. Hypothesising object relations from image transi-

tions. In van Harmelen [203], pages 292–296.

[181] P. Santos and M. Shanahan. A logic-based algorithm for image sequence in-

terpretation and anchoring. In G. Gottlob and T. Walsh, editors. Proceedings

of the 18th International Joint Conference on Artiﬁcial Intelligence (IJCAI-03),

pages 1408–1410. Morgan Kaufmann, 2003.

[182] M. Schaefer, E. Sedgwick, and D. Stefankovic. Recognizing string graphs in

NP. Journal of Computer and System Sciences, 67(2):365–380, 2003.

[183] I. Schlaisich and M.J. Egenhofer. Multimodal spatial querying: what people

sketch and talk about. In C. Stephanidis, editor. Proceedings of the 9th Interna-

tional Conference on Human-Computer Interaction (HCI-01), pages 732–736.

Lawrence Erlbaum, 2001.

A.G. Cohn, J. Renz 595

[184] C. Schlieder. Representing visible locations for qualitative navigation. In N.P.

Carreté and M.G. Singh, editors. Qualitative Reasoning and Decision Technolo-

gies, pages 523–532. CIMNE, Barcelona, 1993.

[185] C. Schlieder. Reasoning about ordering. In A. Frank and W. Kuhn, editors.

Spatial Information Theory: A Theoretical Basis for GIS, Lecture Notes in Com-

puter Science, vol. 988, pages 341–349. Springer-Verlag, Berlin, 1995.

[186] C. Schlieder. Qualitative shape representation. In P. Burrough and A.M. Frank,

editors. Proceedings, GISDATA Specialist Meeting on Geographical Objects

with Undetermined Boundaries. Francis Taylor, 1996.

[187] S. Schulz, P. Daumke, B. Smith, and U. Hahn. How to distinguish parthood

from location in bioontologies. In Proc. AMIA Symposium 2005, pages 669–

673, Washington DC, 2005.

[188] M. Shanahan. Default reasoning about spatial occupancy. Artiﬁcial Intelligence,

1995.

[189] P. Simons. Parts: A Study in Ontology. Clarendon Press, Oxford, 1987.

[190] B. Smith. Mereotopology: a theory of parts and boundaries. Data and Knowl-

edge Engineering, 20(3):287–303, 1996.

[191] B. Smith and A.C. Varzi. The nîche. Noûs, 33(2):198–222, 1999.

[192] T. Sogo, H. Ishiguro, and T. Ishida. Acquisition of qualitative spatial repre-

sentation by visual observation. In Proceedings of the 16th International Joint

Conference on Artiﬁcial Intelligence (IJCAI-99), pages 1054–1060, Stockholm,

Sweden, 1999.

[193] J.G. Stell. Boolean connection algebras: A new approach to the region connec-

tion calculus. Artiﬁcial Intelligence, 122:111–136, 2000.

[194] A. Tarski. Les fondaments de la géométrie des corps. Ksiega Pamiatkowa Pier-

wszego Polskiego Zjazdu Matematycznego, pages 29–33, 1929. A suplement to

Annales de la Société Polonaise de Mathématique. English translation: Founda-

tions of the geometry of solids. In A. Tarski. Logic, Semantics, Metamathemat-

ics. Oxford Clarendon Press, 1956.

[195] A. Tarski. A Decision Method for Elementary Algebra and Geometry. In J.C.C.

McKinsey, editor. The RAND Corporation, Santa Monica, CA, 1948.

[196] A. Tate, J. Hendler, and M. Drummond. A review of AI planning techniques.

In J. Allen, J. Hendler, and A. Tate, editors. Readings in Planning.Morgan

Kaufman, San Mateo, CA, 1990.

[197] M. Thorup. Map graphs in polynomial time. In 39th Annual Symposium on

Foundations of Computer Science (FOCS-98), pages 396–405, 1998.

[198] S. Thrun. Robotic mapping: A survey. In G. Lakemeyer and B. Nebel, editors.

Exploring Artiﬁcial Intelligence in the New Millennium. Morgan Kaufmann,

2002.

[199] T. Topaloglou. First order theories of approximate space. In F. Anger et al.,

editors. Working Notes of AAAI Workshop on Spatial and Temporal Reasoning,

pages 283–296, Seattle, 1994. American Association for Artiﬁcial Intelligence.

[200] J.F.A.K. Van Benthem. The Logic of Time. D. Reidel Publishing Company, Dor-

drecht, Holland, 1983.

[201] N. Van de Weghe, A.G. Cohn, P. De Maeyer, and F. Witlox. Representing mov-

ing objects in computer-based expert systems: The overtake event example.

Expert Systems with Applications, 29(4):977–983, November 2005.

596 13. Qualitative Spatial Representation and Reasoning

[202] N. Van de Weghe, A.G. Cohn, G. De Tre, and P. De Maeyer. A qualitative

trajectory calculus as a basis for representing moving objects in geographical

information systems. Cybernetics and Control, 35(1):97–119, 2006.

[203] F. van Harmelen, editor. Proceedings of the 15th European Conference on Arti-

ﬁcial Intelligence (ECAI’2002), Lyon, France, July 2002. IOS Press, 2002.

[204] A. Varzi. Parts, wholes and part-whole relations: the prospects of mereotopol-

ogy. Data and Knowledge Engineering, 20(3):259–286, 1996.

[205] A.C. Varzi. On the boundary between mereology and topology. In R. Casati,

B. Smith, and G. White, editors. Philosophy and the Cognitive Sciences: Pro-

ceedings of the 16th Wittgenstein Symposium. Hölder–Pichler–Tempsky, Vi-

enna, 1994.

[206] L. Vieu. Spatial representation and reasoning in AI. In O. Stock, editor. Spatial

and Temporal Reasoning, pages 3–40. Kluwer, 1997.

[207] T. Wagner and K. Hübner. An egocentric qualitative spatial knowledge repre-

sentation based on ordering information for physical robot navigation. In D.

Nardi, M. Riedmiller, C. Sammut, and J. Santos-Victor, editors. RobuCup, Lec-

ture Notes in Computer Science, vol. 3276, pages 134–149. Springer, 2004.

[208] H. Walischewski. Learning regions of interest in postal automation. In Proceed-

ings of 5th International Conference on Document Analysis and Recognition

(ICDAR’99), Bangalore, India, 1999.

[209] D.S. Weld and J. De Kleer, editors. Readings in Qualitative Reasoning About

Physical Systems. Morgan Kaufman, San Mateo, CA, 1990.

[210] A.N. Whitehead. Process and Reality. The MacMillan Company, New York,

1929. Corrected edition published in 1978 by Macmillan.

[211] A.N. Whitehead. In D.R. Grifﬁn and D.W. Sherburne, editors. Process and Re-

ality, corrected edition. The Free Press, Macmillan Pub. Co., New York, 1978.

[212] F. Wolter and M. Zakharyaschev. Spatial reasoning in RCC-8 with Boolean

region terms. In Proceedings of the 14th European Conference on Artiﬁcial In-

telligence, pages 244–250, 2000.

[213] F. Wolter and M. Zakharyaschev. Spatio-temporal representation reasoning

based on RCC-8. In Principles of Knowledge Representation and Reasoning

Proceedings of the Seventh International Conference (KR’2000), pages 3–14,

2000.

[214] M.F. Worboys and M. Duckham. Geographic Information Systems: A Comput-

ing Perspective. 2nd edition. CRC Press, Boca Raton, FL, 2004.

[215] K. Zimmermann. Enhancing qualitative spatial reasoning—combining orienta-

tion and distance. In A. Frank and I. Campari, editors. Spatial Information The-

ory: A Theoretical Basis for GIS, Lecture Notes in Computer Science, vol. 716,

pages 69–76. Springer-Verlag, Berlin, 1993.

[216] K. Zimmermann. Measuring without distances: the delta calculus. In A. Frank

and W. Kuhn, editors. Spatial Information Theory: A Theoretical Basis for GIS,

Lecture Notes in Computer Science, vol. 988, pages 59–68. Springer-Verlag,

Berlin, 1995.

[217] K. Zimmermann and C. Freksa. Enhancing spatial reasoning by the concept of

motion. In A. Sloman, editor. Prospects for Artiﬁcial Intelligence, pages 140–

147. IOS Press, 1993.

Handbook of Knowledge Representation

Edited by F. van Harmelen, V. Lifschitz and B. Porter

DOI: 10.1016/S1574-6526(07)03014-3

597

Chapter 14

Physical Reasoning

Ernest Davis

An intelligent creature or automaton that is set in a complexuncontrolled world will be

able to act more effectively and ﬂexibly if it understands the physical laws that govern

its surroundings and their relation to its own actions and the actions of other agents. In

this chapter we discuss work by KR researchers that tries to represent commonsense

knowledge and carry out commonsense reasoning over some basic physical domains.

There is, of course, a vastbody of computer science and scientiﬁc computing which

deals in one way or another with physical phenomena; almost all of this lies outside

the scope of KR research and hence of this chapter. Even within AI, there are many

types of physical reasoning that are excluded here. For instance, the automated visual

recognition of a scene is, in a sense, a type of physical reasoning. Image formation

is a physical process; the problem in vision is to infer plausible characteristics of a

scene given an image of it. Why is this not considered a problem for KR physical

reasoning? Mainly because the physics involved is too specialized. A single, quite

complex, physical process, and a single type of inference about the process are at

issue; and the computational techniques to be applied are highly tuned to that process

and that inference and hardly generalize to any other kind of problem.

At the other end of the spectrum, most of the physical theories that appear in the

KR literature, such as the STRIPS representations of actions, are too crude and narrow

in scope to be of any interest as a physical theory. For instance, the classic blocks

world theory applies only to rectangular blocks piled in strict stacks and manipulators

constrained to moving a single block from one top of a stack to another; moreover, it

does not characterize the positions or motions of the block or manipulator while being

moved. The theory is therefore not even a useful start toward a general realistic theory

of blocks of general shape in general positions being moved by an actual manipulator.

The most important difference between KR physical reasoning and scientiﬁc com-

puting is that, whereas scientiﬁc computing almost always aims at achieving a high

In principle, high-level physical reasoning could enter into visual recognition, either by providing

constraints or measures of likelihood for possible scenes [44] or by relating physical conditions of the

image formation process to qualities of the image—e.g., if the lens cap is left on, the image will be black. In

practice, the former has been rarely attempted in vision research, and the latter, as far as I know, has never

been attempted.

598 14. Physical Reasoning

degree of numerical accuracy, KR is almost always content to achieve just a qualita-

tive description. In many cases, predicting qualitative behavior with a high degree of

certainty depends on predicting numerical values with a high degree of accuracy—

e.g., will the car fall off the cliff, or stop short? In such cases, qualitative reasoning

necessarily gives ambiguous results; either the car will stop short and remain intact,

or it will fall over the edge and will crash and possibly explode. The quest for numer-

ical accuracy means that most scientiﬁc computations involve a ﬁne-grained division

of time or space or both (except in the special cases of problems that have an exact

symbolic solution). By contrast, KR physical reasoning almost always divides space,

time, or space–time into physically signiﬁcant intervals/regions/histories bounded by

signiﬁcant events/boundaries.

KR also differs from scientiﬁc computing in that it often attempts to:

• Incorporate a theory of action.

• Use knowledge for inference in different directions.

• Generate explanations in addition to answers.

• Address everyday domains at the human scale, rather domains that are esoteric,

highly specialized, very small or very large.

• Use theories that are psychological plausible but not necessarily scientiﬁcally

correct.

• Use explicit theories of causality.

• Study explicitly the interaction between alternative theories at different levels

of abstraction. Scientiﬁc computation uses many theories at different levels of

abstraction, but the problem of choosing the theory appropriate to a situation or

of integrating multiple theories in solving a problem is generally left to a human

understander (or hard-wired into code).

As contrasted with the ad hoc physical theories used in most planning and temporal

reasoning, KR work in physical reasoning is distinguished by:

• Generality. The attempt to deal with all or nearly all possible conﬁgurations

within a given domain. E.g., dealing with arbitrary conﬁgurations of blocks of

arbitrary shape rather than with stacks of rectangular blocks.

• Continuous time and continuous change over time.

• Geometry and continuous change over space.

Of course, the dividing lines between KR physical reasoning and ad hoc KR the-

ories at one end and conventional scientiﬁc computing at the other is not a sharp one;

indeed, a very important problem for KR is how to integrate all these together.

KR physical reasoning generally involves two important forms of nonmonotonic

reasoning. The ﬁrst is a closed-world assumption, that all the entities that will in-

ﬂuence a physical system are known or easily determined. This assumption is made

both at the level of theory, that the domain theory accounts for all relevant types of

E. Davis 599

events, processes, and so on; and at the level of the speciﬁc problem, that the problem

statement accounts for all the individual objects, actions, and so on. The second is an

idealization assumption, that a particular idealization can be safely used. Again this

can either be at the level of the choice of theory, such as assuming that the objects

in a problem can be modeled as rigid, or at the level of problem description, such as

taking a block to be strictly rectangular. Ultimately, it must be expected that KR phys-

ical reasoning will have to deal with combining degrees of certainty, and thus require

probabilistic or some similar form of reasoning, but little or no such work has yet been

done.

Research in KR physical reasoning—which, for the remainder of this chapter we

will call simply “physical reasoning”—can largely be divided into four categories:

Qualitative calculus. The development of representations and inference tech-

niques for numeric quantities and functions whose value and relations are spec-

iﬁed qualitatively. These calculi are the subject of Chapter 9 of this Handbook

and are therefore not further discussed here.

Architecture. The development of general frameworks which support the state-

ment of physical theories and the description of speciﬁc problems and scenar-

ios. Section 14.1 describes the component model and the process model. Again,

these theories are presented in Chapter 9, so our description here is brief and

focuses on the ontology used in these architectures.

Domain theories. The analysis of particular physical domains. Section 14.2 de-

scribes kinematic and dynamic theories of solid objects and the theory of liq-

uids.

Multiple models and levels of abstraction. Any model of a physical situation used

in a reasoning task will include some features of the situation and abstract away

others. Thus, a single situation may have many different models, which vary in

the features and the detail they include. For instance, depending on the reason-

ing task, it may be suitable to model a soccer ball as a point object, a perfect

sphere, or an irregular sphere; a rigid object or an elastic object; an object of

uniform material, a uniform closed rubber shell around an interior of air, or

a rubber shell with an inﬂation hole around an interior of air. Moreover, a rea-

soner may use more than one of these models in the course of a single reasoning

task. The issues of choosing an appropriate model and combining models are

therefore critical aspects of physical reasoning. These issues are discussed in

Section 14.3.

We conclude in Section 14.4 with a historical and bibliographical survey; here we

will mention some further work in the area that falls outside the above categories.

Terminological comment: In this chapter a ﬂuent is an entity whose value may

change as a function of time. For instance, the ﬂuent “Temperature(O1)” represents

the temperature of object O1 as function of time; the ﬂuent “Place(O1)” represents the

region occupied by object O1 as a function of time; the Boolean ﬂuent “On(OA, OB)”

represents the function of time which is TRUE at times when object OA is on OB

and FALSE at other times. A parameter is a ﬂuent whose value is in a numeric-valued

space, such as temperature. Standard mathematical numerical and geometric functions

600 14. Physical Reasoning

are extended to ﬂuents in the obvious way; for instance, if f and g are parameters, then

f + g denotes the parameter whose value at any time t is the sum of the values of f

and g at t.

14.1 Architectures

An architecture for physical reasoning is a representational schema; that is, it is a

structure that deﬁnes a high-level ontology and a basic set of relations and that sup-

ports the representation of various general domains and of speciﬁc problems, and the

carrying out of particular types of inferences over those representations. Thus, it is

roughly analogous to the STRIPS or PDDL representation for planning. The best es-

tablished and most extensively studied architectures for physical reasoning are the

component model and the process model; since these have been already considered in

Chapter 9, our treatment of them here is brief and focuses on their ontologies rather

than on reasoning methods.

14.1.1 Component Analysis

Many complex systems are designed and can be analyzed as a ﬁxed conﬁguration of

standard components.

A component is an atomic entity with a number of ports. Each port has associated

with it a number of parameters with numerical values. The component imposes con-

straints on the values of the parameters over time. These constraint are generally either

algebraic constraints over the values of the parameters at a given time, or differential

equations, relating the derivatives of the parameters at a given time to their values. In

the component model, these constraints comprise the entire physical characteristics of

the component; aside from the constraints, the component is a black box.

For example, a resistor has two ports a and b. Each port p has two parameters: the

inﬂowing current InCurrent(p) and the voltage Voltage(p). A resistor r is character-

ized by two equations:

InCurrent(a) =−InCurrent(b) and

Voltage(b) − Voltage(a) = resistance(r) · InCurrent(b).

A capacitor c has the same types of ports and parameters and is characterized by the

equations

InCurrent(a) =−InCurrent(b) and

InCurrent(b) = Capacitance(c) · Derivative(Voltage(b) − Voltage(a)).

A node is a collection of ports connected together. The node imposes a constraint

on the parameters of the ports determined by the domain theory. For instance, in the

electronics domain, if ports p

...p

are connected at a node, then that creates the

constraints

InCurrent(p

) +···+InCurrent(p

) = 0 and

Voltage(p

) = Voltage(p

) = ···Voltage(p

E. Davis 601

A system is deﬁned by a collection of components, and a partition of their ports

into nodes. The structure of connections and the component characteristics are ﬁxed

over time; what varies overtime are the values of the parameters. The set of constraints

generated by the components and by the nodes determines the behavior of the system

over time.

Electronic systems are the archetypal and best example of a domain that can be

analyzed using the component model. The model has also been applied to hydraulic

devices, heat transfer systems, and mechanical systems of certain types.

Actions can be incorporated into the component architecture by modeling an agent

as an exogenous signal. That is, an agent is modeled as a component for which the

values of the parameters are not determined by the theory and the remainder of the

system, but rather can be “chosen”. For example, in the electronics domain, an agent

could be a voltage source that can choose a waveform to output; the waveform it

chooses is its action.

Typical reasoning tasks carried out over component models include:

• Static evaluation. If all the constraints are algebraic, then determine the state (or

the set of possible states) of the system.

• Initial value problem. If the constraints include differential equations, then de-

termine the progress of the system following some starting condition.

• Signal response. Determine the output of a system in response to a speciﬁed

signal at some input.

• Comparative static evaluation. Determine the effect of changing some compo-

nent characteristic on the static state of the system.

• Comparative dynamic evaluation. Determine the effect of changing some com-

ponent characteristic on the dynamic progress of the system.

The best known program using the component model was the ENVISION program

of de Kleer and Brown [17]. ENVISION used the sign calculus to solve qualitatively

the initial value problem and the comparative static evaluation problem. ENVISION

also proposed a model of causality, in which an change to some exogenous parameter

in the system causes changes to other parameters by propagating through the network,

in a manner that has a sequence, though no measurable time duration.

14.1.2 Process Model

In the process model [23], change is brought about by processes, events, actions, and

indirect inﬂuences between parameters.

A process is active over a time interval. It is characterized by preconditions and

effects. The preconditions must hold for the process to begin. and they must continue

to hold throughout the interval in which the process is active. If the preconditions

cease to hold, then the process stops. The effects of a process are direct inﬂuences on

numeric ﬂuents. A direct inﬂuence is a contribution to the derivative of the ﬂuent; the

derivative of the ﬂuent is the sum of the inﬂuences of all the processes that act on it.

For example, consider the process of a tap t ﬁlling a bucket b. The preconditions

are that the tap is open, the bucket is under the tap, and the bucket is not yet full.