Received: from etlpost.etl.go.jp by moose.cs.indiana.edu
	(8.7.1/IUCS.1.39) id HAA12094; Sun, 31 Dec 1995 07:32:27 -0500 (EST)
Received: from etlpom.etl.go.jp by etlpost.etl.go.jp (8.6.9+2.4W/2.7W)
	id VAA05916; Sun, 31 Dec 1995 21:32:18 +0900
Received: by etlpom.etl.go.jp (4.1/6.4J.6-ETLpom.MASTER)
	id AA10512; Sun, 31 Dec 95 21:33:23 JST
Received: by captain.etl.go.jp (4.1/6.4J.6-ETL.SLAVE)
	id AA05365; Sun, 31 Dec 95 21:31:06 JST
Message-Id: <9512311231.AA05365@captain.etl.go.jp>
To: ITALLC96@cs.indiana.edu
Cc: yoshki@tl.etl.go.jp, osawa@etl.go.jp, nakashim@etl.go.jp
Subject: ITALLC96 Submission (replacement)
Date: Sun, 31 Dec 1995 21:31:05 +0900
From: Hideyuki Nakashima <nakashim@etl.go.jp>
Status: RO


I am sorry but please replace our previous submission with the
following.  Two PS files should remain the same.

The diff:
24,25c24,25
< \author{H.~Nakashima, I.~Ohsawa and Y.~Kinoshita\\
< {\small \tt nakashim@etl.go.jp,osawa@etl.go.jp,yoshiki@etl.go.jp}\\
---
> \author{H.~Nakashima and I.~Ohsawa\\
> {\small \tt nakashim@etl.go.jp,osawa@etl.go.jp}\\

Hiday
------------

\documentstyle[11pt]{article}
\input psfig
\def\epsfile{\leavevmode\psfig}
\newcommand{\infon}[1]{\mbox{$\langle\!\langle$#1$\rangle \!\rangle$}}
\newcommand{\supports}[2]{#1 \mbox{$\models$} #2 }
\newcommand{\constraint}[2]{#1 \mbox{$\Leftarrow$} #2}
\newcommand{\involves}[3]{\mbox{$ #1 \Leftarrow #2 \mid #3 $}}
\newcommand{\fconstraint}[2]{#1 \mbox{$\Rightarrow$} #2}
\newcommand{\carries}[3]{\mbox{$#1\ |\hspace{-0.02cm}|\hspace{-0.1cm}-\ $\supports{#2}{#3}}}
\newcommand{\notsupports}[2]{\mbox{#1 $\not\models$ #2 }}
\newcommand{\dual}[1]{\mbox{$\overline{#1}$}}
\newcommand{\sem}[1]{\mbox{$[\![$#1$]\!]$}}

\oddsidemargin=0cm
\evensidemargin=0cm
\topmargin=-1cm
\textwidth=16cm
\textheight=23.5cm

% \date{1991-04-01\\ Revised 1991-05-12}
% \trnumber{91-7}

\title{Inference with \MSS\\Extended Abstract}
\author{H.~Nakashima and I.~Ohsawa\\
{\small \tt nakashim@etl.go.jp,osawa@etl.go.jp}\\
{\small Electrotechnical Laboratory}\\
{\small 1-1-4 Umezono, Tsukuba 305 Japan}}
% \division{Cooperative Architecture}

\begin{document}

\newtheorem{myexp}{Example}[df]
\newenvironment{myexample}{\begin{myexp}\mbox{\ }\\\rm}{\end{myexp}}
\newcommand{\comment}[1]{}
\newcommand{\ms}{mental situation}
\newcommand{\mss}{\ms s}
\newcommand{\Ms}{Mental situation}
\newcommand{\Mss}{\Ms s}
\newcommand{\MS}{Mental Situation}
\newcommand{\MSS}{\MS s}
\newcommand{\defn}{\mbox{$\stackrel{def}{=}$}}
\newcommand{\set}[2]{\{#1 |  #2 \}}
\newcommand{\pair}[1]{\mbox{$\langle #1 \rangle$}}
\newcommand{\minfon}[1]{\mbox{$\langle \hspace{-5pt} \langle #1\rangle\hspace{-5pt} \rangle$}}
\newcommand{\sit}[2]{\mbox{$\langle #1, #2 \rangle$}}
\newtheorem{definition}{Definition}
\newtheorem{notation}{Notation}[definition]
\newtheorem{lemma}{Lemma}[definition]
\newtheorem{theorem}{Theorem}
\newcommand{\r}[1]{\mbox{$^{{\it #1}}$}}

\maketitle

\begin{abstract}
Extension of Situation Theory is described to model
intelligent agents' internal mental structure.  Elements of the
structure are called \mss .  A \Ms\ corresponds to an entity in Situation
Theory, not to a situation.  A set of \mss\ is the mental image of the
real situation.

By making the structure richer, we can explain many aspects of
intelligence.  Specialization is the most important operation on the
structure.  We will show that the essence of situated inference relies
on the operation.

\end{abstract}

\comment{
$B!c2?$,=PMh$?$+L@<($9$k$3$H!d(B
$BFC$K(B

inheritance
(Nixon problem)

$B!c(Binfon$B$rDj5A$9$k$3$H!d(B
}

\section{Introduction}

There have been many knowledge representation frameworks proposed,
including semantic networks, frame theory and several kinds of logic.
However, few of them took ``situatedness,'' or context dependency, of
knowledge and intelligence into account until recently.

The fact that situations play important role in analysis of
intelligence is pointed out by many researchers.  An agent can behave
intelligently because it is attuned to the situation.  Nakashima and
Tutiya\cite{Nakashima-Tutiya-91}, however, argued that limiting our
consideration into real situations is not proper.  Especially for
planning, when one cannot actually try and observe the change in real
situations, the result of possible actions should be calculated
mentally and be compared each other to choose the best one.  Since the
real situation cannot be observed in that case, an agent cannot
achieve so called a situated inference\cite{Barwise-Etchemendy90}.
However, it is not practical to have two sets of inference schemata
separately for real situations and hypothetical planning since they
are used in mixture (cf. partial planning \cite{Katagiri90}).  We must
conjecture the existence of situation equivalent structure in our
mind.

A theory of
knowledge representation and reasoning must reflect this observation
and must be able to
\begin{enumerate}
\item express the relations of situations and the agent, and
\item treat situations as first class objects of reasoning.
\end{enumerate}
Situation theory\cite{SA}\cite{Devlin91} is
unique in that it treats situations as objects.
The basic idea is that the truth value of logical proposition is
situation dependent.  
For example, the truth value of a sentence ``It is raining today''
cannot be fixed unless its situation (time and location) is fixed.
Based on this observation, the situation theory defines a proposition
as a pair of {\it situation} and a sentence called {\it infon},
written as:
\begin{quote}
\supports{{\it situation}}{{\it infon}}
\end{quote}

Back in the early era of artificial intelligence, similar formalism
was proposed by McCarthy as situation calculus, although the
motivation was different.  Later it was extended into a second order
form:
\begin{quote}
holds({\it proposition}, {\it situation})
\end{quote}
which has similar appearance as the proposition of the situation
theory.  Recently, the situation is recognized as the context of
representation and reasoning\cite{Guha92,McCarthy93}.  Contexts are
first class objects of the language.  Rich description can be applied
to a context, which was not possible in situation calculus.
\comment{
At this
point, the difference between the situation theory and contextual
representation is almost negligible as far as knowledge representation
is concerned.  However, the situation theory lacks a theory for
reasoning.
}

The main subject of this paper is to give a theory of
reasoning.  The framework proposed is richer than those of Guha or
McCarthy in the sense that primitive relations between situations are well
defined in our framework while it is up to the programmer in their case.

The formalism given is based on the author's previous work on
knowledge representation based on the multiple world
mechanism\cite{Nakashima84E,Nakashima90:PRICAI} (and programming with
situation theory\cite{Prosit-FGCS,NPS-91}).  There, any piece of
knowledge is treated as context dependent.  The context consists of
other pieces of knowledge and the context structure is created by
dynamic nesting of worlds.  The concept of worlds used in
Uranus\cite{Uranus} is one of the origin of \mss\ described in this
paper.


By eliminating elements that the situation guarantees to be fixed, an
agent can keep the representation minimum, making reasoning most
efficient.  When the guarantee is invalidated, however, the system
must represent the information explicitly.  What we need is a
representational framework in which information can be passed from
situation to representation and vice versa.  The system can forget
about the surrounding situation to efficiently reason within the
situation, or it can objectize the situation to reason about the
complex structure of the situations.


Let us consider an example of representing locations of objects for
robot planning.  When a robot scans its visual image and makes an
internal map of outside objects, it is natural to represent them
something like
\begin{quote}
at(object1, location(3.5, 4.8)).\footnote{The syntax is
not important here.  Only the informational content counts.}
\end{quote}

\comment{

Here we
assume that the robot is using x-y coordinate system to represent the
location.  When the robot moves object1, it can easily update its
location by changing the x-y coordinates of the representation.
}

However, when the robot wants to remember all the history of the
locations of objects or wants to plan future positions of them, it becomes
necessary to represent the time together with the location like
\begin{quote}
at(object1, location(3.5, 4.8), time(1992-01-01, 17:33:05)).
\end{quote}
The ``time'' information was not newly introduced.  It is always
there.  It was the robot that did not require the information.  The
representation of the robot (without time) was correct because it
matched the real situation at that moment although ``that moment''
was not explicitly represented.  We say that the representation is
{\it attuned to} the situation.  This is why the robot needs another
form when it wants to represent the state of
the situation it is {\it not} in.

\comment{
In conventional approaches, the time information was treated as
``defaults''.  When it is not explicitly represented, it is considered
to be the current time by default.  This notion of ``default''
implicitly assumes existence of ``total information''.  Anything
missing is treated as a default.  Here we claim that the assumption of the
existence of total information is false.  We cannot list all
(potentially) necessary information beforehand (analogous to
the frame problem\cite{FrameProblem}).  When the robot is shipped to
the United States, it will find that the time zone is different and
must also represent it like
\begin{quote}
at(object1, location(3.5, 4.8), time(1992-10-01, 17:33:05, JST)).
\end{quote}
Or, when the robot gets installed a pair of jet boots and begins to fly
around, it needs 3D representation of the location:
\begin{quote}
at(object1, location(3.5, 4.8, 0.0), time(1992-10-01, 17:33:05, JST)).
\end{quote}
The requirement increases as the robot faces more complicated structure
of situations.
}

An agent can also change the point of view.  For example, when a robot
actually plans to move its hands, it is better to use body centered
coordinate rather than the room centered x-y coordinate.  It further
needs hand centered coordinates for their finger movements.
It needs something like
\begin{quote}
at(object1, right(3degree), distance(45cm)).
\end{quote}
Or else, the robot can even use qualitative representation like
\begin{quote}
at(object1, in-the-front, near).
\end{quote}
The bottom line is that there is no ``complete representation'' nor
``canonical form''.  It is situation dependent.
What we need is a framework in which we can express
\begin{itemize}
\item the relation
between situation and representation,
\item the relation between representation in different situations, and
\item the relation between situations.
\end{itemize}
We propose \mss\ for the purpose.


\section{Situated Representation}

Here, we formally describe our representation language which is an
extension of situation theory.  Details not described here are the
same as in situation theory.  The basic idea of the extension is how
{\it not} to represent information that is obvious in the situation.

We will use the term ``mental'' to denote that ``situations'' and
``infons'' we are talking about are not out there in the world, but
rather they should be considered as mental representations.
The following description is based on \cite{NOK-91}.

\subsection{Mental Infon}

Since we must explicitly name each
argument role,
we first introduce {\it argument roles} to distinguish different
arguments of relations.
\begin{definition}
{\it AR} : a set of argument roles.
\end{definition}

\comment{
Here we are not committed to whether argument roles are
specific to each relation or universal to all relations.  If they are
specific, then the effect of specialization (definition
\ref{specialization}) is limited to several infons that share the
relation.  If not, all infons may be affected.
}

\begin{definition}
{\it ME} : a set of mental entities.  They are given as primitives.
\end{definition}

Mental entities here correspond to ``parameters'' in situation
theory.  They are used to point to the entities in the world.
In our formalism, mental situations are also mental entities.

\comment{
We have many perspectives to a single entity in the world.  For
example, the same planet Venus is conceived either as ``the morning
star'' or ``the evening star''.  In our formalism, a mental entity is
represented as a set of all those images that the representer knows
to be about the same entity.
\footnote{
This definition of mental entity is closely related to what Devlin
calls ``an oracle''\cite{Devlin91}.  It also reflects the analysis of
human concepts by Lakoff\cite{Lakoff87}.
}
Note that those entities can be imaginary, having no counter part in
the real world.  When a mental entity has a counter part
in the real situation, then
\begin{quote}
$me \in ME \Rightarrow \exists r \in R$ such that $me=r$.
\end{quote}
}

When the arity of $r$ is 1, {\it me} is a set of
entities that belong to the class defined by $r$.
Members of $r$ are the entities in the real world.  Therefore when $r$
is, say, `bird', then it is a set of all birds.  However, it is not
usually the case for mental entities.  We, first, don't know
all birds.  Instead, we have a ``typical'' bird for mental entities.

A mental infon consists of a triplet of a relation, a set of
role-value pairs and a polarity.

\begin{definition}
A mental infon is a triple \pair{r,f,p} where
\begin{enumerate}
\item $r \in {\it ME}$: a relation name,
\item  $f : {\it AR} \stackrel{f}{\rightarrow} {\it ME}$ is a finite
mapping from {\it AR} to {\it ME}, and
\item $p \in \{0,1\}$: the polarity.
\end{enumerate}
\end{definition}

\begin{notation}
A mental infon \pair{r,f,p} is written as
\infon{{\it r}, \r{role_1}$a_1,\dots,\r{role_n}a_n ; p$} where
$role_i \in$ domain(f) and $a_i \in$ range(f).
$p$ may be omitted when it is 1 (meaning positive).
\end{notation}

For example, an
infon with relation=kill, killer=Brutus and
killee=Caesar is written as
\begin{quote}
\infon{kill, \r{killer}Brutus, \r{killee}Caesar}, 
\end{quote}
or
\begin{quote}
\infon{kill, \r{killee}Caesar, \r{killer}Brutus}.
\end{quote}
Note that Brutus and Caesar are mental entities.
Mental entities form their own mental
situations around them as described in the next section.

\comment{
Note also that the arguments are order-free.
\footnote{
This feature of situated representation is best suited for syntactic
and semantic analysis of Japanese, in which complement phrases can
appear almost in any order.  
}
}


\begin{definition}
{\it MI}: the set of all mental infons.
\end{definition}

\begin{definition}
The negation of an infon $\sigma$ is written as $\overline{\sigma}$.
\end{definition}

\subsection{Primitive \MS}
\begin{definition}
A primitive \ms\ is a pair \pair{n, i} where
\begin{enumerate}
\item $n \in ME$: the unique identifier of the primitive \ms, and
\item $i\subseteq MI$: the set of mental infons which
the primitive \ms\ supports.
\end{enumerate}
\end{definition}
The name corresponds to the agent's conception of the \ms\ and can be
any element of {\it ME}, including relations.

There can be two \mss\ with exactly the same set of mental infons but
with different names.  In this case, they correspond to two distinct
concepts which accidentally have the same characteristics.

\begin{definition}

{\it PMS} : the set of all primitive \mss\ ($ME \times 2^{MI}$)

\end{definition}

\begin{notation}
For all $s\in${\it PMS},
{\it s.ME} denotes {\it ME} associated with {\it s}, and
{\it s.MI} denotes the set of {\it MI} ($2^{\it MI}$)
associated with {\it s}.
\end{notation}

\begin{definition}\label{pms-infon}
$\forall\sigma\in{\it MI}$, $\forall${\it s}$\in${\it PMS},
\supports{{\it s.ME}}{$\sigma$} \defn\ 
$\sigma\in{\it s}$.{\it MI}
\end{definition}
Thus, a mental infon $\sigma$ is supported by a primitive 
mental situation {\it s} just in case {\it s} contains
$\sigma$ as an element of its 
set of mental infons.

A typical primitive mental situation we are considering corresponds to
our conceptualization of a certain entity.  For example, a primitive
mental situation for Caesar\footnote{
This idea is parallel to Devlin's ``oracle'' [\cite{Devlin91}].}
is a pair of a mental entity {\it Caesar}
and a set of infons about Caesar.  We can write this as follows
using definition \ref{pms-infon}:
\begin{quote}
\supports{Caesar}{\infon{name, \r{family}Caesar, \r{given}Julius}}\\
\supports{Caesar}{\infon{position, \r{rank}general, \r{city}Rome}}\\
\supports{Caesar}{\infon{kill, \r{killee}Caesar, \r{killer}Brutus}}\\
\supports{Caesar}{$\dots$}
\end{quote}
Note that we use a mental entity to denote the mental situation
associated with it.

For readers familiar with knowledge representation frameworks in AI,
we point out that our formalism of {\it primitive} \mss\ has a simple
mapping (table \ref{frame})
to the frame system [\cite{Frame}].
\begin{table}[htb]
\begin{centering}
\begin{tabular}{|l|l|}\hline
our framework & the frame system\\\hline
mental situation & frame\\
relation  & slot\\
role      & facet\\
value     & value\\\hline
\end{tabular}
\caption{Correspondence to the frame system}
\label{frame}
\end{centering}
\end{table}

However, the frame system presupposes fixed cluster of frames, and do
not support operations like specialization or globalization described
below.  Another shortcoming of the frame system is that it has no
formal framework for reasoning other than inheritance.  The user must
provide procedural knowledge for reasoning.

\subsection{\MS}

Starting from a primitive \ms, and applying a sequence of
either specializations or globalizations, definitions of which are
given later in this section, the inferencer can reach any
form of (non-primitive) mental situations.  
The detailed mechanism to allow this operation is not important in
this paper, and makes the definition more complex.   Therefore, we
will just consider specialization in the following definitions of
mental situations.

\begin{definition}\label{ms}
A \ms\ is a triplet \pair{n, i, s} where
\begin{enumerate}
\item $n \in {\it ME}$ is the name,
\item $i \subseteq {\it MI}$ is the set of mental infons it supports, and
\item $s \in  2^{{\it AR} \times {\it ME}}$ is
information about some of the missing argument roles.
\end{enumerate}
\end{definition}

\begin{definition}
$MS$: the set of all \mss\ (${\it PMS} \times2^{AR \times ME}$).
\end{definition}

A primitive \ms\ is a \ms\ with $s=\phi$.
A primitive \ms\ is specialized by fixing one of its argument roles
with a particular value.
For example, a primitive \ms\ {\it s} supporting an infon \infon{kill,
\r{killer}Brutus, \r{killee}Caesar} is specialized by fixing
the value of $\r{killer}$ to Brutus.
Once it is fixed, we do not have to mention it explicitly.  Thus we can
write the infon as  \infon{kill, \r{killee}Caesar}.
We attach the fixed part to {\it s}.

Before defining specialization, let us define a partial function $sp$
on mental infons.

\begin{definition}
sp: $MI \times AR \times ME \rightarrow MI$ is called ``selective
projection'' defined as follows:

$\forall \pair{r_0,f_0,p_0} \in MI, a\in AR, n\in ME, $
\[ sp(\pair{r_0,f_0,p_0},a,n)=
 \left\{ 
\begin{array}{ll}\pair{r_0,f_1,p_0} & \mbox{if $f_0(a)=n$}\\
\perp &{\rm otherwise}
\end{array} \right.\]
where domain($f_1$)=domain($f_0)\setminus\{a\}$ and
$ \forall x \in {\rm domain}(f_1), f_1(x)=f_0(x))$.
\end{definition}

Now we are ready to define specialization.
\begin{definition}\label{specialization}
Let $s_1=\pair{n_1, i_1, an_1}$
and $s_0 = \pair{n_0,i_0,an_0}$ be \mss,
$a$ be a role and $n$ be a mental entity.
Then $s_1$ is defined to be a specialization of  $s_0$ with $a$ and $n$,
if and only if the following propositions are satisfied:
\begin{enumerate}
\item
$\forall \sigma_1\in MI$,
\[
\supports{s_1}{\sigma_1} \Leftrightarrow\\
\begin{array}{ll}
\left(\exists \sigma_0, \ \supports{s_0}{\sigma_0} \land
\hspace*{3mm} \sigma_1 = sp(\sigma_0, a, n)\right)\ \lor\\
\left(\supports{s_0}{\sigma_1}\land \sigma_1=\pair{r,f,p}\land a \not\in {\rm domain}(f)\right)
\end{array}
\]
\item
$an_1 = an_0 \cup \{\pair{a,n}\}$
\end{enumerate}
\end{definition}

\comment{
The above definition claims that a specialized \ms\ $s_1$ supports an
mental infon only when one of the following conditions holds:
\begin{enumerate}
\item When the original \ms\ $s_0$ supports a mental infon with the designated
role $a$ and value $n$, then $s_1$
supports an infon without $a$ and $n$, with all
values of other roles remaining unchanged.

\begin{myexample}
\supports{$s_0$}{\infon{time,\r{clock}4:00,\r{period}pm,\r{zone}JST}}\\
\hspace*{2cm}$\Downarrow$ specialization with \r{zone}JST\\
\supports{$s_1$}{\infon{time,\r{clock}4:00,\r{period}pm}}\\
\end{myexample}
\item When $s_0$ supports a mental infon which does not
contain $a$, then $s_1$ supports the
same mental infon.
\begin{myexample}
\supports{$s_0$}{\infon{time,\r{clock}4:00,\r{period}pm,\r{zone}JST}}\\
\hspace*{2cm}$\Downarrow$ specialization with \r{actor}John\\
\supports{$s_1$}{\infon{time,\r{clock}4:00,\r{period}pm,\r{zone}JST}}\\
\end{myexample}
\end{enumerate}
}

\comment{
Note that the following proposition follows from the definition:
when $s_0$ supports a mental infon with the designated
role $a$ but with a different value, then $s_1$
does not support it, unless $s_0$ accidentally
supports an infon without $a$ and $n$, but with all the
values of other roles being the same.
}
\begin{myexample}
\supports{$s_0$}{\infon{time,\r{clock}4:00,\r{period}pm,\r{zone}JST}}\\
\hspace*{2cm}$\Downarrow$ specialization with \r{zone}GMT\\
\notsupports{$s_1$}{\infon{time,\r{clock}4:00,\r{period}pm,\r{zone}JST}}\\
\end{myexample}


\begin{myexample}
\supports{$s_0$}{\infon{time,\r{clock}4:00,\r{period}pm,\r{zone}JST}}\\
\supports{$s_0$}{\infon{time,\r{clock}11:00,\r{period}pm,\r{zone}PST}}\\
\supports{$s_0$}{\infon{in,\r{loc}solar-system}}\\
\hspace*{2cm}$\Downarrow$ specialization with \r{zone}JST\\
\supports{$s_1$}{\infon{time,\r{clock}4:00,\r{period}pm}}\\
\supports{$s_1$}{\infon{in,\r{loc}solar-system}}\\
\end{myexample}


\begin{notation}
$s/^{r}n$ denotes a specialization of {\it s} 
with a role $r$ and a value $n$.
\end{notation}

When the specialization is applied to a situation, the information
used for specialization is said to be moved from infons to the
situation.
Therefore, the following two sentences express exactly the same information.
\begin{quote}
\supports{$s$}{\infon{time,\r{clock}4:00,\r{zone}JST}}\\
\hspace*{2cm} $\Updownarrow$\\
\supports{$s/\r{zone}JST$}{\infon{time,\r{clock}4:00}}
\end{quote}
The constituent ``JST'' is implicit in the $s/\r{zone}JST$
(corresponding to Japan) situation while
it is explicit in the $s$ (corresponding to the world) situation.
When an intelligent agent makes an inference, it uses $s/\r{zone}JST$
rather than just the situation $s$.

The result of a sequence of specializations on
different argument roles does not depend on the order in which they
are applied:
\begin{quote}
$\forall s \in {\it MS}, a_1, a_2 \in {\it AR}, n, m \in {\it ME}$
$ \ s/^{a_1}n/^{a_2}m \equiv s/^{a_2}m/^{a_1}n$
\end{quote}

%\subsection{Globalization}

Globalization is the inverse operation of specialization to be used to
make mental infons less situation dependent.  It has also been called
context lifting (for example, \cite{McCarthy93}).

\comment{
When the mental situation at hand is a specialized one, then the
inverse operation is trivial.

There are cases, however, when one must
globalize a primitive \ms.
For example, a child in
Japan may begin by representing time as
\begin{quote}
\infon{time,\r{clock}4:00}
\end{quote}
without knowing the existence of other roles.
And later when (s)he grows up to know that there are other countries,
(s)he needs a more global representation such as
\begin{quote}
\infon{time,\r{clock}4:00,\r{zone}JST}.
\end{quote}
}

\comment{There is more than one way to specialize a
situation {\it wrt.~ME} when it fills different argument roles.
\begin{quote}
\supports{$s_h$}{\infon{kill,Mitsuhide,Nobunaga}}\\
\supports{$s_h$}{\infon{kill,Hideyoshi,Mitsuhide}}
\end{quote}
could be specialized either to
\begin{quote}
\supports{$s_h$/Mitsuhide}{\infon{kill,Nobunaga}}\\
\supports{$s_h$/Mitsuhide}{\infon{kill,Hideyoshi,Mitsuhide}}
\end{quote}
or
\begin{quote}
\supports{$s_h$/Mitsuhide}{\infon{kill,Mitsuhide,Nobunaga}}\\
\supports{$s_h$/Mitsuhide}{\infon{kill,Hideyoshi}}
\end{quote}
The choice is up to the agent but we
usually prefer the former, since in ``killing''
relation, we can omit the killee but not
the killer.
}

\subsection{Inclusion}

\begin{definition}\label{inherit}
$ms_1 \sqsupseteq ms_2$ iff
\begin{quote}
\fconstraint{\supports{$ms_1$}{$\sigma$}}{\supports{$ms_2$}{$\sigma$}}
if $\sigma$ is coherent with $ms_2$.
\end{quote}
\end{definition}
Note the direction of inclusion ($\sqsupseteq$) and implication
($\Rightarrow$).  Infons are inherited from super-\ms\ to sub-\ms.

Coherency is defined as usual.
\begin{definition}
An infon $\sigma$ is coherent with $ms \in MS$ iff
\notsupports{$ms$}{$\overline{\sigma}$}
\end{definition}

\section{How to Reason with \MSS}

\subsection{Inference {\em in} a Situation {\em about} Situations}
\label{IIS}\label{IAS}

Inference {\em in} a situation (IIS hereafter) and inference {\em
about} situations (IAS hereafter) are two different types of
inference\cite{Nakashima-Tutiya-91}.  IIS is
conducted by fully taking advantage of being in the situation.  The
agent does not have to consider the situation part.
IAS is used to change the situation for IIS.

At any stage, the agent has many \mss\ to make inference with.  They
form a heterarchy altogether.  However, since IIS is used to make
inference, only some part of the heterarchy, those that are inclusive
one another, is used.  Therefore, we assume that an agent always puts
oneself in one of the \mss\ and has access to its super-situations.
IAS is used to change the \ms\ one is in.

An agent takes advantage of knowing constraints on situations.  In short,
an agent uses constraint for reasoning.\cite{Prosit}.  Constraints could be
within situations (IIS) or between situations (IAS).

\subsection{Inheritance}

Inheritance, which is a quite common mechanism, is implemented in
almost all knowledge representation systems.
It is also the simplest form of inference with \mss\ (IIS).
A situation inherits properties from its super situations ({\it cf.}
definition \ref{inherit}).

As claimed in \cite{Nakashima-Tutiya-91}, a logical implication:
\begin{quote}
$\forall x. bird(x)\rightarrow fly(x)$\\
$\forall x. canary(x)\rightarrow bird(x)$
\end{quote}
can be replaced by inheritance:
\begin{quote}
\supports{bird}{\infon{fly}}\\
canary $\sqsubseteq$ bird
\end{quote}

Treatment of exceptions is an important issue.  Some birds are known
not to fly, for example.  If a situation explicitly supports an infon,
then its dual is not inherited.  Thus, in the presence of
\begin{quote}
\supports{penguin}{$\overline{\infon{fly}}$}
\end{quote}
\infon{fly} is not inherited from bird to penguin.

\subsection{View}
Some of the situations are statically
fixed and some are dynamically created on
the fly (using specialization defined in
the definition \ref{specialization}) for the sake of reasoning.
For example, it is for sometime convenient to
create a situation for a person's whole
life, while it is for another time convenient to create a
situation of a time slice with many persons in it.

Note the fact that specialization can be applied to a set of \mss .
This enables the agent to specialize the whole \mss\ altogether
preserving the structure.  It can introduce any new ``view''.


\subsection{Script change}\label{script-change}

Scripts\cite{Schank75} explain how one can behave
intelligently if one has a proper script for the situation.  However, it
does not account for how such a script is brought into the scope.

Now we are ready to answer the old question: ``how can we make active a
proper script?''  There are two processes involved: learning and
inference {\em about} situations.  Learning is a slow process to
construct \ms\ structure and inference is a fast process to move
around the structure.

Although the agent is in one of the \mss\ at one time, other exclusive
ones may also be in its mind (short term memory), ready to be used.
Using IAS, the agent can decide which one to go into.  More detailed
process is described with an example of reasoning about a ``part time
four-wheel-drive car''.

Some part of the
\mss\ must be replaced with a new one whenever the circumstance
changes.  This is analogous to computers' swapping memory contents
with disk or changing values of variables due to context changes.  
\footnote{If you are familiar with Lisp systems, the following analogy
should make sense.  To hold the values of variables, there are two
techniques: deep binding and shallow binding.  Deep binding requires
small amount of computation for context change but large amount for
reference to the value.  On the other hand, shallow binding requires
larger amount of computation for context change and constant reference
time.  We could use shallow binding technique for keeping
information.}
The cost of swapping of the current information is
expected to be relatively small compared to the cost of inference,
provided that the situation changes rather smoothly (when it changes
drastically, even we human are get surprised and need some time to
adjust).


\subsection{Representing Time}
\label{time}

When one has a spatio-temporal representation of the state of affairs
like:
\begin{quote}
\supports{s}{\infon{on, A, B, t0}}\\
\supports{s}{\infon{on, C, D, t1}}\\
\supports{s}{\infon{on, A, C, t2}}
\end{quote}
it is a simple matter to re-represent them along the time sequence.
\begin{quote}
\supports{s/t0}{\infon{on, A, B}}\\
\supports{s/t1}{\infon{on, C, D}}\\
\supports{s/t2}{\infon{on, A, C}}
\end{quote}

Frame axiom\cite{FrameProblem}: a state remains the same unless
explicitly said/inferred to change, is implemented by imposing
inclusion relation over the specialized situations:
\begin{quote}
$s/t0 \sqsupseteq s/t1 \sqsupseteq s/t2.$
\end{quote}
Since s/t0, s/t1 and s/t2 are all different specializations of s, this
inclusion violates one of the conditions.  {\it ME}'s of those
specializations are not the same.  Therefore this inclusion is not
naturally deduced.  It must be explicitly given to the system.

\begin{figure}[htb]
\begin{center}
\epsfile{file=mental-time.ps}
\end{center}
\caption{Theorist's view of time}
\end{figure}

By imposing inheritance over situations, and by introducing a constraint
``one object is on exactly one thing,''\footnote{\.{x}, \.{y} and \.{z} are
parameters ranging over mental entities.
For more details of how constraints are represented and used, confer Prosit\cite{Prosit}.}
\begin{quote}
\fconstraint{\infon{on, \.{x}, \.{y}}$\land$ \.{y} $\not =$ \.{z}}{$\overline{\infon{on, \.{x}, \.{z}}}$}
\end{quote}
the following propositions are derived:
\begin{quote}
\supports{s/t0}{\infon{on, A, B}}\\
\supports{s/t1}{\infon{on, C, D}}\\
\supports{s/t1}{\infon{on, A, B}}\\
\supports{s/t2}{\infon{on, A, C}}\\
\supports{s/t2}{\infon{on, C, D}}
\end{quote}

The above formalization is based on the theorist's view.  A situated
agent has another view depicted in figure \ref{actual-time}.  The main
point is that the agent is always situated in ``now''.  The time
independent representation does not actually exist.  It is quite
interesting that this view explains the formalization of STRIPS which
was used to solve the frame problem\cite{FrameProblem}.

\begin{figure}[htb]
\begin{center}
\epsfile{file=actual-time.ps}
\end{center}
\caption{Agent's view of time}\label{actual-time}
\end{figure}

\comment{	
\subsection{Part-time 4WD}

One concrete example of script change is explained with the mental
model of the driver of so called a part-time four-wheel-drive car
(PT4WD hereafter).\cite{Nakashima84E} Although four-wheel-drive is
preferable on slippery roads, it has several demerits in normal
conditions.  One of the solutions is a PT4WD that could be operated
either in 4WD mode or in FF(front wheel drive) mode.  There is a
selection lever to change the mode.  So, PT4WD behaves as a 4WD while
the lever is on 4WD side and it behaves as a FF while the lever is on
FF side.  This situation is modeled by the driver using the following
two constraints and relations:
\begin{quote}
\fconstraint{(\supports{PT4WD}{\infon{lever, 4WD}})}{\infon{achieve, \infon{in, PT4WD/4WD}}}\\
\fconstraint{(\supports{PT4WD}{\infon{lever, FF}})}{\infon{achieve, \infon{in, PT4WD/FF}}}\\
{PT4WD} / 4WD $\sqsubseteq$ {4WD}\\
{PT4WD} / FF $\sqsubseteq$ {FF}
\end{quote}

\begin{figure}[h]
\epsfile{file=/usr/users/nakashim/ps/mental-4wd.ps,scale=0.7}
\end{figure}

\infon{achieve, \infon{in,PT4WD/4WD}} should be treated as a (mental)
action of the reasoner to change
\ms of inference, rather than a simple information.  It is
written as {\tt (?(in PT4WD/4WD))} in Prosit to distinguish it from a
simple assertion.  {\tt ?} is used to make an infon into
a goal to be achieved.
\footnote{For a proper treatment of action in
situation theory, see \cite{Ohsawa91}.}

If the lever is changed while PT4WD is in either of the specialized
situation, then it must once go back to PT4WD to re-select the proper
specialization again.
\begin{quote}
\fconstraint{\supports{PT4WD/4WD}{\infon{lever-change}}}{\infon{achieve, \infon{out}}}\\
\fconstraint{\supports{PT4WD/FF}{\infon{lever-change}}}{\infon{achieve,
\infon{out}}}
\end{quote}

\infon{out} is an action to go out of the current specialized mental
situation to the previous (more general) one.  Note that \infon{out}
is a situated notion since the resulting situation just depend on the
original \ms\ in which the reasoner is.  It is not proper to use an
absolute form like \infon{in, PT4WD}.  This kind of absolute notion
cannot cope with future change of \ms structure that may happen when,
say, PT4WD/OPEN/4WD or PT4WD/OPEN/FF is created where OPEN means a
``open car''.

Since out is always followed by going to the other specialized
situation, it could be optimized as
\begin{quote}
\fconstraint{\supports{PT4WD/4WD}{\infon{lever-change}}}{\infon{achieve,
\infon{go, ../FF}}}\\
\fconstraint{\supports{PT4WD/FF}{\infon{lever-change}}}{\infon{achieve,
\infon{go, ../4WD}}}
\end{quote}
``../FF'' should be interpreted in the same manner as Unix\footnote{
USA $\models$Unix is a trade mark of AT\&T.\\
\hspace*{6mm}Japan $\models$Unix is a trade mark of Maranz.}
path expression, which means ``go one level up in the
hierarchy and then go down to FF''.
\footnote{When more than one generalization exists like in the case of
PT4WD/OPEN/4WD, then the path must be specified as ``..(OPEN)/FF''.}
This reformulation of knowledge is what is called learning.

Note that some part of multiple inheritance problem is solved with
this schema.  Although PT4WD inherits both from 4WD and FF, it does
not directly do so.  Instead, PT4WD must first be
specialized to form a proper inheritance path.
}

\comment{

\subsection{Multiple Classification Hierarchy}

Treatment of multiple classification hierarchy becomes simple.
When we classify members of our society, we have many mutually
independent class hierarchies.
Marital state and sex are two of those.

\begin{quote}
human
\end{quote}
if specialized either to
\begin{quote}
human/male\\
human/female
\end{quote}
or
\begin{quote}
human/single\\
human/married.
\end{quote}
They form a heterarchy.  An agent could use either of them that
fits better to the purpose of reasoning.  Two further specializations
\begin{quote}
human/male/single\\
human/single/male
\end{quote}
are equal since specializations are commutative.

\begin{figure}[htb]
\begin{center}
\epsfile{file=/usr/users/nakashim/ps/mental-human.ps,height=2in}
\end{center}
\end{figure}
It is equally easy to add another classification like `adult' and
`child'.
}

\section{Comparison with Other Work}

\subsection{Contexts}
Guha, McCarthy and others
\comment{
 are trying to formalize contexts.
We share the very idea of contextualized representation.
The notation of lifting context (or, de-contextualization of knowledge)
can be considered as the dual operation of specialization.
The difference is that lifting rules are given as a first order rule,
while specialization is a structured operation over situations.

Another difference is that they do not give a framework to use more
than one context together (for example, through inheritance).
}
\subsection{Inheritance Systems}
\comment{

There are many other knowledge representation systems that implement
inheritance through a class hierarchy (for example,
}
\cite{RobertsGoldstein77}, \cite{Bobrow-Winograd77}, \cite{Fahlman81},
\cite{Touretzky86}, and many others
\comment{
).
However, few of them support heterarchical
hierarchies or dynamic change of the inheritance path.
}
\subsection{Multiple World Mechanism}
\comment{

Multiple world mechanism by Nakashima} \cite{Nakashima84E},
\cite{Nakashima89}, \cite{Nakashima90}
\comment{ is an attempt to introduce and
fully utilize context dependent nature of knowledge representation.
It can represent some of the features described in this paper including
dynamic change of the inheritance path.
}
\subsection{Frame System}
\comment{

The concept of Frame system by Minsky
}\cite{Frame}
\comment{
 is actually a
sub-variant of this work.

The core idea of Frame is that preexisting knowledge helps an agent
to reason efficiently.  Scripts and schema are along the same line.
Nevertheless Minsky nor others did not give the detailed mechanisms of
{\em how} frames are used in reasoning.  This paper is an attempt to
give it.

Frames are pointing
to one another and form a frame system.  A particular action of the
agent in a frame forces the agent to follow the pointer to another frame.
However, the frame system must have a statically fixed structure.  It
cannot explain the dynamic nature of \ms.
}
\subsection{Mental Space}
\comment{

Mental space}
\cite{Fauconnier85}
\comment{
 is introduced to explain linguistic
phenomena.  The concept of mental space is quite similar to that of
\ms.  Although there are several technical differences as described
later, the theory of mental space tells us how to use mental
situations in particular cases of communication.

A mental space is represented as an extendable set, which consists
of elements, relations over elements.  There are connectors between
elements of different mental spaces.  Meanings of sentences,
particularly references of expressions, are described as relations
among mental spaces and their elements.

In \ms , there is no explicit concept of connectors between elements.
Elements in situation theory are objects that are pointed to by
parameters that are filling argument roles of relations.  \Mss\ are
linked together by several relations such as inclusion, but not their
elements.  When relations among elements in different \mss\ must be
expressed, those elements are turned into \mss .
}
\comment{
\section{Summary}

The idea of \ms is introduced.
\Mss are used to model mental activities of intelligent agents.
Main concepts introduced are:
\begin{description}
\item[mental entity] corresponds to a set of (real or imaginary) entities.
\item[mental situation:] corresponds to a set of infon on a mental entity.
\item[specialization:] is an operation over mental situations.  It is
a sub-classification of the original one.
\end{description}

By making the structure richer, we can explain many aspects of
intelligence.  Specialization is the most important operation on the
structure.  Situated inference, multiple inheritance, and introduction
of new scripts are explained on the model.

\section*{Acknowledgment}

The authors' stay at CSLI, especially discussion with Stanley Peters
and with Hinrich Sch\"{u}tze, was valuable to develop the idea
expresses in this paper.   Discussions in STS working group at ICOT
were also helpful.
}

\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{SEFvR81}

\bibitem[BE90]{Barwise-Etchemendy90}
Jon Barwise and John Etchemendy.
\newblock Information, infons, and inference.
\newblock In {\em Situation Theory and its Applications, I}, pages 33--78. CSLI
  lecture notes 22, CSLI, 1990.
\newblock ISBN-0-937073-54-7.

\bibitem[BFI{\etalchar{+}}92]{Prosit}
Janik Borota, Michael Frank, Atsushi Itoh, Hideyuki Nakashima, Stanley Peters,
  Michael Reilly, and Hinrich Sch\"{u}tze.
\newblock The {PROSIT} language v1.0.
\newblock Technical report, {CSLI}, 1992.

\bibitem[BP83]{SA}
Jon Barwise and John Perry.
\newblock {\em Situations and Attitudes}.
\newblock MIT Press, 1983.

\bibitem[BW77]{Bobrow-Winograd77}
D.~G. Bobrow and Terry Winograd.
\newblock An overview of {KRL}-0, a knowledge representation language.
\newblock {\em Cognitive Science}, 1:3--46, 1977.

\bibitem[Dev91]{Devlin91}
Keith Devlin.
\newblock {\em Logic and Information I: Infons and Situations}.
\newblock Cambridge Univ. Press, 1991.

\bibitem[Fau85]{Fauconnier85}
Gilles Fauconnier.
\newblock {\em Mental Spaces}.
\newblock MIT Press, 1985.

\bibitem[GL92]{Guha92}
R.V. Guha and D.B. Lenat.
\newblock Language, representation and contexts.
\newblock {\em Journal of Information Processing}, 15(3):340--349, 1992.

\bibitem[Kat90]{Katagiri90}
Yasuhiro Katagiri.
\newblock Structure of perspectivity: A case of {J}apanese reflexive pronoun
  ``{\it zibun}''.
\newblock In {\em Proc. of AAAI-90}, pages 958--963, 1990.

\bibitem[McC85]{McCarthy93}
John McCarthy.
\newblock Notes on formalizing context.
\newblock In {\em Proc. of {IJCAI} 93}, pages 555--560, 1985.

\bibitem[MH69]{FrameProblem}
John McCarthy and Pat~J. Hayes.
\newblock Some philosophical problems from the standpoint of artificial
  intelligence.
\newblock In {\em Machine Intelligence 4 (eds. B. Meltzer and D. Michie)},
  pages 463--502. Edinburgh University Press, 1969.

\bibitem[Min75]{Frame}
Marvin Minsky.
\newblock A framework for representing knowledge.
\newblock In Patric Winston, editor, {\em The Psychology of Computer Vision}.
  McGraw Hill, 1975.

\bibitem[Nak84]{Nakashima84E}
Hideyuki Nakashima.
\newblock Knowledge representation in {Prolog/KR}.
\newblock In {\em Proc. of 1984 International Symposium on Logic Programming}.
  IEEE, 1984.

\bibitem[Nak86]{Uranus}
Hideyuki Nakashima.
\newblock Uranus reference manual.
\newblock {\em Bulletin of Electrotechnical Laboratory}, 50, 1986.

\bibitem[Nak89]{Nakashima89}
Hideyuki Nakashima.
\newblock Logical semantics of multiple world mechanism for knowledge \
  representation in logic programming.
\newblock {\em Advances in Software Science and Technology}, 1:17--28, 1989.

\bibitem[Nak90a]{Nakashima90:PRICAI}
Hideyuki Nakashima.
\newblock Commonsense reasoning with multiply embedded contexts.
\newblock In {\em Proc. of {PRICAI} '90}, pages 414--419, 1990.

\bibitem[Nak90b]{Nakashima90}
Hideyuki Nakashima.
\newblock Inference about situations (in {Japanese}).
\newblock {\em Journal of {J}apanese Society of AI}, 5(5):588--594, 1990.

\bibitem[NOK91]{NOK-91}
Hideyuki Nakashima, Ichiro Ohsawa, and Yoshiki Kinoshita.
\newblock Inference with mental situations.
\newblock {TR}-91-7, {ETL}, 1991.

\bibitem[NPS91]{NPS-91}
Hideyuki Nakashima, Stanley Peters, and Hinrich Sch\"{u}zte.
\newblock Communication and inference through situations.
\newblock In {\em Proc. of {IJCAI}-91}, pages 76--81, 1991.

\bibitem[NSHP88]{Prosit-FGCS}
Hideyuki Nakashima, Hiroyuki Suzuki, Per-Kristian Halvorsen, and Stanley
  Peters.
\newblock Towards a computational interpretation of situation theory.
\newblock In {\em Proc. of FGCS 88}, 1988.

\bibitem[NT91]{Nakashima-Tutiya-91}
Hideyuki Nakashima and Syun Tutiya.
\newblock Inference {\em in} a situation {\em about} situations.
\newblock In {\em Situation Theory and its Applications, 2}, pages 215--227.
  CSLI, 1991.

\bibitem[RG77]{RobertsGoldstein77}
R.~B. Roberts and I.~P. Goldstein.
\newblock the {FRL} manual.
\newblock {AI}-memo 409, {MIT}, 1977.

\bibitem[Sch75]{Schank75}
Roger~C. Schank.
\newblock {\em Conceptual Information Processing}.
\newblock North-Holland, 1975.

\bibitem[SEFvR81]{Fahlman81}
David S~.Touretzky Scott E.~Fahlman and Walter van Roggen.
\newblock Cancellation in a parallel semantic network.
\newblock In {\em Proc. of the 7th {IJCAI}}, pages 257--263, 1981.

\bibitem[Tou86]{Touretzky86}
David~S. Touretzky.
\newblock {\em The Mathematics of Inheritance Systems}.
\newblock Morgan Kaufmann Publishers, 1986.

\end{thebibliography}


\end{document}
