<filename>transport-docs/bp/en/experiments.tex
\chapter{Experimental evaluation}\label{experiments}

In this chapter, we will describe and run experiments
that compare our planners from the last two chapters
with domain-independent planners from the IPC.
We will briefly discuss the acquired results and interpret them.

\section{Methodology}

Using our benchmarking software (see Attachment 4\comment{\nameref{transport-project}}), we will now run experiments in an
environment similar to the original
IPCs. The rule pages state that
planners have to be single-threaded and use a maximum of 2, 4, or 6 GB of memory (depending on the competition year), with a maximum run time of 30 minutes.

Since the IPC rule pages vary on the exact processor specification or the amount of memory available to each planner between competitions,
we adjust the parameters slightly by running our planners
for 30 minutes on each problem, using 4 GB of RAM.
Our planners will get canceled and prompted for a plan after the time runs out. 
All our experiments are run on
\comment{a computer
with an 8 core 64-bit processor \texttt{Intel Core i7-6700 CPU @ 3.40GHz}
and 16 GB of memory, running Gentoo Linux.
A big thank you goes out to the faculty for providing access to these machines.
}
the clusters of MetaCentrum.\puncfootnote{\url{https://www.metacentrum.cz/en/}}
Due to the nature of computing on MetaCentrum, we were not able to guarantee that all problems and planners
run on the exact same processor, only on very similar ones
(approximately equivalent to \texttt{Intel Xeon E5-2650 v2 2.6 GHz}).
The performance of our planners does not change significantly
when changing the run time from 30 to 15 minutes or when run
on slightly different processors.

We run all our planner implementations in Java using Oracle's OpenJDK 
version \texttt{1.8.0\_131-b11}.
The results presented here were obtained with the \TEver{} version of the TransportEditor project.\puncfootnote{Git tag \TEtag{}, available at \url{https://github.com/oskopek/TransportEditor}} The \texttt{NOTICE.txt} files
in the project module directories specify
the exact versions of libraries used.
In all planners where nondeterminism occurs,
we set the initial random seed to 2017
(on all individual problem runs).

The evaluation criteria remain the same as in the IPC:
we focus on plan \textit{quality} in favor of planner run time.
The quality of a plan for a specific planner and sequential problem $p$ is defined as:
$$\frac{\mt{total-cost}(\mt{planner}(p))}{\mt{total-cost}(BEST)},$$
where the results called $BEST$
are either precalculated outside of the competition environment or they are the best result of one of the planners in the competition, depending on which plan has a lower total cost.
Quality is, therefore, a number between $0$ and $1$.
The overall goal for planners is to maximize the sum of qualities over the problem instances in a given dataset, called the \textit{total quality}.
For temporal domains, quality is calculated in the same way, just by substituting total cost
for total time. We sometimes refer to total cost and total time as the \textit{score} of the planner, a term that is not dependent on the domain variant.

We will use four datasets for our experiments --- the seq-sat-6, seq-sat-7,
and seq-sat-8 datasets for sequential
and the tempo-sat-6 for temporal planners (Section~\ref{datasets}).
All the datasets used are available in the
software project sources (see Attachment 1\comment{\nameref{cd-contents}}).
Descriptions of planners that we will refer to by their competition names can be found in the respective competition results or booklets for IPC~2008,\puncfootnote{\url{http://icaps-conference.org/ipc2008/deterministic/Planners.html}} IPC~2011 \citep{Garcia-Olaya2011}, and IPC~2014 \citep{Vallati2015}.
Due to space constraints, we only show the three
best non-baseline planners from each competition
in the result quality tables and plots, based on total quality.
In the temporal dataset tempo-sat-6 quality table, we only show the two best
and add another external domain-independent planner
to the comparison, the 2014 version of Temporal Fast Downward (TFD2014).






















\section{Sequential Transport}

In this section, we present the results of our sequential planners on the seq-sat-6, seq-sat-7, and seq-sat-8 datasets. Specifically, these planners are included in the experiment:
\begin{description}
\item[MSFA3] The meta-heuristically weighted SFA planner (Section~\ref{msfa}) with the package and vehicle distance heuristic (Section~\ref{sfa3})
\item[MSFA5] The meta-heuristically weighted SFA planner with the general marking heuristic (Section~\ref{sfa5})
\item[RRAPN] The Randomized Restart Around Path Nearby planner (Section~\ref{rrapn})
\end{description}

\subsection{Results}\label{sequential-results}

We show an IPC quality table and a quality plot
for the experimental runs on the seq-sat-6 dataset (Figure~\ref{fig:seq-sat-6-results}), seq-sat-7 dataset (Figure~\ref{fig:seq-sat-7-results}), and the seq-sat-8 dataset (Figure~\ref{fig:seq-sat-8-results}). Details about the specific plans along with the benchmark results can be found in Attachment 1\comment{\nameref{cd-contents}}.

\begin{figure}[tbp]
\centering
\begin{subtable}{\textwidth}
\centering
\scriptsize
\renewcommand{\footnotesize}{\scriptsize}
\input{../data/seq-sat-6-ipc-scores}
\caption{Quality and score of sequential planners on the seq-sat-6 dataset.}
\label{tab:seq-sat-6-ipc-scores}
\end{subtable}

\vspace{0.5cm}
\begin{subfigure}{\textwidth}
\centering
\includegraphics[width=1.0\textwidth]{../imga/seq-sat-6-quality}
\caption{Quality plot of sequential planners on the seq-sat-6 dataset.}
\label{fig:seq-sat-6-quality}
\end{subfigure}
\caption{Planner results on seq-sat-6.}
\label{fig:seq-sat-6-results}
\end{figure}

\begin{figure}[tbp]
\centering
\begin{subtable}{\textwidth}
\centering
\scriptsize
\renewcommand{\footnotesize}{\scriptsize}
\input{../data/seq-sat-7-ipc-scores}
\caption{Quality and score of sequential planners on the seq-sat-7 dataset.}
\label{tab:seq-sat-7-ipc-scores}
\end{subtable}

\vspace{0.5cm}
\begin{subfigure}{\textwidth}
\centering
\includegraphics[width=1.0\textwidth]{../imga/seq-sat-7-quality}
\caption{Quality plot of sequential planners on the seq-sat-7 dataset.}
\label{fig:seq-sat-7-quality}
\end{subfigure}
\caption{Planner results on seq-sat-7.}
\label{fig:seq-sat-7-results}
\end{figure}

\begin{figure}[tbp]
\centering
\begin{subtable}{\textwidth}
\centering
\scriptsize
\renewcommand{\footnotesize}{\scriptsize}
\input{../data/seq-sat-8-ipc-scores}
\caption{Quality and score of sequential planners on the seq-sat-8 dataset.}
\label{tab:seq-sat-8-ipc-scores}
\end{subtable}

\vspace{0.5cm}
\begin{subfigure}{\textwidth}
\centering
\includegraphics[width=1.0\textwidth]{../imga/seq-sat-8-quality}
\caption{Quality plot of sequential planners on the seq-sat-8 dataset.}
\label{fig:seq-sat-8-quality}
\end{subfigure}
\caption{Planner results on seq-sat-8.}
\label{fig:seq-sat-8-results}
\end{figure}



\subsubsection{IPC 2008}

In the updated results of the sequential satisficing track of IPC 2008\footnote{\url{http://icaps-conference.org/ipc2008/deterministic/Results.html}} published after the competition,
the overall winner LAMA (a Fast Downward based planner)
was hands-down the best planner on the sequential Transport domain, winning
with a total quality of $28.93/30$, where all other planners had less than $20/30$.
Only 5 plans generated by LAMA had a worse total cost than the best known plans.

After adding our planners to the results,
the total quality of LAMA drops to $24.43/30$,
because several larger problems were solved better than the
best known solution from IPC 2008.
Our best planner on the IPC 2008 dataset, RRAPN, achieves a total quality of $27.77/30$,
which is a slight improvement over LAMA and other planners. The biggest gain of RRAPN is in being able to calculate
solutions of larger problems fast, which can be observed on
the results on problems 7--10 or 25--27,
which are the largest problems.
On the other hand, RRAPN fails to achieve optimal scores
on some smaller problems like problem number 2 or 12,
due to its explicit nature.

MSFA3 and MSFA5 are quite similar both in their construction and results on this dataset.
They generally obtain better results than RRAPN on smaller problems
(problems 2--3, 21--22),
but they can generate very good results even on larger problems,
like 14--20 or 28--29.
The reason why RRAPN occasionally obtains better plans than the
admissible heuristic of MSFA5 is that we weight it
with weights greater than or equal to 1,
therefore, making the heuristic inadmissible.
Based on total quality, MSFA5 marginally comes out on top as the better one of the two MSFA planners on this dataset.
All three of our planners beat all planners from the original competition based on total quality.

\subsubsection{IPC 2011}

The 2011 competition featured 20 sequential Transport problems,
with 4 planners (dae\_yahsp, LAMA 2008 and 2011, and roamer) achieving a total quality of more than $15/20$.
Interestingly, LAMA 2008 was able to produce better plans than its 2011 version in 12 out of 20 problems. The overall winner on Transport in 2011, roamer, achieved comparable scores on most problems to both versions of LAMA.

RRAPN consistenly achieves better scores than all domain-independent planners from the original competition in 17 out of the 20 problems (problem 4, 5, and 6). This can again be attributed to the size
of the problems (see Table~\ref{tab:dataset-dimensions}).

Even though RRAPN is better than the original planners more often than both MSFA planners,
they come out on top based on total cost.
The differences in performance between MSFA planners
is almost indistinguishable, even on individual problem instances.
Even more interesting, the problems
where they perform well are complementary to the ones where RRAPN performs well,
as is visible on the results of problems 3--6, 10--12, and 13--15.

\subsubsection{IPC 2014}

In the sequential satisficing track of IPC 2014, the winner on the Transport domain
was without a doubt the Mercury planner, achieving
a stunning $20/20$ total quality. Even more interesting is the fact that
the runner-up yahsp3-mt achieved a score of only $10.74/20$
and all other planners achieved sub $10/20$ total quality,
accentuating the performance of Mercury even more.

After adding the results of our planners to the quality table,
the total quality of yahsp3-mt is lowered to $10.29/20$.
Mercury loses its spotless results, but still significantly dominates all
other planners, including ours, at $19.25/20$.

RRAPN manages to outperform yahsp3-mt with $15.80/20$, yet it fails
to match the results of Mercury, not even in one problem.
Both MSFA planners outperform RRAPN on this dataset with qualities around $18.50/20$,
but still do not come reasonably close to beating Mercury.
However, they do (marginally) outperform Mercury on some problems, like
problems 4--7, 9--10, 12, and 18--19.
The results of MSFA3 and MSFA5 on this dataset are almost identical.

















\section{Temporal Transport}

In this section, we present the results of our temporal planners on the tempo-sat-6 dataset. The following planners are included in the experiment:
\begin{description}
\item[MSFA5Sched] The scheduled MSFA5 planner (Sections~\ref{msfa} and~\ref{sfa5})
\item[RRAPNSched] The scheduled (Section~\ref{sched}) RRAPN planner (Section~\ref{rrapn})
\item[TFD2014] The Temporal Fast Downward planner, version 0.4 from IPC~2014 \citep[Preferring Preferred Operators in Temporal Fast Downward]{Vallati2015}
\item[TRRAPN] The Temporal RRAPN planner (Section~\ref{temporal-approach})
\end{description}

An external temporal planner, TFD2014, was added to the experiments
to be able to compare our planners to more recent systems.
TFD2014 is a newer version of the original TFD planner that took part in IPC 2008. Additionally, it is the only planner which we allow to run for the full 30 minutes.

\subsection{Results}\label{temporal-results}

We show an IPC quality table and a quality plot of an experimental run of these planners on the tempo-sat-6 dataset (Figure~\ref{fig:tempo-sat-6-results}).
Additionally, sample Gantt charts \citep{Gantt1910} of two chosen plans are shown in Figure~\ref{fig:tempo-sat-6-gantt}.
The generated plans and benchmark results can be found in Attachment 1\comment{\nameref{cd-contents}}.

\begin{figure}[tbp]
\centering
\begin{subtable}{\textwidth}
\centering
\scriptsize
\setlength{\tabcolsep}{4.6pt}
\renewcommand{\footnotesize}{\scriptsize}
\input{../data/tempo-sat-6-ipc-scores}
\caption{Quality and score of temporal planners on the tempo-sat-6 dataset.}
\label{tab:tempo-sat-6-ipc-scores}
\end{subtable}

\vspace{0.5cm}
\begin{subfigure}{\textwidth}
\centering
\includegraphics[width=1.0\textwidth]{../imga/tempo-sat-6-quality}
\caption{Quality plot of temporal planners on the tempo-sat-6 dataset.}
\label{fig:tempo-sat-6-quality}
\end{subfigure}
\caption{Planner results on tempo-sat-6.}
\label{fig:tempo-sat-6-results}
\end{figure}

Planners that entered the 2008 temporal satisficing track at the IPC did not cope well with the Transport domain
--- only two non-baseline planners (SGPlan$_6$ and TFD) were able to produce at least one plan
for any problem. Additionally, only the smallest problem, problem number 1, was solved
to the best known score by any planner.
The best total quality was only $7.5/30$, achieved by
{SGPlan$_6$. No other domain in the temporal track had a lower best total quality
than Transport, which, assuming reasonably generated problem instances, hints
at Transport being one of the harder domains for domain-independent temporal planners.
We observe an evident performance increase of Temporal Fast Downward,
when comparing the qualities of plans of TFD (from 2008) and TFD2014.

Our results further show that using a simple domain-dependent scheduling approach
yields an improvement over domain-independent temporal planners
that took part in IPC 2008. Our scheduling planners RRAPNSched
and MSFA5Sched achieve total qualities of $27.13/30$
and $14.52/30$, respectively.
The scheduled MSFA5 planner does not generate plans of such variety as RRAPN,
and therefore produces worse results when scheduled using our algorithm,
mostly due to the inability of the scheduler to add enough \refuel{}
actions to the existing plans to make them feasible.

RRAPNSched, on the other hand, is able to beat even newer temporal planners like TFD2014
by a significant margin.
We see that RRAPNSched produces plans with worse scores than the best known score on smaller problems, which is mainly due to the fact that plans for smaller problems are easier to precalculate and hence the best known score estimate is closer
to the optimum than the estimates for larger problems.

An interesting case is problem number 10,
which was not solved by any of our planners based purely on scheduling.
This problem contains a single petrol station at location \texttt{city-loc-1},
which, unfortunately, is not present in many precomputed shortest
paths and the vehicles therefore do not drive through it often.
What is more, even fewer of those paths coincide with ones
on which the planners deliver packages.
This results in most generated plans being infeasible fuel-wise.

One way to solve the issue is to use TRRAPN planner's approach,
which knows about fuel during planning and 
sometimes adds fuel runs to the plan, during which a chosen vehicle
drives to a petrol station to refuel.
TRRAPN achieves the best total quality from all our planners,
beating RRAPNSched by about $0.8$,
even though it is marginally worse on some problems (for example, problems 4--7). TRRAPN makes up for this by getting better scores on
larger problems, where it takes RRAPNSched more effort to plan with fuel feasibly,
as can be observed on problems 10, 19, 26, and 30.

In Figure~\ref{fig:tempo-sat-6-gantt}, we see a comparison of the plans
of RRAPNSched and TFD2014 for problem number 12.
Observe that the important difference between the two plans
is that \texttt{truck-1} chooses to pick up and move \texttt{package-4}
while it is delivering \texttt{package-2}. It then later picks it up again and delivers
it while \texttt{truck-2} is delivering \texttt{package-3}.
In the plan of TFD2014, \texttt{truck-1} did not pick up \texttt{package-4}
while delivering \texttt{package-2} and then had to travel further to deliver it
--- this is basically the only difference between the two plans,
and it makes a difference in makespans of more than 50.
Finally, observe that due to the nature of RRAPN, \texttt{truck-1}
dropped \texttt{package-4} and then went back to pick it up, even though it had enough capacity
to carry it for the whole time. Another important observation, however, is that this had no effect on the total makespan
of the plan.

\section{Overall results}

The attained results show that domain-specific information can be leveraged
to generate plans of better quality.
We have designed and implemented Transport planners that are able to beat
all results from the sequential
and temporal satisficing tracks of the 2008 and 2011 IPCs.
In the 2014 IPC, we would have attained second place on overall quality in the Transport domain, behind the impressive result of Mercury. 
Our planners achieve satisfactory results across datasets,
as can be observed in Table~\ref{tab:planner-summary}.

\begin{table}[tb]
\centering
\begin{subtable}[t]{0.48\textwidth}
\centering
\begin{tabular}{lr}
\toprule
\multirow{2}{*}{\textbf{Planner}} & \textbf{Average}\\
& \textbf{quality}\\
\midrule
MSFA3 & 0.924\\
MSFA5 & \textbf{0.928}\\
RRAPN & 0.890\\
\bottomrule
\end{tabular}
\caption{Average quality on sequential datasets.}
\label{tab:seq-summary}
\end{subtable}
\quad
\begin{subtable}[t]{0.48\textwidth}
\centering
\begin{tabular}{lr}
\toprule
\multirow{2}{*}{\textbf{Planner}} & \textbf{Average}\\
& \textbf{quality}\\
\midrule
MSFA5Sched & 0.484\\
RRAPNSched & 0.904\\
TRRAPN & \textbf{0.932}\\
\bottomrule
\end{tabular}
\caption{Average quality the temporal dataset.}
\label{tab:tempo-summary}
\end{subtable}
\caption{Average quality of our planners across datasets.}
\label{tab:planner-summary}
\end{table}

Another major advantage previously unmentioned is that
our planners generate good solutions quite fast.
To show this, we present results from running all our planners on all problems for 3 seconds each (Table~\ref{tab:planner-results-short}).
The achieved scores are very close to the
scores from long planning runs, except for problems
where the planner did not find a plan at all in the
given time limit.

\begin{figure}[!b]
\centering
\begin{subfigure}{0.8\textwidth}
\centering
\includegraphics[width=1\textwidth]{../imga/tempo-sat-6-gantt-p12-RRAPN}
\caption{RRAPNSched}
\label{fig:tempo-sat-6-gantt-12-rrapn}
\end{subfigure}

\begin{subfigure}{0.8\textwidth}
\vspace{0.2cm}
\centering
\includegraphics[width=1\textwidth]{../imga/tempo-sat-6-gantt-p12-TFD}
\caption{TFD2014}
\label{fig:tempo-sat-6-gantt-12-tfd}
\end{subfigure}
\caption{Gantt charts of the RRAPNSched and TFD2014 planners on the tempo-sat-6 \texttt{p12} problem.}
\label{fig:tempo-sat-6-gantt}
\end{figure}

\begin{table}[p]
\centering
\begin{subtable}{0.48\textwidth}
\centering
\scriptsize
\renewcommand{\footnotesize}{\scriptsize}
\setlength{\tabcolsep}{3.5pt}
\input{../data/seq-sat-6-ipc-scores-short}
\caption{Quality and score of our planners on the seq-sat-6 dataset.}
\label{tab:seq-sat-6-ipc-scores-short}
\end{subtable}
\quad
\begin{subtable}{0.48\textwidth}
\centering
\scriptsize
\renewcommand{\footnotesize}{\scriptsize}
\setlength{\tabcolsep}{2pt}
\input{../data/tempo-sat-6-ipc-scores-short}
\caption{Quality and rounded score of our planners on the tempo-sat-6 dataset.}
\label{tab:tempo-sat-6-ipc-scores-short}
\end{subtable}

\vspace{0.5cm}
\begin{subtable}{0.48\textwidth}
\centering
\scriptsize
\renewcommand{\footnotesize}{\scriptsize}
\setlength{\tabcolsep}{3.5pt}
\input{../data/seq-sat-7-ipc-scores-short}
\caption{Quality and score of our planners on the seq-sat-7 dataset.}
\label{tab:seq-sat-7-ipc-scores-short}
\end{subtable}
\quad
\begin{subtable}{0.48\textwidth}
\centering
\scriptsize
\renewcommand{\footnotesize}{\scriptsize}
\setlength{\tabcolsep}{3.5pt}
\input{../data/seq-sat-8-ipc-scores-short}
\caption{Quality and score of our planners on the seq-sat-8 dataset.}
\label{tab:seq-sat-8-ipc-scores-short}
\end{subtable}
\caption{Results of our planners when run for 3 seconds on all datasets.}
\label{tab:planner-results-short}
\end{table}

