\documentstyle[12pt]{article}

% BEGIN stuff for times and dates
\newcount\hours
\newcount\minutes
\newcount\temp
\newtoks\ampm

% set the real time of day

\def\setdaytime{%
   \temp\time 
   \divide\temp 60
   \hours\temp 
   \multiply\temp -60
   \minutes\time 
   \advance\minutes \temp 
   \ifnum\hours =12 \ampm={p.m.} \else
   \ifnum\hours >12 \advance\hours -12 \ampm={p.m.} \else \ampm={a.m.} \fi \fi
}

\setdaytime

\def\theMonth{\relax
  \ifcase\month\or
    Jan\or Feb\or Mar\or Apr\or May\or Jun\or
    Jul\or Aug\or Sep\or Oct\or Nov\or Dec\fi}

\def\theTime{\the\hours:\ifnum \minutes < 10 0\fi \the\minutes\ \the\ampm}

\def\jmcdate{ \number\year\space\theMonth\space\number\day}
% END stuff for times and dates

%******************************
%******************************

\begin{document}
\title{OVERCOMING UNEXPECTED OBSTACLES}
\author{John McCarthy, Stanford University}
\date{}
\maketitle

\abstract{The present note illustrates how logical formalizations of common
sense knowledge and reasoning can achieve some of the open-endedness
of human common sense reasoning.  A plan is made to fly from Glasgow
to Moscow and is shown by circumscription to lead to the traveller
arriving in Moscow.  Then a fact about an unexpected obstacle---the
traveller losing his ticket---is added without changing any of the
previous facts, and the original plan can no longer be shown to work
if it must take into account the new fact.  However, an altered plan
that includes buying a replacement ticket can now be shown to work.
The formalism used is a modification of one developed by Vladimir
Lifschitz, and I have been informed that the modification isn't
correct, and I should go back to Lifschitz's original formalism.}

\section{Introduction}

	In contrast to reasoning within a formal theory of the
conventional sort used in science or operations research, common sense
reasoning (McCarthy 1959) is open-ended.  More facts than were
originally taken into account may turn out to be relevant.
Formalizing common sense requires a formal system that preserves this
open-endedness.  It can be done by formalizing nonmonotonic reasoning.

	We present a straightforward example of how a system might
take into account new facts.  An unexpected obstacle vitiates the
inference that the usual sequence of actions will achieve a goal.
Then, without changing any existing premise, a system can infer that
inserting a suitable new action in the sequence achieves the goal.

1. We use a general formalism for describing the effects of actions.
It is a variant due to Vladimir Lifschitz (1987) of the
situation calculus (McCarthy and Hayes 1969).

2. Specific facts concerning travel by airplane from one city to
another are given.  The need for a flight to exist and for the
traveller to have a ticket are made explicit preconditions.

3. Facts relevant for flying from Glasgow to Moscow via London
are mentioned, i.e. the flights are mentioned.

4. The circumscription formalism of (McCarthy 1980, 1986) is used to
minimize certain predicates, i.e.  $precond$, $noninertial$, $causes$,
$occurs$ while allowing the predicate $holds$ to vary.

5.  It can then be inferred (nonmonotonically) that flying
from Glasgow to London and then flying to Moscow results in being
in Moscow.

6. Facts giving the consequences of losing a ticket and
buying a ticket are included.  They do not change the result
of the previous inference.

7. An assertion that the ticket is lost in London is then added
to the previous facts.  Now it can no longer be inferred that the
previous plan succeeds.  However, it can be inferred that the
plan of flying to London, then buying a ticket and then flying to
Moscow does succeed.

	This example shows that it is possible to make a formalism
that (1) can be used to infer that a certain plan will succeed, (2)
can no longer infer that the plan will succeed when an obstacle
is asserted to exist, (3) can be used to infer that a different plan that
includes actions to overcome the obstacle will succeed.

	Our formulas include only the parameters needed to illustrate
the reasoning.  They don't even include the traveller, i.e. the
person whose actions are reasoned about.  From the point of view
of demonstrating full common sense reasoning this is a blemish.
However, we believe that the very formulas used here can be preserved
provided we {\it enter} a suitable {\it context}.  Formal reasoning
about contexts is discussed in (McCarthy 1993).

\section{The Formulas}

	Here are the formulas.
% from /u/jmc/e89/glasgo.sli with added comments
% suppress vertical bars
\overfullrule=0pt
%
$$holds(not\ p,s) \equiv \lnot holds(p,s)$$
%
This relates the operator $not$ as applied to fluents to logical
negation.
%
$$succeeds(a,s) \equiv (\forall p)(precond(p,a) \supset holds(p,s)).$$
%
This tells us that an action {\it succeeds} in a situation $s$
if all its preconditions hold in the situation.  Actually, it's
a definition of the predicate $succeeds$.
%
$$succeeds(a,s) \land causes(a,p) \supset holds(p,result(a,s)).$$
%
If an action succeeds in a situation and it is one that causes a
fluent to hold, then the fluent holds in the situation that
results from the preformance of the action.
%
$$\lnot noninertial(p,a) \land holds(p,s) \supset holds(p,result(a,s))$$
%
This tells us that unless an action affects a fluent, then
the fluent holds after the action if it held before the action.
%
$$occurs(e,s) \supset outcome\ s = outcome\ result(e,s)$$
%
This and the next axiom give the effects of events different from actions.
%
$$\forall e \lnot occurs(e,s) \supset outcome\ s = s$$
%
$$rr(a,s) = outcome\ result(e,s)$$
%
This is an abbreviation for the situation that results from an action after
all the events that occur after it have happened.
%
$$causes(fly(x,y),at\ y)$$
%
This is the first axiom specifically about the effects of flying.  It says
that flying from $x$ to $y$ causes being at $y$.
%
$$precond(at\ x,fly(x,y))$$
%
You must be at $x$ to fly from there to $y$.
%
$$precond(hasticket,fly(x,y))$$
%
Also you must have a ticket.
%
$$precond(existsflight(x,y),fly(x,y))$$
%
And there must be a flight.
%
$$causes(loseticket, not\ hasticket)$$
%
The effect of losing a ticket.
%
$$causes(buyticket,hasticket)$$
%
The effect of buying a ticket.
%
$$holds(at\ Glasgow,S0)$$
%
This is the first fact about the initial situation $S0$.  The
traveller is at Glasgow.
%
$$holds(hasticket,S0)$$
%
He has a ticket in $S0$
%
$$holds(existsflight(Glasgow,London),S0)$$
%
$$holds(existsflight(London,Moscow),S0)$$
%
The necessary flights exist.
%
$$circum(Facts;causes,precond,noninertial,occurs;holds)$$
%
This is the circumscription of the predicates $causes$, $precond$,
$noninertial$ and $occurs$ with $holds$ allowed to vary
 that is done with the conjunction
(called $Facts$) of these axioms.  Understanding this may
require reading (McCarthy 1986); (Lifschitz 1987) would
also help.
%
Once the circumscription has been done, we can show
%
$$holds(at Moscow,rr(fly(London,Moscow),rr(fly(Glasgow,London),S0))),$$
%
but not if we add
%
$$occurs(loseticket,result(fly(Glasgow,London),S0)).$$
%
However, in this case we can show
%
$$holds(at Moscow,rr(fly(London,Moscow),
rr(buyticket,
\ \ rr(fly(Glasgow,London),S0)))).$$

\section{Avoiding Considering Preconditions}

	It is a precondition for air travel without additional
actions that one be clothed, $holds(clothed(traveller),s)$, that one
not be lame $holds(not\,lame(traveller),s)$,
 and $holds(speaks\hbox{-}English(traveller),s)$,
etc.  With a bow towards later explaining how to make this happen
using formalized contexts (McCarthy 1989, 1991,1992)
 we'll abbreviate the above to the
propositional fluents $clothed$, $not\ lame$ and $speaks\hbox{-}English$.
In one respect these conditions are similar to the condition
that one have a ticket.  However, one is willing to specify as
part of the formalization of air travel that one have a ticket,
but it is not reasonable to refer explicitly to these other
conditions.

	Here's an approach to doing it.  The simplest approach
would be to have a fluent $ab7(traveller)$, abbreviated $ab7$,
and have sentences $not\ clothed \supset ab7$, etc.  We then
use $not\ ab7$ as a precondition for flying.  We then circumscribe
$ab7$.  This doesn't work well enough for two reasons.  First
we still have to mention all these other conditions in the
circumscription and circumscribe them also.  Second, suppose
one of the conditions fails, e.g. the traveller is lame so a
wheelchair must be provided.  Then we lose $not\ ab7$, and
we haven't got rid of the other conditions.

	At present I think the first problem has to be solved
by some form of $present$ resembling the {\em scope} of Etherington,
Perlis and Kraus (1989).  If we circumscribe it, we are jumping to
the conclusion that the interfering phenomena aren't present
The second problem may perhaps be solved by introducing a
parameter $exceptions$ to $ab7$ and requiring that none of
the exceptions be unresolved.

Both of these ideas require details.


\section{References}

\noindent
{\bf Etherington, David W. and Sarit Kraus and Donald Perlis (1989)}:
``Nonmonotonicity and the Scope of Reasoning'', Computer Science
Department, University of Maryland or AT\&T Bell Laboratories.
(to appear in {\it Artificial Intelligence}).

\noindent
{\bf Lifschitz, Vladimir (1987)}:
``Formal theories of action'', in: {\it The Frame Problem in Artificial
Intelligence, Proceedings of the 1987 Workshop}, 1987.
% FTA.TEX[ARC,VAL]

\noindent {\bf McCarthy, John (1959)}: ``Programs with Common Sense'', in {\it
Proceedings of the Teddington Conference on the Mechanization of
Thought Processes}, Her Majesty's Stationery Office, London.
  Reprinted in (McCarthy 1990).
%  common[e80,jmc],
% common.tex[e80,jmc]

\noindent
{\bf McCarthy, John and P.J. Hayes (1969)}:  ``Some Philosophical Problems from
the Standpoint of Artificial Intelligence'', in D. Michie (ed), {\it Machine
Intelligence 4}, American Elsevier, New York, NY.  Reprinted in (McCarthy 1990).
%  phil.tex[ess,jmc] with slight modifications

\noindent
{\bf McCarthy, John (1980)}: 
``Circumscription - A Form of Non-Monotonic Reasoning'', {\it Artificial
Intelligence}, Volume 13, Numbers 1,2, April.  Reprinted in (McCarthy 1990).
%  .<<aim 334, circum.new[s79,jmc], cirnew.tex[s79,jmc]>>

\noindent
{\bf McCarthy, John (1986)}:
``Applications of Circumscription to Formalizing Common Sense Knowledge''
{\it Artificial Intelligence}, April 1986.  Reprinted in (McCarthy 1990).
%  circum.tex[f83,jmc]

\noindent {\bf McCarthy, John (1987)}:
``Generality in Artificial Intelligence'', {\it Communications of the ACM}.
Vol. 30, No. 12, pp. 1030-1035.  Reprinted in (McCarthy 1990).
% genera[w86,jmc]

\noindent {\bf McCarthy, John (1989)}:
``Artificial Intelligence, Logic and Formalizing Common Sense'',
in Thomason, Richmond, ed. {\it Philosophical Logic
and Artificial Intelligence}, Kluwer Academic Publishing,
Dordrecht, Netherlands.  Reprinted in (McCarthy 1990).
% thomas[f88,jmc],  final printed version in thomas[s89,jmc]

\noindent {\bf McCarthy, John (1990)}:
{\it Formalizing Common Sense}, Ablex.

\noindent {\bf McCarthy, John (1993)}: ``Notes on Formalizing Context'',
submitted to IJCAI-93.




\vfill

{\tiny\noindent /@sail.stanford.edu:/u/jmc/w93/glasgow.tex: begun 1992 Aug 22, \LaTeX ed
\jmcdate\ at \theTime}
\end{document}
