****************************************************************

The Scope and Limits of Simulation in Cognitive Models by Ernest Davis and Gary Marcus, unpublished, December 2014.

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 *, to appear.

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:

- Given the signs of direction v and rotation matrix P, find the possible signs of the image of v under P. Moreover, for each possible sign vector of v * P, generate exact instantiations of v and P that yields that result.
- Given the signs of rotation matrices P and Q, find the possible signs of the composition P * Q. Moreover, for each possible sign matrix for the composition, generate exact instantiations of P and Q that yield that result.

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 *J _{a}(S)* and

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
*J _{a}(S)* and

****************************************************************

**
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:

- 1. Determining whether such a constraint network is consistent is decidable, but essentially as hard as determining whether a set of comparable size of algebraic constraints over the real numbers is consistent.
- 2. If R and S are bounded, regular regions that are not related by an affine transformation, then they can be distinguished by a constraint network. That is, there is a constraint network and a particular node in that network such that there is a solution where the node is equal to R, but no solution where the node is equal to S.

****************************************************************

** 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:

- 1. Geometric approximation.
- 2. Abstraction of a complex kinematic structure by a simpler kinematic structure. For example, the abstraction of a collection of tightly-linked objects as a single object.
- 3. Abstraction of a kinematic structure by a simpler theory. For example, the abstraction by a connectivity graph in configuration space.
- 4. Approximation of a complex kinematic structure by more complex theory. For example, the approximation of a chain by a string.
- 5. Approximation of a more complex theory by a kinematic theory. For example, the approximation of solid object dynamics by kinematics.

****************************************************************

**
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,

- a. P terminates when executed starting in T; and
- b. After any beginning of the execution of P starting in T,
- b.i. A will know whether P has successfully finished;
- b.ii. A will know of every action whether or not it is a next step of P; and
- b.iii. All the next steps of P are feasible.

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

- a. P1 is executable for A at T; and
- b. Any execution of P1 starting in T will constitute an execution of P starting in T.

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:

- Positive verification: Showing that a plan is feasible.
- Negative verification: Showing that a plan is infeasible.
- Monotonicity: The more an agent knows, the more plans are executable.
- Reduction for omniscient agent: For an omniscient agent, a plan is executable if and only if it is necessarily physically feasible, and a plan is epistemically feasible as task if and only if it is possibly physically feasible.
- Simple recursive rules that are sufficient condition for the feasibility of a plan described as a sequence or a conditional combination of subplans.

****************************************************************

**
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: 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:

- 1. Non-monotonic logics will try to enforce the idealization by supposing that the ball will miss the switch. This anomaly does not seem to be solvable by the kinds of techniques that have been applied to the Yale Shooting Problem, which it superficially resembles. We show that this problem is analogous to anomalies in non-monotonic logic that are time-independent.
- 2. A probabilistic analysis is possible, but it relies on independence assumptions that are hard to justify in general.
- 3. For completely specified systems, the rule "If the idealization gives solvable equations, then assumes that it holds" is, in fact, a monotonic system of inferences. It should therefore be possible to characterize this in a purely deductive theory. We show that this is, indeed, possible for simple cases, but can get messy in complex systems.
- 4. Programs that make physical predictions can avoid these problems by simply avoiding reasoning from the future to the past. Though most current programs observe this restriction, it seems likely that more powerful and general systems will have to violate it, and thus deal with this issue.
- 5. Finally, we look at dynamic systems where the idealization can be observed at any single instant, but it is inconsistent over extended intervals.

****************************************************************

**
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 *

****************************************************************

**
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.