Date sent: Fri, 10 Jan 1997 12:10:58 +1300
From: Stephen Cranefield <stephen@eros.otago.ac.nz>
To: "STEPHEN MACDONELL - INFO" <stevemac@commerce.otago.ac.nz>
Subject: Discussion Papers
Steve,
Here's one for you. Its citation is:
S. J. S. Cranefield and M. K. Purvis,
"An agent-based architecture for software tool coordination",
Proceedings of the Workshop on Theoretical and Practical Foundations
of Intelligent Agents, Pacific Rim International Conference on
Artificial Intelligence, 1996
(to appear in Lecture Notes in Artificial Intelligence, Springer, 1997).
I'll append the LaTeX source and bibtex file below.
- Stephen
------------------------------------------------------------------------
\documentstyle[epsfig,times,html]{llncs}
\newcommand{\ob}{\allowbreak} % for bibtex and Web refs
%"ob" for optional break
\begin{document}
\newlength{\fred}
\setlength{\fred}{\textwidth}
\addtolength{\fred}{-2\fboxsep} % -2 x \fboxsep
\addtolength{\fred}{-2\fboxrule} % -2 x \fboxrule
\addtolength{\fred}{-0.5mm}
%\addtolength{\fred}{-1em}
%\addtolength{\fred}{-12pt} % - \tabcolsep
\title{An Agent-based Architecture for\\Software Tool Coordination}
\author{Stephen Cranefield and Martin Purvis}
\institute{Computer and Information Science, \\
University of Otago, \\
PO~Box~56, Dunedin, New Zealand\\
\{scranefield,mpurvis\}@commerce.otago.ac.nz}
\maketitle
\begin{abstract}
This paper presents a practical multi-agent architecture for assisting
users to coordinate the use of both special and general purpose
software tools for performing tasks in a given problem domain. The
architecture is open and extensible being based on the techniques of
agent-based software interoperability (ABSI), where each tool is
encapsulated by a KQML-speaking agent. The work reported here adds
additional facilities for the user to describe the problem domain, the
tasks that are commonly performed in that domain and the ways in which
various software tools are commonly used by the user. Together, these
features provide the computer with a degree of autonomy in the user's
problem domain in order to help the user achieve tasks through the
coordinated use of disparate software tools.
This research focuses on the representational and planning
capabilities required to extend the existing benefits of the ABSI
architecture to include domain-level problem-solving skills. In
particular, the paper proposes a number of standard ontologies that
are required for this type of problem, and discusses a number of
issues related to planning the coordinated use of agent-encapsulated
tools.
\end{abstract}
\bibliographystyle{unsrt}
\section{Introduction}
Every computer user must at some time have wished their machine was
more ``intelligent'' and could reason about the task being performed
by the user and the steps that must be performed to achieve that task.
In particular, for many computer users, their day-to-day work involves
the use of a variety of different software tools, developed
independently and using different data representations and file
formats. Coordinating the use of these tools, remembering the correct
sequence of commands to apply each tool to the current problem and
incorporating new and modified tools into their work patterns adds
additional demands on the user's time and memory. This paper
discusses an agent-based architecture designed to remove this drudgery
from the user. The paper also includes a discussion of related
planning and ontological issues.
The architecture combines the techniques of agent-based software
interoperability (ABSI) \cite{facilitator_manual} with a planning
agent and facilities for the user to describe the problem domain, the
tasks that are commonly performed in that domain and the ways in which
various software tools are commonly used by the user. Together, these
features provide the computer with a degree of autonomy in the user's
problem domain. The user can request the initiation of domain-level
tasks and the system will plan and execute the appropriate sequence of
tool invocations. If a task is not completed in one session, the
system will remember the current state of the task and how any
intermediate data files relate to the overall task. By simply
requesting the continuation of the task, the user can cause the
planner to begin from where it left off previously. Providing these
abilities has implications for the nature of the planning agent and
also suggests the necessity of developing ontologies for certain
standard information storage formats.
This work places no requirements on the internal structure of agents
in the system (which, apart from specialised planning and console
agents, are simply encapsulations of existing software tools).
Instead it focuses on the representational and planning capabilities
required to extend the existing benefits of the ABSI architecture to
include domain-level problem-solving skills.
\section{Agent-based Software Integration}
In today's heterogeneous software environments, with tools written at
different times for various specific purposes, there is an increasing
demand for interoperability among these tools \cite{Genesereth}.
While distributed object models such as CORBA \cite{CORBA} are
currently gaining widespread industrial acceptance as standards for
sharing data and exchanging services amongst distributed applications,
research is underway towards finding higher-level, declarative models
of communication and cooperation. Progress in this area has been made
in the field of ``Agent-Based Software Interoperability'' (ABSI)
\cite{facilitator_manual}, also known as ``Agent-Based Software
Engineering'' \cite{Genesereth}. This involves the encapsulation of
software tools and information servers as ``agents'' that can receive
and reply to requests for services and information using a declarative
knowledge representation language, {\it e.g.}\ KIF (Knowledge
Interchange Format), a communication language, KQML (Knowledge Query
and Manipulation Language) and a library of formal ontologies defining
the vocabulary of various domains.
The agents are connected in a ``federation architecture'' which
includes special `facilitator' agents such as the one developed by the
Stanford University Computer Science Department's Logic Group
\cite{facilitator_manual}. Facilitator agents receive messages and
forward them to the most appropriate agent depending on the content of
the message (this is known as ``content-based routing''). Agents are
responsible for registering the type of message they can handle with
the facilitator. Tools can be spread across different platforms to
form an open and extensible agent system: a new tool can be added to
the system by providing it with a `transducer' program (that
translates between KQML and the tool's own communications protocol) or
a `wrapper' layer of code (a KQML interface written in the tool's own
command or scripting language) and registering its capabilities with a
facilitator agent.
\section{Desktop Utility ABSI}
ABSI projects discussed in the literature have to date largely focused
on domains where the software tools to be integrated are complex
and/or expensive to develop, {\it e.g.}\ concurrent engineering of a
robotic system \cite{PACT}, civil engineering \cite{civil_eng},
electronic commerce \cite{commerce_net}, and distributed civic
information systems \cite{knowledgeable_community}. In contrast with
these large-scale integration efforts, the problem addressed in this
paper is how to support interoperation among an evolving workbench or
toolkit of general purpose utilities and special-purpose tools.
Working with such a toolkit can typically be characterised as follows:
\begin{itemize}
\item
A number of tasks are performed in sequence, possibly over an extended
period of time and with significant time intervals between some of the
tasks.
\item
Information recording the current state of the problem domain must be
kept and updated as each task is performed.
\item
A variety of data formats and software tools are used to perform the
different tasks. Relevant new tools may appear and existing tools
may be replaced or upgraded over time.
\item
Some general-purpose tools may be used to support work in a number of
different problem domains.
\end{itemize}
Typically, the problem domain is relatively simple and can be
adequately defined using standard data modelling representations ({\it
e.g.}\ the relational data model). Also, as some of the tools used
may be general purpose utilities such as relational database
management systems, programmable text editors and spreadsheets, for
maximum reusability these should be encapsulated by agents that
communicate in terms of the data formats the tools operate on. An
architecture to support this type of tool interoperation must
therefore include ontologies describing low-level data formats and how
these can be related to higher-level representations of the domain.
As each of the tools used may only perform a small part of the overall
task, the overhead of coordinating the use of different tools into a
coherent sequence represents a significant overhead. Thus planning
support is needed to help the user select the appropriate sequence of
tools to be used.
We will refer to this type of ABSI problem as ``Desktop utility ABSI''
to distinguish it from the large scale interoperability projects
referenced above. One application area that falls into this area is
administrative work involving the management of information stored in
common data formats such as text files, spread sheets and relational
databases.
\section{The Architecture}
\begin{figure}[htbp]
\centerline{\epsfig{file=small-arch-pic.eps,width=15pc,height=7.8pc}}
%\centerline{\epsfig{file=arch.eps,width=65mm,height=33.8mm}}
%\centerline{\epsfig{file=arch.ps,width=15pc,bbllx=164pt,bblly=524pt,bburx=415pt,bbury=723pt,clip=}}
\caption{The desktop utility agent system architecture}
\label{arch_fig}
\end{figure}
Figure~\ref{arch_fig} shows our architecture for Desktop
Utility ABSI \cite{Baltimore}. This is based on the federation
architecture with the addition of two specialised agents: a planning
agent and a console agent.
\subsection{The Planning Agent}
For interoperating systems involving a few complex agents (large scale
ABSI) the patterns of interaction between the agents are likely to be
known in advance and limited in scope. In contrast, for desktop
utility agent systems, there may be many simple agents each
encapsulating a number of operations performed by various
general-purpose tools. To achieve a user's high-level goal in the
problem domain, it may be necessary for a number of different agents
to perform actions in an appropriate sequence.
It would be tedious if the user were required to specify this sequence
of agent invocations. However, deducing an appropriate sequence of
agent actions to achieve a goal is an AI planning problem and
facilitators whose is knowledge is expressed using KIF
({\it e.g.}\ the Stanford facilitator \cite{facilitator_manual}) do not support
planning well as they have no notion of state and time. Rather than
attempting to extend the function of a facilitator to perform
planning, our architecture contains a specialised planning agent.
Each agent is required to register with the planning agent by sending
specifications of the actions it can perform (consisting of the
actions' preconditions and effects).
\begin{figure}[htbp]
\fbox{
\parbox{\fred}{
\rule{\fred}{0pt}
\begin{tabbing}
{\bf Action: } \= \kill
{\bf Agent: } \> {\tt dbase-agent} \\
{\bf Action: } \> {\tt (add-marks ?f ?ass ?db)} \\
{\bf Description: } \\
{\tt\ }Add marks for assignment {\tt ?ass} in file {\tt ?f} to the
database {\tt ?db}.\\
\\
{\bf Preconditions: } \\
{\tt\ (database-matches-datamodel ?db info202-dm) }\\
{\tt\ (file-format ?f (delim \#\char92, (listof string string number))) }\\
{\tt\ (file-represents-relation ?f }\\
{\tt\ \ \ \ (select ASSESS (= cmptid ?ass))}\\
{\tt\ \ \ \ info202-dm }\\
{\tt\ \ \ \ (stuid cmptid mark)}\\
{\tt\ \ \ \ ?state)}\\
\\
{\bf Postconditions: } \\
{\tt\ (database-includes-relation ?db }\\
{\tt\ \ \ \ (select ASSESS (= cmptid ?ass)) }\\
{\tt\ \ \ \ info202-dm}\\
{\tt\ \ \ \ (do (add-marks ?f ?ass ?db) ?state))}
\end{tabbing}
}}
\caption{Specification for a database agent action}
\label{action_spec}
\end{figure}
Figure~\ref{action_spec} shows a specification\footnote{In this case
no preconditions are retracted by the action, although in general this
is possible.}\ for an action performed by a database agent as part of
a university course administration process (the predicates appearing
in the specification are explained in Sect.~\ref{ontologies}). This
describes an ability of the database agent to read in a specially
formatted marks file (as produced by a utility used to systematically
mark student's electronically submitted programming assignments) and
to update the student marks database. Note that an explicit state
variable appears in some of the pre- and post-conditions. The reason
for this is explained in Sect.~\ref{state_variables}.
This agent action is designed for a specialised problem
domain: its specification contains terms from the problem domain
ontology. Agents may also encapsulate the general-purpose data
manipulations of desktop utilities. For example, an agent might
encapsulate the ability of the Excel spreadsheet to take as input a
text file containing a column of numbers and produce a printed
histogram of these numbers. In general, one agent wrapper must be
provided for each application, and this will register with the
planning agent all the functionalities of the underlying application
that have been encoded in the agent. It is not envisaged that the
full functionality of general packages such as spreadsheet or word
processing applications could be expressed declaratively in a single
specification. However, it should be possible to provide
specifications for various simple computations that the application
can perform.
\subsection{The Console Agent}
In the desktop utility agent architecture the user interacts with a
console agent that accepts requests expressed using the ontology of
the user's various problem domains. In particular, the user can issue
a request \verb|(perform ?task)| where {\it task} is the (possibly
parameterised) name of a problem-domain level task that the user
wishes to be performed. This request is packaged up as a KQML message
and sent to the facilitator, which will forward it to the planning
agent. Once an appropriate sequence of agent actions has been planned
it is sent back to the console agent which is then responsible for
invoking agents to perform these actions for the user. The console
agent also keeps track of the current state of the system
({\it i.e.}\ what information is currently recorded and what it represents).
\subsection{Using the Architecture}
The initial step in using the architecture involves defining a problem
domain (which need only be done once for each domain). The user must
define a data model defining the entities of interest in
the domain. This is done by asserting facts (using the
console agent) defining the relations in the domain. It is also
necessary to assert facts describing the initial state of the system,
{\it i.e.}\ what information is recorded in data files or databases
and how it relates to the domain-level data model. In conjunction
with an existing ontology defining the terminology of relational data
models, this defines an ontology for the user's domain.
The various domain-related tasks to be performed are specified by
declaring their names and parameters and their precondition and goal
states (in terms of the information recorded before and after the task
is performed). The user may also provide a specification of possible
expansions of each task into an ordered set of subtasks (see
Sect.~\ref{planning_issues}). In addition it is assumed that the user
has previously developed or acquired agent wrappers for the various
general or special-purpose tools used to support work in this domain.
These wrappers must be equipped with planning operator style
specifications of (a subset of) the possible actions these tools can
perform. These specifications describe the actions' preconditions and
effects in terms of the domain ontology or standard data storage
ontologies as described in Sect.~\ref{ontologies}.
When the user requests a task to be performed via the console agent,
the planner generates a sequence of agent actions that can satisfy the
task specification. These actions are then invoked by the console
agent. Note that while these actions are considered to be atomic by
the planner they may involve the invocation of an agent-encapsulated
tool which may possibly require a series of user interactions. During
execution the console agent keeps track of the current state of the
system (in terms of the facts asserted and retracted by the actions'
planning operators).
\section{Required Ontologies}
\label{ontologies}
%\subsection{States and actions}
%\label{state_assertions}
%Very simple ontology -- nothing as complicated as what is being
%developed by the ARPA/Rome Laboratory Planning Initiative (ARPI)
%Planning Ontology Construction Group (POCG) \cite{POCG}.
\subsection{File Formats}
In large scale ABSI projects, where there are a fixed number of
interoperating tools that are specialised for a particular domain, it
makes good sense to encapsulate each tool within an agent that speaks
a high-level domain-related ontology. In contrast, in desktop utility
ABSI there may be agents controlling various general-purpose tools
that act at a relatively low data representation level ({\it e.g.}\ by
performing manipulations on files). As these tools could be used in
various problem domains it would limit their reusability in an ABSI
framework if their agent wrappers could only declare their abilities
in terms of a single high-level domain. Although for a general
purpose tool it would be possible to generate separate agent wrappers
corresponding to different domain ontologies, this would clearly be a
duplication of effort. Instead, a generic tool should be described at
the level at which it operates. Thus a utility that can manipulate
text files should be described in terms of an ontology of text files.
There are a number of different levels at which the contents of text
files are typically viewed, {\it e.g.}\ as a sequence of characters, a
sequence of lines or a sequence of records.
Figure~\ref{file_ontologies_fig} shows a hierarchy of ontologies being
constructed for representing the contents of a text file in a
declarative fashion, along with the type of facts used to describe the
file contents at each level.
\addtolength{\fred}{0.5mm}
\addtolength{\fred}{-1em}
\addtolength{\fred}{-2\tabcolsep} % - \tabcolsep
\begin{figure}[htb]
\fbox{
\begin{tabular}{ll}
{\bf Conceptual level} & {\bf Fact schema} \\\hline
& \\
{\bf Relational} & {\tt (tuple ?pairs ?rel ?dm)}\\
& {\em pairs\/} is the set of attribute-value
pairs in relation {\em rel\/} of data\\
& model {\em dm}\\
\multicolumn{1}{@{\hspace{1.5em}}l}{$\Uparrow$} & \\
\multicolumn{2}{@{\hspace{0.5em}}l}{\hbox{
\begin{minipage}[t]{\fred}
An ontology relating lists of records to sets of tuples, using
facts asserting which relation and data model a file corresponds to
and which fields correspond to which attributes.
\end{minipage}}}
\\
\multicolumn{1}{@{\hspace{1.5em}}l}{$\Downarrow$} & \\
& \\
{\bf Records and fields}& {\tt (field ?i ?n ?f ?v)} \\
& Field {\em i\/} of record {\em n\/} in file
{\em f\/} has value {\em v\/}\\
\multicolumn{1}{@{\hspace{1.5em}}l}{$\Uparrow$} & \\
\multicolumn{2}{@{\hspace{0.5em}}l}{\hbox{
\begin{minipage}[t]{\fred}
An ontology for string parsing, based on facts describing the
record format.
\end{minipage}}}
\\
\multicolumn{1}{@{\hspace{1.5em}}l}{$\Downarrow$} & \\
& \\
{\bf Seq.\ of lines} & {\tt (line ?n ?f ?s)} \\
& Line {\em n\/} of file {\em f\/} is the
string {\em s}\\
\multicolumn{1}{@{\hspace{1.5em}}l}{$\Uparrow$} & \\
\multicolumn{2}{@{\hspace{0.5em}}l}{\hbox{
\begin{minipage}[t]{\fred}
An ontology describing newline terminated strings.
\end{minipage}}}
\\
\multicolumn{1}{@{\hspace{1.5em}}l}{$\Downarrow$} & \\
& \\
{\bf Seq.\ of chars} & {\tt (char ?n ?f ?c)}\\
& Character {\em n\/} in file {\em f\/} is {\em c\/}\\
\end{tabular}
}
\caption{A hierarchy of text file ontologies and how they relate facts
at different levels of abstraction }
\label{file_ontologies_fig}
\end{figure}
\addtolength{\fred}{1em}
\addtolength{\fred}{2\tabcolsep} % - \tabcolsep
To relate the different viewpoints the ontologies also need to
describe how to translate information between the different
representational levels. For instance, the information that the file
named ``students.dat'' is a text file with three string-valued fields
delimited by commas might be represented by the following fact:
\begin{verbatim}
(file-format "students.dat"
(delim #\, (list-of string string string)))
\end{verbatim}
This predicate would be defined in an ontology by a formula stating
how facts about records and fields can be inferred from facts about
lines in files. For instance, the fact
\begin{verbatim}
(line 10 "students.dat" "9601234,Joe Smith,A0100001")
\end{verbatim}
would allow the following three facts to be deduced:
\begin{verbatim}
(field 1 10 "students.dat" "9601234")
(field 2 10 "students.dat" "Joe Smith")
(field 3 10 "students.dat" "A0100001")
\end{verbatim}
Thus the \verb|file-format| fact above provides the information needed
to translate between the line-based view of a file and the
record-based view. Similarly, facts of the following form could be
used to link the record-based and the relational views of a file:
\begin{verbatim}
(file-represents-relation
?file ?rel ?data-model ?att-list ?state)
\end{verbatim}
As tuples in relations are {\em sets\/} of attribute-value pairs,
whereas the fields in a record are ordered, the argument {\tt
?att-list} is required to specify the order in which the attributes
appear in the file\,---\,this is a list which is some permutation of
the attributes of the relation {\tt ?rel}.
\label{state_variables}
The explicit mention of a state in this fact is necessary because in
the type of tool use supported by this architecture, domain-level
tasks may not be completed in a single session and there may be
information stored in temporary files that are more up-to-date than
other information sources. For example, in the university course
administration domain, the user may run a marking utility to mark
student assignments and then go home for the day before updating the
course database with the marks recorded in the file that was output by
the marking utility. At this point the database and the text file
contain information relating to different stages of the high level
``mark assignment'' task: the database does not reflect the fact that
the latest assignment has been marked, whereas the text file does.
The final argument in the fact above specifies which (possibly
earlier) state in the plan the information in the file represents. It
will be an expression of the form $({\tt do}$ $a$ $s)$ representing
the state resulting from performing action $a$ in a state $s$ (which
may itself be represented by an expression of this form).
It is important to note that the ontologies described above are only
{\em specifications\/} of standard terminologies that may be used by
agents. While some agents may perform inference using the formulae in
an ontology, all that is {\em required\/} of an agent is that its use
of the terminology in an ontology be consistent with the ontology's
logical theory. Defining ontologies describing different conceptual
views of files, and how to translate between these levels of
abstraction, does not imply that all file processing will be performed
using an inference system. In practice, these
ontologies\,---\,particularly at the lower levels\,---\,might be
implemented by `procedural attachment', so that telling a file manager
agent a \verb|file-format| fact such as the one above would result in
that agent reading and parsing the file and sending a stream of {\tt
field} facts to all interested agents.
\subsection{Data Models and Databases}
\label{rel_data_ont}
In any ABSI project there needs to be at least one high-level ontology
describing the problem domain (in some cases there may be several due
to different agents having different views of the domain). In the
example domain described above, the problem area involves student
details, assignments and marks. An ontology for this domain can be
created in various ways, {\it e.g.}\ an object-oriented model could be
based on the Stanford ontology library's frame ontology
\cite{KSL-Ontology-Server}. However, like all applications involving
a relational database, a domain model already exists: the relational
data model developed for the database application. This could be
easily described as an ontology if a standard ontology of relational
data models were available. Such an ontology would define the
concepts of base relations and their attributes and attribute domains,
as well as a way of naming relations derived from the base relations.
The discussion in this paper assumes the existence of such an ontology
(which is currently under development) with relations described using
the relational algebra, {\it i.e.}\ relations can be built from the
base relations using operations such as select, join and project.
Users will define the relational data models for their problem domains
by asserting facts naming the model and describing its base relations.
The relational data model ontology will also allow the user to declare
semantic information such as candidate keys, foreign keys, foreign key
rules and default attribute values, thus supporting agents that can
update derived relations (``view updates'').
For the course administration example, using a domain ontology based on
a relational data model, a tuple in a base relation STUDENT (recording
student ID numbers, names and Novell NetWare IDs) could be represented
by the following KIF fact:
\begin{verbatim}
(tuple (setof (stuid "9601234")
(stuname "Joe Smith")
(nw_id "A0100001"))
student info202-dm)
\end{verbatim}
where {\tt student} names the relation and {\tt info202-dm} names the
particular relational data model (there could be more than one problem
domain, and hence more than one data model in use at a time).
The relational data model ontology discussed above describes a
conceptual model of a domain, whereas the text file ontologies
discussed in the previous section describe the physical
representations of data. Just as the text file ontologies refer to
files, we need an ontology in which there is a concept of a database
(as opposed to the conceptual model implemented by it). A database is
a separate concept from a relational data model: a database could
represent information from several relational models; conversely the
information pertaining to a single data model could be split (or
duplicated) across several databases. Therefore it is necessary
to have an ontology for actual databases, defining (amongst others)
the predicate:
\begin{verbatim}
(database-matches-datamodel ?database ?data-model)
\end{verbatim}
This declares that the tables in the database match the relational
data model specified (including any integrity checks implied by the
foreign key information in the data model). This predicate can be
implemented by procedural attachment to the database query language.
\section{Planning Issues}
\label{planning_issues}
\subsection{Hierarchical Task Network Planning}
The nature of desktop agent interoperation imposes a number of demands
on the planner. The aim of this architecture is to remove as much
manual coordination of tool use as possible from the user. For this
multi-agent system to be as autonomous as possible, facilities need to
be provided to assist the user in providing as much information about
the problem domain as possible. In particular, the user may have
common patterns of tool use that could improve the performance of the
planner if it could make use of them. Such a facility is provided by
hierarchical task-network (HTN) planners such as UMCP \cite{UMCP}.
With this type of planner, the user can provide the planner with
declarations describing possible decompositions of tasks into ordered
networks of subtasks. The basic planning step involves expanding a
task into one of its possible networks of subtasks and then attempting
to resolve any unwanted interactions between steps in the plan that
were introduced by this expansion. A task expansion can also include
subtasks of the form ${\mit achieve}(g)$ where $g$ is a goal. By
providing methods for expanding `achieve' tasks, the user can also
provide the planner with (domain-specific) goal-directed planning
capabilities.
\subsection{Ontologies and Abstraction}
An important characteristic of desktop utility ABSI is the mix of
domain-specific and general-purpose tools. To use the information
output by general-purpose tools as input to domain-specific tools, it
is necessary to store facts stating how these low-level
representations relate to the problem domain's data model. For
example, Fig.~\ref{action_spec} shows the specification for an action
that can be performed by a database-encapsulating agent in the
university course administration domain: to update a student record
database from a specially formatted text file. The action
specification contains some pre- and post-conditions that are
inherently related to the problem domain (university course
administration). Other conditions are expressed using the lower level
ontologies of file formats and databases. The planner may need to
switch back and forth between these different levels of description as
the following example shows.
Before the {\tt add-marks} action can be performed a marking utility
must be run to allow the tutor to systematically mark each student's
electronically submitted programming assignment and create a file
containing the marks. When encapsulated by an agent, the
postconditions for this ``mark assignments'' action are as follows:
\begin{verbatim}
(file ?f
(delimited #\, (listof string string string number)))
(file-represents-relation ?f
(join STUDENT (project (select ASSESS (= cmptid ?ass))
(stuid mark)))
info202-dm
(stuid stuname nw_id mark)
(do (mark ?ass ?f) ?state))
\end{verbatim}
The format of the output file, and the relation it represents differ
from that required by the {\tt add-marks} action. The planner must
find a way to achieve the preconditions of the {\tt add-marks} action
starting from the postconditions shown above. This is a text file
manipulation process that takes the file produced as a result of
running the marking program and converts it into a format suitable for
adding information to the ASSESS table in the database. This can be
performed by two operations at the text file level: deleting two
fields of the file and then adding a new field containing the
assignment name in each row. Figure~\ref{step3_fig} shows how these
two file-level operations can be used to achieve the preconditions of
the {\tt add-marks} action starting with the postconditions of the
{\tt mark} action (the state expressions are not given in
full).
\addtolength{\fred}{-0.5mm}
\begin{figure}[htbp]
\fbox{
\parbox{\fred}{
\rule{\fred}{0pt}
\begin{tabbing}
{\tt\ (file ?f }\\
{\tt\ \ \ \ (delimited \#\char92, (list-of string string string number))) }\\
{\tt\ (file-represents-relation ?f }\\
{\tt\ \ \ \ (join STUDENT (project (select ASSESS (= cmptid ?ass)) }\\
{\tt\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (stuid mark))) }\\
{\tt\ \ \ \ info202-dm }\\
{\tt\ \ \ \ (stuid stuname nw\char95 id mark) }\\
{\tt\ \ \ \ }{\it state1}{\tt )}
\end{tabbing}
}}
\vspace{1.5\baselineskip}
{\Huge\quad\quad $\Downarrow$\quad} Delete columns 2 and 3 from file {\tt ?f}
\vspace{1.5\baselineskip}
\fbox{
\parbox{\fred}{
\rule{\fred}{0pt}
\begin{tabbing}
{\tt\ (file ?f (delimited \#\char92, (list-of string number))) }\\
{\tt\ (file-represents-relation ?f }\\
{\tt\ \ \ \ (project (select ASSESS (= cmptid ?ass)) }\\
{\tt\ \ \ \ \ \ \ \ \ \ \ \ \ (stuid mark)) }\\
{\tt\ \ \ \ info202-dm }\\
{\tt\ \ \ \ (stuid mark) }\\
{\tt\ \ \ \ }{\it state2}{\tt )}
\end{tabbing}
}}
\vspace{1.5\baselineskip}
{\Huge\quad\quad$\Downarrow$\quad} Insert new column 2 with value of {\tt ?ass} in
every row
\vspace{1.5\baselineskip}
\fbox{
\parbox{\fred}{
\rule{\fred}{0pt}
\begin{tabbing}
{\tt\ (file ?f (delimited \#\char92, (list-of string string number))) }\\
{\tt\ (file-represents-relation ?f }\\
{\tt\ \ \ \ (select ASSESS (= cmptid ?ass))}\\
{\tt\ \ \ \ info202-dm }\\
{\tt\ \ \ \ (stuid cmptid mark)}\\
{\tt\ \ \ \ }{\it state3}{\tt )}
\end{tabbing}
}}
\caption{The file manipulation process}
\label{step3_fig}
\end{figure}
To infer that this sequence of file manipulations can be used as a
link in a plan involving higher level concepts requires the planner to
drop down a level in the hierarchy of ontologies, generate a subplan
at that level and then produce a specification of that subplan at the
higher conceptual level. This translation process could be defined as
a HTN planner `task'; however, it would also be useful if the planner
could solve this problem without such presupplied help from the user.
Existing hierarchical planning techniques may be applicable to this
problem. This is an issue requiring further investigation.
\subsection{Incorporating Run-Time Information}
\label{planning_and_execution}
In some domains, the planning agent may not be able to expand a task
in a plan network until it has information that may only be available
at run time. For example, in the university course administration
domain, the task of marking every student's submitted work for a given
assignment can be broken into two subtasks: first to invoke the
marking utility for some subset of the students and then (sometime
later) to mark the assignments for the rest of the students (a
compound task to be expanded further). The subset of students whose
assigments are marked during the first subtask can not be known at run
time\,---\,it depends on how much time the tutor has. The expansion
of the second subtask will also depend on this information. To
address situations such as this, the planner's action description
language must have a formalism for representing information that will
become available during the execution of a plan. The planner must
also be capable of interleaving planning and execution, and
instantiating the run-time information.
These capabilities have been provided in previous planning research by
allowing special ``run-time variables'' to appear in action
preconditions and effects \cite{ambros-ingerson} and this work has
been extended to address other issues related to planning in the
absence of complete information about the world
\cite{golden,knoblock95}. The formalism of ``provisions''
\cite{williamson} was introduced to generalise the role that parameter
instantiation and run-time variables play in the flow of information
between actions in a plan. This is also the only work in this area to
address HTN planning. The notion of a provision is powerful but seems
unintuitive as a primitive concept in a planning formalism. There is
much scope for further research in this area to clarify how
information flow in plans can best be modelled.
\subsection{Planning to Communicate}
Planners traditionally model actions by the changes they make to a
world state. In the ABSI framework, agents communicate by sending
messages in KQML to each other and these communications do not
directly change the state of the world. However, if the world model
includes facts describing the planner's knowledge of the knowledge of
other agents appearing in the plan, planning operators for different
types of KQML messages can be specified in terms of the changes they
make to these facts. This approach would require the planner to
include at least some of the inference capabilities of epistemic logic
and may introduce needless complexity. An alternative approach is for
the planner to specify agent actions and generate plans under the
hypothesis that a global shared knowledge base is available to all
agents. The resulting plan could then be transformed into one
including communication acts, in the same way that a program for a
shared-memory parallel process can be translated into a program for a
message-passing architecture. These two approaches for planning to
communicate will be investigated and compared in future work.
\section{Related Work}
As discussed earlier, this work builds upon the ABSI federation
architecture \cite{Genesereth,KSL-Ontology-Server}.
SRI's Open Agent Architecture \cite{Cohen} allows agent-encapsulated
desktop tools to interoperate in a distributed heterogeneous
environment. Agents communicate via a distributed blackboard. User
interface considerations are a focus of this work, while ontological
issues and planning for high-level tasks are not addressed.
The SIMS architecture \cite{SIMS} is specialised for agents
encapsulating distributed information sources. The agents are
relatively complex, containing planning and learning components, and
use domain and information source models developed using specialised
knowledge representation tools.
Softbots \cite{Etzioni} are complex stand-alone agents that can invoke
various tools on behalf of the user. However, there is no facility
for users to extend or alter a softbot's functionality.
%\section{Further Work}
%Implementation, data model, database and spreadsheet (refs) ontologies.
\section{Conclusion}
This paper has presented an agent-based architecture for a type of
software interoperability problem (desktop utility ABSI) different
from the large scale ABSI projects discussed in the literature. In
particular the use of a planning agent to automate the selection of
actions to jointly achieve domain tasks has been discussed. It has
been suggested that hierarchical task-network planning techniques be
used so the user can provide guidance on how different tools can be
combined for particular tasks. Combining the use of special-purpose
tools with general-purpose utilities means that at times during the
performance of a task, information corresponding to different stages
of the task may be stored in different formats and the implications of
this on the planner has been discussed.
Standard ontologies for data formats are required to facilitate the
use of general-purpose tools with this architecture and the design of
database and text file format ontologies have been outlined.
A prototype implementation \cite{Our-Web-page} of the architecture has
been developed using the Java Agent Template \cite{JAT} to build the
console agent, the facilitator (with help from Amzi! Prolog and its
Java interface \cite{Amzi}) and KQML-speaking agent ``transducers''
for tools running under Windows NT and Unix. The Common Lisp HTN
planner UMCP \cite{UMCP} is currently being used with a KQML interface
provided by the KAPI software \cite{KAPI}. Currently work is
continuing on the implementation of this architecture and example
software agents to encapsulate the tools of the course administration
domain.
Further work involves elaborating the planning requirements for this
architecture (as outlined in Sect.~\ref{planning_issues}) and the
ontologies discussed above. Also, ontologies for other common tools
such as spreadsheets will be required (\cite{Spreadsheet} may provide
a useful starting point). A user interface will be developed to help
non-sophisticated users compose their problem domain description, the
specifications of the tasks to be performed in that domain and create
agent wrappers for their existing software tools.
At present our research assumes that all agents share the same
ontologies for the domain description and the data formats they
operate on. This work should eventually address the problem of
interoperation between agents with different ontologies for the same
domain \cite{SIMS,wiederhold}.
\section*{Acknowledgements}
This research is supported by an Otago Research Grant. Thanks to
Aurora Diaz for her ongoing work in implementing this architecture.
\bibliography{workshop}
\end{document}
------------------------------------------------------------------------
@TechReport{Abelson,
author = "H. Abelson and M. Eisenberg and M. Halfant and J.
Katzenelson and E. Sacks and G. J. Sussman and J.
Wisdom and K. Yip",
title = "Intelligence in Scientific Computing",
institution = "Artificial Intelligence Laboratory, Massachusetts
Institute of Technology",
year = "1988",
number = "AI Memo 1094"
}
@Misc{Amzi,
key = "Amzi! inc.",
title = "Amzi! {Inc.}\ {WWW} home page",
howpublished = "\htmladdnormallink{http://\ob www.\ob amzi.\ob com/}{http://www.amzi.com/}"
}
@InProceedings{Baltimore,
author = {S. J. S. Cranefield and M. K. Purvis},
title = {Agent-Based Integration of General-Purpose Tools},
booktitle = {Proceedings of the Workshop on Intelligent
Information Agents, Fourth International Conference on Information and
Knowledge Management},
year = 1995,
month = {December},
note = {\htmladdnormallink{http://\ob www.\ob cs.\ob
umbc.\ob edu/\ob \char126 cikm/\ob iia/\ob proc.html}{http://www.cs.umbc.edu/~cikm/iia/proc.html}}
}
@Misc{CORBA,
key = {CORBA},
author = {{Advanced} {Computing} {Laboratory}, {Los} {Alamos} {National} {Laboratory}},
title = {Information Resources for {CORBA} and the {OMG}},
howpublished = {http://\ob www.\ob acl.\ob lanl.\ob gov/\ob CORBA/}
}
@InProceedings{Cohen,
author = {P. R. Cohen and A. Cheyer and M. Wang and S. C. Baeg},
title = {An Open Agent Architecture},
booktitle = {Proceedings of the Spring Symposium on Software
Agents, {\rm Technical Report SS-94-03}},
year = 1994,
publisher = {AAAI Press},
note = {\htmladdnormallink{ftp://\ob ftp.\ob ai.\ob sri.\ob
com/\ob pub/\ob papers/\ob cheyer-aaai94.ps.gz}{ftp://ftp.ai.sri.com/pub/papers/cheyer-aaai94.ps.gz}}
}
@Book{Date,
author = "C. J. Date",
title = "An Introduction to Database Systems",
publisher = "Addison Wesley",
year = "1995",
edition = "6th"
}
@Misc{Etzioni,
author = {O. Etzioni and N. Lesh and R. Segal},
title = {Building Softbots for {UNIX}},
howpublished = {Unpublished technical report},
year = 1992,
note = {\htmladdnormallink{ftp://\ob june.\ob cs.\ob
washington.\ob edu/\ob pub/\ob etzioni/\ob
softbots/\ob softbots-tr.ps.Z}{ftp://june.cs.washington.edu/pub/etzioni/softbots/softbots-tr.ps.Z}}
}
@InProceedings{Finin,
author = "T. Finin and R. Frizson and D. McKay and R. McEntire",
title = "{KQML} as an Agent Communication Language",
booktitle = "Proceedings of the Third International Conference on
Information and Knowledge Management (CIKM'94)",
year = 1994,
publisher = "ACM Press",
month = nov
}
@article{Genesereth,
title = "Software Agents",
author = "M. R. Genesereth and S. P. Ketchpel",
journal = "Communications of the ACM",
month = jul,
volume = 37,
number = 7,
year = 1994,
pages = "48--53"}
@TechReport{Gruber,
author = "T. Gruber",
title = "Ontolingua: a Mechanism to Support Portable Ontologies",
institution = "Knowledge Systems Laboratory, Stanford University",
year = "1991",
number = "KSL-91-66"
}
@Misc{JAT,
author = {{Agent}-Based Engineering Research Group, Stanford University},
title = {Java {Agent} {Template} {Web} page},
howpublished = {http://\ob cdr.\ob stanford.\ob edu/\ob ABE/\ob JavaAgent.html}
}
@Misc{KAPI,
title = {Lockheed/{EIT}/{Stanford} {KQML} {API} {Web} page},
howpublished = {ftp://\ob hitchhiker.\ob space.\ob lockheed.\ob
com/\ob pub/\ob aic/\ob shade/\ob software/\ob
KAPI/\ob README.html}
}
@Misc{KSL-Ontology-Server,
key = {Knowledge Systems Laboratory},
author = {Stanford {Knowledge} {Systems} {Laboratory}},
title = {Ontology {Server} {Web} page},
howpublished = {http://\ob www-ksl-svc.\ob stanford.\ob edu:5915/}
}
@Misc{Our-Web-page,
key = {SARG},
author = {University of {Otago}},
title = {Software {Agents} {Research} {Group} {Web} page},
howpublished = {http://\ob divcom.\ob otago.\ob ac.\ob nz:800/\ob
COM/\ob INFOSCI/\ob SECML/\ob lab/\ob sarg}
}
@Article{PACT,
author = "M. R. Cutkosky and R. S. Engelmore and R. E. Fikes
and M. R. Genesereth and T. R. Gruber",
title = "{PACT}: An Experiment in Integrating Engineering Systems",
journal = "Computer",
year = "1993",
volume = "26",
number = "1",
pages = "28--37"
}
@Misc{POCG,
key = {POCG},
title = {Planning {Ontology} {Construction} {Group} home page},
howpublished = "\htmladdnormallink{http://\ob www.\ob ai.\ob rl.\ob
af.\ob mil/\ob PI/\ob Ontology.html}{http://www.ai.rl.af.mil/PI/Ontology.html}"
}
@Article{SHADE,
author = "J. G. McGuire and D. R. Kuokka and J. C. Weber and
J. M. Tenenbaum and T. R. Gruber and G. R. Olsen",
title = "{SHADE}: Technology for Knowledge-Based Collaborative
Engineering",
journal = "Concurrent Engineering: Research and Applications",
year = "1993",
volume = "1",
number = "3"
}
@InCollection{SIMS,
author = {C. A. Knoblock and J. L. Ambite},
title = {Agents for Information Gathering},
booktitle = {Software Agents},
publisher = {AAAI/MIT Press},
year = 1996,
editor = {J. Bradshaw},
note = {forthcoming. Also \htmladdnormallink{http://\ob www.\ob isi.\
ob
edu/\ob sims/\ob papers/\ob 95-agents-book.ps}{http://www.isi.edu/sims/papers/95-agents-book.ps}}
}
@Article{STRIPS,
author = {R. E. Fikes and N. J. Nilsson},
title = {{STRIPS}: A New Approach to the Application of Theorem Proving to
Problem Solving},
journal = {Artificial Intelligence},
year = 1971,
volume = 2,
pages = {189--208}
}
@Book{Searle,
author = "J. R. Searle",
title = "Speech Acts",
publisher = "Cambridge University Press",
year = "1969",
address = "Cambridge"
}
@InProceedings{Spreadsheet,
author = {S. S. Ali and S. Haller},
title = {Interpreting Spread Sheet Data for Human-Agent Interactions},
booktitle = {Proceedings of the Workshop on Intelligent
Information Agents, Fourth International Conference on Information and
Knowledge Management},
year = 1995,
month = {December},
note = {\htmladdnormallink{http://\ob www.\ob cs.\ob
umbc.\ob edu/\ob \char126 cikm/\ob iia/\ob proc.html}{http://www.cs.umbc.edu/~cikm/iia/proc.html}}
}
@InProceedings{UMCP,
author = {K. Erol and J. Hendler and D. S. Nau},
title = {{UMCP}: A Sound and Complete Procedure for
Hierarchical Task-Network Planning},
booktitle = {Proceedings of the 2nd International Conference on
AI Planning Systems},
editor = {K. Hammond},
year = 1994,
pages = {249--254}
}
@InProceedings{ambros-ingerson,
author = {J. Ambros-Ingerson and S. Steel},
title = {Integrating planning, execution and monitoring},
booktitle = {Proceedings of the 7th National Conference on
Artificial Intelligence},
year = {1988},
pages = {735--740}
}
@Article{civil_eng,
author = "T. Khedro and M. Genesereth",
title = "The Federation Architecture for Interoperable
Agent-Based Concurrent Engineering Systems",
journal = "International Journal on Concurrent Engineering,
Research and Applications",
year = "1994",
volume = "2",
pages = "125--131"
}
@Misc{commerce_net,
author = "W. Wong and A. Keller",
title = "Developing an {Internet} Presence with Online
Electronic Catalogs",
howpublished = "Stanford Center for Information Technology,
\htmladdnormallink{http://\ob www-db.\ob stanford.\ob
edu/\ob pub/\ob keller/\ob 1994/\ob cnet-online-cat.ps}{http://www-db.stanford.edu/pub/keller/1994/cnet-online-cat.ps}"
}
@TechReport{facilitator_manual,
author = "N. Singh",
title = "A {Common} {Lisp} {API} and Facilitator for {ABSI}: version 2.0.3",
institution = "Logic Group, Computer Science Department, Stanford University",
year = "1993",
number = "Logic-93-4"
}
@InProceedings{golden,
author = {K. Golden and O. Etzioni and D. Weld},
title = {Omnipotence Without Omniscience: Efficient Sensor Management for Planning},
booktitle = {Proceedings of the 12th National Conference on
Artificial Intelligence},
year = {1994},
publisher = {AAAI Press},
pages = {1048--1054},
note = {file://\ob cs.\ob washington.\ob edu/\ob pub/\ob
ai/\ob tr94-01-03.ps.Z}
}
@InProceedings{knoblock95,
author = {C. A. Knoblock},
title = {Planning, Executing, Sensing, and Replanning for Information Gathering},
booktitle = {Proceedings of the Fourteenth International Joint
Conference on Artificial Intelligence},
year = {1995},
note = {http://\ob www.\ob isi.\ob edu/\ob sims/\ob papers/\ob 95-sage.ps}
}
@InProceedings{knowledgeable_community,
author = "T. Nishida and H. Takeda",
title = "Towards the Knowledgeable Community",
pages = "157-166",
booktitle = "Proceedings of the International Conference on the Building
and Sharing of Very Large Scale Knowledge Bases",
year = "1993",
note = "\htmladdnormallink{http://ai-www.aist-nara.ac.jp/doc/people/takeda/doc/ps/kbks.ps}{http://ai-www.aist-nara.ac.jp/doc/people/takeda/doc/ps/kbks.ps}"
}
@Misc{ontology_library,
key = "Sharable {Ontology} {Library}",
title = "Sharable Ontology Library",
howpublished = "Knowledge Systems Laboratory, Stanford University,
\htmladdnormallink{http://www-ksl.stanford.edu/knowledge-sharing/ontologies/README.html}{http://www-ksl.stanford.edu/knowledge-sharing/ontologies/README.html}"
}
@TechReport{singh,
author = "N. P. Singh and M. A. Gisi",
title = "Coordinating Distributed Objects with Declarative Interfaces",
institution = "Computer Science Department, Stanford University",
year = "1995",
note = "\htmladdnormallink{http://\ob logic.\ob stanford.\ob
edu/\ob sharing/\ob papers/\ob oopsla.ps}{http://logic.stanford.edu\s/sharing/papers/oopsla.ps}"
}
@Unpublished{tawakol95,
author = {Omar A. Tawakol},
title = {Personal Communication},
note = {Logic {Group}, {Stanford} {University}},
year = 1995,
month = {August}
}
@InProceedings{wiederhold,
author = {G. Wiederhold},
title = {Interoperation, mediation, and ontologies},
booktitle = {Proceedings of the Workshop on Heterogeneous
Cooperative Knowledge Bases, International Symposium
on Fifth Generation Computer Systems},
year = {1994},
pages = {33--48},
note = {http://\ob db.\ob stanford.\ob edu/\ob pub/\ob
gio/\ob 1994/\ob medont.ps},
}
@InProceedings{williamson,
author = {M. Williamson and K. Decker and K. Sycara},
title = {Unified Information and Control Flow in Hierarchical
Task Networks},
booktitle = {Proceedings of the {AAAI-96} Workshop on Theories of
Action, Planning and Control},
year = {1996},
note = {http://\ob www.\ob cs.\ob cmu.\ob edu/\ob\char126
softagents/\ob papers/\ob provisions.ps}
}
