\newpage
\subsection{Part 1: Modelling Sokoban}
\subsubsection{Task 1: Knowledge base}
\begin{itemize}
	\item{Q1}\\
		We describe the connections using the four main directional words,
		namely: $north,south,east,west$ and the predicate $connected(From, To,
		Direction)$. In this way the push possibility axiom can check in the
		direction of the crate to see if the push is a valid move. In this way we
		don't have to do anything fancy with arithmetics.
	\item{Q2}\\
		We use the functions $agent(X, S_i), crate(cratename, X, S_i)$ and
		$target(cratename, X)$ to easily represent the information. We chose to
		hard code the locations of the crates because then the resolution will be
		much faster.
	\item{Q3}\\
		$\begin{array}{llllll}
			connected(loc11, loc21, east) & \wedge &
			connected(loc11, loc12, north) & \wedge &
			connected(loc12, loc22, east) & \wedge\\
			connected(loc12, loc13, north) & \wedge &
			connected(loc13, loc23, east) & \wedge &
			connected(loc13, loc14, north) & \wedge\\
			connected(loc14, loc24, east) & \wedge &
			connected(loc21, loc31, east) & \wedge &
			connected(loc21, loc22, north) & \wedge\\
			connected(loc22, loc32, east) & \wedge &
			connected(loc22, loc23, north) & \wedge &
			connected(loc23, loc33, east) & \wedge\\
			connected(loc23, loc24, north) & \wedge &
			connected(loc31, loc32, north) & \wedge &
			connected(loc32, loc33, north) & \wedge\\
			connected(loc21, loc11, west) & \wedge &
			connected(loc12, loc11, south) & \wedge &
			connected(loc22, loc12, west) & \wedge\\
			connected(loc13, loc12, south) & \wedge &
			connected(loc23, loc13, west) & \wedge &
			connected(loc14, loc13, south) & \wedge\\
			connected(loc24, loc14, west) & \wedge &
			connected(loc31, loc21, west) & \wedge &
			connected(loc22, loc21, south) & \wedge\\
			connected(loc32, loc22, west) & \wedge &
			connected(loc23, loc22, south) & \wedge &
			connected(loc33, loc23, west) & \wedge\\
			connected(loc24, loc23, south) & \wedge &
			connected(loc32, loc31, south) & \wedge &
			connected(loc33, loc32, south) & \wedge\\
			crate(cratec, loc21, s0) & \wedge &
			crate(crateb, loc22, s0) & \wedge &
			crate(cratea, loc23, s0) & \wedge\\
			agent(loc32, s0) & \wedge\\
		\end{array}$
	\item{Q4}\\
		$goal(s)\rightarrow\\
		crate(cratea, loc12, s) \wedge
		crate(crateb, loc13, s) \wedge
		crate(cratec, loc11, s)$
\end{itemize}

\subsubsection{Task 2: Actions}
\begin{itemize}
	\item{Q5}\\
		$\begin{array}{rl}
			Poss(move(x, y), s) & \equiv \\
				& (\exists z: connected(x, y, z)) \wedge\\
				& \neg(crate(x, y, s))
		\end{array}$
	\item{Q6}\\
		$\begin{array}{rl}
			Poss(push(x, y), s) & \equiv\\
				& agent(x, s) \wedge\\
				& (\exists z:
					connected(x, z, y) \wedge
					(\exists \gamma: crate(\gamma, z, s))
					\wedge\\
				&	(\exists \alpha: 
						connected(z, \alpha, y) \wedge
						(\nexists \beta: crate(\beta, \alpha, s))
					)
				)
		\end{array}$
	\item{Q7}\\
		$\begin{array}{rl}
			agent(x, result(z, s)) & \rightarrow\\
				& (\exists y: z = move(y, x)) \vee\\
				& (\exists \alpha:
					z = push(\beta, \alpha) \wedge
					connected(\beta, x, \alpha)) \vee\\
				& (\exists \epsilon, \gamma:
					z \neq move(x, \epsilon) \wedge
					z \neq push(x, \gamma) \wedge
					agent(x, s))\\
					crate(x, y, result(A, s)) & \rightarrow\\
				& (\exists z,\alpha:
					A = push(z\wedge \alpha)\wedge\\
				&	(\exists \beta:
						connected(z\wedge \beta\wedge \alpha)\wedge
						connected(\beta\wedge y\wedge \alpha)\wedge
						crate(x\wedge \beta\wedge s)
					)
				) \vee\\
				& (\exists z,\alpha:
					A \neq push(z, \alpha)\wedge
					connected(z, y, \alpha)\wedge
					crate(x, y, s)
				)
		\end{array}$
\end{itemize}

\newpage
\subsection{Part 2: Implementation}
\subsubsection{Task 3: Translate Axioms}
The domain description can be found in \textit{./src/domaintask1.pl} and in
Listing~\ref{domaintask1} and is a literal translation from logics to
\textit{prolog} code except for the visited predicate. The visited predicate
disallows the agent to reverse it's previous move immediately. This makes the
planning much faster because it can cut of a lot of branches.

\subsubsection{Task 4: The Planning Problem in Figure 1}
The instance description for this task can be found in
\textit{./src/instancetask4.pl} and in Listing~\ref{instancetask4}. This is a
literal translation of the description in logics. The goal location for the
crates are hard coded to increase the performance.

\subsubsection{Task 5: Crates go to Any Goal Location}
The instance description for this task can be found in
\textit{./src/instancetask5.pl} and in Listing~\ref{instancetask5}. This is an
adaptation of Listing~\ref{instancetask4} in the sense that in the goal state
the same goal locations for the crates apply but the crate instance does not
matter any more. Any combination of crates on the locations will be a valid
goal.

\subsubsection{Task 6: Inverse Problem}
For tackling the inverse problem we have added a visited predicate that
describes if the agent has visited that particular location. In the instance
description found in \textit{./src/instancetask6.pl} or in
Listing~\ref{instancetask6} we made sure to mark the starting location for the
agent as visited because the agent does not have to revisit the starting
location. The goal is a simple \textit{forall} that will only satisfy if for
all locations known the visited fluent is true. To generate all locations we
used the fact that all locations are connected to some other location. This
could be implemented more efficiently because in the current situation the
locations sequence contains a lot of duplicate locations. We reused the domain
description from task 4 with the visited fluent and adapted it slightly so that
it is never unset and therefore records all locations the agent has been. The
full ode can be found in \textit{./src/domaintask6.pl} or in
Listing~\ref{domaintask6}.

\newpage
\subsection{Part 3: Extending the domain}
\subsubsection{Task 7: Unlocking the Crates}
For adding keys we have added in the instance definition, found in
\textit{./src/instancetask7.pl} or Listing~\ref{instancetask7}, new key fluents
that define were the keys are found. We also changed the crate fluent to arity
$4$ so that it also has a key attached to it. In the domain specification,
found in \textit{./src/domaintask7.pl} or Listing~\ref{domaintask7}, we added a
pickup move that allows the agent to pickup a certain key. When the agent picks
up a key the \textit{keyinbag} fluent is then set so that the possibility
function for the push action can incorporate the fact that a key has to be
picked up to push a certain crate.

\newpage
\subsection{Part 4: General questions}
\subsubsection{Task 10: Sitcalc expressivity}
Situation calculus(\textit{sitcalc} from now on) is very expressive because you
can express yourself very detailed without encountering the frame problem. When
the problem space expands the computational strength needed explodes.
\textit{Sitcalc} is therefore not very useful when you want to plan far behind.
For comparison, calculating a \textit{sokoban} path 10 steps in the future
already takes hours on a normal computer.

The model is easy to extend to bigger and more complex problems, it doesn't
scale that well however...

\subsubsection{Task 11: Related work}
Zhou, N. (2013). A Tabled Prolog Program for Solving Sokoban, 124, 561–575. doi:10.3233/FI-2013-849

The paper treats the \textit{sokoban} problem as a general shortest path
problem. And it also uses lookup tables to speed up the search. This was used
in a competition on certain \textit{sokoban} problems.
