\documentstyle[bk11, psfig, named]{article} 

\newcommand{\ignore}[1]{} \newcommand{\circlelet}[1]{\makebox[.85em]{\sc #1}\raisebox{.03em}{$\!\!\!\!\!\!\:\!\bigcirc\!$}} 

\textwidth       6.5in  \textheight      9.6in  \topmargin      -1.in \oddsidemargin  -0.175in
\evensidemargin -0.175in
\headheight      4ex  %this gets rid of an annoying error message 

\ignore{ [RS89] Riesbeck & Schank. Inside Case-Based Reasoning. Hillsdale, N.J.: LEA,       1989. } 

% Margin notes
\newcommand{\note}[1]{\marginpar{\it #1}}
\newcommand{\scenario}[1]{\begin{quote} {\bf Example: }{\it #1}
\end{quote}}
\newcommand{\subsubsubsection}[1]{
\vspace{.10in}  

{\bf #1} 

\vspace{.10in}}
\newcommand{\subsubsubsubsection}[1]{} 

%\raggedright 

\renewcommand{\textfraction}{.1}
\renewcommand{\topfraction}{.9}
\renewcommand{\bottomfraction}{.9} 

\title{Planning to Schedule} 

\date{\today}
\author{Garrett A. Pelton}
\begin{document}           % End of preamble and beginning of text.
\bibliographystyle{named}
\abstract{ 

} 
\maketitle 

\section{Introduction} 

Planning is interesting and hard when subproblems interact, but when the
subproblems primarily interact over the available resources, standard planing
search techniques are not effective at finding a viable plan. This loss of
planning effectiveness is partly due to grouping together decisions about {\it
how} to achieve a goal and {\it what} resources will be used to achieve the
goal. When later decisions cause a resource conflict, this grouping limits the
number of applicable methods for resolving that conflict. For example, in
planning the solution to a logistics problem that has many subgoals, such as
battling a forest fire, a classical planner decides {\it how} to deploy the
firefighters and their associated equipment. The planner can also pick the
resources (like what planes, trucks etc.) the plan's implementation should
use. However, many of the resources may be interchangeable, and backtracking to
change a compatible resource discards other good decisions that will have to be
remade. This type of resource changing occurs often, since the solution of such
a logistics problem not only achieves the goal but also attempts to minimize
some plan-quality criteria (e.g. achievment by some time, or within some cost
limit). In these problems, the proper selection of resources {\it is} both the
most time-consuming component and often the critical aspect of the
solution. Thus a simple resource selection approach coupled with chronological
backtracking is unlikely to come up with a good solution in any reasonable
amount of time.

As an example, consider the military deployment problem shown on the right of
Figure~\ref{deployment-plan}. The goal in this problem to achieve
air-superiority over City-1 and City-2 by a certain date (called the
due-date). Air-superiority simply means that your airforces control the air
space. The plans for the actual force deployment are complex, because they
include all of the previously learned safety and effectiveness
dependencies. Airplanes needing a safe place to land, is the start of such a
chain of dependencies. Infantry troops can create a safe place for aircraft to
land, but first the surrounding area must be secure. Securing an area might
involve deploying other different aircraft, anti-aircraft forces and/or
specialized security forces all depending upon the other forces and amount of
support in the area.

\begin{figure*}[b]
%\psfig{figure=figures/constraint-ex.ps} 
The left side has a simple map 
The right side has a more complex goal-tree.
\caption{Plan for achieving air superiority over two cities using resource types.} 
\label{deployment-plan}
\end{figure*}

A plan tree showing the considered planning operators is given on the right of
Figure~\ref{deployment-plan}. Each planning operator represents doing some
activity (e.g. moving some entity), but no specific resources have been
assigned. Instead each planning operator works with a resource type, and and in
many cases these types represent aggregates of individual resources (e.g. an
infantry-battalion or a C-5 transport plane squadron) that might be
individually assigned. Working with resource types simplifies the planning
problem in Figure~\ref{deployment-plan}but the generated plans can not make the
desired due-date. If in an attempt to make the due-date the individual
resources are considered\footnote{Actually the number of individuals in an
infantry battalion was divided by 10 and the capacity of the transports was
also divided by 10 just to make the problem tractable.}, then the planning
problem in Figure~\ref{deployment-plan} with YYY operators expands to XXX {\it
experiment needs to be run} operators. Since the two problems interact over
resources, going to the higher level of detail in assigning resources causes
backtracking over the resource assignments to occur (enough heuristic knowledge
was added to this experiment so that no backtracking was necessary to create
this large plan.). This backtracking would be removing perfectly valid
decisions and giving us possibly an exponential explosion in the number of
operators considered as the different possible bindings are tried.

The two areas marked in grey on Figure~\ref{deployment-plan} denote the planing
associated with deploying one of the two available infantry battalions to
City-1 and City-2. This simple subproblem contains a large number of the issues
that this paper addresses. Extracting this subproblem from the larger problem
provides a way to describe various solutions to those issues. What should be
remembered though is that, what look like local decisions affect the much
larger set of nodes. This propagation of planning decisions exacerbates any
problems by increasing the number of decisions that have to be re-considered.

As will be shown in Section~\ref{example-prob} these two sub-problems interact
over resources in such a way that neither the planner nor scheduler alone can
generate a reasonable solution in a reasonable time without detailed domain
knowledge. The planner's problems comes from having to work with individual
planes rather than aggregate resource types which makes the problem XXX times
harder. The scheduler's problems come from having to consider contingency plans
for each resource assignment rather than consider contingency plans for the
difficult resource assignments. However, together the planner and scheduler can
operate in a straight forward synergistic manner and solve this small
subproblem. Even more important is that the problem solving does not need to
alter the other parts of the deployment plan in
Figure~\ref{deployment-plan}. This localization of effort should mean this
solution methodology will scale to larger systems. This paper is partly a
proposal to test this localization hypothesis.

In addition to solving some "insolvable" problems, the 

\section{Example Problem}
\label{example-prob}

\begin{figure*}[tbp]
\psfig{figure=figures/2-deploy-map.eps} 
\begin{verbatim}
Goal - An infantry battalion at City-1 by 1/4
       An infantry battalion at City-2 by 1/4

Current State -
   Infantry battalion A at City-3
   Infantry battalion B at City-4
     An infantry battalion consists of
        500 soldiers and 100 tons of equipment
        The equipment is 25 4-ton trucks
   3 C5s at City-5
     C5s can carry 50 tons of Bulk Cargo and
                   40 passengers
   3 C141s at City-6
     C141s can carry 10 tons of Bulk Cargo and
                    140 passengers
   Current date is 1/1 

  Resource Compatibility
	C-5s can land at City-1, City-2, City-4, City-5, City-7
	C-141s can land at all Cities


Operators
  Send (ground-unit transportation-resource from-location to-location)
    (:activity-type transport :agent transportation-resource)
    preconditions
      ground-unit is deployed at from-location
      transportation-resource is deployed at from-location
      from-location is a location compatible with transportation-resource 
      to-location is a location compatible with transportation-resource
    postconditions
      transportation-resource is deployed at to-location
      ground-unit is deployed at to-location
  Move (transportation-resource from-location to-location)
    (:activity-type transport :agent transportation-resource)
    preconditions
      transportation-resource is deployed at from-location
      from-location is a location compatible with transportation-resource
      to-location is a location compatible with transportation-resource
    postconditions
      transportation-resource is deployed at to-location
\end{verbatim}
\caption{Example problem of moving two groups of troops} 
\label{example-prob-fig}
\end{figure*}

Figure~\ref{examp-prob-fig} shows the problem of getting two infantry
battalions to two different cities within three days. It doesn't make any
difference to the solution which battalion is in which city. However, unit
cohesiveness demands that each battalion be entirely deployed in the same city
on the third day. Splitting the battalions up permanently is not a valid
solution. This relatively simple problem is made more complex by the fact that
barely enough resources exist to solve the problem, causing the solutions to
interact over the resources and as will be shown they must share resources. The
extent of the interaction can only be determined before-hand by the planner, if
the planner concerns itself with separately planning the movement of each
soldier and piece of equipment. With 500 soldiers and 25 4-ton trucks in each
battalion, and 16 planes, each step in the plan has over 200,000 possible
bindings making this approach unworkable even for short simple plans. Instead
of resorting to a standard hierarchical grouping of the soldiers, this paper
proposes to use the plans themselves to organize the individuals into {\it
equivalence classes}, where all the individuals in an equivalence class can be
considered as a group, and can be scheduled over the resources as a group. This
equivalence class grouping greatly reduces the planning effort because the
planner only sees the number of distinct equivalence classes.

In this example, the planner has a preference for the shortest-path solutions
and a preference for not using common resources. Without the shortest-path
preference the planner is perfectly willing to plan out a long byzantine path,
that will probably fail because of exceeding the due-date. With the shortest
path heuristic, all the paths of length $n$ are all tried before paths of
length $n+1$. The shortest-path preference is a crude method of limiting the
planning effort in a way that maximizes the likelihood of the plan's completion
by the due-date. This heuristic also gives a breadth first search
characteristic to searching for solution paths. This breadth-first issue will
be discussed in Section~\ref{search-heuristics}. The second preference (not to
use common resources) is again a crude method of deciding between plans that
use common resources and those that don't. It represents an attempt to keep the
utilization of the common resources (planes) as low as possible. Since the
common resources are costly (planes) not using them except when necessary is an
attempt to limit the cost of the solution.

The presentation will first describe the planning algorithm. Then using that
algorithm start with a highly abstract representation. This representation will
not find a solution, but examining why it fails provides insight into both why
the abstract representation is useful for the planner and how to fix its
problems while maintaining the useful qualities.

\subsection{Planner description}
\label{planner-description}

\begin{figure*}[tbp]
\begin{tabbing}
MM\=M\=M\=M\=M\=MMM\=MMM\=MMMMMMMMMMMMMMMMMMMMM\=\\
\>{\it Planning algorithm}\>\>\>\>\>\>\> Execution trace\\
PLAN-IT(Goals, Operators, State) \\
1\>{\it Do for each unachieved goal}\\
2\>\>{\it Select Goal}\>\>\>\>\>\>Infantry battalion at City-1\\
\>\>\>\>\>\>\>\>(SEND, MOVE)\\
3\>\>{\it Do for each possible operator}\\
4\>\>\>{\it Select Applicable Operator}\>\>\>\>\>SEND\\
\>\>\>\>\>\>\>\> SEND Inf-A using C141s to City-1,\\
\>\>\>\>\>\>\>\> SEND Inf-B using C5s to City-1,\\
\>\>\>\>\>\>\>\> SEND Inf-B using C141s to City-1)\\
5\>\>\>{\it Do for each possible binding}\\
6\>\>\>\>{\it Select binding}\>\>\>\>SEND Inf-A using C5s to City-1\\
7\>\>\>\>{\it if operator has unresolved preconditions}\\
8\>\>\>\>\>{\it result = PLAN-IT(Goals - }\\
\>\>\>\>\>\>{\it selected-goal + unresolved-preconditions,}\\
\>\>\>\>\>\>{\it Operators, State)}\\
9\>\>\>\>{\it else result = PLAN-IT(Goals - selected-goal, Operators,}\\
\>\>\>\>\>\>{\it State modified by operator)}\\
10\>\>\>\>{\it if result = SUCCESS return SUCCESS}\\
11\>\>\>\>{\it End-Do on bindings}\\
12\>\>\>{\it End-Do operators}\\
13\>\>{\it End-Do goals}\\
14\>{\it if unachieved goals return FAILURE}\\
15\>{\it else return SUCCESS}
\end{tabbing}
\caption{Total order state space planner.} 
\label{simple-planner}
\end{figure*}

At this point, the details of planning start to become important. Figure~\ref{simple-planner} shows a simple planning algorithm on the left and a trace for part of the transport problem on the right. This algorithm is similar to total order state space planners like Prodigy \cite{}. The arguments given in this section will be shown in Section~\ref{plan-space} to also apply to plan space planners, like UCPOP \cite{} with a few changes. 

The algorithm in Figure~\ref{simple planner} has 3 choice points: selecting a goal, selecting an operator and selecting a binding. Selecting the goal is a meta-planning decision that determines how the planning should proceed. In our example trace, the planner arbitarily picks sending the troops to City-1 as the first goal to work on.

Once a goal is selected, the planner looks for operators that can achieve the
goal. An operator consists of a generators, pre-conditions and actions. Each
operator component consists of a set of propositions with variables and
constants. Given a selected goal, the planner uses Means Ends Analysis
\cite{NewellSimon} (MEA) to find a set of operators that can achieve that
goal. MEA finds the operators whose actions unify with the selected goal
implying the operator could achieve the selected goal. The planner selects a
single operator from this set of operators via some heuristic process. This
operator decision is a decision about how to achieve the goal. In the example
trace, two operators can deploy troops. The MOVE operator has the troops going
by themselves (driving on their trucks), and the SEND operator has the troops
being sent via some common resource (planes). The planner selects the SEND
operator because a previously tried MOVE operator failed. The MOVE operator
failed because of the ocean between the source and destination locations made
truck travel impossible.

Once an operator is selected, the planner propagates the goal-bound variable bindings to all the variables with the same name on the pre-condition side. The planner creates the set of possible bindings for the non-goal bound variables, by creating the cross product of all the possible values for each variable as defined by the operator's generators. The operator's generators provide all possible values of a particular type. The cross product of these possible values along with the goal-promoted values form the set of possible bindings for the chosen operator.

Figure~\ref{simple-planner} shows the planner selecting one of these bindings. This selection again can be heuristically guided. One of the most useful domain independent heuristics is to pick a binding associated with the smallest set of unfulfilled pre-conditions. An unfulfilled pre-condition is one that will not unify with the current state after being unified with the bindings. The unfulfilled pre-conditions get added to the set of goals as the algorithm recurses, and the smallest set heuristic, means the goal-set grows at the slowest rate possible. If no unfulfilled pre-conditions exist for a binding, then in the algorithm of Figure~\ref{simple-planner} the state is changed.  Changing the state \footnote{Stone and Veloso \cite{stonV95} show that postponing this changing of the state can be beneficial for some problem classes. However, whether the state changing is delayed or not does not affect this proposal.} means the planner's representation of the state is changed according to the actions in the operator. This modification ensures that all the actions of the operator are considered in the plan.

\subsection{Plane fleet, All Army}

This abstracts away from all location information in the planner. The planner considers the infantry battalions and planes as large aggregrate resources. The planner is looking for a sequence of operators that will describe how to deploy the troops. By abstracting away from the individuals, the planner gains in efficiency but as we will see, loses the ability to generate the plans that correspond to a satisfactory solution. This loss occurs because the only solution to the problem has the battalions split across different resources, with each component must take a different path (requiring a different plan) to get to its destination.

Figure~\ref{abs-solution} shows the plan generated when considering the problem at this high level of abstraction. The figure shows that planning considered both the MOVE and the SEND operators as possible methods for achieving each goal. The MOVE operators though were found to be dead-ends when no bindings could be found. This lack of bindings comes from not allowing the infantry to drive over the oceans. All the paths to achieve the goal cross the ocean, so some transport across the ocean must occur to achieve the goals. This ocean transport can be achieved by the SEND operators when the planes are bound to the transportation-resource.

The SEND operators

\begin{figure*}[b]
\begin{tabbing}
MM\=MM\=MM\=MM\=MMMMMMMMM\=MMMMMMMMMMM\\
\>\>\>\>\>{\bf Initial Goals}\\
\>\>\>\>\>Infantry battalion at City-1\\
\>\>\>\>\>Infantry battalion at City-2\\
\>\>\>\>\>{\bf Initial state}\\
\>\>\>\>\>Infantry battalion Inf-A at City-3\\
\>\>\>\>\>Infantry battalion Inf-B at City-4\\
\>\>\>\>\>c5s at City-5\\
\>\>\>\>\>c141s at City-6\\
\>\>\>\>\>City-3's airport can handle c141s\\
\>\>\>\>\>City-4's airport can handle c5s and c141s\\
\>\>\>\>\>City-5's airport can handle c5s and c141s\\
\>\>\>\>\>City-6's airport can handle c5s and c141s\\
\>\>\>\>\>City-7's airport can handle c5s and c141s
\end{tabbing}
\end{figure*}




 Figure~\ref{two-moves} shows the 

\begin{figure*}[b]
%\psfig{figure=figures/two-moves.ps} 
The left side has a more complex goal-tree.
\caption{Deploying two sets of troops.} 
\label{two-moves}
\end{figure*}


At this point the plan-sched planning algorithm starts to differ from the standard method. Rather than select a particular binding from the cross-product set, plan-sched breaks the elements of this set into {\it equivalence classes} defined by the operator's pre-conditions that don't match the current state. All the elements within a single class when bound to the appropriate variables leave the same set of pre-conditions unfulfilled. Since the unfulfilled preconditions form the new goals, all the elements of an equivalence class are associated with the same set of future planning goals.  


{\it I need a good simple example at this point. My current examples have the following problems 
\begin{enumerate}
\item deploying troops: The bushiness of the tree is too small. WHy not just generate all the alternatives, and then hand it over to scheduling? Also too much to explain.
\item One-way-rockets to three space-stations: Not sure what is cheating.
\end{enumerate} } 

Scheduling directly attacks this type of resource selection problem, within the context of a set of already known plans. Thus a planner could construct a set of resource independent plans for later scheduling. In essence, delaying the resource decisions until after plan creation. However, this large grained integration of planning and scheduling ignores the fact that the quality of the generated plan depends upon the schedule. Without some knowledge about resource contention, the planner itself can't make planning decisions that will improve the quality of the plan. {\it some aspect of the example} The planner could construct contingency plans for all envisioned scheduling difficulties however that approach produces possibly exponentially more work.  In contrast, a finer grained integration of the two tasks means planning can provide contingency plans only when required by scheduling. Thus reducing the {\it (by how much?)} number of contingency plans expanded while maintaining much the same scheduling flexibility in doing the resource selection. The fine grained integration also means planning could utilize the current scheduling information about resource contention when generating its plans, thus possibly creating more schedulable plans. This paper is a proposal to investigate the types of synergy that a fine grained integration between planning and scheduling might provide. 

To create plans for the scheduler, the planner must delay its resource selection.  Planners select resources by binding a particular resource to an operator parameter called a variable.  A simple planning algorithm is given in Figure~\ref{simple-planner}. This algorithm is similar to state space planners like Prodigy \cite{}. The arguments given in this section will be shown in Section~\ref{plan-space} to also apply to plan space planners, like UCPOP \cite{} with a few changes. The algorithm in Figure~\ref{simple planner} has 4 choice points. Its first choice occurs when it selects an unachieved goal from the goal-set. The goal decision is a meta-planning decision that determines how the planning should proceed. Once a goal is selected, the planner looks for operators that can achieve the goal. An operator consists of a generator part, a set of pre-conditions and an action part. Given a selected goal, the planner uses Means Ends Analysis\cite{NewellSimon} (MEA) to find a set of operators that can achieve that goal. MEA finds the operators whose actions unify with the selected goal implying the operator could achieve the selected goal. The planner selects a single operator from this set of operators via some heuristic process. This operator decision is a decision about how to achieve the goal. 

Once an operator is selected, the planner unifies the action with the goal, and propagates the variable bindings to all the variables with the same name on the pre-condition side.  The planner creates the set of possible bindings for the non-goal bound variables, by creating the cross product of all the possible values for each variable as defined by the operator's generators. At this point the plan-sched planning algorithm starts to differ from the standard method. Rather than select a particular binding from the cross-product set, plan-sched breaks the elements of this set into {\it equivalence classes} defined by the operator's pre-conditions that don't match the current state. All the elements within a single class when bound to the appropriate variables leave the same set of pre-conditions unfulfilled. Since the unfulfilled preconditions form the new goals, all the elements of an equivalence class are associated with the same set of future planning goals.  

These equivalence classes are important, because they define the set of values that scheduling can select from. They represent planning indifferent choices for this step in the plan. Planning indifferent means changing a choice from within the same equivalence class will mean that the plan doesn't have to change. However, the equivalence classes can become further fragmented by later preconditions that the set members particiapate with.  

Figure~\ref{simple planner} also shows another decision (Application) could occur, however for expository reasons we will address it later.  



This paper is a proposal to investigate the amount and type of variable binding processing that should occur during planning.  For some problems, simple arbitrary selection coupled with backtracking is the most cost effective approach to variable binding. For other problems, \cite{stefik and joslin} show propagating variable bindings in a constraint network can be worth the extra work over arbitrary selection. A planner using constraint propagation can discover dead-end planning paths via propagation earlier (with less work) than by just planning. Joslin \cite{joslin} also shows that the extra work entailed by constraint propagation is not worthwhile compared to the simpler arbitrary selection for some problems that are very similar to the situations where constraint propagation is worthwhile. This paper proposes to push this idea of doing more reasoning when binding variables, and investigate when this extra reasoning is worthwhile. 

The proposed extra reasoning done by the planning system will allow it to alter previous binding choices when conflicts appear. This capability is fundamentally different from constraint propagation. Both Joslin's and Stefik's planning systems use constraint propagation to detect impossible paths, but their planners use this information to start backtracking when infeasible paths are discovered.  This backtracking strategy optimizes for the case of the planner generating a new sub-plan that utilizes the new binding. However for logistics problems, the current plan might be just fine, it just has to occur with different bindings. The need to get the fire-fighting equipment to a location doesn't change, and the plan for how to achieve that goal (fly on a plane) might also not change, but perhaps a different plane could be used to get it there.  

Chronological backtracking is used in most planners because of its simplicity. However chronological backtracking's stack-like manner of creating and removing variable bindings also biases the planner against re-using a plan when a simple variable binding change occurs. A stack like binding strategy means a more recent binding will always change before changing a binding decided before it. This strategy works fine when the choice between bindings is truly arbitrary and doesn't depend on the current (and perhaps future) state of the problem solving. However, a more important binding is discovered 

The stack strategy also works when the choices can be correctly ordered with the most changeable choice being selected last. Search control rules \cite{Minton, Prodigy} can be used to create such an ordering. However, search control creates an ordering that is optimal only at variable binding time. Later in the problem solving, new information could affect the desireability of this binding choice. However, when using a stack strategy, a binding can only be changed if the problem solving finds a dead-end that the binding dependes on.  

new information that affects the binding choice.  To go beyond the ordering and stack based approaches, and characterize both the successes that can be achieved and the limitations of a more dynamic binding of variables. 

The number of contingency plans is smaller in the two pass system because every possible contingency has to be expanded. Even ignoring the explosion in possible plans due to variable bindings, planning still produces too many contingencies. A detailed analysis of the number of contingencies will be given later, for now consider planning your activities while on a 3 day business trip. At some time during the trip you have a goal of spending some personal time with a friend. When planning this goal, your planning system could allocate eating dinner with the friend for day-1, day-2 or day-3. Likewise a lunch meal is possible, but less preferable. A planning system would pick dinner for one of the days, in-effect binding the friend-personal-time variable to dinner on the chosen day, say day-1. Subsequent planning choices might or might not depend upon this choice. Later in this planning excercise, dinner on day-1 is discovered to be the only time available for some other required activity, and a conflict has arisen. One way to resolve this conflict is to recognize that the second required activity can't be achieved and start backtracking in the planner. Instead if a scheduler did the variable binding the scheduler would know of the initial three choices and the day-1 conflict. The obvious solution is to simply change the dinner to a different day. If any plans were dependent (like restaurant choices) were dependent upon the original choice extra planning would have to occur with the new choice. Rather than expand possible contingencies for decisions this planning/scheduling system changed those earlier decisions when appropriate, and re-planned from the new decision when required. This plan mutability associated with integrating a plan with later decisions is outside the capabilities of planning systems today. 

In addition, in a combinded system scheduling difficulties can be planned around. If, in the previous example, day-1 was picked for the dinner because it was the only day available when planning the dinner goal, then the conflict would still arise later. However, the resolution of the conflict requires changing an earlier (upstream) planning alternative, rather than changing a plan indifferent variable binding and regenerating the dependent (downstream) parts of the plan. Upstream planning decisions were made before a decision, while downstream planning decisions were made afterwards. In the example, the first available planning decision to change is the decision about a dinner meeting. This could be changed to a lunch meeting. In general some more work also could be done to ensure that the reduction in utility of a lunch meeting is smaller than the reduction of changing one of the other dinner appointments, and scheduling the dinner with a friend later that week. This type of general task changing when scheduling problems arise is outside the capabilities of scheduling systems today. 

The logistics domain contains many planning problems like that above, where the plans have to be coordinated to meet some group performance criteria. Typically the problems of interest are large military deployments, coordinated activities (building a house) or emergency situations (like getting doctors to an earthquake site, or forest fighters to a fire, or oil spill technology to an oil spill). This paper is particularly interested in the problems that don't have pre-known plans.  Launching a space-shuttle is an example of a large logistic task that has been so well analyzed that almost all the contingency plans have been expanded. Coordinating each space shuttle launch is difficult, but mostly consists of scheduling the resources to meet a launch window. When executing such a schedule, problems arise and planning around those problems may have to be done, but little planning is required in coming up with the initial schedule. In contrast, the military deployments and emergency situations all require more up-front planning effort, and this planning effort is constrained by both the novel situation and the available resources. This dual constraint is the source of the planning/scheduling interactions and is what requires the extra complexity of a combined system. 

Linking a planner and scheduler address the logistics domain's functional needs, but how to handle the extra complexity while generating viable good schedules is unclear. The research issues in such a system include finding a common representation and a method to control the two interacting NP-Hard processes. Another important research issue involves deciding when doing the extra variable binding work is worthwhile.  

A common representational scheme provides the planner and scheduler a language to describe the state of the problem solving and each system's current state. The decisions made by a process have to be immediately and completely available to the other process. Once a method of interaction is available, the important issue becomes ensuring the synergistic application of both systems. 

Assuming a single threaded system means that only the planner or the scheduler can be running at any one time, using both systems implies switching between them via some switching strategy. The optimal switching strategy would pick the system that could provide the most benefit for the least cost. Since these are NP-Hard problems, the best that can be done is to use an estimate of the cost and benefit as an heuristic to guide the switching decision. Switching from planning when the planning search branching factor is high is an example of an heuristic strategies that emphasizes planning cost. This search topology heuristic assumes that scheduling will help limit the planning possibilities, so that upon returning to planning either: fewer paths are available, or the confidence in making an arbitrary choice is high. Many other possible heuristics are possible, and each can be measured for effectiveness by seeing how well a schedule created under that heuristic can meet its quality requirements. 

This paper proposes a combined system that delays the variable bindings in planning as long as possible by keeping the bindings as sets. This delay allows the scheduling system to use the set of possible plan indifferent choices and thus make a more informed choice. It also allows the scheduling system flexibility in altering a previous variable binding choice to allow a later decision to bound. The modified plan doesn't need to change, as long as the previous variable binding is altered so that the variable is now bound to a different choice from the plan indifferent set. To keep the variable binding process under control, a supervisory process decides whether to continue trying to improve the variable bindings, or to improve the plans. The supervisory process uses a simple heuristic cost/benefit model to determine whether to search for a new plan or to search for a better set of bindings. 

The planner and scheduler are linked through a constraint propagation system. The initial goals are represented as nodes in a constraint network. As planning decisions are made, the constraint network changes to represent the planning decisions. Scheduling works within the constrained nodes to do variable assignment. By including the nodes in a constraint network, the implications of both binding and relaxing decisions can be propagated to reduce or expand later search choices. This methodology gives the most flexibility at a relatively cheap cost. 

	\subsection{Domain analysis} 

	\subsection{} Integrating a new task with a set of current commitments involves both recognizing how the current commitments constrain and possibly enhance choices for achieving the new task, and recognizing the situations where the previous commitments should be reconsidered. This paper proposes studying this integration scenario within the context of large logistical problems like building a house or planning a military exercise. In these problems, new tasks arise from either execution problems, a better understanding of the situation, and/or refining goals. Each individual task is relatively simple, and consumes only a fraction of the available resources. However, the integration of a new task with the existing tasks is a complex problem because the set of resources may not be adequate to completely meet a set of conflicting overall demands (e.g. due-date and quality) placed on those resources. This paper looks at the planning of the new task within the constraints of the existing tasks and possibly adjusting those constraints when necessary.  

The key aspect of these problems is that many of the planner's choices are underconstrained making the choice arbitrary. The planner's initial choice though reasonable at that time, might be unreasonable in the future. For example, giving some carpenters a new task of fixing a rickety floor by Friday, conflicts with the task of painting some walls on Friday that the carpenters were to install on Thursday. However, if the choice of Friday for painting the walls was arbitrary, and no other task, like showing the house on Saturday, constrains the painting to occur on Friday then it could occur later. Though changing the painting to occur on Monday may or may not be simple, it is a choice that the planner could make. To recognize that the painting could be moved, the planner needed to know how the painting was temporally constrained. To know if the painting should be moved the planner needs to balance the expected cost of moving the task against the expected cost of other solutions.  

This proposal describes linking a planner and scheduler, in a system called PLAN-SCHED, to address these exact problems. Given a new task, the planning system will generate a plan for completing the task. This plan will be constrained at each step by the current set of already planned tasks. The scheduler operates as the decision procedure for the planner by ordering the set of planning choices according to a set of preferences. In addition, if no choices exist, then the scheduler will assess whether to create new choices for the planner. As in the example above, one method of creating a choice is by changing a previous decision, another method is by relaxing a constraint (say due-date). If creating a choice is reasonable, then the newly created choice will be presented to the planner and, if necessary, a new task will be added for the planner to handle the implications of the change (e.g. call the painters to reschedule). 

The major source of power in PLAN-SCHED is that the planner does not have to backtrack through many of the decisions. Instead, many arbitrary decisions are changed in a consistent manner without the planner's intervention. Only the leaves of the planner's goal tree can be handled in this way. If later planning decisions depend upon a particular earlier choice in a way that can't be represented in the constraint network, then if the choice is changed the dependent decisions must be re-decided. For example, when planning to send soldiers on a mission, the destination airport must first be secured. Securing an airport requires planning for that specific airport. Changing the airport will require new planning for the new airport. The choices that can be changed independently of the planner are called {\it mutable} choices, otherwise the choice is {\it non-mutable}. PLAN-SCHED classifies a choice non-mutable when a later planning step depends on the choice in a way that changing the choice would change the plan. 

To determine whether a plan step depends upon a previous choice, the planning choices are grouped into sets. The elements of a particular set are considered indifferent by the planner. This keeping of sets is similar to that done by \cite{} and by itself can improve the performance of the planning activity. When a plan step is proposed that includes an element of a set, the planner creates a new set with the original set elements that could also be included in the plan step. At any time, the elements of a particular set represent the set of consistent values from the planner's point of view and any choice from this set is considered arbitrary. These arbitrary choices are made by the scheduler according to its preferences, and can be changed without changing the plan. 

Changing even a mutable choices though may not be free, PLAN-SCHED has an overall supervisory process that uses a cost and benefit model for each component to decide where to spend its computational resources, and control the decision process. This supervisory process works in a simple decision theoretic way to minimize the costs and maximize the benefits. As an example, the supervisory process looks at the tradeoff of re-planning after changing a non-mutable choice and re-scheduling after changing a mutable choice. 

This proposal investigates using such a planning/scheduling framework to solve large ill-defined logistic problems. These problems consist of a large set of relatively independent tasks that interact mainly on resource issues. However, the plans for doing the tasks are not known apriori. There may or may not be enough resources to do all the tasks, but any particular task is underconstrained with regards to resources. 





\section{Plan-Sched components} 

Plan-Sched is implemented using technology from both Prodigy (a planner) and Ditops (a scheduler). These two system have been brought together under a supervisory process shown in Figure~\ref{sys-arch}. Figure~\ref{sys-arch} shows the constraint propagator (which is a Ditops component) as a separately accessible component. In fact, Ditops also provides the framework for the supervisory process.  

	\subsection{Supervisory Process} 

A supervisory process links the planner and scheduler within PLAN-SCHED and decides where to spend its computational resources. This supervisory process determines whether to continue planning, extend the constraint propagation, change a previous arbitrary decision, change a previous arbitrary decision that involves re-planning, or change a committed plan. To make these decisions the supervisory process has to determine the mutability difference of planning choices, and have a cost and benefit model for each process. The cost/benefit model estimates the expected cost and benefit of pursuing a particular process and the supervisory process simply picks the best process. Each of these processes and their corresponding cost/benefit models will be described in more detail in the next section. 

	\subsection{Planner} 

\section describing Prodigy and how it integrates with constraint propagation and scheduling. 

		\subsubsection{cost/benefit model} 	\subsection{Constraint Propagation} 

\begin{figure*}[b]  %\psfig{figure=figures/constraint-ex.ps}
\caption{Constraint Satisfaction Problem}  
\label{constraint-graph} 
\end{figure*}  

Constraint Satisfaction problems have a goal of finding a problem state that satisfies a given a set of constraints. Assigning time on a resource  is an example of a constraint satisfaction problem as are cryptarithmetic puzzles \cite{}. A constraint satisfaction problem is usually defined as a graph where the nodes represent variables and contain sets of possibly valid values. The edges of the graph represent the constraints between the variables. Constraint propagation is a technique for ensuring that the set of values for a variable are consistent with the constraints.  

Figure~\ref{constraint-graph} shows the graph for a simple constraint problem from Mackworth \cite{} that has 5 nodes with not-equal constraints between the nodes. Nodes A and B each have 2 possible values {\it x,y}, while node C could have 3 possible values {\it x,y,z}. 

		\subsubsection{cost/benefit model} 	\subsection{Scheduler} 

Describe preferences and changes to mutable choices. 

		\subsubsection{cost/benefit model} 

\section{Example} 

PLAN-SCHED has been tested on a small logistic domain where planning by itself is still intractable due to the large number of possible under constrained choices. In these tasks, PLAN-SCHED used an arc-consistent constraint propagator \cite{} and made no decisions about extending the propagation. Its model  





process also  

this difference in the mutability of choices  At each planning choice point, the choices have been ordered by a set of preferences. However, in planner constructs the choices  

constrains the The planner's decision The existing tasks were also possibly under-constrained in there resource assignments. The 

In many logistical problems, like building a house, the goal is achieved by creating a set of relatively independent tasks and then scheduling these tasks over a period of time to use some common resources.  



This paper proposes studying the integration of the planning and scheduling activities to determine and take advantage of any synergies from such an integration. A synergistic integration would create both better schedules (shorter time to reach goal or better utilization of resources) and better plans (more likely to be achieved). The planning to achieve a goal alternates between the planning procedure and the scheduling procedure depending on which process is currently more effective. The entire process can be thought of as a dual search procedure, where each search procedure provides constraint for the other.  At any time, the most effective procedure provides the most constraint, and eliminates the most choices, in this dual search.  Deciding when scheduling is the most effective procedure to execute, and similarily when planning is the effective procedure is the subject of this paper. Since switching is not free, deciding when to switch is also addressed. 

The key to the dual search is knowing which procedure will currently provide the most constraint. Once constraints are known then utilizing those constraints through some constraint propagation procedure (like arc-consistency) is cheap. As an example, Assume a person (called Sue) has a goal of taking a weekend skiing vacation from Pittsburgh to either Colorado or Vermont. How does one start the planning process? If Sue ignores her resources, then she might first plan the trip to Colorado and then the trip to Vermont. Making the decision based upon how hotel and plane availabilities fit her current schedule. However if Sue knows she doesn't have the money for the plane fare, then she can cheaply eliminate a whole portion (the Colorado trip) of the planning process. Sue used knowledge about a required resources to limit her planning effort, before the planning recognized it was required. Instead she started with some simple scheduling of her resources, and recognized that she would have to fly to Colorado and that required more money than she had. 

It seems we have a chicken-egg problem, since how did Sue know that she had to fly to Colorado? Why did she first consider her limited money resources rather than her busy time resources? This paper solves these problems through a set of planning abstraction levels. In the case of Sue, she plans out both trips at a very high level of abstraction, that lets her notice the plane trip to Colorado. Scheduling her resources then eliminates that possibility, so that any further effort is concentrated on the Vermont trip. The key issue addressed here is how to best utilize these abstraction levels. (Perhaps also to learn them). 

In the example above we can think of both the planning and scheduling processes as posting constraints on the available problem solutions. The initial abstract planning process takes all of Sue's possible activities and constrains her to consider only those activities that could help her achieve the goal of a skiing weekend. These activities require resources for their achievement. The scheduling process looks at assigning resources to activities and in effect constrains the set of Sue's possible activities to those that can utilize the available resources (can't go to Colorado). Despite the differences in the algorithms (which will be justified later) this view of both processes posting constraints on the same problem provides the basis for communicating information about the problem from one process to the other. 

Joslin \cite{Josl95} treats planning as posting constraints in his Descartes system. Whenever Descartes postpones making a planning decision, it posts all the known constraints about that decision. Joslin shows that propagating these constraints can, in some problems, substantially reduce the planning search space, over waiting for the planning system to make a decision about the constraint. This power comes from considering some aspects of all the constraints on a decision early, rather than handling the constraints one at a time.  Joslin shows that handling the constraints in any pre-determined sequential order will cause problems because it is impossible to determine in advance the constraints that indicate this decision is a dead end and shouldn't be pursued.  However, Joslin also shows that always handling the constraints can be prohibitively expensive, because the effort to process the constraints can grow exponentially for a small number of planning decisions, and it is just easier to make the planning decision. 

The planning/scheduling system described in this paper fits somewhere between Joslin's bounds. It uses planning to make a set of cheap decisions at an abstract level, and then scheduling to propagate the constraints associated with those decisions. The results of the delayed constraint propagation can be: no feasible solution, multiple feasible solutions or a unique solution. No feasible solutions, means that planning must come up with a new plan. Multiple feasible solutions means some further planning decisions must be made. A unique solution means single values have been picked for the unbound (abstracted over) variables, and the problem is solved.  

The key to this planning/scheduling system is deciding when planning is cheap. The proposed method for making this decision is a threshold on the number of possibilities for assigning values to variables. This choice was made because in our chosen domain of logistic problems, the cost of assigning consistent values to such variables is known to be expensive \cite{smith,fox}. This expense differs from what Joslin experienced because it comes not from the constraints created within a plan, but rather from the many constraints on these variables that exist in the initial state independently of the currently being constructed plan. The variables whose bindings are being postponed could either have continuous valued domains (e.g. start time) or have a large number of possible discrete values (e.g. which flight to take). The insight here is that rather than instantiate all the possible values, the planner will carry the values as a set, called a {\it binding-set}, and then use scheduling to constrain the picking of values when the values are actually needed. 

In carrying values as a set, this work is similar to \cite{anurag's work, and AIPS-94 paper}. However, the intention of that work is to delay the selection of values until the selection was forced. The intention here is to use a set as a type of abstract object that represents all the objects and carry along with the sets the constraints generated by planning on the values in the sets.  In the previous work, the constraints on those values were eagerly applied always giving a consistent set of values in the sets. Instead this paper proposes to delay the application of the constraints on the sets as long as the planning process can continue cheaply. 

This delay in creating consistent sets means some unnecessary planning work will occur, because planning choices that lead to dead ends will not be recognized until the constraints are propagated. The planning work done on these dead end paths will have to be thrown away and other paths taken.  The backtracking choices are guided by the hopefully reduced set of choices provided by the scheduling system's constraint propagation. In addition, when scheduling can provide information, individual planning decisions are expected to be cheap. Thus the thrown away work should be small. However, this delay does show that the system will cycle, between planning and scheduling each providing constraint towards finding a solution. 

If a problem includes a partial plan, a set of constraints, and initial data, the planning/scheduling system is flexible enough to start solving it with the scheduling process. Factory floor scheduling with a strict process plans and orders is a degenerate case of the aforementioned cycle where the initial process is scheduling and the planning process is simply to pick a different previously known process plan for a part when scheduling finds the current plan infeasible.  

PLAN-SCHED has been partially implemented using {\bf Prodigy}\cite{VeloCPBFB95} a case-based planning tool and {\bf Ditops}\cite{Smit95},\cite{SmitLB96b} a dynamic scheduling tool. Within PLAN-SCHED Prodigy takes a Goal description in the logistics domain and creates a plan for achieving that goal. This plan has abstracted away from resource and time considerations. DiTops is then invoked to test how the created plan integrates with all other current plans in the usage of the limited resources. If the plan integrates well, then it is accepted. If scheduling problems occur, then the current strategy is to go back and attempt to re-plan for the same goal taking into consideration the constraint information provided by Ditops. 

PLAN-SCHED currently creates plans for military missions and doesn't explicitly maintain binding sets. Instead the planning knowledge generally abstracts away specific bindings in the large sets. However, a user can specify in the goal specific bindings from a set. For example, the user could request that a brigade from the 81st airborne go to Saudi Arabia, instead of simply asking that an unspecified paratroop brigade go to Saudi Arabia. The user, who is very familiar with these different levels of abstraction, finds this specification capability useful.  However, since the planner doesn't currently have a representation for the values in the sets, the interaction between the planning and scheduling components is limited. 

PLAN-SCHED uses an estimate of how much continuing planning will cost to determine if scheduling should instead be done. In a similar manner, PLAN-SCHED needs to be able to estimate the scheduling cost. The expected scheduling cost is a function of how the resources required by the current plan steps interact with the time-varying utilization of those resources. In general, the higher the utilization of a resource, the harder it is to schedule. The actual equations for the scheduling cost include other factors (like cost of constraint propagation) and will be given later. The expected scheduling cost provides both an estimate for planning choices, and for deciding when to switch from planning to scheduling. Planning can use the expected scheduling cost in its decisions as an estimate for how likely a particular choice will be schedulable and thus not a dead-end. However, the main use of the expected scheduling cost will be to compare against the expected planning cost to decide when to switch. 

PLAN-SCHED also needs to consider the benefits of doing the search via either planning or scheduling. It could be that costly planning is more useful than cheap scheduling or vice versa. PLAN-SCHED defines the expected ``usefulness'' of a process as the amount of expected constraint it will supply to the sear Determining this metric is complicated because backtracking can remove constraints. For example, picking a flight greatly narrows the number of possibilities for Sue in planning/scheduling her skiing vacation. However, if she has to revisit the flight decision then all work based upon that decision might be thrown away. In this case, the benefits of making any particular flight decision is small, because it may not be reconsidered.  

However, these choices can be delayed until  

This method naturally distinguishes variables with continuous valued domains from variables with a discrete valued domain. The number of possible choices in a continuous valued variable is large, and any limitations  



The proposed planning-scheduling system takes a large number of high-level goals that interact over a fixed set of resources and plans/schedules them in a serial fashion. Before committing to a plan for a particular goal, the scheduling system has ensured the feasibility of achieving the plan's goal given the resources and all the previous commitments.  

In addition, by maintaining the large normal case computational gains can be achieved by separating these tasks with only a modest increase in worst case computational complexity.   

	\subsection{Why is it important} 

The techniques, described in this paper, are aimed at helping to solve the problems that arise in large unique logistic problems. Examples of these problems are: Organizing the medical teams and support equipment to respond to a natural/man-made disaster, Organizing the teams and equipment to fight a forest fire, Organizing the troops and equipment to accomplish some military goal and Organizing the activities to build a particular house. A deployment plan for these logistic tasks, though is non-trivial to create because of the large number of simultaneous and interacting plan components. Also in many cases a complete plan has limited viability because new information can be received that invalidates portions of the plan. Ignoring the difficulty in constructing such a plan, the timely deployment of the correct resources in these problems can save lives and/or money {\it any citations??}. 

	\subsection{Example-multiple-one-way-rockets} 

We will use a simple variation of the one-way rocket where we have 15 objects each of which has a destination of 1 of 3 space-stations. To get to a space-station, the object has to get to a rocket, and take the rocket to the station. Unfortunately each rocket can only reach one station, and can only be used once. To get to a rocket, the object has to be put on the single truck, and then taken off the truck once the truck is at the rocket. The path taken by one of the objects should be: Pick-up by truck, Move truck to rocket, Put-down from truck, Load onto rocket, Unload from rocket. However, since we only have 3 rockets, the objects have to be put on the right rocket. A more detailed description of the problem is given below.  

Though somewhat artificial, this is an extremely hard planning problem. It's difficulty comes from the planner having to backtrack for each object whenever the rocket goes to the wrong space-station. This backtracking comes from the planner not being able to recognize that a rocket already has objects going to another target. Thus an object for space-station B could be unloaded onto a rocket with objects for other space-stations. Backtracking is the only option to remove this mistake in classical planners. However, It is possible to use the sets described before to make this problem easier. 



Objects A-1, A-2, A-3, A-4, A-5,
       B-1, B-2, B-3, B-4, B-5,
       C-1, C-2, C-3, C-4, C-5 

Space-stations A, B, C 

Earth Locations loc-1, loc-2, Launch-pad 

Truck - truck at Launch-pad 

Initial State -  A-1, B-1, C-1 at location loc-1 A-2, B-2, C-2 at location loc-2 R-1, R-2, R-3 at location Launch-pad 

Goal State -  A-1, A-2, at location space-station A B-1, B-2, at location space-station B C-1, C-2, at location space-station C 

Operators 

Truck-Load (truck object)  (pre-condition truck-location == object-location)  (post-condition (object-location on truck)) 

Move-Truck (loc-1, loc-2)  (pre-condition truck-location loc-1)  (post-condition truck-location loc-2) 

Truck-Unload (object trucks-loc)  (pre-condition (object-location on truck)  (post-condition (object-location on trucks-loc)) 

Rocket-load (rocket object)  (pre-condition rocket-location == object-location)  (post-condition (object-location on rocket)) 	 Rocket-Unload (rocket object rockets-loc)  (pre-condition (object-location on rocket)  (post-condition (object-location at rockets-loc)) 

Move-Rocket (Rocket)  (pre-condition rocket-location launch-pad)  (post-condition rocket-location loc-2) 

Prodigy execution 

54 Rocket-Unload operators, 1 for each choice of an object
                        and   rocket at a space-station  

Pick one A-2, R-1, ss-A 

9 Move-Rocket (R-1 ss-A) 

6 Rocket-load operator R-1 A-2 

6 truck-unload (A-2 launch-pad) 

3 move-truck (loc-2 launch-pad) 

6 truck-load (loc-2 A-2) 

3 move-truck (launch-pad loc-2) 

If we add search control to only pick items on the path to some goal, we still get an exponential problem. The issue is we need to load up everything going to space-station 2 (for example) and then shoot the rocket at it. 

In set notation we get 

Goal
         (A-1 A-2) (B-1 B-2) (C-1 C-2)
             (ss-A)    (ss-B)    (ss-C) 

rocket-unload (A-1 A-2)     (B-1 B-2)     (C-1 C-2)              (R-1 R-2 R-3) (R-1 R-2 R-3) (R-1 R-2 R-3)              (ss-A)        (ss-B)        (ss-C) 

Move-Rocket doesn't change the sets because all the rockets and space-stations                                             have the same attributes. 

Rocket-Load doesn't change the sets because all the rockets and objects                                            have the same attributes. 

truck-unload doesn't change the sets because all the rockets and objects                                            have the same attributes. 

move-truck divides the sets distinguishing objects on their location (A-1)         (A-2)         (B-1)         (B-2)         (C-1)         (C-2)  (R-1 R-2 R-3) (R-1 R-2 R-3) (R-1 R-2 R-3) (R-1 R-2 R-3) (R-1 R-2 R-3) (R-1 R-2 R-3) (ss-A)        (ss-A)        (ss-B)        (ss-B)        (ss-C)        (ss-C) (loc-1)       (loc-2)       (loc-1)       (loc-2)       (loc-1)       (loc-2) 

truck-load doesn't change the sets 

move-truck doesn't change the sets. 

We now have a problem of assigning a rocket to each trip. Part of the problem is that we have more trips than rockets, and that there is an implicit constraint in that a rocket used for one trip can't be used for another. We haven't applied any operators or changed the planner's state. We have just done a set oriented Means Ends Analysis (MEA) from the goal to the initial state. 

As we start to apply the planning operators, the s {\it this is not the example I want at this time.} 

	\subsection{Example-Multiple-battlefield actions} 

This example is a variation on the problem of securing an airport and surrounding area as a prelude to using the airport for a military operation. The example involves securing 3 different airports at about the same time. Securing one of the airports is functionally independent from securing the other airports. Knowing about this independence makes this problem fit into PLAN-SCHED's area of expertise. Later we will discuss the issues in recognizing this independence.  

The airport securing example contains 3 parts each increasing in complexity. In the first part, enough resources exist to secure each of the airports, however not enough resources exist to simultaneously transport the securing forces to all 3 airports. This part has contention over transportation resources.  The airports are far enough away from each other that the same aircraft cannot be simultaneously used in two of the securing operations.  The second part of the example reduces the resources available to secure the airports, forcing the reuse of some of the resources used in an earlier securing operation. The third and final part, moves the airports closer together creating opportunities to simutaneously use some of the same securing resources (such as fighter planes) in two different securing operations. Figure~\ref{airport-secure} shows all 3 parts of airport-securing example. Notice most of the example doesn't change between the parts. 

The problem presented in Figure~\ref{securing-mult-airports} is a simplification of a more complex planning/scheduling problem generated by the FORMAT system as a demonstration of the use of planning in retrieving cases. The details left out are not critical to the functioning of the planning/scheduling system but distract from a simple presentation. 

The basic flow in this example is to plan until scheduling seems to be likely to be useful in recognizing a dead-end. This example uses a capacity criteria for deciding when scheduling had a high likelihood for terminating a planning path. If an operator is of activity-type transport, then the variable associated with the agent attribute is assumed to be a schedulable resource. Given the set of values bound to a resource variable in an operator, and the time-bounds for that operator we can calculate an available capacity for doing the operator. This available capacity might be different for different types of cargo. In this example, if the required capacity for any cargo type is within 80\% of the available capacity then scheduling is done to ensure that enough capacity actually exists. The number 80\% is strictly used for expository purposes. 

This example uses some domain based abstraction. The knowledge that some operators represent transport activities, and others more general activities is used in this example. 

The set of bindings are always drawn from a constrained set of possible bindings. The possible bindings are constrained by previous choices for bindings. If the set of bindings is 0 over some time-span, then we go look and see if we can generate some bindings. 



\begin{figure*}[tbp] 
\begin{verbatim} Goal - maintain air-superiority over Sarajevo airport by 1/15       maintain air-superiority over saudi airport    by 1/22       maintain air-superiority over kuwait airport   by 2/2 

Current State -     3 squadrons (A,B,C) of F15s at Mcclellan Air Force Base (PRJY)      F15's missions include air-superiority     5 C5s at Mcclellan Air Force Base (PRJY)    5 C5s at Grissom Air Force Base (CTGC)      C5s can carry 30 tons of Bulk Cargo and                    40 passengers       5 C141s at Mcclellan Air Force Base (PRJY)    5 C141s at Andrews Air Force Base (AJJY)      C141s can carry 10 tons of Bulk Cargo and                      140 passengers       Infantry battalion A at Ellsworth AFB (FXBM)    Infantry battalion B at Andersen AFB (AJJY)    Infantry battalion C at Boise AFB (BXRH)      An infantry battalion consists of          500 soldiers and 100 tons of equipment         The equipment is mostly enough trucks to move           the battalion     Hawk battalion A at Ellsworth AFB (FXBM)    Hawk battalion B at Andersen AFB (AJJY)    Hawk battalion C at Boise AFB (BXRH)      A hawk battalion consists of          500 soldiers and 60 tons of equipment         The equipment is mostly enough trucks to move           the battalion     Security Force A at Ellsworth AFB (FXBM)    Security Force B at Andersen AFB (AJJY)    Security Force C at Boise AFB (BXRH) 	  A security force consists of          150 MPs.     Dog Team A at Ellsworth AFB (FXBM)      A dog team is treated as          25 soldiers         25 dogs (same as 300 lbs of bulk).     Terrorism threat at Sarajevo    Weapons-smuggling threat at Saudi    Current date is 1/1
\end{verbatim}
\caption{Example of securing multiple airports.}  
\label{securing-mult-airport-state}
\end{figure*}  

\begin{figure*}[tbp] 
\begin{verbatim} Operators   Deploy (air-unit from-location to-location)     (:activity-type transport :agent air-unit)     preconditions        air-unit is deployed at from-location        (SAME-END (to-location is a secured airport))     postconditions        air-unit is deployed at to-location   Send (ground-unit transportation-resource from-location to-location)     (:activity-type transport :agent transportation-resource)     preconditions        ground-unit is deployed at from-location        transportation-resource is deployed at from-location        from-location is a location compatible with transportation-resource        to-location is a location compatible with transportation-resource     postconditions        transportation-resource is deployed at to-location        ground-unit is deployed at to-location   Move (transportation-resource from-location to-location)     (:activity-type transport :agent transportation-resource)     preconditions        transportation-resource is deployed at from-location        from-location is a location compatible with transportation-resource        to-location is a location compatible with transportation-resource     postconditions        transportation-resource is deployed at to-location   Secure-no-smuggling (airport)     (:activity-type operation :effective-after 3 days :expected-duration 3 days)     preconditions        internal-security-force of police is deployed at airport        airport is within country and not known smuggling area        external-security-force-1 capable of anti-airforce activities                is deployed within country        external-security-force-2 of standard troops                is deployed within country     postconditions        airport is secured   Secure-smuggling (airport)     (:activity-type operation :effective-after 3 days :expected-duration 3 days)     preconditions        internal-security-force of police and dogs is deployed at airport        airport is within country and known smuggling area        external-security-force-1 capable of anti-airforce activities                is deployed within country        external-security-force-2 of standard troops                is deployed within country     postconditions        airport is secured   Support-superiority (location air-unit)     (:activity-type operation :effective-after 1 day :expected-duration ongoing)     preconditions        air-unit is at location and capable of superiority        location is an airport     postconditions        location has air-superiority
\end{verbatim}         
\caption{Example of securing multiple airports.}  
\label{securing-mult-airport}
\end{figure*}  

The goal in Figure~\ref{securing-mult-airports} shows that we want to maintain air superiority over 3 airports. Air superiority is a military term that means the only airplanes flying are those the military wants to be flying. Superiority requires constant maintenance and checking by aircraft in the area, and an airport that the interdicting aircraft can use. This airport must be {\it secured} before a military aircraft can land there. Securing an airport requires a security force, and backup forces in the area to protect the airport from air and ground threats.  The composition of the security force itself depends upon whether the airport is a site for weapons smuggling. If weapons smuggling has occurred at an airport, then dogs accompany the security force to help detect weapons. The security force, the backup forces and the aircraft all have to be transported to the appropriate locations, and all these activities should occur before the due-date. PLAN-SCHED attempts to create a plan and schedule that will acheive these goals. 

The current state in Figure~\ref{securing-mult-airports} shows a set of forces that can be used to acheive the goals. The state also includes a set of known facts about the world (e.g. the current time). These facts guides PLAN-SCHED's choices. 

The operators in Figure~\ref{securing-mult-airports} describe the possible activities that could be used to acheive the goal. The operators are augmented with some temporal and type information. {\it Transport} type operators have the time from starting the operation until the effects can be assumed is dependent on the values of some of their parameters (in particular the to-location and the from-location and the trasportation resource). For example, taking a jet from the Eastern US to Europe is faster than taking a jet from the Eastern US to Japan, simply because the first trip is shorter. In constrast, {\it Operation} type operators have a duration that is considered independent of their parameters. In Operation type operators, the expected duration is simply given.  

The operators also include temporal information relating the pre-conditions to the effects. The default relation is for the pre-condition to be fully in effect {\it before} starting to count time for the effect.``Fully in effect'' means the operator that asserts the pre-condition must have been in effect for a temporal interval the length of its ``effective-after'' parameter in the case of Operation type operators. Transport operator's effects are effective after an interval associated with the distance the transportation occurs over. For example, passengers have to be at the airport before flying to their destination. Since the passengers arrival at the airport is modeled as an effect of a Transport type operator, the schedule must include the transportation time to the plane.  

The deploy operator shows that in certain cases the relationship of a pre-condition to the effects is better modeled by assuming they end at the same time.  This type of relationship is called a {\it same-end} relationship. This type of relationship is better for the deploy operator because it allows the flying of the planes to overlap the securing of the airport. This may not make much difference for fast planes. However, if we were instead modeling ships and ports, then having a ship start a 2 week journey while the port was being secured is a better model than making the ship wait for the port to be secured. 

		\subsubsection{execution trace} 

\begin{enumerate}
\item Starting from the goal 3 copies of the Support-superiority operator are instantiated, one for each of the 3 goals. Each of these operators is instantiated with a set of 3 possible choices for the interdicting squadron. 

\item We prefer (via a control rule) working on the goal with the shortest deadline, and so we pick the Sarajevo goal to expand. 

\item The expansion leads us to the deploy operator. The deploy operator has the following choices for its parameters
\begin{description} 
\item[air-unit] - (F15-A F15-B F15-C) 
\item[from-location] (Sarajevo Saudi Kuwait Ellsworth AFB Andersen AFB                        Boise AFB Mcclellan AFB) 
\item[to-location] (Sarajevo Saudi Kuwait Ellsworth AFB Andersen AFB                        Boise AFB Mcclellan AFB)
\end{description} 

\item The choice of Sarajevo for to-location is made by preferences. 

\item Now we come to our first real choice. Do we pick a ``from-location'' and thus allow expansion of the ``air-unit is deployed at from-location'' precondition of DEPLOY? Or do we expand the ``(to-loc is a secured airport)'' precondition. Using whatever cost models we'll pick one. Lets say we decide to bind the ``from-location''.  

There is a planning cost to binding the from-location to any other location than Mcclellan AFB. Thus to possibly reduce this cost we bind the from-location to Mcclellan AFB. 

Now we can expand the (to-loc is a secured airport) precondition. 

\item We again have a choice whether to pick the Secure-no-smuggling or Secure-smuggling operators to implement the securing of the airport.  The Secure-no-smuggling operator is the correct choice, but the planner has no way to know that it can't achieve the precondition of weapons-smuggling.  Perhaps someone on the street knows. However, choosing Secure-smuggling turns out to be a dead-end because no operators can achieve the weapons-smuggling pre-condition. Also perhaps much planning search will occur before the dead-end is noticed. For expository reasons we will pick the right operator, Secure-no-smuggling. 

\item We now have a choice of which pre-condition of Secure-no-smuggling to expand. All three have to do with moving a force to the airport, so a simple look ahead cost model won't help. Likewise committing to a choice from an open set doesn't help. Picking at random we expand getting an internal-security-force to Sarajevo.  

\item We notice that the Send operator is the only operator that can get the internal-security-force to Sarajevo. However it requires a transportation-resource, and to and from locations. Using the same reasoning as in step 5, we can bind the to loc to Sarajevo and ignore sending the internal-security-force elsewhere. This does not mean the trip is direct, just that the last leg ends at Sarajevo.  

Unfortunately no transportation-resource is at any of the air force bases where the security-force are located. Do we send the security force to the transportation resources, or do we send the transportation resources to the security-force? We also have to use more than one transportation resource, since the security force is 150 people and the largest plane seats 140. The number of resources required will depend upon the type of resources allocated. Planning could attempt to make progress on some of these goals. However, scheduling can provide constraint more efficiently at this point, because the issues don't revolve around the ordering of actions but rather the allocation of resources.  

Scheduling allocates resources, and for this problem it evaluates the options available for the planner to pick and selects some bindings. We currently have the following variables and sets of values:
\begin{description} 	\item[operator-choice]  ({\it SUPPORT-SUPERIORITY-(dd 1/15)} SUPPORT-SUPERIORITY-(dd 2/2) SUPPORT-SUPERIORITY-(dd 2/15)) 	\item[binding-choice SUPPORT-SUPERIORITY loc] ({\it Sarajevo} Saudi Kuwait Ellsworth AFB Andersen AFB                        Boise AFB Mcclellan AFB Grissom AFB Andrews AFB) 	\item[binding-choice SUPPORT-SUPERIORITY air-unit] (F15-A F15-B F15-C) 	\item[binding-choice SUPPORT-SUPERIORITY time] (AFTER 1/1 BEFORE 1/15) 	\item[pre-condition SUPPORT-SUPERIORITY] air-unit is at loc 	\item[operator-choice] (DEPLOY) 	\item[binding-choice DEPLOY air-unit] - (F15-A F15-B F15-C) 	\item[binding-choice DEPLOY to-location] ({\it Sarajevo} Saudi Kuwait Ellsworth AFB Andersen AFB                        Boise AFB Mcclellan AFB Grissom AFB Andrews AFB) 	\item[binding-choice DEPLOY from-location] (Sarajevo Saudi Kuwait Ellsworth AFB Andersen AFB                        Boise AFB Mcclellan AFB Grissom AFB Andrews AFB) 	\item[binding-choice DEPLOY time] (AFTER 1/1 BEFORE SUPPORT-SUPERIORITY) 	\item[pre-condition DEPLOY] ((air-unit is at from-location)                        {\it (to-location is secured airport)}) 	\item[operator-choice] (SECURE-SMUGGLING {\it SECURE-NO-SMUGGLING})  	\item[binding-choice SECURE-NO-SMUGGLING location] ({\it Sarajevo} Saudi Kuwait Ellsworth AFB Andersen AFB                        Boise AFB Mcclellan AFB Grissom AFB Andrews AFB)  	\item[binding-choice SECURE-NO-SMUGGLING internal-security] (Security-A Security-B Security-C)  	\item[binding-choice SECURE-NO-SMUGGLING external-security-1] (Hawk-A Hawk-B Hawk-C)  	\item[binding-choice SECURE-NO-SMUGGLING external-security-2] (Infantry-A Infantry-B Infantry-C) 	\item[binding-choice SECURE-NO-SMUGGLING time] (AFTER 1/1 BEFORE DEPLOY)  	\item[pre-condition-choice SECURE-NO-SMUGGLING] ({\it deploy-internal-security}                        deploy-external-security-1 deploy-external-security-2)    
\item[operator-choice] ({\it SEND} MOVE)   	\item[binding-choice SEND ground-unit] (Infantry-A Infantry-B Infantry-C                        Hawk-A Hawk-B Hawk-C {\it (Security-A Security-B Security-C) } Dog-Team-A)   	\item[binding-choice SEND transportation-resource] (C5-1 C5-2 C5-3 C5-4                        C5-5 C5-6 C5-7 C5-8 C5-9 C5-10                         C141-1 C141-2 C141-3 C141-4 C141-5 C141-6 C141-7 C141-8                        C141-9 C141-10 )  	\item[binding-choice SEND to-loc] ({\it Sarajevo} Saudi Kuwait Ellsworth AFB Andersen AFB                        Boise AFB Mcclellan AFB Grissom AFB Andrews AFB)  	\item[binding-choice SEND from-loc] (Sarajevo Saudi Kuwait Ellsworth AFB Andersen AFB                        Boise AFB Mcclellan AFB Grissom AFB Andrews AFB) 	\item[binding-choice SEND time] (AFTER 1/1 BEFORE SECURE-NO-SMUGGLING) 
\end{description}   At this point, should we stop planning and start binding some of our choices? As one can see the branching factor grows tremendously at this point. However, the combinatorics are containable, if all the choices can be kept in sets. While I'll show that we are only able to defer some of these decisions for a while longer, the issue here is whether doing the assignment will cause this planning path to now be recognized as a dead end. If the assignment is delayed then possible future planning effort will be wasted. In constrast, the assignment of resources involves substantial work that will be more constrained if more of the plan is known. For example, the time constraint allows the assignment of transportation-resources's to occur anytime between 1-1 and before SECURE-NO-SMUGGLING. However, if other (currently unknown) activities have to occur before the transportation-resources can be used (like ensuring they have fuel), the date picked could have to be moved. This movement would most likely occur on tightly constrained resources, and thus one measure that would indicate to assign the resources now would be the available capacity of the resource in the time period. 

A segment of the scheduling community would consider the right solution is to do the binding now, and repairing any incorrect assignment problems later. They find that doing what would seem to be good initial assignments do not necessarily mean much less (only 8\%
cite{} ) scheduling than random initial assignments. Thus the cost of rescheduling is small compared to the possible gain of less planning.  However these studies handle a static set of constraints (at least within a plan). Measuring the correct point for at least our set of problems is a portion of the proposed work. 

\item 

The number of transportation steps required for the journey is now an issue. For this example, we simply use a control rule to prefer plans with the fewest number of steps. However, even with picking the fewest number of steps we have an issue of direction of travel. While the security team can't travel by itself the infantry and hawk battalions can transport itself over land via their trucks. Again because it is not important to the example, we will have the  system prefer flying the transportation resources to where the cargo and people exist, over moving the people and cargo to the transportation resource. 

Given these choices, we now have to expand the transportation-at from-location precondition of the SEND operator. This represents moving the transportation resources to the transported items. This choice though breaks up the large set because we have to pick between Mcclelland AFB, Grissom AFB and Andrews AFB. We also don't know if all of the aircraft at any particular AFB can actually transport the items. 

\end{enumerate} 

	\subsection{Example-Transportation Choices}
\begin{figure*}[tbp] 
\caption{Military example of gaining air superiority over multiple airports.}
\label{securing-mult-airport-graph}
\end{figure*}  

Figure~\ref{securing-mult-airport-graph} shows a partial order plan for gaining military air superiority over 3 areas at about the same time. By looking at the details of the area in bold (shown in Figure~\ref{moving-troops}), we can describe some of the issues that come up when linking planning and scheduling within a small problem. The small problem involves moving personnel and equipment from one location to another in a timely manner. The solution of this problem, requires planning to find how to move the troops and equipment and scheduling to determine the feasibility of the moves. By linking the planner and scheduler together with a joint constraint based system, the planner can also separate the work on the non causally related goals thus simplifying the planner's portion. These non causally related goals do interact over resources, and the constraint propagation system and scheduler handles these interactions independently of the planner when possible. As we shall see, the problem gets interesting when the interactions require adjusting of the plan. 

The details of Figure~\ref{securing-mult-airport-graph} are purposefully obscured because they require an explanation and understanding of the military troop movement domain that is unnecessary when considering the issues involved in linking planning and scheduling. These issues arise at specific critical points of Figure~\ref{securing-mult-airport-graph} and just the pertinent components will be used to describe the point. Figure~\ref{securing-mult-airport-graph} is included to make apparent that decisions at these critical points affect a much larger problem that could be any size. 

\begin{figure*}[tbp] 
\begin{verbatim} Goal - An infantry battalion, hawk battalion and           security force deployed at Sarajevo airport by 1/15       An infantry battalion, hawk battalion and           security force deployed at Saudi airport by 1/22 

Current State -    5 C5s at Mcclellan Air Force Base (PRJY)    5 C5s at Grissom Air Force Base (CTGC)      C5s can carry 50 tons of Bulk Cargo and                    40 passengers       2 C141s at Mcclellan Air Force Base (PRJY)    3 C141s at Andrews Air Force Base (AJXF)      C141s can carry 10 tons of Bulk Cargo and                      140 passengers       Infantry battalion A at Ellsworth AFB (FXBM)    Infantry battalion B at Andersen AFB (AJJY)      An infantry battalion consists of          500 soldiers and 100 tons of equipment         The equipment is mostly enough trucks to move           the battalion     Hawk battalion A at Ellsworth AFB (FXBM)    Hawk battalion B at Andersen AFB (AJJY)      A hawk battalion consists of          500 soldiers and 60 tons of equipment         The equipment is mostly enough trucks to move           the battalion     Security Force A at Ellsworth AFB (FXBM)    Security Force B at Andersen AFB (AJJY) 	  A security force consists of          150 MPs.     Current date is 1/1 

	C-5s can land at Mcclellan Grissom Andersen Boise 	C-141s can land at Mcclellan Grissom Andersen Boise Ellsworth Andrews 

\end{verbatim}
\caption{Transporting troops example - Initial State.}
\label{troop-transport-state}
\end{figure*}  

\begin{figure*}[tbp] 
\begin{verbatim} Operators   Send (ground-unit transportation-resource from-location to-location)     (:activity-type transport :agent transportation-resource)     preconditions        ground-unit is deployed at from-location        transportation-resource is deployed at from-location        from-location is a location compatible with transportation-resource        to-location is a location compatible with transportation-resource     postconditions        transportation-resource is deployed at to-location        ground-unit is deployed at to-location   Move (transportation-resource from-location to-location)     (:activity-type transport :agent transportation-resource)     preconditions        transportation-resource is deployed at from-location        from-location is a location compatible with transportation-resource        to-location is a location compatible with transportation-resource     postconditions        transportation-resource is deployed at to-location 

\end{verbatim}
\caption{Transporting troops example - Operators}
\label{troop-transport-operators}
\end{figure*}  

Figure~\ref{troop-transport-operators} corresponds to a critical section of the plan Figure~\ref{securing-mult-airport-graph}, where the planner is attempting to find a reasonable way to send the troops to their respective locations in a timely manner using the resources at hand. This section of the plan is difficult partly because the planner and scheduler are working with aggregrate representations of the troops and their cargo, and only a portion of the aggregrate can fit on any transportation resource. In addition, the planner doesn't have a good model of the scheduling results that is any cheaper than actually assigning the resources. Finally, the planner has multiple possible decisions that can affect whether the deadlines are met (fly planes to troops, drive troops to planes, meet somewhere in-between, etc.), but again doesn't have a good way to judge the results without doing the scheduling. We will see that planning decisions have to be retracted because what was thought to be the best idea at planning time turns out to lead to late arrivals when scheduling. 

		\subsubsection{execution-trace} 

\begin{enumerate}
\item We start out by instantiating a SEND and a MOVE operator for each of the forces that we want to be deployed. 

\item We initially limit the operators to those with the closest deadline. Since the deadline for any operators that occur in service of a chosen operator, will be before any of the other possible operators, we will end up with a depth first search strategy with this approach. Thus we only consider the SENDs and MOVEs to Sarajevo. 

We arbitrarily order the SEND operators over the MOVE operators {\it shouldn't there be a good reason for this?} 

We now have 3 indistinguishable SEND operators corresponding to each military force.  We arbitrarily pick one (say the infantry). 

\item We now look at the bindings for this SEND operator.  \begin{description}
\item[ground-unit] (all-infantry units)
\item[transportation-resource] (all transportation resources (c5 and C141)
\item[from-location] (all locations)
\item[to-location] Sarajevo
\end{description} 

\item The bindings are broken into 3 groups by the unmatched pre-conditions each of the bindings engenders.
\begin{description}
\item[Ground-unit is not deployed at from-location] all from-locations where transportation-resources are located but ground-units aren't. (Mcclellan, Grissom, and Andrews)
\item[Transportation-resource is not deployed at from-location] all from-locations where transportation-resources are located but transportation-units aren't. (Ellsworth, Andersen, and Boise).
\item[Ground-unit is not deployed at from-location
\&\\      Transportation-resource is not deployed at from-location] all from-locations where transportation-resources and ground-units are not located. (Sarajevo, Saudi and Kuwait).
\end{description} 

The first set of bindings represents a goal of getting the infantry units to a base for later departure by plane to the destination. The second set of bindings represents flying the plane to the infantry-units and then going to the destination. The last set of bindings represents both forces moving toward some common meeting point and from there going to the destination. Note longer paths could be created (and will be). However, the planner is set up to prefer shorter paths when possible, and in particular the shortest time path. 

Two sets of preferences help make this decision. One preference is for simpler paths. This preference prefers the bindings with fewer unresolved pre-conditions. The second preference prefers faster transportation. Though we don't actually know the transportation time until an operator (and binding) is chosen to achieve the un-fulfilled pre-condition. We will see that the air transport is prefered over the ground transport. At this time we arbitrarily pick the binding that flies the plane to the ground-unit. 

\item Pick unresolved pre-condition Transportation-resource not deployed at Ellsworth or Andersen.  

\item Pick operator (Move
\& Send) to implement unresolved pre-condition.  

Again, we have 2 ways to achieve the goal of being deployed at a location. Picking the same way as before, we choose the Send operator. Unfortunately no transportation-resource is adequate to move a plane. So this operator choice quickly leads to a dead-end.  Backing up we pick the Move operator as the means of getting the airplanes to one of the air bases with the infantry. 

\item This Move operator has no unfulfilled pre-conditions, so it can be applied immediately. The operator application could be delayed if we thought that more sub-goalling would give us a higher likelihood plan. However, for this example, we will ignore this issue and apply the operator now. 

One of the side-effects of application is the resources required for this operator are assigned via scheduling. Thus choices are made. In this case, we have to pick the security force to be sent (because that defines the to-location for the move), and the airplanes to send (because that defines the from-location for the move). Since no bottlenecks exist, scheduling arbitrarily picks the infantry-unit at Ellsworth AFB. Picking this infantry unit constrains the types of airplanes that can be used for transport to C141s. The scheduler then allocates a C141 to fly to Ellsworth from an arbitrarily picked location (Andrews). This allocation reserves the C141 for the time it takes to move the plane, and also reserves some airport capacity at Andrews for takeoff and Ellsworth for landing. 

\item 

Once the MOVE operator has applied, the SEND operator can also apply.  The scheduler is also called to allocate the plane and airports for the temporal interval, and a problem is discovered. The single C141 doesn't have enough capacity to haul all the infantry unit's equipment. 

This type of resource problem is easily handled in the scheduler though. The scheduler knows the causal link between the SEND and MOVE operators. It also knows that the plan (up to this point) is indifferent to the use of different planes, even if they started from different airports. Thus the scheduler {\it peels} apart the movement requirements allocating resources and updating the common state. It does this peeling until all the infantry battalion has been moved.  

This peeling can be described as a short planning/scheduling loop. After assigning a resource that move part of the infantry unit, the scheduler asks the planner for another short plan to move a smaller infantry unit from the same location to the same destination. When this plan is complete, the scheduler is re-invoked to assign a resource to the new plan fragment. This loop is repeated until all the infantry unit has been moved. This particular planning/scheduling loop is special cased in the scheduler, as an implementation improvement. 

However, it will take 50 C141 trips to move all the infantry equipment. We only have 5 C141s, thus the duration of a round trip (2 days) times the number of round trips needed (10) exceeds the amount of time available (15 days) to move the infantry unit to Sarajevo. Thus once the scheduler has figured out how to get the infantry unit to Sarajevo, it will notice that this current plan exceeds the desired duration. Upon noticing the duration problem, the scheduler simply reports that a problem exists. The top-level process then has to decide what the appropriate fix is for the problem. 

The choices are limited for the top-level process in this case because all the resources are being utilized on a single issue. Either it can expand the available scheduling space, by relaxing constraints or adding resources, or it can change the space by generating a new plan. Since the scheduler doesn't have any new resources and the due-date and start-date are considered unmovable, a new plan is requested where C141s are not required to move the infantry unit. Looking backwards up the planning tree, the most recent decision made that lead to the C141s was the picking of Ellsworth AFB. This decision is changed and a successful schedule is created that mixes C141s and C5s. 

\item 

A similar issue arises when the planner works on the second goal. However, this time no alternate source of infantry units is available. The infantry units must come from Ellsworth. The backwards search of the planning tree now ignores switching bases (because no alternatives are available) and instead stops at the SEND/MOVE choice of bindings. It picks the alternative binding that causes the infantry unit to move (using its trucks) to the transport-resource's airbase. All the pre-conditions of this MOVE operator exist in the state, so the MOVE operator can immediately apply. The scheduling in this case is simpler, because all the personnel and equipment move at once and don't require multiple trips. However, once the personnel and equipment get to the transport-resource's airbase, multiple trips are again required to transport the troops to the Saudi airbase. 

\end{enumerate} 

In this example we can see the scheduling system acting like a dynamic control rule that selects a binding of values to a variable. This type of control rule is useful, because it can not only examine the current state to determine an assignment but also can do a substantial amount of projection and changin of the current assignments. We saw the projection capability when the scheduling system found that using just the C141s to transfer the infantry would not work, given the number of C141s available. The changing of current assignments occured when the third infantry unit was deployed, and in its deployment, the scheduling system substituted a C5 for a C141 assigned to a previous operartion so that the current operation could use the C141.  

In general, the scheduling system optimizes the picking of a binding by searching the possible bindings. This search can include the previous bindings, thus achieving a new binding where the combination of bindings (new and changed) is better according to its view of optimality. Deciding on the best bindings is similar to bin-packing and is NP-Hard ~\cite{GareyJohnson}. Thus having a complex method of controlling the bindings is as we've seen useful, but it necessitates having a controlling system that can arbitrate between the scheduling system and the planning system. 

	\subsection{Example-Sue's vacation} 

Agent - Sue 

Goal - Ski at a familiar resort for a weekend in this winter. 

Current State   Many resorts, however, only the following are ``familiar''    Sugarbush Vt.    WinterPark Co.    Sue's Current Location - Pgh, PA.   Current Date Jan 1, 1997.    known locations     Warren Vt. (location of Sugarbush)     Albany NY. (Closest airport to Warren)     Pgh, PA     WinterPark Co.     Denver Co. (closest airport to WinterPark)    Constraints - Many though only these are useful for this problem    Variable         Constraint    Sue's location   At wedding on Feb 15.                     At Puxatawney on Feb 2                     At Mom's on March 25    12 weekends in Winter labled 1-12 

Operators    Check-in (resort, time-interval)     pre - Have reservation at resort for time-interval           At resort before time-interval     post - at resort for time-interval    Drive-to-location (agent from-location, to-location)     from-location <> to-location     pre - agent at from-location at time foo     post - agent at to-location after time foo    Fly-to-location (agent from-location, to-location)     from-location <> to-location     from-location is an airport.     to-location is an airport.     pre - agent at from-location at time foo     post - agent at to-location after time foo    make-reservation (resort, time-interval)     pre - room available during interval           agent available during interval     post - Have reservation at resort for time-interval 

How Prodigy would plan out Sue's trip  

check-in instantiated 24 times = 2 resorts * 12 weekends.  (note, it is possible that CHECK-IN could eliminate weekends that are busy.         However, that seems a strange knowledge representation. You should be         checking for conflicts when making the reservation, not when checking in. One instantiation is picked. WLOG pick Winterpark Weekend 7 (Feb 22).  Two new sub-goals are created from pre-conditions    Have a reservation at resort WinterPark for Weekend 7    At resort WinterPark before Weekend 7. 

Arbitrarily pick At resort WinterPark before Weekend 7.  4 Drive-to-location operators instantiated one for each possible starting    location for driving. 

Arbitrarily pick At Albany before.  New sub-goal (At Albany)   4 Drive-to-location operators and 2 fly-to-location operators instantiated. 

Arbitrarily pick FLY-TO-LOCATION where initial location is Pgh  Matches current State -- Can apply. 

Work on Goal "Have a reservation"  Sue is free and room is available  MAKE Reservation 

Done. 

The description of Prodigy solving Sue's trip problem depended upon several serendipitous bindings, and is not a very good plan. The planning could have picked at step 2 a weekend that was unavailable. This would not be noticed until step 7. The planning wouldn't know the reason why it couldn't make progress at step 7, so it would backtrack through other choices until it got back to step 2. In addition, a particularly bad choice (Albany) was made in step 4. However, the planner has no concept that the choice was bad or why it was bad. Luckily the planner made a particularly serendipitous choice in step 6, when it picked Pgh as a reasonable place to go to Albany. 

The first problem (serendipitous choice) is quickly handled by doing constraint propagation before choosing. The indication that constraint propagation is desireable is that a choice exists. The constraint propagation would remove the three invalid choices. However, later planning decisions might need to know that these choices were removed from the planning. Knowing that some of the choices were constrained by current activities, allows the planner/scheduler to determine if perhaps some previous commitments should be changed. To do constraint propagation, the set of possible values have to exist and the constraints have to be known. In this case, any use of Sue is constrained to occur at a different time from any current use of Sue. She can't do 2 things at once. 

The second problem of finding a good path is more difficult to resolve. Here again we have multiple choices (4 choices for where we should leave from to drive to WinterPark). One method of making this choice would be to estimate the time to do each of the choices and then pick the smallest. One could do constraint propagation on the duration results, along with the constraints that the entire plan take a weekend, and that Sue wants to ski for some part of that weekend to eliminate the obvious impossible choices. In getting to WinterPark, the constraint propagation would eliminate all the choices but driving from Denver. However, when considering driving to Warren, both Albany and Pittsburgh are possible starting points. Using constraint propagation to remove unreasonable choices is valuable, because backtracking choices are removed. In the going to WinterPark example, we would backtrack through the other choices of starting location even though they are unreasonable. 

Constraint propagation detects simple dead planning branches earlier than planning would by considering all the implications of choices. Planning generally addresses the implications of a choice one at a time in a sequential manner. This consideration doesn't have to be depth first, but usually it is. In constrast, by considering all the implications in parallel constraint propagation's search operates in a fundamentally different manner. Both searches are combinatorial in nature, and can solve the same class of problems.  

By combining the searches however, Joslin
\cite{} shows that some problems can be solved more easily. When combining the two searches, a decision has to be made as to whether to do constraint propagation or to plan. Limiting the constraint propagation to arc-consistency is how Joslin makes this choice. Arc consistency stops the propagation of constrained choices when the immediate neighborhood of each choice is consistent. Several polynomial algorithms exist for doing arc consistent propagation
\cite{}. Joslin also shows that for some problems this propagation choice is less efficient than just planning. Joslin does not investigate the various other choices available or how one might intelligently choose the best option. These options include continuing with a more stringent constraint propagation, not doing constraint propagation, or doing some other reasoning to reduce the available choices. 

In constrast, rather than reduce the choices, opportunity propagation gives preferences to synergistic choices. Opportunities are somewhat the inverse of constraints. An opportunity is a recognition that relating some choices to previous choices creates better plans. These relations are similar to the preferences created by search control rules \cite{Minton, Laird}. However, search control rules by themselves don't propagate their preferences. Instead they provide an even weaker form of opportunity recognition, than proposed here. As an example, when going on vacation, Sue could schedule her vacation so that she is at the same location as a wedding she also wants to attend the next day. Selecting the same location is a recognition of an opportunity to reduce travel. However, suppose it is not the ``same'' location but shares some attributes and can be recognized as reasonably close. Search control rules in general don't provide a mechanism for selecting these preferences. In this case, opportunity propagation is similar to goal-activation in ACT-R \cite{Anderson}. However, opportunity propagation can help in all the choices not just goal-activation. \note{This last argument is somewhat bogus. Anderson also has rule selection etc.} 

The constraints and opportunities are a form of domain knowledge. This knowledge can be of general use or specific to a smaller class of problems. General use constraints, like an object can't be in 2 places at the same time, is usually encoded in the problem-solver/planner. The more specific constraints, like a bus's limit on the number of passengers, are supplied when defining the problem to be solved. In the early parts of this paper, the different types of constraints are used interchangeably. However, the following example clearly distinguishes the general constraints and opportunities from the problem specific ones. 

\subsection{Temporal planning} 

The problem solver solved the previous example somewhat serendiptiously partly because it didn't have a representation of the expected temporal flow of the plan's execution. To solve this problem each plan step includes a temporal interval to represent the period of time it is being executed. The results of a plan step are only guaranteed to be true at the end of the interval. These intervals are similar to Allen's \cite{} representation of actions as occuring over some interval. Like in Allen the representation of relations between intervals plays an important part in planning the temporal. However, unlike Allen's relations, the relations in this paper allow a user controlled mismatch of end points. For example, in Allen's temporal logic defining interval I-1 as ``meeting'' interval I-2 means the end point of I-1 occurs simultaneously with the starting point of I-2. In this paper's relations, I-1's end might occur slightly before or after the start of I-2. This allowed mismatch helps both in recognizing opportunities, and in monitoring a plan's execution. 

Thus we modify the problem definition of Sue's vacation to be: 

Agent - Sue 

Goal - Ski at a familiar resort for a weekend (interval 2 days duration       starting on a Saturday ending on a Sunday) this winter.        constraint -- Start time - Saturday Morning                     End Time   - Sunday Afternoon 

Current State   Many resorts, however, only the following are ``familiar''    Sugarbush Vt.    WinterPark Co.    Sue's Current Location - Pgh, PA.   Current Date Jan 1, 1997.    known locations     Warren Vt. (location of Sugarbush)     Albany NY. (Closest airport to Warren)     Pgh, PA     WinterPark Co.     Denver Co. (closest airport to WinterPark)  Constraints - Many though only these are useful for this problem    Variable         Constraint    Sue's location   At wedding on Feb 15 (Monday morning).                     At Puxatawney on Feb 2 (Saturday morning)                     At Mom's on March 25 weekend (Saturday)    minimize cost    minimize time off work  (> 1 day unacceptable)    12 weekends in Winter labled 1-12  Opportunity recognizers.   Limit travel time    

Operators    Check-in (resort, time-interval)          :duration 15 min     pre - Have reservation at resort for time-interval           At resort before time-interval     post - at resort for time-interval    Drive-to-location (agent from-location, to-location)          :duration distance(from-location,to-location)/55         :resource car     from-location <> to-location     pre - agent at from-location at time foo     post - agent at to-location after time foo    Fly-to-location (agent from-location, to-location)         :duration distance(from-location,to-location)/500         :resource commercial-flight     from-location <> to-location     from-location is an airport.     to-location is an airport.     pre - agent at from-location at time foo           agent has a reservation on flight           flight is at time foo     post - agent at to-location after time foo    make-hotel-reservation (resort, time-interval)         :duration 15 min     pre - room available during interval           agent available during interval     post - Have reservation at resort for time-interval    make-airline-reservation (airline, time-interval)         :duration 15 min     pre - flight available within interval           agent available during interval     post - Have reservation on flight 

How Temporal-constraint-Prodigy would plan out Sue's trip  

check-in instantiated 24 times = 2 resorts * 12 weekends.  Constraint propagation removes 2 weekends leaving  20 options. One instantiation is picked. WLOG pick Winterpark Weekend 7 (Feb 22).  Two new sub-goals are created from pre-conditions    Have a reservation at resort WinterPark for Weekend 7    At resort WinterPark before Weekend 7. 

Arbitrarily pick At resort WinterPark before Weekend 7.  4 Drive-to-location operators instantiated one for each possible starting    location for driving.   Opportunity rule for limiting travel time orders these    Denver, Pittsburgh, Albany, Warren 

Pick At Denver before.  New sub-goal (At Denver)   4 Drive-to-location operators and 2 fly-to-location operators instantiated.   Opportunity rule for limiting travel time orders these    Drive-from WinterPark, Fly-from Pittsburgh, Fly-from Albany,     Drive-from Pittsburgh, Drive-from Albany, Drive-from Warren   Drive-from WinterPark is eliminated because it forms a state loop. 

Pick FLY-TO-LOCATION where initial location is Pgh  Matches current State -- Can apply. 

Work on Goal "Have a reservation"  Sue is free and room is available  MAKE Reservation 

Done. 

However, we haven't decided on what flights Sue will take, and whether going to WinterPark on this weekend is a reasonable choice. Note that the pick of weekend, location and flight are the only unconstrained and non-opportunistically guided choices. These choices are picked via scheduling.  

		\subsubsection{Scheduling vs. Planning} 

When the planning system has a set of indifferent choices, it asks the scheduling system for its advice. The picking of values given a possibly conflicting set of preferences is a scheduling problem. In the initial case of picking where to go, the scheduling system has no input so the choice is made at random. Likewise the scheduling system doesn't have input on what weekend. However, in picking flights, the scheduling system uses the preferences for short travel time, mimizing cost, and minimizing time off from work to make a decision. The scheduling system is acting like a complicated decision procedure for the planning system. 

Having the scheduling system as the decision procedure provides flexibility that is not available with simpler decision systems. In particular, the scheduling system can relax some of the decisions. This relaxation is especially important in synchronizing otherwise separate tasks. As an example, we know Sue needs to be in Albany on Monday Feb 15 to attend a wedding. The start time for her to start driving to the wedding is the previous Sunday evening. This entire task has been planned in advance of her vacation. However, when considering driving to Albany to go skiing on Feb 13th, The scheduler can recognize that the previous driving task can be merged with this task. This merging can occur without re-planning because no planner imposed constraints are being violated. Instead, some arbitrary scheduling decisions are simply relaxed. {\it A better example is needed here. This though is the guts of the proposal} 





		\subsubsection{Why aren't flights picked by the planning system?} 

The planning system finds its solution at a particular abstraction level. Once a solution occurs at that abstraction level, then the details have to be filled in. The abstraction level is defined in the problem. However, some guidance  

To decide on the flights,  

	\subsection{What are we doing} 

These logistic problems share a particular characteristic that can be exploited to create a solution in a reasonable amount of time. This characteristic is, a large number of the subgoals in the plan are not causally related and only interact over resources. A plan to achieve a subgoal drawn from this set of unrelated subgoals is not required and does not threaten any of the other plans in the set, except in how the plan uses the common resources. Since the subgoals are not causally related, a planner can independently generate a plan for each subgoal, and then a scheduler can schedule this set of plans given the current resources. This separation of the planning and scheduling can greatly lessen the computational burden when creating a complete scheduled plan, because the planning choices can often not consider the resources (thus reducing work for each plan step), and the scheduling choices can rely on working with a valid plan (thus removing some backtracking). 

This paper describes an integrated planning and scheduling system, and how such a system handles large logistic problems.  Functionally, the combined system sequentially produces the plans, and these new plans are integrated with the existing plans one at a time via scheduling.  The combined system can generate new plans that avoid a bottleneck resource thus avoiding scheduling problems. It also can break a large plan up into a set of smaller independent sub-plans. 

uses planning to modify the current plans ensures that the plan modifications correctly take into account all the current knowledge. Thus the combined system addresses the two major drawbacks to the plan re-use approach. 

This plan/schedule approach can generate feasible schedules to accomplish the plans in reasonable time because of some computational efficiencies that will be described soon{\it when}. However, the usefulness of the final schedule depends upon the appropriateness of the generated plans. Also what should happen if the scheduling fails? Given a finite set of resources and enough plans that use those resources, the scheduling system must reply that some of the plans are infeasible. Instead of keeping the scheduling and planning process distinct, this paper proposes to create a tightly coupled planning/scheduling system that addresses the problems that occur by separately considering the planning and scheduling aspects of the task. This paper will show the integrated approach provides functionality unavailable in a separated system, is more computationally efficient allowing larger problems to be addressed, and produces ``better'' plans/schedules than are produced from the separated system. 

The plan re-use approach assumes the individual plans only interact over resource usage. This powerful assumption makes the planning and/or plan modification tasks much simpler, because planning occurs on much smaller problems. This assumption often works in the logistical domain, and provides a basis for separating the plan generation and resource selection (scheduling) activities. However it doesn't hold in general, because synchronization points often exist in logistical problems. As an example, getting a passenger to a plane is a planning problem that might be independent of ensuring the arrival of the other passengers.  However if the plane can't take off until everyone has arrived, the plane's departure is a synchronization point for all the individual people transportation plans. In the beginning of this paper we will consider the issues arising when the plans can be considered independent except for their utilization of common resources.  Relaxing this assumption will be discussed later in the paper. The existance of a synchronization points turns out to guide the interaction between the planner and scheduler. 

{\it What is being implied here is that the initiator of requests changes when a sychronization point is discovered. The scheduler notices the synchronization point. If the sub-plan before the synchronization point fails, then the scheduler asks for a new sub-plan that can reach the synchronization point. Thus the scheduler has gone from the slave to master. This switch occurs because the scheduler ``knows'' about the synchronization point and what happened before it, while the planner does not. Example could be Manuela's one-way rocket. Three independent goals to get goods on the rocket. Possibly several possible plans for each of the goals. Rocket is a synchronization point. The planner is asked for alternative plans to get the goods to the rocket if the goods will not get them there on time.} 

	\subsection{Why is this integration a win} 

Combining planning and scheduling is useful because they operate with different assumptions and these differences can be exploited to create a more efficient system than considering either separately. Scheduling and planning both search for their solutions, but differ in their approach. Scheduling works as a constraint satisfaction problem and in addition uses knowledge about time to both limit its search and provide powerful operators to skip around in its search space. Generative planning can be thought of a combinatorial search through either plan-space or state-space. At any time for both types of planners, a partially ordered plan can be built\cite{}. This partial-order plan represents the current set of actions in the plan along with the dependencies between those actions. This partial order plan can then be used for scheduling purposes. 

As mentioned before, scheduling solves constraint satisfaction problems, where the search involves finding values for a set of variables given some consistency criteria. In the logistic domain this translates into assigning a temporal-duration of a resource (the value) to a set of plan-actions (the variables) so the plan-actions can all occur. The consistency criteria in the logistics domain can include meeting due-dates, not exceeding resource bounds, and reducing waiting time. Scheduling is searching for reasonable resources to assign to a set of plan-actions. To do the resource allocation the scheduler has to consider all the possible resources, and the time-varying utilization of those resources for each plan-action in each plan. Just assigning resources to plan-actions is an NP-hard problem (similar to bin-packing\cite{GareyJ}). The time-varying availability of the resources makes the problem harder by expanding the number of assignment choices, because a single resource can be considered multiple times. 

However, at the cost of search completeness, schedulers can take advantage of knowledge of both the domain and time. This knowledge can be used to create special operators that can skip around in the search space, reducing the search space considerably while still providing for flexibility in the actual scheduling.  An example of domain knowledge in the logistics domain, is the recognition of commonality in the processes\cite{Smith} used to achieve independent goals. This commonality allows the scheduler to aggregate these processes scheduling them together as a group. The temporal knowledge is domain independent and allows the scheduler to operate while knowing how time flows. This allows the scheduler to shift groups of operations from one time slot to either some earlier or later time. This shift will open up a hole where perhaps a new operation can be scheduled. By themselves these aggregate and temporal operators don't affect the completeness of the search, instead when applicable they can reduce the number of steps to a solution by adapting a currently valid schedule to new information. Since these operators must also be considered at each step in the resource assignment process, including them could actually increase the search space. However, when combined with a strong committment process the search space does get reduced. 

The scheduler used in this work (Ditops\cite{}) doesn't backtrack over commitments once they are made. The scheduler searches for the most appropriate resource time-slice and once a time-slice is found, it doesn't renege on that commitment. Instead, it now uses the schedule-adaptation operators to change previous commitments in known valid ways. However, these schedule-adaptation operators do not cover all the possible resource assignments, and thus lead to a fast, but incomplete, search of the possible resource assignments. 

This scheduler incompleteness provides the combined scheduler/planner an opportunity for an additional synergy. When the scheduler determines a plan is infeasible to schedule over some resources, a decision has to be made about whether the plan should be repaired, or the schedule should be repaired. Repairing the plan means picking some new commitments and re-planning. Repairing the schedule means investigating whether the scheduler's search limitations can be overcome so that a required resource assignment can be made. When repairing the schedule, the {\it planner?} is operating like a user unscheduling (releasing commitments) operations and then rescheduling them. 

One reason scheduling is more efficient than planning at assigning resources, is that it is working with a partial order plan that if executed will achieve the goal. Thus the resource search only occurs when it is required. Considering resources at every step in the plan includes the useless consideration of resources on those planning paths that will be discarded. This argument of eliminating useless detailed work for infeasible paths is similar to the argument for using abstraction when planning \cite{}. However, this paper shows that additional synergies are possible from the different searches. In particular, the abstraction hierarchy can be selectively chosen for certain planning operators. This selectivity can cause planning to avoid resources with scheduling bottlenecks while still planning without considering resources most of the time. 

The integrated system can be more computationally efficient only if it can exploit some synergies that exist between the scheduling and planning processes. If one views both processes as search, then one possible synergy is the mutual reduction of search space. Switching the search process Another possible synergy is 

The goal of combining planning and scheduling is to reduce the overall computational problem. 

\begin{itemize}
\item Plan without considering resources until a possible plan has been constructed. This strategy reduces the scheduling problem because only the resources that can be used by the plan should be considered. If planning has selected specific resources, then this also limits the scheduling work. This strategy also reduces the planning problem because, as described before, resources are not checked for discarded paths. 

\item Check for bottleneck resources before planning. This reduces the total planning/scheduling problem by avoiding plans that use the bottleneck resources. These plans have a high likelihood of being discarded.  

Checking for bottleneck resources without a plan requires either: an estimate of what resources any possible plan will use, an estimate of the time-frame of any possible plan, or both. 

\end{itemize} 







Utilizing the relative independence assumption means that solving a planning problem can usually occur  

How the planning system responds to a reply that a plan is infeasible, and how these responses affect how to achieve the plan's goals is the subject of this research.  The general approach to handling plan-infeasible replies, is to search two different sources of knowledge: the knowledge about recovering from scheduling problems by fixing the schedule, and the planning knowledge about alternative plans. Both methods allow the planner to recover from scheduling problems due to the limited search done in the scheduling. The schedule-fixing knowledge addresses problems where the plan is fundamentally sound, but fixing the schedule goes beyond the set of methods built into the scheduler. These scheduler methods handle the most common schedule pathologies, and the planner is simply doing a more complete search. As an example the planner could request the scheduler to remove a previously scheduled plan with some slack time, so that the new plan can be scheduled. The unscheduled plan can then be re-added to the scheduler, thereby reducing the overall tardiness in the schedule. 

The plan-fixing knowledge addresses the level of abstraction used by the planning system. The planner normally doesn't concern itself with resource availability. When fixing the plan, the planner pays closer attention to the availability of the resources. In particular, the planner pays attention to the resource availability for the critical resources. This attention to the critical details should allow the planner to find alternative plan choices that have a better chance of being schedulable. As an example, the planner could add steps to a plan to ensure enough aircraft are available, when a plan for flying critical cargo fails because insufficient aircraft are available. In this example, the planner could also have decided to ship the cargo from some alternative site that did not have the capacity problem. 

Both types of (schedule-fixing and plan-fixing) knowledge are currently used in several scheduling systems. However, the knowledge has not been utilized in a general way. Instead, specific methods with their associated applicability rules have handled scheduling problems as pathologies that don't require any deep run time analysis. This pathology approach has been very successful in certain domains where most of the scheduling problems encountered fall into the schedule-fixing class~\cite{Smit95}. The pathology approach has also been successful when the plans and the subsequent replanning are simple~\cite{OateC94}. This paper describes work to apply more general  techniques in domains where: the plans themselves are more complex, the interaction between plans is also complex, and re-planning can generate completely different plans. The adding of resources mentioned in the planning-problem above is an example of re-planning that is beyond most scheduling systems. 

Planning systems also can consider the scheduling types of knowledge. However, planning systems attempt to find feasible plans given some consistent criteria, and this limits their applicability to solving large logistics type problems. Smith shows in ~\cite{Smit95}, that the factory-floor scheduling domain could have both a minimize Work In Progress (WIP) criteria, and a maximize resource allocation criteria. These criteria conflict, and part of the scheduler's work is resolving the conflict in an adequate way when possible. Scheduling systems thus look for satisficing solutions given a set of constraints. Finally to find some solution, scheduling systems limit their search to those problems associated with assigning plan steps to a limited set of resources. This is a reasonable approach when the plans are static, without many contingencies. However, this work addresses domains where either the plans are not static, or could have many different contingencies. 

\section{Logistics Domain}  

The techniques, described in this paper, are aimed at helping to solve the problems that arise in large unique logistic problems. Examples of these problems are: Organizing the medical teams and support equipment to respond to a natural/man-made disaster, Organizing the teams and equipment to fight a forest fire, and Organizing the troops and equipment to accomplish some military goal.  The characteristic issues of these problems are: 

\begin{itemize}  	\item Unique. A canned response is probably not only wasteful but probably does the wrong things. Every example problem has unique aspects, requiring unique solutions. Adapting old solution, with small changes is very effective.  	\item Generic. All the solutions consist of many small plans for moving people and equipment. These plans are:  	\begin{itemize}  		\item Mostly independent.  		\item Interact mainly through contention for scarce resources.  	\end{itemize} 
\end{itemize}  

One way to handle this domain, is to plan out the entire domain using the resources in the planning task. However this complete planning approach is computationally infeasible; given the number of possible goals (thousands), the large number of ways to accomplish any particular goal, and since all the goals interact over resources. 

Instead this paper proposes to create a set of new plans (or appropriately modify old plans) and then check these plans for feasibility by scheduling the plans to use the available resources. By itself, this is not a new idea. However, we plan to interleave the planning and scheduling so that planning can take advantage of previous scheduling activity, and scheduling a plan can become a complex interaction between the planner and scheduler. 

The environment of logistics problem also contains uncertainties, and changes dynamically. Airports can be covered in fog. Gas tanks can only be half full. These uncertainties can represent either unforeseen problems, or unforeseen opportunities.  While this paper doesn't describe the recognition of the problems/opportunities, the fact they exist means that when they are recognized the plans/schedules must be able to change. These changes must both be quick, and be biased towards minimizing the disruption of the current plans/schedule. At the least the cost of changing a plan/schedule must be represented. Turning a ship around to pick up a package doesn't occur for free.  
\section{System Architecture}  

\begin{figure*}[b]  %\psfig{figure=figures/format-prodigy-ditops.ps} 
\caption{System Architecture.}  
\label{sys-arch} 
\end{figure*}  

Figure~\ref{sys-arch} shows the components used to address the problem of creating large feasible logistic plans.  {\bf FORMAT}\cite{} is a tool that allows people to manage all the details in large logistic problems, and define specific logistic goals. {\bf Prodigy}\cite{VeloCPBFB95} is a case-based planning tool that takes a FORMAT defined high-level goal and searches its case library for previous cases of plans that might satisfy the goal. Prodigy returns any found plans along with extra instructions describing how to modify the plans for this specific goal. {\bf Ditops}\cite{Smit95},\cite{SmitLB96b} tests the feasibility of integrating the Prodigy produced plan with all the other ongoing activities that might be utilizing resources the plan requires. The goal of the Prodigy-Ditops communication is to ensure the feasibility of the plans that Prodigy returns to FORMAT. In addition to the message passing mechanisms just described, Prodigy and Ditops share at some level, the data describing the current state of the system.  	\subsection{Prodigy}  

Upon reception of a high-level goal from FORMAT, Prodigy both searches its case library for appropriate cases, and simultaneously generates a new plan for the high-level goal. Prodigy searches for cases to make the returned plans be as similar to previous plans as possible. This similarity makes the detailed planning and execution of those plans simpler. 

The reason Prodigy generates a plan in conjunction to searching its case library is to ensure that all the conditions for the cases have been checked. In particular, if a piece of planning knowledge would affect the plan only when certain conditions exist, then a case might have an over-general index with regards to those conditions. The generative plan is useful as a check on the validity of the cases. 

The feasibility of a plan could be checked at various times during the planning process. We have chosen to check the feasibility only after creating a complete plan. This approach means both the cases and the generated plan can be checked for feasibility. Thus Prodigy passes a complete plan, along with any constraints between plan actions, to Ditops. Ditops then takes the plan and attempts to schedule it in conjunction with all the previous plans.  	\subsection{Ditops}  

Ditops is a resource-directed scheduling system that uses a beam search technique to schedule possibly thousands of time-dependent plans that utilize hundreds of resources. A plan enters Ditops as a set of {\it demands} for moving cargo (people are a type of cargo) from one location to another. Ditops uses these demands to create a set of {\it activities} that represent a process that when executed can satisfy the demands. These activities require {\it resources} and occur over some time {\it interval}. An activity can also be related temporally with other activities. The Prodigy planning activity defines some of these temporal relationships. These Prodigy defined relationships come from the partial ordering of the demands that Prodigy encountered when creating the plan.  	\subsection{Prodigy-Ditops Interface}  

The interface between Prodigy and Ditops has many issues concerning how much information should be shared and how long the shared information should persist.  This interface communicates scheduling problems back to the planner. It also defines a method of describing both the state of the scheduler and the state of world. The entire planning/scheduling system can be viewed as a generate (planner) and test (scheduler) type of system. The purpose of the interface is to move the appropriate knowledge back from the test portion to the generate portion. This movement will make the generate portion more likely to pass the test portion. In other words, planning will be more likely to produce feasible plans. 

\section{Hard problems} 

This section describes two problems, "multiple one-way rocket" and "multiple plan" that are difficult for planning and scheduling respectively, but can be solved by the planning/scheduling integration system described here. 

	\subsection{Multiple one-way rocket} 

The multiple one-way rocket problem is a variant of the "one-way rocket" problem in \cite{Veloso-thesis}. The one-way rocket problem is to create a plan that will get a set of packages from earth to some other location (let's say a space station) using a rocket that cannot return. Creating the plan is difficult for a state-space planner, if an early commitment strategy is taken when planning\cite{}. The difficulty arises from the planner constantly backtracking when it finds that some of the packages were left on the ground. However by delaying action commitments, creating the plan becomes much easier, because the planner doesn't have to backtrack over the launching of the rocket. The actions being delayed are the changes to the state. Instead the planner can recognize within a set of possible actions (load 

\bibliography{research} 

\end{document}     



