Physical Reasoning in an Open World by Zhuoran Zeng and Ernest Davis. Advances in Cognitive Systems, November 2021.
Most work on physical reasoning, both in artificial intelligence and in cognitive science, has focused on closed-world reasoning, in which it is assumed that the problem specification specifies all relevant objects and substance, all their relations in an initial situation, and all exogenous events. However, in many situations, it is important to do open-world reasoning; that is, making valid conclusions from very incomplete information. We have implemented in Prolog an open-world reasoner for a toy microworld of containers that can be loaded, unloaded, sealed, unsealed, carried, and dumped.
****************************************************************
Metric topologies over some categories of simple open regions in Euclidean space arXiv 2109.08, September 2021.
What does it mean for a shape to change continuously? Over the space of convex regions, there is only one "reasonable" answer. However, over a broader class of regions, such as the class of star-shaped regions, there can be many different "reasonable" definitions of continuous shape change.
We consider the relation between topologies induced by a number of metrics over a number of limited categories of open bounded regions in n-dimensional Euclidean space. Specifically, we consider a homeomorphism-based metric; the Hausdorff metric; the dual-Hausdorff metric; the symmetric difference metric; and the family of Wasserstein metrics; and the topologies that they induce over the space of convex regions; the space of unions of two separated convex regions; and the space of star-shaped regions. We demonstrate that:
****************************************************************
Limits on simulation approaches in intuitive physics, by Ethan Ludwin-Peery, Neil Bramley, Ernest Davis, and Todd Gureckis. Cognitive Psychology, vol. 127, June 2021.
A popular explanation of the human ability for physical reasoning is that it depends on a sophisticated ability to perform mental simulations. According to this perspective, physical reasoning problems are approached by repeatedly simulating relevant aspects of a scenario, with noise, and making judgments based on aggregation over these simulations. In this paper, we describe three core tenets of simulation approaches, theoretical commitments that must be present in order for a simulation approach to be viable. The identification of these tenets threatens the plausibility of simulation as a theory of physical reasoning, because they appear to be incompatible with what we know about cognition more generally. To investigate this apparent contradiction, we describe three experiments involving simple physical judgments and predictions, and argue their results challenge these core predictions of theories of mental simulation.
****************************************************************
Broken Physics: A Conjunction-Fallacy Effect in Intuitive Physical Reasoning by Ethan Ludwin-Peery, Neil Bramley, Ernest Davis, and Todd Gureckis. Psychological Science, November 2020.
One remarkable aspect of human cognition is our ability to reason about physical events. This article provides novel evidence that intuitive physics is subject to a peculiar error, the classic conjunction fallacy, in which people rate the probability of a conjunction of two events as more likely than one constituent (a logical impossibility). Participants viewed videos of physical scenarios and judged the probability that either a single event or a conjunction of two events would occur. In Experiment 1 (n= 60), participants consistently rated conjunction events as more likely than single events for the same scenes. Experiment 2 (n= 180) extended these results to rule out several alternative explanations. Experiment 3 (n= 100) generalized the finding to different scenes. This demonstration of conjunction errors contradicts claims that such errors should not appear in intuitive physics and presents a serious challenge to current theories of mental simulation in physical reasoning.
****************************************************************
Computational limits don't fully explain human cognitive limitations by Ernest Davis and Gary Marcus. Response to Resource-rational analysis: Understanding human cognition as the optimal use of limited computational resources by Falk Lieder and Thomas Griffiths, Behavioral and Brain Sciences, Vol. 43, 2020.
The project of justifying all the limits and failings of human cognition as inevitable consequences of strategies that are actually “optimal” relative to the limits on computational resources available may have some value, but it is far from a complete explanation. It is inconsistent with both common observation and a large body of experimentation, and it is of limited use in explaining human cognition.
****************************************************************
Limits on the use of simulation in physical reasoning, by Ethan Ludwin-Peery, Neil Bramley, Ernest Davis, and Todd Gureckis, Cognitive Science, 2019.
In this paper, we describe three experiments involving simple physical judgments and predictions, and argue their results are generally inconsistent with three core commitments of probabilistic mental simulation theory (PMST). The first experiment shows that people routinely fail to track the spatio-temporal identity of objects. The second experiment shows that people often incorrectly reverse the order of consequential physical events when making physical predictions. Finally, we demonstrate a physical version of the conjunction fallacy where participants rate the probability of two joint events as more likely to occur than a constituent event of that set. These results highlight the limitations or boundary conditions of simulation theory.
****************************************************************
Proof Verification Technology and Elementary Physics. In Algorithms and Complexity in Mathematics, Epistemology, and Science, N. Fillion, R. Corless, and I.S. Kotsireas (eds.) Springer, 2019.
Software technology that can be used to validate the logical correctness of mathematical proofs has attained a high degree of power and sophistication; extremely difficult and complex mathematical theorems have been verified. This paper discusses the prospects of doing something comparable for elementary physics: what it would mean, the challenges that would have to be overcome; and the potential impact, both practical and theoretical.
****************************************************************
Commonsense Reasoning about Containers using Radically Incomplete Information, by Ernest Davis, Gary Marcus and Noah Frazier-Logue, Artificial Intelligence Journal, July 2017 248, 46-84. PDF Word Journal version.
In physical reasoning, humans are often able to carry out useful reasoning based on radically incomplete information. One physical domain that is ubiquitous both in everyday interactions and in many kinds of scientific applications, where reasoning from incomplete information is very common, is the interaction of containers and their contents. We have developed a preliminary knowledge base for qualitative reasoning about containers, expressed in a sorted first-order language of time, geometry, objects, histories, and actions. We have demonstrated that the knowledge suffices to justify a number of commonsense physical inferences, based on very incomplete knowledge.
****************************************************************
The Scope and Limits of Simulation in Cognitive Models by Ernest Davis and Gary Marcus, arXiv 1506.04956. June 2015.
It has been proposed that human physical reasoning consists largely of running "physics engines in the head" in which the future trajectory of the physical system under consideration is computed precisely using accurate scientific theories. In such models, uncertainty and incomplete knowledge is dealt with by sampling probabilistically over the space of possible trajectories ("Monte Carlo simulation"). We argue that such simulation-based models are too weak, in that there are many important aspects of human physical reasoning that cannot be carried out this way, or can only be carried out very inefficiently; and too strong, in that humans make large systematic errors that the models cannot account for. We conclude that simulation-based reasoning makes up at most a small part of a larger system that encompasses a wide range of additional cognitive processes.
****************************************************************
Bounding changes in probability over time: It is unlikely that you will change your mind very much very often Unpublished, November 2013.
Under some circumstances, a probabilistic reasoner who encounters a sequence of observations will change his estimate of the likelihood of a proposition φ from very low to very high and back again many times. However, the prior probability of such a sequence of observations is necessarily very small. We compute an exact value of the maximal value of this probability, as a function of the amount of change and the number of changes. The calculation does not involve any independence assumptions over the observations.
****************************************************************
The Scope and Limits of Simulation in Automated Reasoning by Ernest Davis and Gary Marcus. Artificial Intelligence Journal , 233, April 2016, 60-72
In scientific computing and in realistic graphic animation, simulation --- that is, step-by-step calculation of the complete trajectory of a physical system --- is one of the most common and important modes of calculation. In this article, we address the scope and limits of the use of simulation, with respect to AI tasks that involve high-level physical reasoning. We argue that, in many cases, simulation can play at most a limited role. Simulation is most effective when the task is prediction, when complete information is available, when a reasonably high quality theory is available, and when the range of scales involved, both temporal and spatial, is not extreme. When these conditions do not hold, simulation is less effective or entirely inappropriate. We discuss twelve features of physical reasoning problems that pose challenges for simulation-based reasoning. We briefly survey alternative techniques for physical reasoning that do not rely on simulation.
****************************************************************
The Relevance of Proofs of the Rationality of Probability Theory to Automated Reasoning and Cognitive Models. Unpublished.
A number of well-known theorems, such as Cox's theorem and de Finetti's theorem, prove that any model of reasoning with uncertain information that satisfies specified conditions of "rationality" must satisfy the axioms of probability theory. I argue here that these theorems do not in themselves demonstrate that probabilistic models are in fact suitable for any specific task in automated reasoning or plausible for cognitive models. First, the theorems only establish that there exists some probabilistic model; they do not establish that there exists a useful probabilistic model, i.e. one with a tractably small number of numerical parameters and a large number of independence assumptions. Second, there are in general many different probabilistic models for a given situation, many of which may be far more irrational, in the usual sense of the term, than a model that violates the axioms of probability theory. I illustrate this second point with an extended examples of two tasks of induction, of a similar structure, where the reasonable probabilistic models are very different.
****************************************************************
How robust are probabilistic models of higher-level cognition? by Gary Marcus and Ernest Davis. Psychological Science, Vol. 24, No. 12, 2013, 2351-2360. Paper in Word. Supplement in Word.
An increasingly popular theory holds that the mind should be viewed as a "near optimal" or "rational" engine of probabilistic inference, in domains as diverse as categorization, word learning, pragmatics, naïve physics, and predictions of the future. We argue that this view, often identified with Bayesian models of inference, is markedly less promising than widely believed, undermined by post hoc practices that merit wholesale reevaluation. We also show the common equation between probabilistic and "rational" or "optimal" is not justified.
****************************************************************
Reasoning from Radically Incomplete Information: The Case of Containers. by Ernest Davis, Gary Marcus, and Angelica Chen. Advances in Cognitive Systems, 2013, 273-288.
In domains such as physical reasoning, humans, unlike programs for scientific computation, can often arrive at useful predictions based on radically incomplete information. Consider the capacity to reason about containers --- boxes, bottles, cups, pails, bags, etc --- and the interactions of containers with their contents. You can reason that you can carry groceries in a grocery bag and that they will remain in the bag, with only very weak specifications of the shape and material groceries being carried, the shape and material of the bag, and the trajectory of motion. Here we describe the initial stages of development of a knowledge-based system for reasoning about manipulating containers, in which knowledge of geometry and physics and problem specifications are represented by propositions, and suggest that this approach suffices to justify a number of commonsense physical inferences, based on very incomplete knowledge.
****************************************************************
The Expressive Power of First-Order Topological Languages. Journal of Logic and Computation, Vol. 23, No. 5, 2013, 1101-1141.
Abstract: We consider the expressive power of the first-order structure < O,C > where O is either of two of different domains of extended regions in Euclidean space, and C(x,y) is the topological relation ``Region x is in contact with region y.'' We prove two main theorems:
1. Let P[Q] be the domain of bounded, non-empty, rational polyhedra in two- or three-dimensional Euclidean space. A relation G over P[Q] is definable in the structure < P[Q], C > if and only if G is arithmetic and invariant under rational PL-homeomorphisms of the space to itself. We also extend this result to a number of other domains, including the domain of all polyhedra and the domain of semi-algebraic regions.
2. Let R be the space of bounded, closed regular regions in n-dimensional Euclidean space. Any analytical relation over lower-dimensional (i.e. empty interior) compact point sets that is invariant under homeomorphism is implicitly definable in the structure < R,C >.
****************************************************************
A Qualitative Calculus for Three-Dimensional Rotations by Azam Asl and Ernest Davis. Spatial Cognition and Computation 14:1, 2014, 18-57. Journal version.
Abstract: We have developed a qualitative calculus for three-dimensional directions and rotations. A direction is characterized in terms of the signs of its components relative to a fixed coordinate system. A rotation is characterized in terms of the signs of the components of the associated 3x3 rotation matrix. A system has been implemented that can solve the following problems:
We have also proven some related complexity and expressivity results. The satisfiability problem for a qualitative rotation constraint network is NP-complete in two dimensions and NP-hard in three dimensions. In three dimensions, any two directions are distinguishable by a qualitative rotation constraint network.
****************************************************************
The Winograd Schema Challenge, by Hector Levesque, Ernest Davis, and Leora Morgenstern. KR-2012.
Abstract: In this paper, we present an alternative to the Turing Test that has some conceptual and practical advantages. Like the original, it involves responding to typed English sentences, and English-speaking adults will have no difficulty with it. Unlike the original, the subject is not required to engage in a conversation and fool an interrogator into believing she is dealing with a person. Moreover, the test is arranged in such a way that having full access to a large corpus of English text might not help much. Finally, the interrogator or a third party will be able to decide unambiguously after a few minutes whether or not a subject has passed the test.
****************************************************************
Elementarily Equivalent Structures for Topological Languages over Regions in Euclidean Space. Journal of Logic and Computation, 23:3, 2013, 457-471. Journal paper
Abstract: We prove that the class of rational polyhedra and the class of topologically regular regions definable in an o-minimal structure are each elementary equivalent to the class of polyhedra for topological languages.
****************************************************************
Qualitative Spatial Reasoning in Interpreting Text and Narrative.
Spatial Cognition and Computation, 13:4, 2013, 264-294.
Journal version
John Bateman's response to me.
My response to Bateman.
Abstract: Simple natural language texts and narratives often raise problems in commonsense spatial knowledge and reasoning of surprising logical complexity and geometric richness. In this paper, I consider a dozen short texts --- five taken from literature, the remainder contrived as illustrations --- and discuss the spatial reasoning involved in understanding them. I conclude by summarizing their common features, and by tentatively drawing some morals for research in this area.
****************************************************************
Preserving Geometric Properties in Reconstructing Regions from Internal and Nearby Points. Computational Geometry: Theory and Applications, 45:5-6, 2012, 234-253. Link to journal article (Science Direct).
Abstract: The problem of reconstructing a region from a set of sample points is common in many geometric applications, including computer vision. It is very helpful to be able to guarantee that the reconstructed region ``approximates'' the true region, in some sense of approximation. In this paper, we study a general category of reconstruction methods, called ``locally-based reconstruction functions of radius a,'' and we consider two specific functions Ja(S) and Fa(S) within this category. We consider a sample S, either finite or infinite, that is specified to be within a given Hausdorff distance d of the true region R, and we prove a number of theorems which give conditions on R and d that are sufficient to guarantee that the reconstructed region is an approximation of the true region. Specifically, we prove:
1. For any region R, if F is any locally-based reconstruction method of radius a where a is small enough, and if the Hausdorff distance from S to R is small enough, then the dual-Hausdorff distance from F(S) to R, the Hausdorff distance between their boundaries, and the measure of their symmetric difference is guaranteed to be small.
2. If R is r-regular, then for any e,p > 0, if a is small enough, and the Hausdorff distance from S to R is small enough then each of the regions Ja(S) and Fa(S) is e-similar to R and is an (e,p) -approximation in tangent of R.
****************************************************************
Qualitative Reasoning and Spatio-Temporal Continuity. This chapter appears in Qualitative Spatio-Temporal Representation and Reasoning: Trends and Future Directions edited by S. Hazarika, copyright 2012, IGI Global.
This chapter discusses the use of transition graphs for reasoning about continuous spatial change over time. We first present a general definition of a transition graph for a partition of a topological space. We define the path-connected and the homogeneous refinements of such a partition. The qualitative behavior of paths through the space corresponds to the structure of paths through the associated transition graphs, and of associated interval label sequences; and we prove a number of metalogical theorems that characterize these correspondences in terms of the expressivity of associated first-order languages. We then turn to specific real-world problems, and show how this theory can be applied to domains such as rigid objects, strings, and liquids.
****************************************************************
Ontologies and Representations of Matter. AAAI-10.
Abstract: We carry out a comparative study of the expressive power of different ontologies of matter in terms of the ease with which simple physical knowledge can be represented. In particular, we consider five ontologies of models of matter: particle models, fields, two ontologies for continuous material, and a hybrid model. We evaluate these in terms of how easily eleven benchmark physical laws and scenarios can be represented.
****************************************************************
Pouring Liquids: A Study in Commonsense
Physical Reasoning Artificial Intelligence, vol. 172,
2008, pp. 1540-1578.
There is an
appendix containing the formal object-level proof of the main example.
Errata in Artificial
Intelligence version (these are incorporated in the local version
above).
Abstract: This paper presents a theory that supports commonsense, qualitative reasoning about the flow of liquid around slowly moving solid objects; specifically, inferring that liquid can be poured from one container to another, given only qualitative information about the shapes and motions of the containers. It shows how the theory and the problem specification can be expressed in a first-order language; and demonstrates that this inference and other similar inferences can be justified as deductive conclusions from theory and the problem specification.
****************************************************************
How Does a Box Work? A Study in the Qualitative Dynamics of Solid Objects. Artificial Intelligence, 175, 2011, 299-345. Official electronic version. There is an appendix containing the formal object-level proof of the main example.
Abstract: This paper is an in-depth study of qualitative physical reasoning about one particular scenario: using a box to carry a collection of objects from one place to another. Specifically we consider the plan, plan1 ``Load objects uCargo into box oBox one by one; carry oBox from location l1 to location l2.'' We present qualitative constraints on the shape, starting position, and material properties of uCargo and oBox and on the characteristics of the motion that suffice to make it virtually certain that plan1 can be successfully executed. We develop a theory, consisting mostly of first-order statements together with one default rule, that supports an inference of the form ``If conditions XYZ hold, and the agent attempts to carry out plan1 then presumably he will succeed.'' Our theory is elaboration tolerant in the sense that carrying out the analogous inference for carrying objects in boxes with lids, in boxes with small holes, or on trays can reuse much of the same knowledge. The theory integrates reasoning about continuous time, Euclidean space, commonsense dynamics of solid objects, and semantics of partially specified plans.
****************************************************************
The Expressivity of Quantifying over Regions. Journal of Logic and Computation. vol. 16, 2006, pp. 891-916.
Abstract: We categorize in recursion-theoretic terms the expressivity of a number of first-order languages that allow quantification over regions in Euclidean space. Specifically we show the following:
1. Let U be any class of closed regions in Euclidean space that includes all simple polygons. Let C(x,y) be the relation, ``Region x is connected to region y,'' and let Convex(x) be the property, ``Region x is convex.'' Then any relation over U that is analytical and invariant under affine transformations is first-order definable in the structure < U, C, Convex >.
2. Let U be as in (1), and let Closer(x,y,z) be the relation ``Region x is closer to y than to z.'' Then any relation over U that is analytical and invariant under orthogonal transformations is first-order definable in the structure < U, Closer >.
3. Let U be the class of finite unions of intervals in the real line. Then any relation over U that is analytical and invariant under linear transformations is first-order definable in the structure < U,Closer >
4. If the class of regions is restricted to be polygons with rational vertices, then results analogous to (1-3) hold, substituting ``arithmetical relation'' for ``analytical relation''.
****************************************************************
A First-Order Theory of Communication and Multi-Agent Plans. By
Ernest Davis and Leora Morgenstern.
Journal of Logic and Computation, Vol. 15, No. 5, 2005,
pp. 701-749.
Appendix A: Changes to the theory and consistency proof from ``Knowledge and Communication: A First-Order Theory.''Abstract:
In Postscript. in PDF.
Appendix B: Proof of correctness of sample plan. in Postscript. in PDF.
This paper presents a theory expressed in first-order logic for describing and supporting inference about action, knowledge, planning, and communication, in a multi-agent setting. The underlying ontology of the theory uses a situation-based temporal model and a possible-worlds model of knowledge. It supports plans and communications of a very general kind.
The construction of the theory has been guided by the following toy multi-agent planning problem:
A warehouse has a robot on every floor and an elevator that carries packages between floors. A robot on one floor wants to get a package, whose location is unknown. He therefore constructs the following plan: He will broadcast a request to all the other robots, asking whoever has the package to call the elevator, to load the package onto the elevator, and to inform him that the package is on the elevator. He will then call the elevator and, when it arrives, unload the package.
We show that the solution to the problem can be proven correct within the theory. We also prove that the theory is consistent. In the course of constructing the theory, we encounter a paradox analogous to Russell's paradox; we devise a fairly general solution to the paradox sufficient for examples of this kind.
****************************************************************
Knowledge and Communication: A First-Order Theory.
Artificial Intelligence, vol. 166, 2005, pp. 81-140.
Paper in
Postscript.
Paper in
PDF
Abstract: This paper presents a theory of informative communications among agents that allows a speaker to communicate to a hearer truths about the state of the world; the occurrence of events, including other communicative acts; and the knowledge states of any agent --- speaker, hearer, or third parties --- any of these in the past, present, or future --- and any logical combination of these, including formulas with quantifiers. We prove that this theory is consistent, and compatible with a wide range of physical theories. We examine how the theory avoids two potential paradoxes, and discuss how these paradoxes may pose a danger when this theory are extended.
Previously appeared as the conference paper,
A First-Order Theory of Communicating First-Order Formulas,
KR-04.
Paper in Postscript.
Paper in PDF.
Power-point presentation (Zipped directory
with a .ppt and several .wav files).
****************************************************************
Processes and Continuous Change in a SAT-based Planner. Ji-Ae Shin and Ernest Davis. Artificial Intelligence, vol. 166, 2005.
Abstract: The TM-LPSAT planner can construct plans in domains containing atomic actions and durative actions; events and processes; discrete, real-valued, and interval-valued fluents; and continuous linear change to quantities. It works in three stages. In the first stage, a representation of the domain and problem in an extended version of PDDL+ is compiled into a system of propositional combinations of propositional variables and linear constraints over numeric variables. In the second stage, the LPSAT constraint engine (Wolfman \& Weld 2000) is used to find a solution to the system of constraints. In the third stage, a correct parallel plan is extracted from this solution. We discuss the structure of the planner and show how a real-time temporal model is compiled into LPSAT constraints.
Previously appeared as the conference paper, Continuous Time in a SAT-Based Planner. By Ji-Ae Shin and Ernest Davis. AAAI-04, pp. 531-536. Paper in Postscript . Paper in PDF .
****************************************************************
Describing spatial transitions using mereotopological relations over histories. NYU Computer Science Tech. Report 2000-809, October 2000.
Abstract: Muller (1998) develops a language of motion and shape change in terms of topological relations and temporal order relations between regions of space-time. He uses this language to state and prove the transition rules developed in (Randell, Cui, and Cohn, 1992) that constrain the changes in spatial relations possible for objects whose shape changes continuously. Unfortunately, Muller's statement of the transition rules is inadequate. This paper presents an alternative statement of these transition rules.
****************************************************************
Continuous Shape Transformation and Metrics on Regions. Fundamenta Informaticae, . Vol. 46, Nos. 1-2, 2001, pp. 31-54
Abstract: A natural approach to defining continuous change of shape is in terms of a metric that measures the difference between two regions. We consider four such metrics over regions: the Hausdorff distance, the dual-Hausdorff distance, the area of the symmetric difference, and the optimal-homeomorphism metric. Each of these gives a different criterion for continuous change. We establish qualitative properties of all of these; in particular, the continuity of basic functions such as union, intersection, set difference, area, distance, and the boundary function; the transition graph between RCC relations (Randell, Cui, and Cohn, 1992). We discuss the physical significance of these different criteria.
We also show that the history-based definition of continuity proposed by Muller (1998) is equivalent to continuity with respect to the Hausdorff distance. An examination of the difference between the transition rules that we have found for the Hausdorff distance and the transition theorems that Muller derives leads to the conclusion that Muller's analysis of state transitions is not adequate. We propose an alternative characterization of transitions in Muller's first-order language over histories.
****************************************************************
Constraint Networks of Topological Relations and Convexity. E. Davis, N.M. Gotts and A.G. Cohn) CONSTRAINTS Vol. 4 No. 3, 1999, pp. 241-280.
Abstract: This paper studies the expressivity and computational complexity of networks of constraints of topological relations together with convexity. We consider constraint networks whose nodes are regular regions (a regular region is one equal to the closure of its interior) and whose constraints have the following forms: (i) the eight ``base relations'' of [Randell, Cui, and Cohn, 92], which describe binary topological relations of containment and adjacency between regions; (ii) the predicate, ``X is convex.'' We show the following results:
****************************************************************
Order of Magnitude Comparisons of Distance. In Journal of AI Research vol. 10, 1999, pp. 1-38.
Abstract: Order of magnitude reasoning -- reasoning by rough comparisons of the sizes of quantities -- is often called ``back of the envelope calculation", with the implication that the calculations are quick though approximate. This paper exhibits an interesting class of constraint sets in which order of magnitude reasoning is demonstrably fast. Specifically, we present a polynomial-time algorithm that can solve a set of constraints of the form ``Points a and b are much closer together than points c and d.'' We prove that this algorithm can be applied if ``much closer together'' is interpreted either as referring to an infinite difference in scale or as referring to a finite difference in scale, as long as the difference in scale is greater than the number of variables in the constraint set. We also prove that the first-order theory over such constraints is decidable.
****************************************************************
The Naive Physics Perplex AI Magazine, vol. 19, no. 4, Winter 1998, pp. 51-79.
Abstract: The ``Naive Physics Manifesto'' of Pat Hayes [1978] proposes a large-scale project of developing a formal theory encompassing the entire knowledge of physics of naive reasoners, expressed in a declarative symbolic form. The theory is organized in clusters of closely interconnected concepts and axioms. More recent work in the representation of commonsense physical knowledge has followed a somewhat different methodology. The goal has been to develop a competence theory powerful enough to justify commonsense physical inferences, and the research is organized in microworlds, each microworld covering a small range of physical phenomena. In this paper we compare the advantages and disadvantages of the two approaches. We also discuss some difficult key issues in automating commonsense physical reasoning.
****************************************************************
A Highly Expressive Language of Spatial Constraints. NYU Computer Science Tech. Report. 714.
Abstract: AI applications require the representation and manipulation of partial spatial knowledge of many different kinds. This paper argues that a representation rich in primitives but fairly restricted in logical form will suffice for many of these purposes. We present and discuss one such representation language. We demonstrate that the language is expressive enough to capture exactly or closely approximate many of the representations that have been used in the AI literature. It also contains some original constructs for dealing with collections of regions of unknown cardinality.
****************************************************************
Approximation and Abstraction in Solid Object Kinematics. NYU Computer Science Tech. Report. 706.
Abstract: Physical reasoning often involves approximating or abstracting the situation or the theory at hand. This paper studies the nature of approximation and abstraction as applied to the kinematic theory of rigid solid objects. Five categories of approximation are considered:
****************************************************************
Approximations of Shape and Configuration Space NYU Computer Science Tech. Report. 703. A later, much improved, version from 2007, has the title Kinematic Tolerance and the Topology of Configuration Space
Abstract (from the later version): Most physical calculations that involve the shapes of objects are carried out by approximating the actual shape in terms of a idealized, or nominal, shape description. It then becomes a problem to determine whether calculations based on idealized shapes in fact carry over to actual shapes. This paper addresses the following instance of that problem, in the domain of solid object kinematics: Suppose that it is known that the ideal shapes approximate the real shape to a specified tolerance, or degree of accuracy. In what respects, or to what degree, can we expect that the physical behavior will resemble the calculated behavior?
In studying this problem, we consider two definitions of ``shape approximation'' and three definitions of ``similarity of physical behavior,'' all original to this paper. We prove a number of theorems that give conditions that suffice to guarantee that, if the real shape of the object is close enough to the nominal shape, then the real behavior will be close to the behavior computed from the nominal shape. Moreover, we show that these relations are, at least in principle, computable, if the idealized shapes are semi-algebraic.
History: The original paper was submitted to JAIR in 1995. The reviewers requested major revisions. I made major revisions, particularly adding discussions of computability, and resubmitted it in 1999. This time it was rejected as unsuitable to the audience of JAIR. The editor suggested that it might be more suitable to a robotics journal. By this time it was 2001, and I was discouraged about it, so I let it lie until 2007. In 2007 I got some encouragement about it, so I revised it (mostly bringing the related work section up to date) and submitted it under the new title to the International Journal of Robotics Research. The editor, John Hollerbach, rejected it as unsuitable to the audience of IJRR, without sending it to reviewers, but suggested that I might want to submit it to a specialized conference on kinematics --- which, as far as I can determine, don't exist, and which I doubt would be interested --- or to a computational geometry journal.
So I sent it to Computational Geometry: Theory and Applications. The editor, Rudolf Fleischer, rejected it immediately on the grounds that it was written in AI paper style (proofs in an appendix at the end) rather than theoretical CS/math style (proofs in the middle). So I fixed the format, and resubmitted it. Fleischer rejected it again, saying that he was unable to find anyone willing to review it, in part because of its length.
So in the end the paper is unpublished, but it does have the probably unique distinction of having been rejected by an AI journal, a robotics journal, and a computational geometry journal.
Ironically, this is the most original and technically deepest paper I have ever written. Moral: Originality and technical depth are not sufficient to make a paper publishable.
****************************************************************
Knowledge Preconditions for Plans. Journal of Logic and Computation, vol. 4, no. 5, Oct. 1994, pp. 721-766
Abstract: For an agent to be able to rely on a plan, he must know both that he is physically capable of carrying out the physical actions involved, and that he knows enough to carry out the plan. In this talk, we advance and discuss new definitions of ``knowing enough to carry out a plan'', for the case of a single agent carrying out a sequence of primitive actions one at a time. We consider both determinate and indeterminate plans.
Definition: A plan P (determinate or indeterminate) is executable for agent A at time T if and only if,
Definition: An indeterminate plan P is epistemically feasible as a task for agent A at time T if there exists a plan P1 such that A knows at time T that
We show how these definition can be expressed in a formal logic, using a situation calculus model of time and a possible worlds model of knowledge. The definitions strictly subsume previous theories for the single-agent case without concurrent actions.
We illustrate the power of the definitions by showing that they supports results of the following kinds:
****************************************************************
Branching Continuous Time and the Semantics of Continuous Action. Second International Conference on AI Planning Systems, 1994.
Abstract: It is often useful to model the behavior of an autonomous intelligent creature in terms of continuous control and choice. For example, a robot who moves through space can be idealized as able to execute any continuous motion, subject to constraints on velocity and acceleration; in such a model, the robot can ``choose'' at any instant to change his accelleration. We show how such models can be described using a continuous branching time structure. We discuss mathematical foundations of continuous branching structures, theories of continuous action in physical worlds, embedding of discrete theories of action in a continuous structure, and physical and epistemic feasibility of plans with continuous action.
****************************************************************
The Kinematics of Cutting Solid Objects. Annals of Mathematics and Artificial Intelligence, vol. 9, no. 3,4, 1993, pp. 253-305.
Abstract: This paper studies how the cutting of one solid object by another can be described in a formal theory. We present two alternative first-order representations for this domain. The first views an object as gradually changing its shape until it is split, at which time the original object ceases to exist and two (or more) new objects come into existence. The second focuses instead on chunks of material which are part of the overall object. A chunk persists with constant shape until some piece of it is cut away, when the chunk ceases to exist. We prove that the two theories are equivalent under ordinary circumstances, and we show that they are sufficient to support some simple commonsense inferences and algorithms.
****************************************************************
The Semantics of Tasks that can be Interrupted or Abandoned. First International Conference on AI Planning Systems, 1992.
Abstract: It is often desirable to allow a robot in a dynamic, uncontrolled environment to interrupt or abandon some task that engages it. To facilitate this, it is helpful to include in the language of plans such control structure as ``Carry out task T1 until condition Q becomes true,'' or ``Proceed with the execution of task T1 whenever it does not interfere with task T2.'' To define such control structures formally, it is necessary to define what it means to begin carrying out a task, independently of whether the task is completed. This paper presents a formal semantics for a language of plans that includes these control structures, together with concurrency and partial specification. Such a semantics will support the formal verification of plans of this kind.
****************************************************************
Axiomatizing Qualitative Process Theory. Third International Conference on Knowledge Representation and Reasoning, 1992.
Abstract: We show that the type of reasoning performed by Forbus' (1985) Qualitative Process (QP) program can be justified in a first-order theory that models time and other measure spaces as real-valued quantities. We consider the QP analysis of a can of water with a safety valve being heated over a flame. We exhibit a first-order theory for the microworld involved in this example, and we prove the correctness of the first two transitions in the envisionment graph. We discuss the possibility of deriving the closure conditions in the theory via non-monotonic inference.
****************************************************************
Infinite Loops in Finite Time: Some Observations. Third International Conference on Knowledge Representation and Reasoning, 1992.
Abstract: Formulating physical theories using real-valued space and time often raises the difficult issue of clustered variation: states that change their value infinitely often in a finite interval, or infinite sequences of events that occur in a finite interval. Some physical theories permit nonsensical models unless clustered variation is prohibited; others force clustered variation to occur. This paper surveys a number of technical issues involved with clustered variation, without attempting to find a uniform treatment of the issue. We present examples of theories where clustered variation must be allowed and of theories where it must be prohibited. We discuss the meaning of plans containing infinite series of events. We present constraints on real-valued fluents and spatial fluents that guarantee discrete variation of important associated states. We show that requiring discrete variation may be inconsistent with allowing infinitely many objects in the universe, even if each object is individually well-behaved. We show how the need for requiring discrete variation may depend subtly on the particular ontology chosen for the domain.
****************************************************************
Physical Idealization as Plausible Inference. Tech. Rep. 534, NYU Comp. Sci. Dept., December, 1990. Logical Formalisms of Commonsense Reasoning, Stanford Spring Symposium, 1991.
Abstract: The analysis of physical systems almost always relies on idealized models of the objects involved. Any idealization, however, will be incorrect or insufficiently accurate some of the time. It seems reasonable, therefore, to view a physical idealization as a defeasible inference which can be withdrawn in the presence of contrary evidence. This talk discusses the consequences of such a view. We focus on examples where a system may or may not go into a state where idealizations are violated, such as dropping a ball near an open switch connected across a battery. We show that:
****************************************************************
Lucid Representations. Tech. Rep. 565, NYU Comp. Sci. Dept., June 1991.
Abstract: This paper criticizes the widespread idea that knowledge bases in AI systems should be complete and that representations should be "model-like". The arguments in favor of such representations are less cogent and more ambiguous than they appear at first. Levesque's suggestions that representations should be "vivid" is extremely restrictive, particularly in its uniform imposition of a closed-world assumption. Spatial representations that are adequate for reasoning about a wide range of physical phenomena must ultimately either use complex symbolic reasoning or deal with partial and imperfect approximations. Requiring that temporal representations be fully detailed simulations will often be extremely inefficient. Finally, a flexible intelligent system must necessarily deal with partial information of all kinds, and the techniques for carrying out reasoning about partial information using complete representations are very limited in their application.
****************************************************************
Order of Magnitude Reasoning in Qualitative Differential Equations.
in J. de Kleer and D. Weld (eds.),
Readings in Qualitative Physical Reasoning
Morgan Kaufmann, 1989, pp. 424-434.
Table 1 in
plain text.
Abstract: We present a theory that combines order of magnitude reasoning with envisionment of qualitative differential equations. Such a theory can be used to reason qualitatively about dynamical systems containing parameters of widely varying magnitudes. We present a mathematical analysis of envisionment over orders of magnitude, including a complete categorization of adjacent pairs of qualitative states. We show how this theory can be applied to simple problems, we give an algorithm for generating a complete envisionment, and we discuss the implementation of this algorithm in a running program.
****************************************************************
Solutions to a Paradox of Perception with Limited Acuity. First International Conference on Knowledge Representation and Reasoning, 1989.
Abstract: A realistic theory of perception and knowledge must deal with the fact that perceptions have limited acuity. However, in constructing such a theory, care must be taken to avoid a paradox whereby an agent can extract perfect knowledge from imperfect perceptions, using his knowledge of these imperfections. This paper presents two ways to avoid this paradox: first, by supposing that the agent has imperfect knowledge of his own perceptual system; second, by assuming that the perceptual system behaves non-deterministically.
****************************************************************
Reasoning about Hand-Eye Coordination. IJCAI-89 Workshop on Knowledge, Perception, and Planning
Abstract: This paper outlines a formal theory capable of supporting inferences about plans involving continuous coordination between sensors and effectors such as "Follow the sun until reaching a river; follow the river until reaching a lake." In particular, it presents a framework in which such actions can be represented and their physical effects, physical preconditions, and knowledge preconditions can be defined.
****************************************************************
A Logical Framework for Commonsense Predictions of Solid Object Behavior. AI in Engineering, vol. 3 no. 3, 1988, pp. 125-140. This appeared in somewhat different form as A Framework for Qualitative Reasoning about Solid Objects,
Abstract: Predicting the behavior of a qualitatively described system of solid objects requires a combination of geometrical, temporal, and physical reasoning. Method based on formulating and solving differential equations are not adequate for robust prediction, since the behavior of a system over extended time may be much simpler than its behavior over local time. This paper discusses a first-order language, in which one can state simply physical problems and derive their solutions deductively, without recourse to solving the differential equations. This logic is substantially more expressive and powerful than any previous AI representational system in this domain.
****************************************************************
Inferring Ignorance from the Locality of Visual Perception. Proc. AAAI-88, pp. 786-790
This paper presents a logical theory that supports high-level reasoning about knowledge and perception. We construct a formal language in which perception can be described. Using this languages, we state some fundamental axioms, and we show that these are sufficient to justify some elementary but interesting inferences about perception. In particular, our axioms make it possible in some cases to infer that an agent does not know about a particular event, because he has had no way to find out about it.
****************************************************************
Error Correction in Cognitive Maps. Proc. Workshop on Sensor Fusion: Spatial Reasoning and Scene Interpretation, SPIE, 1988, pp. 332-337.
Abstract: A mobile robot that maintains a dynamic cognitive map will often find that the information in the map is contradicted by his perceptions, and is therefore erroneous. Such errors may be the result of an earlier misperception, an erroneous matching, an erroneous default assumption, computation errors, a change in the world over time, or an erroneous previous error correction. Due to the complexity of inference in forming cognitive maps, domain-independent strategies for error correction, such as data-dependencies or conditional probabilities, are not sufficient by themselves to give a robust error correction scheme. Rather, domain-specific techniques and heuristics must be applied. We discuss some of the basic issues involved in detecting, diagnosing, and correcting errors in the cognitive map. We also discuss how a robot may decide whether to take action in order to gather relevant information.
****************************************************************
Constraint Propagation with Interval Labels. Artificial Intelligence, vol. 32, 1987, pp. 281-331.
Abstract: Constraint propagation is often used in AI systems to perform inference about quantities. This paper studies one particular kind of constraint propagation, where quantities are labelled with signs or with intervals, and these labels are propagated though recorded constraints. We review the uses of such inference schemes in AI systems of various kinds, and evaluate their strengths and weaknesses. In particular, we determine the completeness and running time of constraint propagation for various kinds of labels and constraints.
****************************************************************
A Representation for Complex Physical Domains Sanjaya Addanki and Ernest Davis. Proceedings of the 9th IJCAI, pp. 443 - 446, 1985
Abstract: We are exploring a system, called PROMPT, that will be capable of reasoning from first principles and high level knowledge in complex physical domains. Such problem-solving calls for a representation that will support the different analysis techniques required (e.g. differential, asymptotic, perturbation etc.) Efficiency considerations require that the representation also support heuristic control of reasoning. The paper lays the ground work for our effor by briefly describing the ontology and the representation scheme of PROMPT. Our ontology allows reasoning about multiple pasts and different happenings in the same space-time. The ontology provides important distinctions between materials, objects, bulk and distributed abstractions among physical entities. We organize world knowledge into ``prototypes'' that are used to focus the reasoning process. Problem-solving involves reasoning with and modifying prototypes.
****************************************************************
Planning and Executing Routes through Uncertain Territory. By D. McDermott and E. Davis, Artificial Intelligence, vol. 22, pp. 107 - 156, 1984
Planning routes and executing them requires both topological and metric information. A natural implementation of a `cognitive map' might therefore consist of an assertional data base for topological information and a `fuzzy map' for the metric information. A fuzzy map captures facts about objects by recording their relative positions, orientations, and scales in convenient frames of reference. It is fuzzy in the sense that coordinates are specified to lie in a range rather than having fixed values. The fuzzy map allows easy retrieval of information. The same information is also represented in a discrimination tree, which allows an object to be retrieved given its location and other attributes. The problem of constructing a fuzzy map is more difficult; we present a partial solution, an algorithm that assimilates a fact, first by imposing constaints on the fuzzy coordinates of the objects involved, then by rearranging or growing the tree of frames of reference. Route planning is modelled as a process of finding the overall direction and topology of the path, then filling the details by deciding how to go around barriers. It uses the retrieval algorithms. Our program SPAM carries out all these processes.
****************************************************************
A High Level Real-Time Programming Language Tech. Rep. 145, NYU Comp. Sci. Dept., October 1984
Abstract: COAL is a high-level language for writing real-time programs, particularly aimed at robotics applications. Our presentation includes an informal description of the language, a formal semantics for most of the constructs, and a few examples of typical use. The most prominent features of COAL are variables whose value changes continuously with time and extensive use of real-valued functions.
****************************************************************
Shape and Function of Solid Objects: Some Examples Tech. Rep 137, NYU Comp. Sci. Dept., October 1984
Abstract: The relation between shape and function is analysed in three basic types of objects: boxes, buttons, and rings. For each of these types of objects and their subtypes, we give a geometrical description, show how their function related to their shape, and enumerate some geometric heuristics to help determine their use in a given situation.
****************************************************************
An Ontology of Physical Action. Tech. Rep. 123, NYU Comp. Sci. Dept., June 1984
Abstract: This paper presents an ontology for reasoning about the use of rigid objects as tools. We define the concepts of scene, history, constraint, sensor, action and feasibility in extensional terms, and discuss their application to our system. Also, we present formalizations of several intuitive physical laws.
****************************************************************
The MERCATOR Representation of Spatial Knowledge. IJCAI-83
****************************************************************
i What's the Point? By R. Schank, G. Collins, E. Davis, P. Johnson, S. Lytinen, and B. Reiser. Cognitive Science, Vol. 6, No. 3, 1982
Abstract: We present a theory of conversation comprehension in which a line of the conversation is ``understood'' by relating it to one of seven possible ``points''. We define these point and present example where it seems plausible that the failure to ``get the point'' would indeed constitute a failure to understand the conversation. We argue that the recognition of such points must proceed in both a top down and a bottom up fashion, and thus is likely to be quite complicated. Finally, we see the processing of information in the conversation to be dependent on which point classification the user decides on.
****************************************************************
Algorithms for Scheduling Tasks on Unrelated Processors. By E. Davis and J. Jaffe. JACM, Vol. 28 No. 4, October 1981
Abstract: Several algorithms are presented for the nonpreemptive assignment of N independent tasks to M unrelated processors. One algorithm requires polynomial time in N and M and is at most 2 sqrt{M} times optimal in the worst case. This is the best polynomial-time algorithm known for scheduling such sets of tasks. An algorithm with slightly better worst case performance requires polynomial time in N but exponential time in M. This is the best algorithm known that requires time O(N log N) for each fixed value of M.
****************************************************************
Organizing Spatial Knowledge Tech. Report 193, Yale Computer Science Dept., January 1981
Abstract: A large class of spatial reasoning may be analyzed as the inference of the values of metric terms, given a set of constraints on other metric terms. A data structure called a ``fuzzy map'' may be used to represent the known constraints in a canonical form. It is relatively easy to infer term values, given a fuzzy map; however, it is difficult to construct the map from a set of constraints. This paper discusses the questions of what set of constraints may be represented in a fuzzy map, and present a number of heuristics which may be used to incorporate constraints into a map.