\newcommand{\problem}[4]
{\subsection*{Problem #1}
{\it #2}
\vspace{.7em} \mbox{} \\
\noindent
{\samepage
{\bf Analysis of Problem} \\
#3}
\vspace{.7em} \mbox{} \\
\noindent
{\samepage
{\bf Solution} \\
#4}}

%==========================
\section{Problem Scenerios}
%==========================
\label{app:problems}

\hrule
\vspace{1em}

The following are the problem scenarios that we used.  They are
classified into three levels of difficulty, 1, 2, and 3.  Below, for
each problem, we also give an analysis of the issues that need to be
addressed to find a solution to the problem.  Times shown in brackets,
e.g. (5 a.m.), are the time by which the previous action will have
been completed.

%----------
\problem{W}
%----------
%
{You need to design a plan for shipping a boxcar of oranges to Bath by
8 AM today.}
%
{This is the warmup problem.  It is straight forward, and has a number of solutions.}
%
{Use engine E2 (or E3) from Elmira, couple a boxcar to it, and head to
Corning (2 a.m.), where the boxcar can be loaded with oranges (3
a.m.).  Then head to Bath, arriving there at 5 a.m., three hours ahead
of schedule. 

Other solutions will work.  E2 could pick up a boxcar in Dansville (3
a.m.), head to Corning (4 a.m.), load up oranges (5 a.m.), and then
head to Bath (7 a.m.).  Or use engine E1 and pick up a boxcar in
Dansville (3 a.m.) and continue as above.}



%------------
\problem{1-A}
%------------
%
{Transport a tanker of OJ to Avon by 3 PM.  It is now midnight.}
%
{This is a sequencing problem: the user must ensure that the oranges
are brought to the factory, orange juice is manufactured, and then
picked up in a tanker car.  Due to the time constraints, the user must
bring a tanker to the factory at the same time as he brings the boxcar
of oranges.  Other than that, there are relatively few restrictions on
choice of engine, boxcars, and choice of route.}
%
{One solution is to use engine E2 (or E3), and take a boxcar from
Elmira to Corning, arriving there at 2 a.m.  Load oranges into the
boxcar (3 a.m.) and couple a tanker.  Then head back to Elmira (5
a.m.), and make orange juice (6 a.m.).  Then go to Corning (8 a.m.),
Dansville, (9 a.m.), and then arrive at Avon by 12 p.m.

A second solution is to use E1 from Avon.  Go to Dansville (3 a.m.),
and pick up a boxcar.  Then continue on to Corning (4 a.m.), and load
up the boxcar with oranges (5 a.m.) and hook up a tanker.  Then
travel to Elmira (7 a.m.) and make orange juice (8 a.m.).  Then go to
Corning (10 a.m.), Dansville (11 a.m.), and then to Avon, arriving
there at 2 p.m. 

If E2 (or E3) is used, a boxcar at Dansville can be used instead of
the one at Elmira, or the train can go through Bath, instead of
Dansville, on its way to Avon.}

%------------
\problem{1-B}
%------------
%
{Transport 2 boxcars of bananas to Corning by 11 AM.  It is now
midnight.}
%
{This is a straight forward problem, but with a tight time constraint.
Hence there are few choices for engine, boxcar and route that will
result in a plan that finishes on time.  In fact, all valid plans must
travel via Dansville to get from the banana warehouse in Avon to
Corning.}
%
{If engine E1 (from Avon) is used, it must pick up two boxcars in
Dansville (3 a.m.), so that it can return to Avon by 6 a.m.  The
bananas should then be loaded (7 a.m.) and then transported to
Dansville (10 a.m.) and then to Corning, by 11 a.m.  Going to Corning
via Bath will result in the task being completed two hours late.

If E2 or E3 (from Elmira) is used, then it must travel to Corning (2
a.m.), to Dansville (3 a.m.), and then to Avon, arriving there by 6
a.m.  Boxcars can be picked up along the way either in Elmira or in
Dansville.  The rest of the plan is the same as for engine E1.}

%------------
\problem{1-C}
%------------
%
{Transport 4 boxcars of oranges to Bath by 2 PM.}
%
{This problem involves load-limit constraints.  The user must get four
boxcars of oranges to Bath, but an engine can only pull 3 full
boxcars.  So, he must either make two trips or use two trains.  Also
the user must get boxcars from more than one location, since no one
spot has 4 boxcars.  So, the user must be careful not to schedule two
trains onto the same track.}
%
{One straightforward solution is to use E2 (or E3) to deliver the two
boxcars from Elmira to Corning arriving there at 2 a.m.  Load up the
boxcars with oranges (3 a.m.), and then take
them to Bath, ariving there at 5 a.m.  At the same time, take E1 to
Dansville (3 a.m.), pick up two boxcars and take them to Corning,
arriving there at 4 a.m., which will be after E2 has already left.
Load up the boxcars with oranges and arrive at Bath by 7 a.m.

Due to the abundance of time, many other solutions will work,
including using E3 to pick up the boxcars in Dansville; or using E2 to
pick up all of the boxcars first, then load oranges, and then make two
trips to Bath to deliver the oranges.}

%------------
\problem{1-D}
%------------
%
{Ship 3 boxcars of bananas and 3 tankers of OJ to Bath.}
%
{This problem involves sequencing the actions to achieve two tasks.
The first task is to make three tankers of oranges, for which the user
first needs to get three boxcars of oranges, and convert them into
three tankers worth of OJ.  The second task is to ship three boxcars
of bananas.  These two tasks can either be done sequentially or in
parallel.}
%
{The fastest way to accomplish this task is to tackle the two problems
separately.  Both subtasks need three boxcars each.  The orange task
can be done by taking engine E2 (or E3) with the two boxcars at Elmira
to Corning (2 a.m.), and then to Bath (4 a.m.), where a third boxcar
can be picked up.  Then head back to Corning (6 a.m.), where the three
boxcars can be loaded with oranges (7 a.m.) and the three tanker
cars can be added.  Then head to Elmira (9 a.m.), make the orange
juice (10 a.m.), and then head to Corning (12 a.m.) and then to Bath
by 2 p.m.  This finishes the orange juice subtask.  As for the
bananas, take E1 from Avon to Dansville (3 a.m.), hook up the three
boxcars, and return to Avon (6 a.m.).  There, load up the three
boxcars with bananas (7 a.m.), and then head to Bath, arriving there
at 11 a.m.

Since there is no time constraint, many other solutions are possible.
One other solution worth mentioning is using one engine to do the
entire task.  Use engine E2 from Avon, and head to Dansville (3 a.m.),
hook up the three boxcars and head to Corning (4 a.m.), and couple up
the three tankers and fill the boxcars with oranges (5 a.m.).  Then
head to Elmira (7 a.m.), make orange juice (8 a.m.), thus emptying the
three boxcars.  Then head to Corning (10 a.m.), and then to Bath (12
p.m.), and drop off the three tankers of orange juice.  Then head to
Avon (4 p.m.), and load up the boxcars with bananas (5 p.m.), and then
head back to Bath, finishing the task by 9 p.m.}

%------------
\problem{1-E}
%------------
%
{Engine E1 leaves Avon every night at midnight, picks up boxcars in
Dansville, and then continually runs back and forth between Avon and
Dansville until 9 AM, carrying 3 boxcars of bananas to Dansville on
every trip.  Your task is to transport 2 boxcars of oranges to Avon by
9 AM.  It is now 12 midnight.}
%
{This problem involves resource conflicts;  the most direct route
between Corning and Avon, by way of Dansville, is occupied, and so the
alternate route through Bath must be used.

Unfortunately, the scenario presented in the problem uses boxcars that
are not part of the {\sc Trains} domain given on the user's or the
system's map.  In fact, in order to make an integer number of trips,
E1 must drop off the boxcars in Avon, rather than unload them and take
them back to Dansville.  This problem proved difficult for the
conversants.  Of the four users given this problem, two ignored the
constraint, one misread it, and only one pair was able to solve the
problem.}
%
{Use Engine E2 (or E3), and take 2 boxcars from Elmira and go to
Corning (2 a.m.), and load them up with oranges (3 a.m.).  Then go to
Bath (5 a.m.), and then to Avon, arriving there at 9 a.m.}

%------------
\problem{2-A}
%------------
%
{There are 5 boxcars of oranges waiting for you at Corning.  You are to
make 1 tanker of OJ, and then deliver the 1 tanker of OJ plus 4
boxcars of oranges to Bath as soon as possible.}
%
{This problem involves dealing with load-limit constraints: an engine
can only pull three loaded boxcars.  So, the user must break the
problem into two parts (or more) and execute them simultaneously.
Many solutions are possible.  The one below does the task with three
engines, thus finishing the entire task by 9 a.m., with the four
boxcars of oranges arriving there at 6 a.m.}
%
{Take engine E2 from Elmira to Corning (2 a.m.) and pick up one of the boxcars
of oranges and a tanker and take them to Elmira (4 a.m.).  Make a
tanker's worth of orange juice (5 a.m.), then take it to Corning (7
a.m.), and then to Bath, arriving there at 9 a.m.  While this is
happening, take engine E3 and depart from Elmira at 1 a.m. (since it
cannot depart at the same time as E2), and arrive in  Corning at 3 a.m.  In
Corning, hook up three of the boxcars and take them to Bath, arriving
there at 5 a.m.  For the last boxcar, use engine E1 from Avon, and go
to Dansville (3 a.m.), Corning (4 a.m.), and hook up the last boxcar.
Then take it to Bath, arriving there at 6 a.m.}


%------------
\problem{2-B}
%------------
%
{Transport 1 tanker of OJ to Avon and a boxcar of bananas to Corning by
3 PM.}
%
{This is the test problem from the 91 dialogues \cite
{gross-allen-traum:93:tr}.  This problem involves time constraints,
and sequencing of actions, and can only be solved by using two trains
and doing each task separately, but watching for harmful
interactions.}
%
{Take engine E1 to Dansville (3 a.m.), pick up a boxcar, and return to
Avon (6 a.m.).  Load the boxcar with bananas (7 a.m.), then go to
Dansville (10 a.m.)  and then Corning, arriving there at Corning at 11
a.m.  While this is happening, take engine E2 (or E3) with one boxcar
from Elmira and go to Corning (2 a.m.). Load the boxcar with oranges
(3 a.m.) and then pick up a tanker, and return to Elmira by 5 a.m.  At
Elmira, make orange juice (6 a.m.)  and then go to Corning (8 a.m.),
then to Dansville (9 a.m.), and then wait there for an hour for E1 to
clear the track.  Then at 10 a.m., head to Avon, arriving there at 1
p.m.}


%------------
\problem{2-C}
%------------
%
{Ship 3 boxcars of bananas to Dansville, and 2 boxcars of oranges to
Avon.  Both shipments must arrive at their destinations by 9 AM.  It
is now 12 midnight.}
%
{This problem is not solvable, and was pulled from the stack of
problems before it was ever used.}
%
{Getting 3 boxcars of bananas to Dansville will take at least 10
hours.  So, this problem is not solvable.}

%------------
\problem{2-D}
%------------
%
{Ship 1 boxcar of bananas, 1 boxcar of oranges, and 1 tanker of OJ to
Bath.  All 3 commodities must be in Bath by noon.  It is now 12
midnight.}
%
{The difficulty with this problem is that there are three separate
tasks that must be accomplish.  Due to the lenient time constraints, many solutions are possible.}
%
{For the bananas, take engine E1 from Avon to Dansville (3 a.m.), pick
up a boxcar, and then return to Avon (6 a.m.).  Load the boxcar with
bananas (7 a.m.), and head to Bath, arriving there at 11 a.m.  For the
oranges and orange juice, take engine E2 (or E3) with two boxcars from
Elmira to Corning (2 a.m.), load up the boxcars with oranges (3 a.m.)
and hook up a tanker.  Then return to Elmira (5 a.m.), and make one
tanker's worth of orange juice (6 a.m.).  Then go to Corning (8 a.m.),
and then Bath, arriving in Bath at 10 a.m.}

%------------
\problem{2-E}
%------------
%
{Determine the maximum number of boxcars of oranges that you could get
to Bath by 7 AM tomorrow morning.  It is now 12 midnight.}
%
{The difficulty with this problem is that the user must ensure that there
is not a better plan that can bring even more boxcars of oranges to
Bath, and hence must consider alternate solutions.}
%
{Take engine E2 with the two boxcars at Elmira, and go to Corning (2
a.m.), where they can be loaded with oranges (3 a.m.).  Then head to Bath,
arriving there at 5 a.m.  At the same time, take E1 from Avon, go to 
Dansville (3 a.m.), and hook up 3 boxcars.  Then head to Corning (4
a.m.), and load up the boxcars with oranges (5 a.m.).  Then go to
Bath, arriving there at 7 a.m.  The two boxcars in Bath cannot be
filled and brought back to Bath by 7 a.m., so the maximum is 5 boxcars.}

%------------
\problem{2-F}
%------------
%
{Ship 3 boxcars of bananas to Bath and 2 tankers of OJ to Dansville.
All deliveries must be made before noon.}
%
{This problem has two easy subtasks, but the user must travel all over
the map.}
%
{For the bananas, use engine E1, and go to Dansville (3 a.m.), and
pick up the three boxcars there.  Then return to Avon (6 a.m.) and
load up the boxcars with bananas (7 a.m.) and then go to
Bath, arriving there at 11 a.m.  For the orange juice, use engine E2
(or E3).  Take the two boxcars from Elmira and head to Corning (2
a.m.).  Load up the two boxcars with oranges and hook up the two
tankers (3 a.m.).  Then, go back to Elmira (5 a.m.) and make orange
juice (6 a.m.).  Then go to Corning (8 a.m.), and then to Dansville,
arriving there at 9 a.m.}

%------------
\problem{2-G}
%------------
%
{Ship 2 boxcars of bananas and 2 boxcars of oranges to Dansville. All
cargo must arrive by 10 AM.}
%
{This problem should prove relatively easy as long as two engines are
used: one for the transporting the bananas and one for transporting
the oranges.}
%
{Take Engine E1 from Avon to Dansville (3 a.m.), pick up 2 boxcars,
and return to Avon (6 a.m.).  At Avon, load up the two boxcars with
bananas (7 a.m.), and go back to Dansville (10 a.m.).  While this is
happening, take engine E2 (or E3), with two boxcars to Corning (2
a.m.).  Load up the two boxcars with oranges (3 a.m.), and go to
Dansville, arriving there at 4 a.m.}

%------------
\problem{3-A}
%------------
%
{Pick up 2 boxcars of oranges, make into 2 tankers of OJ and ship OJ
from Elmira to Avon, arriving by 1 PM at the latest.  It is now 12
midnight.}
%
{This problem involves sequencing and a difficult time constraint.
The user must schedule the empty
tankers to be taken to the orange juice factory at the same time as
the loaded boxcars are taken there.  The solution below is the only
solution that will work in time.}
%
{Take engine E2 (or E3) from Elmira with two boxcars and go to
Corning (2 a.m.).  Load up the two boxcars with
oranges (3 a.m.) and hook up two tankers.  Then go back to Elmira (5
a.m.) and make the oranges into orange juice (6 a.m.).
Then ship the orange juice to Elmira, via Corning (8 a.m.) and
Dansville (9 a.m.), arriving in Elmira at noon.}

%------------
\problem{3-B}
%------------
%
{Plan a round trip from Avon to Elmira.  On the way out, take 3
boxcars of bananas, and deliver 1 each to Bath, Corning, and Elmira
(you do not have to unload the boxcars, just drop them off).  Bring 2
tankers of OJ back to Avon (you'll have to get oranges and make the
juice).  You must arrive back in Avon within 24 hours.}
%
{Relatively complex subgoal planning is involved.  The user must
realize that while delivering the bananas, two empty boxcars must be
picked up for the transporting the oranges to the OJ factory.

In order to qualify as making a round trip, this problem must be
solved with a single engine doing everything.  Inappropriate solutions
made use of one engine to transport the bananas and a second to handle
the orange juice, which does not constitute making a round trip.  One
problematic aspect of the solution is that it requires returning to
Avon twice, which might be a bit confusing.}
%
{Take engine E1 to Dansville (3 a.m.) and pick up the three boxcars
there.  Then head back to Avon (6 a.m.) and load up the three boxcars
with bananas (7 a.m.), and then go to Bath (11 a.m.).  At Bath, drop
off the boxcar of bananas, and hook up the two empty boxcars.  Then go
to Corning (1 p.m.), where the boxcar of bananas should be dropped
off, two empty tankers hooked up, and the two empty boxcars loaded
with oranges (2 p.m.).  At this point, E1 will have one boxcar of
bananas, two boxcars of oranges, and two empty tankers.  E1 should now
head to Elmira (4 p.m.), drop off the boxcar of bananas there, and
make the oranges into orange juice (5 p.m.).  Then, with the two full
tankers of orange juice, go to Corning (7 p.m.), to Dansville (8
p.m.), and then to Avon, arriving there at 11 p.m.}


%------------
\problem{3-C}
%------------
%
{Transport 2 tankers of OJ to Avon and 3 boxcars of bananas to Elmira.
The bananas must arrive in Elmira by 9 PM.  You can only use Engine E2
to solve this problem because the other engines will be undergoing
routine maintenance.}
%
{The difficulty with this problem is that the user must solve both
subtasks with only a single engine.  Due to the constraint on the
number of loaded boxcars that an engine can pull, the shipment must be
transported in two trips.  There are a number of possible solutions,
since the time constraint is lenient.  Below, we give two solutions,
one that completes the banana task as quick as possible, and a second
that completes the overall plan as quick as possible (and delivers the
bananas by 9 p.m.).}
%
{To complete the banana task as quickly as possible, use engine E2
from Elmira.  Hook up the two boxcars there, and go to Corning (2
a.m.).  Drop off the two boxcars in Corning and load them with
oranges, while engine E2 gets three boxcars of bananas.  Take E2 to
Dansville (3 a.m.), and hook up the three empty boxcars.  Then head to
Avon (6 a.m.), and load the three boxcars with bananas (7 a.m.).  Then
head back to Dansville (10 a.m.), then to Corning (11 a.m.), and then
to Elmira (1 p.m.), where the bananas should be dropped off, eight
hours ahead of schedule.  Then go back to Corning (3 p.m.), and pick
up two empty tankers and the two boxcars loaded with oranges.  Then,
head back to Elmira and make orange juice, finishing this by 6 p.m.
Then take the two tankers of orange juice to Corning (8 p.m.),
Dansville (9 p.m.), and then to Avon, arriving there at 12 a.m., the
following day.

To complete the overall task as quickly as possible, make the orange
juice first, and bring it to Avon when you go to pick up the bananas.
Use Engine E2 with two boxcars, and go to Corning (2 a.m.).  Load the
boxcars with oranges (3 a.m.) and couple the two tankers to the train.
Then go to Elmira (5 a.m.), and turn the two boxcars of oranges into
two tankers' worth of orange juice (6 a.m.).  Then head for Avon, via
Corning (8 a.m.) and Dansville (9 a.m.), stopping in Dansville to
couple a third boxcar.  You should arrive in Avon by 12 p.m.  In Avon,
drop off the two tankers of orange juice and load the three empty
boxcars with bananas, finishing this by 1 p.m.  Then head for Elmira,
by way of Dansville (4 p.m.) and Corning (5 p.m.), arriving in Elmira
at 7 p.m., two hours before the deadline.}


%------------
\problem{3-D}
%------------
%
{It is now 12 midnight.  Transport 2 boxcars of oranges and 1 tanker of
OJ to Avon.  Due to heavy rail traffic, the timing of some of your
stops has been predetermined as follows.

\begin{enumerate}
\item The oranges are due to be processed at the factory in Elmira at
7 AM sharp.  As soon as the OJ is made, the train must leave Elmira.
\item The train can't arrive at Avon before 3 PM because there is no
room.
\end{enumerate}}
%
{This problem involves working around time constraints.  There are
many different solutions possible due to the lenient time constraints.
Note that the wording of the problem seems to imply that a single
train be used; but this is not explicitly stated.}
%
{Take engine E2 (or E3) from Elmira with one boxcar and go to Corning
(2:00 a.m.). Load the boxcar with oranges (3 a.m.) and hook up a
tanker.  Go back to Elmira (5:00 a.m.)  and wait two hours (7 a.m.).
Then make the orange juice (8 a.m.), and hook up a second boxcar.  E2
should now consist of two empty boxcars and a tanker full of orange
juice.  Next, go to Corning (10 a.m.), and load the two boxcars with
oranges (11:00 a.m.), and then head to Avon, by way of Dansville
(12:00 p.m.), arriving there by 3:00 p.m.}

%------------
\problem{3-E}
%------------
%
{Get 7 boxcars of oranges to Elmira by 9 AM.  It is now midnight.}
%
{The solution to this problem involves simultaneous use of engines on
different tracks.  The solution that we give below makes use of all
three engines.  Note that our solution has engine E3 following E2, one hour begind, on the same section of track.}  
%
{Take engine E1 from Avon to Dansville (3 a.m.), hook up the three
boxcars and go to Corning (4 a.m.).  Load the boxcars with oranges (5
a.m.), and go to Elmira, arriving there at 7 a.m.  Take engine E2 and
go to Corning (2 a.m.), and then to Bath (4 a.m.), and pick up the two
boxcars there.  Go back to Corning (6 a.m.) and load up the boxcars (7
a.m.), and go to Elmira, arriving there at 9 a.m.  Take engine E3 with
the two boxcars, depart at 1 a.m. and go to Corning (3 a.m.), and load
up the boxcars with oranges (4 a.m.), and return to Elmira (6 a.m.).}

%------------
\problem{3-F}
%------------
%
{Ship 2 boxcars of bananas and 1 boxcar of oranges to Dansville by noon
using only one engine.  It is now midnight, and the shipment must be
unloaded by 1 PM.}
%
{The user must do the orange task first, in order to be in a position
to accomplish the banana task on time.}
%
{Take engine E2 (or E3) with a boxcar from Elmira and go to Corning (2
a.m.), and load up the oranges (3 a.m.), and go to Dansville, arriving
there at 4 a.m.  Drop off the boxcar of oranges, and have it unloaded,
while E2 picks up two empty boxcars and goes to Avon (7 a.m.).  At
Avon, load the two boxcars with bananas (8 a.m.), then go to
Dansville (11 a.m.), and unload the boxcar, finishing by noon.}


