advanced-planning-exercises.tex

%%%% 11.1: Time, Schedules, and Resources (1 exercises, 0 labelled)
%%%% ==============================================================

\begin{uexercise}
The goals we have considered so far all ask the planner to make the world
satisfy the goal at just one time step. Not all goals can be expressed this way: you
do not achieve the goal of suspending a chandelier above the ground by
throwing it in the air. More seriously, you wouldn't want your spacecraft
life-support system to supply oxygen one day but not the next.
A {\em maintenance goal} is achieved when the agent's plan causes a condition
to hold continuously from a given state onward.  Describe how to
extend the formalism of this chapter to support maintenance goals.
\end{uexercise} 
% id=11.1 section=11.1


%%%% 11.2: Hierarchical Planning (4 exercises, 2 labelled)
%%%% =====================================================

\begin{exercise}%%Nick Hay Question 1
You have a number of trucks with which to deliver a set of packages.
Each package starts at some location on a grid map, and has a
destination somewhere else.  Each truck is directly controlled by
moving forward and turning.  Construct a hierarchy of high-level
actions for this problem.  What knowledge about the solution does your
hierarchy encode?
\end{exercise} 
% id=11.2 section=11.2

\begin{exercise}[HLA-unique-exercise]
Suppose that a high-level action has exactly one implementation as a
sequence of primitive actions.  Give an algorithm for computing its
preconditions and effects, given the complete refinement hierarchy and
schemas for the primitive actions.
\end{exercise} 
% id=11.3 section=11.2

\begin{exercise}
Suppose that the optimistic reachable set of a high-level plan is a
superset of the goal set; can anything be concluded about whether the
plan achieves the goal? What if the pessimistic reachable set doesn't
intersect the goal set? Explain.
\end{exercise} 
% id=11.4 section=11.2

\begin{exercise}[HLA-progression-exercise]
Write an algorithm that takes an initial state (specified by a set of propositional literals) and a sequence of HLAs (each defined by preconditions and angelic specifications of optimistic and pessimistic reachable sets)
and computes optimistic and pessimistic descriptions of the reachable set of the sequence.
\end{exercise} 
% id=11.5 section=11.2


%%%% 11.3: Planning and Acting in Nondeterministic Domains (10 exercises, 2 labelled)
%%%% ================================================================================

\begin{exercise} In \figref{jobshop-cpm-figure} we showed how to
describe actions in a scheduling problem by using separate fields for
\noprog{Duration}, \noprog{Use}, and \noprog{Consume}.  Now suppose we
wanted to combine scheduling with nondeterministic planning, which
requires nondeterministic and conditional
effects.  Consider each of the three fields and explain if they should
remain separate fields, or if they should become effects of the
action. Give an example for each of the three.
\end{exercise} 
% id=11.0 section=11.3

\begin{exercise}
Some of the operations in standard programming languages can be
modeled as actions that change the state of the world. For example,
the assignment operation changes the contents of a memory location,
and the print operation changes the state of the output stream.  A
program consisting of these operations can also be considered as a
plan, whose goal is given by the specification of the program.
Therefore, planning algorithms can be used to construct programs that
achieve a given specification.
\begin{enumerate}
\item Write an action schema for the assignment operator (assigning
the value of one variable to another). Remember that the original value will be overwritten!
\item Show how object creation can be used by a planner to produce a
plan for exchanging the values of two variables by using a temporary
variable.
\end{enumerate}
\end{exercise} 
% id=11.6 section=11.3

\begin{iexercise} 
Consider the following argument: In a framework that allows uncertain
initial states, \termi{nondeterministic effects} are just a notational
convenience, not a source of additional representational power.  For
any action schema \(a\) with nondeterministic effect \(P \lor Q\), we could
always replace it with the conditional effects \(\condeff{R}{P} \land
\condeff{\lnot R}{Q}\), which in turn can be reduced to two regular
actions.  The proposition \(R\) stands for a random proposition that is
unknown in the initial state and for which there are no sensing
actions.  Is this argument correct?  Consider separately two cases,
one in which only one instance of action schema \(a\) is in the plan,
the other in which more than one instance is.
\end{iexercise} 
% id=11.7 section=11.3

\begin{exercise}[conformant-flip-literal-exercise]
Suppose the \(\J{Flip}\) action always changes the truth value of variable \(L\).
Show how to define its effects by using an action schema with conditional effects.
Show that, despite the use of conditional effects, a 1-CNF belief state representation remains in 1-CNF after a \(\J{Flip}\).
\end{exercise} 
% id=11.8 section=11.3.1

\begin{exercise}
In the blocks 
world we were forced to introduce two
action schemas, \(\J{Move}\) and \(\J{MoveToTable}\), in order to
maintain the \(\J{Clear}\) predicate properly. Show how conditional effects can
be used to represent both of these cases with a single action.
\end{exercise} 
% id=11.9 section=11.3.1

\begin{exercise}[alt-vacuum-exercise]
Conditional effects were illustrated for the \(\J{Suck}\) action in the
vacuum world---which square becomes clean depends on which square the
robot is in. Can you think of a new set of propositional variables to
define states of the vacuum world, such that \(\J{Suck}\) has an
{\em unconditional} description? Write out the descriptions of \(\J{Suck}\),
\(\J{Left}\), and \(\J{Right}\), using your propositions, and demonstrate that they
suffice to describe all possible states of the world.
\end{exercise} 
% id=11.10 section=11.3.1

\begin{uexercise}
Find a suitably dirty carpet, free of obstacles, and vacuum it.
Draw the path taken by the vacuum cleaner as accurately as you can.
Explain it, with reference to the forms of planning discussed in this
chapter.
\end{uexercise} 
% id=11.11 section=11.3

\begin{iexercise}
The following quotes are from the backs of shampoo bottles.  Identify each as 
an unconditional, conditional, or execution-monitoring plan.  (a) ``Lather.  
Rinse.  Repeat.''  (b) ``Apply shampoo to scalp and let it remain for several 
minutes.  Rinse and repeat if necessary.''  (c) ``See a doctor if problems 
persist.''
\end{iexercise} 
% id=11.12 section=11.3

\begin{iexercise}
Consider the following problem: A patient arrives at the doctor's
office with symptoms that could have been caused either by dehydration
or by disease \(D\) (but not both).  There are two possible actions:
\(\J{Drink}\), which unconditionally cures dehydration, and
\(\J{Medicate}\), which cures disease \(D\) but has an undesirable side effect
if taken when the patient is dehydrated.  Write the problem
description, and diagram a sensorless plan that solves the
problem, enumerating all relevant possible worlds.
\end{iexercise} 
% id=11.13 section=11.3.1

\begin{uexercise}
To the medication problem in the previous exercise, add a \(\J{Test}\)
action that has the conditional effect \(\J{CultureGrowth}\) when
\(\J{Disease}\) is true and in any case has the perceptual effect
\(\J{Known}(\J{CultureGrowth})\).  Diagram a conditional plan that solves the
problem and minimizes the use of the \(\J{Medicate}\) action.
\end{uexercise} 
% id=11.14 section=11.3.1




%%%%%%%%%%%%% Resources and Time



%%%%%%%%%%%%%%%%%% HTN






%%%%%%%%%%%%% Nondeterminism


% \begin{exercise}
% Write action descriptions for a supermarket shopping domain, so that
% the planner can
% achieve the goal of having three oranges by grabbing a bag, going to
% the store, grabbing the oranges, paying for them, and returning home.  Model
% money as a resource.  Use universal quantification in the operators, and show
% that the original contents of the bag (if any) will still be there at the
% end of the plan.
% \end{exercise}

%\begin{exercise}\label{disjunctive-preconditions-exercise}%
%Modify the \prog{POP} algorithm so that it can handle disjunctive
%preconditions, as described in the chapter.
%\end{exercise}



%%%%%%%%%%%%%%%%%%%%%%%%%%% Conformant planning  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% \begin{exercise}\label{conformant-painting-exercise}
%% In \secref{conformant-planning-section}, we calculated the sequence
%% of belief states as the solution for the sensorless painting problem was executed.
%% Repeat the process for the formulation in which \(\J{Color}\) is a function rather than a predicate. ({\it Hint}: 
%% you can assume that the agent knows \(\All{x} x\eq x\).)
%% \end{exercise}






%%%%%%%%%%%%%%%%%%%%%%%%%%% Conditional effects  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%




%% \begin{exercise} Write out the full description of \(\J{Suck}\) for the double Murphy 
%% vacuum cleaner that sometimes deposits dirt
%% when it moves to a clean destination square and sometimes deposits
%% dirt if \(\J{Suck}\) is applied to a clean square.
%% \end{exercise}


% \begin{exercise}
% In Conditional Graphplan, are two aspects of the same action always mutex?  
% If not, give an example.  If so, do we need a rule that says to always insert 
% a mutex link between them, or will that link already be inserted by the 
% existing mutex rules? 
% \end{exercise}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Online planning and replanning  %%%%%%%%%%%%%%%%%%%%%%%




%\begin{exercise}
%Is the knowledge gained from the perceptual effect {\mathdelim}Known(P){\mathdelim} the same or
%different from {\mathdelim}Known(\lnot P){\mathdelim}? 
%\end{exercise}

%% \begin{exercise}
%% The successor function for the conditional planner generates
%% conditional steps of the form \key{if} {\mathdelim}P{\mathdelim} \ldots where {\mathdelim}P{\mathdelim} is an atom
%% (variable).  Would it add any power to allow full Boolean expressions
%% rather than just a single {\mathdelim}P{\mathdelim}? If yes, show a plan with an arbitrary
%% Boolean expression that has no equivalent plan expressed using only
%% atoms.  If no, show why conditional steps with atoms can express any
%% Boolean expression.
%% \end{exercise}

% \begin{exercise}
% A conditional perceptual effect is of the form
% \condeff{P}{Perceive(Q)}.  These are actually quite common (e.g. when the 
% telescope is focused, you can observe whether the moon is eclipsed). 
% Can the conditional planner outlined in
% this chapter handle conditional perceptual effects?  If yes, explain 
% why; if no, explain how it would have to be modified.
% \end{exercise}

%% \begin{exercise}
%% Write action descriptions, analogous to \eqref{left-k-equation}, for
%% the \(\J{Right}\) and \(\J{Suck}\) actions. Also write a description for
%% \(\J{CheckLocation}\), analogous to \eqref{checkdirt-equation}.
%% Repeat using the alternative set of propositions from
%% \exref{alt-vacuum-exercise}.
%% \end{exercise}



    


%%%%%%%%%%%%%%%% Multiagent