\section{The Networked Kitchen}
\label{netkitchen}

Imagine a kitchen in which all of the appliances are networked
together.  The pantry, cupboards, and refrigerator know their own
contents.  When preparing a recipe, the kitchen would preheat the
oven, identify substitutions in recipes if the user were on a
restricted diet, and would reorder ingredients from the supermarket as
supplies got low.  

\pmarginpic{juggling.ps}{Mike Hawley, Matthew Gray, and Andy Wheeler\\
at the prototype kitchen of the future}

Specifically, consider a recipe assistant, capable of walking a cook
through the preparation of a recipe.  An important sub-application of
this is a system to actually schedule the individual steps of a
recipe.  

\par

The level of assistance provided by the kitchen would vary depending
on user preferences, the particular recipe, and the devices and
sensors available in the kitchen.  The ideal system would be able to
take advantage of as much or as little capability as a kitchen might
offer.

\par


Particular hardware features built for use in the kitchen include a
tag reading system for identifying and locating cooking utensils,
dishes, and ingredients, a digital scale, a microwave oven, a display,
and speech output.  The software for the system uses Hive's
semantic lookup scheme to take advantage of new, previously unknown
hardware that matches certain descriptions.

\subsection{System Design Overview}

This demonstration system for the spring Things That Think consortium
meeting was constructed.  The demonstration system for the kitchen is
composed of nine kinds of agents.  The basic architecture is shown in Figure
\ref{netkitarch}.

\pmarginpic{wiring.ps}{Wiring for the demonstration}

\begin{figure}[htb]
\begin{center}
\mbox{\epsfysize=4in \epsfbox{nka.ps}}
\end{center}
\caption{Network Kitchen Architecture}
\label{netkitarch}
\end{figure}


\par
  At the top level in an agent which manages the
execution of the recipe, in concert with the other service agents.  At
the second level are a set of ``manager'' agents which coordinate
interactions with individual or sets of devices.  Finally, there are
the agents that correspond to the physical devices and services
available in the kitchen.

\par

Although not utilized in the demonstration, an additional agent could
be implemented above the the recipe agent to determine which recipes
are being used.  Implemented, but not used in the demo system is a
generic recipe scheduler capable of managing multiple simultaneous
recipes and managing resource contention.  A more detailed description
of this scheduler appears below in Section \ref{scheduler}.

\subsection{System Design Details}

\subsubsection{Recipe Agent}

The recipe agent oversees interactions and activities in the kitchen
by interacting with the manager agents.  This agent does not
necessarily plan the sequencing of the recipe itself, as that may come
from an independent scheduler, such as the one described below.

\par

A separate recipe agent provides the flexibility to manage the
execution of a recipe in a way suitable to a particular user.  Users
might prefer the use of different schedulers, or the ability to have
custom recipe agents that don't rely on a scheduler at all, as was
used in the demonstration scenario.

\subsubsection{Manager Agents}

The manager agents provide the the underlying ``kitchen logic''.
These agents manage an inventory of food and cookware, manage complex
interactions with hardware, and coordinate communication with the user
through whatever means are available.  These agents provide an
interface to the above described recipe agents, without the recipe
agent needing to be concerned with the actual hardware available in
the kitchen.

\par

Further, these agents will also take care of identifying resources
that may become available that were not anticipated of at the time of
the initial design.  Sufficiently unexpected improvements in the
functionality available may require updates of individual agents to
take advantage of the new capabilities, however the agents will
communicate via a set of well-defined interfaces to ease expansion of
the system.  Individual users are able to dramatically change the
behavior of the entire system by either tuning parameters of these
agents, or replacing them individually, without any pervasive change
to the remainder of the system.

\par

The {\em UserCommunicationAgent} manages all communications to the
user or users of the kitchen.  In the demonstration system, this agent
communicated with the user through verbal prompting as well as
graphical and textual on-screen feedback.  This agent could be readily
modified to provide location based projection, communication via a
wearable computer\footnote{See Section \ref{wearable} for a particular
application of Hive with wearables}, or via an ambient display.  In
the demonstration system, the display systems were reusable generic
display components.

\par

The {\em ScaleManager} managed complex interactions with the scale.
The {\em ScaleAgent} itself (described below) reports only the current
weight on the scale.  The {\em ScaleManager} maintains a recent
history, to identify if an item has been added or removed, how much
has been added since the last step in the recipe, and how much more
needs to be added, when it is notified of the goal by the recipe
agent.  In a kitchen environment with other devices that mandated
complex interactions, similar management agents would be created.

\par

\pmarginpic{bottomwithtag.ps}{Canister with RFID tag}

The inventory management agent, called the {\em TagConcentrator},
manages data from any number of tag readers, of any types. Using the
semantic lookup system described in Section \ref{semantic}, the {\em
TagConcentrator} discovers all of the tag readers available to it, and
organizes the presence, absence, appearance, and disappearance of any
and all tagged items.  Additionally, should new tag readers be
introduced, the {\em Tag Concentrator} will dynamically discover them.

\par

These management agents provide a convenient abstraction for
interacting with varying hardware configurations.  Beyond an
abstraction, however, they utilize Hive's semantic lookup scheme to
automatically identify the best piece or pieces of hardware to use in
a given scenario.  This ability to dynamically utilize available
hardware is one of the key strengths of Hive, and this is accomplished
through separation of functionality into agents, and use of semantic
descriptions.

\subsubsection{Device Agents}

Agents to manage each of the individual tag readers, the microwave,
\pmarginpic{microwave.ps}{Digitally controlled microwave}
the scale, the speech output system, and the on-screen display were
used.  The {\em TagReaderAgent} and {\em ScaleAgent} are both not
specific to the kitchen scenario, and are used in other
scenarios.\footnote{See section \ref{scenarios}} The speech output was
accomplished using an agent previously used for playing music, called
the {\em JukeboxAgent}, and the on-screen text display utilized the
{\em StringDisplayAgent}.  The {\em MicrowaveAgent} is currently only
utilized in the kitchen scenario.

\par

This reuse of components is straightforward in Hive.  Above
and beyond code reuse, however, is actual service reuse.  In the
demonstration setup, a separate audio system was used for the kitchen
demo than for the jukebox demo\footnote{See Section \ref{jukebox}},
however if the second audio system had not been set up, the kitchen
software would have automatically located another audio player, and
utilized that.

\subsubsection{Shadows}


Shadows for each of the device described in the previous section were
used as well.  Some of these shadows were particular to hardware only
utilized in the kitchen, such as the 
\pmarginpic{scale.ps}{Digital scale}
Transcell scale\footnote{While
the shadow for the scale is particular to the kitchen demonstration,
the agent for the scale merely requires a shadow with a particular
interface, and can be utilized with both a kitchen scale, and a
bathroom scale, such as the one used in the Net Weight\cite{netweight}
demonstration.} and the microwave, while others such as the Swatch tag
readers are identical to those used in other scenarios.

\subsubsection{Recipe Scheduler}
\label{scheduler}
A general recipe scheduler is necessary for any regular use of the
networked kitchen.  While it is possible to implement individual
recipes, as was done in the case of the demonstration peanut brittle
\marginpic{peanutbrittle.ps}{Peanut Brittle, in process}
recipe, it becomes impractical to do so for large numbers of recipes.

\par

Most recipes are presented as a fixed schedule, however it is clear to
a person using such a recipe that in fact there are interdependencies,
but rarely is the sequence strict.  For this reason it is useful to
have a dynamic scheduler that is capable of determining what sequence
tasks may be done in, to find an optimal sequence, to manage resource
utilization, and to adapt to unanticipated changes.  Eventually, it
would be useful to build an entire planner, such as CHEF\cite{chef},
rather than merely a scheduler to the system to allow creation of new
recipes from a set of well established rules.

\par

A scheduler based in part on STRIPS\cite{strips} and on Sacerdoti's
procedural nets\cite{procnets} was implemented.  Due to the highly
constrained nature of the recipe scheduling problem, and the fact that
the initial implementation was to be a scheduler only, and not a
generic planner, substantial simplifications were possible.  Further,
in 1971 Fikes and Nilsson write in \cite{strips}
\begin{quote}
However, since we envision uses in which the number
of operators applicable to any given world model might be quite large,
such a simple system would generate an undesirably large tree of world
models and would thus be impractical.
\end{quote}

In the nearly 30 years since then the ``impractical'' has become quite
practical, and the application domain distinctly limits the number of
operators.  For this reason, the scheduler can reasonably employ a
``simple system'' of an exhaustive search rather than requiring a
the more complex approach described in \cite{strips}.

\par

The scheduler accepts recipes as input which specify a list of steps,
their interdependencies and resource requirements.  These
interdependencies can include requirements that certain steps be
completed as prerequisites, that certain steps be started within a
certain time bound after the completion of another step, and any
combination of these timing constraints.  The resource requirements
may require a particular resource, or a resource of a particular type
for a flexibly specified time bound.

\par

For the demonstration system, the scheduler was not integrated with
the system, as a single recipe was being demonstrated repeatedly, and
identically. Integrating the scheduler should be straightforward.  Such
a combined system would then be capable of managing multiple
simultaneous recipes as well.

\par

Currently, the scheduler requires recipes in a fairly unnatural form,
with constraints explicitly stated.  Future work could include
attempts to construct this internal constraint based representation
from recipes in a natural language form.  Intermediate possibilities,
such as a recipe that is human-readable, but also contains some added
constraint information for the scheduler, should be readily doable.

\par

As mentioned above, further work to develop a full featured recipe
planner, rather than simply a scheduler, would be a rich area for new
research.  Simple planning features such as the ability to perform
substitutions and modify recipes for different cooking equipment is a
natural next step.  Beyond that, it is not unreasonable to suggest a
planner that is capable of constructing recipes from scratch, given a
basic set of requirements.

\subsection{Analysis}
\label{cianalysis}

Hive proved a valuable toolkit in developing the kitchen.  A
particular example of how Hive showed its flexibility in this
development occurred when the initially planned tag reading system was
not available.  Originally, the demonstration was intended to use a
single large antenna polyphonic tag reader, in combination with a
couple of the Swatch tag readers.  Two days prior to the
demonstration, the polyphonic tag reader ceased functioning.  Without
any code changes, the demonstration was capable of substituting a
larger number of Swatch tag readers to accomplish the same
functionality.  This was possible due to the fact that Hive utilized a
modular agent architecture and performed all of its lookup based on
semantic parameters, such as requiring that something be a
``tag-reader'', rather than a particular kind, or a particular number
of tag readers.

\par

One useful comparison to make to help determine the efficacy of Hive,
is to compare the kitchen demonstration system built with Hive to the
one built without Hive.  Comparison of functionality, implementation
complexity and code and component reuse show conspicuously some of the
advantages of Hive for applications such as this.

\par

The following table shows an itemization of the features present in
both the Hive and pre-Hive systems.

\begin{figure}[hbt]
\begin{tabular}{|l|l|l|}
\hline
{\bf Feature}& {\bf Hive}&{\bf pre-Hive}\\\hline
On-screen prompting & yes & yes\\\hline
Audible prompting & yes & no \\\hline
Digital scale & yes & yes \\\hline
Tag readers & yes & yes \\\hline
Arbitrarily many tag readers & yes & no \\\hline
Microwave & yes & yes \\\hline
Ability to execute a full recipe & yes & no \\\hline
Ability to execute more than one recipe & yes & no \\\hline
Inventory tracking & yes & no \\\hline
Recipe Selection GUI & yes & yes\\\hline
\end{tabular}
\caption{Pre- and post-Hive feature comparison for the kitchen demonstration}
\end{figure}
\pmarginpic{vanillawithtag.ps}{Vanilla on a tag reader}

The Hive based system implemented the same feature set as the previous
demo as well as a number of new features.  The Hive recipe selection
GUI was substantially less attractive than the pre-Hive system, though
the pre-Hive system only allowed for the selection of a single recipe.
Further, while the pre-Hive system contained support for the
microwave, it was not actually used in the demonstration.
Additionally, in the Hive version, each system component is usable
easily outside the context of the specific demonstration.  As an
example during the demonstration, the microwave was connected
dynamically to an on-screen button to control it.

\par

Measuring implementation complexity and code reuse is difficult,
however ``lines of code'' provides one metric.  The following
table shows the number of lines of code used in each system, and the
portion that is shared with other applications.
\vspace{2mm}

\begin{figure}[hbt]
\begin{tabular}{r|c|c|}
& {\bf Hive} & {\bf pre-Hive} \\\hline
{\bf Non-shared lines of code} & \~{}450 & \~{}3000 \\\hline
{\bf Shared lines of code} & \~{}350 & \~{}300 \\\hline
\end{tabular}
\caption{Code complexity comparison}
\end{figure}

The Hive scenario, of course, requires a large amount of generic
infrastructure.  The implementation complexity for the kitchen
demonstration however, is clearly much less under Hive.  Additionally,
more code is capable of being used in multiple applications under
Hive.

\par

The kitchen is clearly a domain which is open to substantially more
exploration.  Immediate extensions of this system include upgrading to
the originally planned polyphonic tag system, adding new appliances,
and extending software capabilities.  Future possibilities are
discussed further in \ref{analysis}.
