report/ass1.tex

   1 \newpage
   2 \subsection{Part 1: Modelling Sokoban}
   3 \subsubsection{Task 1: Knowledge base}
   4 \begin{itemize}
   5         \item{Q1}\\
   6                 We describe the connections using the four main directional words,
   7                 namely: $north,south,east,west$ and the predicate $connected(From, To,
   8                 Direction)$. In this way the push possibility axiom can check in the
   9                 direction of the crate to see if the push is a valid move. In this way we
  10                 don't have to do anything fancy with arithmetics.
  11         \item{Q2}\\
  12                 We use the functions $agent(X, S_i), crate(cratename, X, S_i)$ and
  13                 $target(cratename, X)$ to easily represent the information. We chose to
  14                 hardcode the locations of the crates because then the resolution will be
  15                 much faster.
  16         \item{Q3}\\
  17                 $\begin{array}{llllll}
  18                         connected(loc11, loc21, east) & \wedge &
  19                         connected(loc11, loc12, north) & \wedge &
  20                         connected(loc12, loc22, east) & \wedge\\
  21                         connected(loc12, loc13, north) & \wedge &
  22                         connected(loc13, loc23, east) & \wedge &
  23                         connected(loc13, loc14, north) & \wedge\\
  24                         connected(loc14, loc24, east) & \wedge &
  25                         connected(loc21, loc31, east) & \wedge &
  26                         connected(loc21, loc22, north) & \wedge\\
  27                         connected(loc22, loc32, east) & \wedge &
  28                         connected(loc22, loc23, north) & \wedge &
  29                         connected(loc23, loc33, east) & \wedge\\
  30                         connected(loc23, loc24, north) & \wedge &
  31                         connected(loc31, loc32, north) & \wedge &
  32                         connected(loc32, loc33, north) & \wedge\\
  33                         connected(loc21, loc11, west) & \wedge &
  34                         connected(loc12, loc11, south) & \wedge &
  35                         connected(loc22, loc12, west) & \wedge\\
  36                         connected(loc13, loc12, south) & \wedge &
  37                         connected(loc23, loc13, west) & \wedge &
  38                         connected(loc14, loc13, south) & \wedge\\
  39                         connected(loc24, loc14, west) & \wedge &
  40                         connected(loc31, loc21, west) & \wedge &
  41                         connected(loc22, loc21, south) & \wedge\\
  42                         connected(loc32, loc22, west) & \wedge &
  43                         connected(loc23, loc22, south) & \wedge &
  44                         connected(loc33, loc23, west) & \wedge\\
  45                         connected(loc24, loc23, south) & \wedge &
  46                         connected(loc32, loc31, south) & \wedge &
  47                         connected(loc33, loc32, south) & \wedge\\
  48                         crate(cratec, loc21, s0) & \wedge &
  49                         crate(crateb, loc22, s0) & \wedge &
  50                         crate(cratea, loc23, s0) & \wedge\\
  51                         agent(loc32, s0) & \wedge\\
  52                 \end{array}$
  53         \item{Q4}\\
  54                 $goal(s)\rightarrow\\
  55                 crate(cratea, loc12, s) \wedge
  56                 crate(crateb, loc13, s) \wedge
  57                 crate(cratec, loc11, s)$
  58 \end{itemize}
  59
  60 \subsubsection{Task 2: Actions}
  61 \begin{itemize}
  62         \item{Q5}\\
  63                 $\begin{array}{rl}
  64                         Poss(move(x, y), s) & \equiv \\
  65                                 & (\exists z: connected(x, y, z)) \wedge\\
  66                                 & \neg(crate(x, y, s))
  67                 \end{array}$
  68         \item{Q6}\\
  69                 $\begin{array}{rl}
  70                         Poss(push(x, y), s) & \equiv\\
  71                                 & agent(x, s) \wedge\\
  72                                 & (\exists z:
  73                                         connected(x, z, y) \wedge
  74                                         (\exists \gamma: crate(\gamma, z, s))
  75                                         \wedge\\
  76                                 &       (\exists \alpha:
  77                                                 connected(z, \alpha, y) \wedge
  78                                                 (\nexists \beta: crate(\beta, \alpha, s))
  79                                         )
  80                                 )
  81                 \end{array}$
  82         \item{Q7}\\
  83                 $\begin{array}{rl}
  84                         agent(x, result(z, s)) & \rightarrow\\
  85                                 & (\exists y: z = move(y, x)) \vee\\
  86                                 & (\exists \alpha:
  87                                         z = push(\beta, \alpha) \wedge
  88                                         connected(\beta, x, \alpha)) \vee\\
  89                                 & (\exists \epsilon, \gamma:
  90                                         z \neq move(x, \epsilon) \wedge
  91                                         z \neq push(x, \gamma) \wedge
  92                                         agent(x, s))\\
  93                                         crate(x, y, result(A, s)) & \rightarrow\\
  94                                 & (\exists z,\alpha:
  95                                         A = push(z\wedge \alpha)\wedge\\
  96                                 &       (\exists \beta:
  97                                                 connected(z\wedge \beta\wedge \alpha)\wedge
  98                                                 connected(\beta\wedge y\wedge \alpha)\wedge
  99                                                 crate(x\wedge \beta\wedge s)
 100                                         )
 101                                 ) \vee\\
 102                                 & (\exists z,\alpha:
 103                                         A \neq push(z, \alpha)\wedge
 104                                         connected(z, y, \alpha)\wedge
 105                                         crate(x, y, s)
 106                                 )
 107                 \end{array}$
 108 \end{itemize}
 109
 110 \newpage
 111 \subsection{Part 2: Implementation}
 112 \subsubsection{Task 3: Translate Axioms}
 113 The domain description can be found in \textit{./src/domaintask1.pl} and in
 114 Listing~\ref{domaintask1} and is a literal translation from logics to prolog
 115 code except for the visited predicate. The visited predicate disallows the
 116 agent to reverse it's previous move immediatly. This makes the planning much
 117 faster because it can cut of a lot of branches.
 118
 119 \subsubsection{Task 4: The Planning Problem in Figure 1}
 120 The instance description for this task can be found in
 121 \textit{./src/instancetask4.pl} and in Listing~\ref{instancetask4}. This is a
 122 literal translation of the description in logics. The goal location for the
 123 crates are hardcoded to increase the performance.
 124
 125 \subsubsection{Task 5: Crates go to Any Goal Location}
 126 The instance description for this task can be found in
 127 \textit{./src/instancetask5.pl} and in Listing~\ref{instancetask5}. This is an
 128 adaptation of Listing~\ref{instancetask4} in the sense that in the goal state
 129 the same goal locations for the crates apply but the crate instance does not
 130 matter any more. Any combination of crates on the locations will be a valid
 131 goal.
 132
 133 \subsubsection{Task 6: Inverse Problem}
 134 For tackling the inverse problem we have added a visited predicate that
 135 describes if the agent has visited that particular location. In the instance
 136 description found in \textit{./src/instancetask6.pl} or in
 137 Listing~\ref{instancetask6} we made sure to mark the starting location for the
 138 agent as visited because the agent does not have to revisit the starting
 139 location. The goal is a simple forall that will only satisfy if for all
 140 locations known the visited fluent is true. To generate all locations we used
 141 the fact that all locations are connected to some other location. This could be
 142 implemented more efficiently because in the current situation the locations
 143 sequence contains a lot of duplicate locations. We reused the domain
 144 description from task 4 with the visited fluent and adapted it slightly so that
 145 it is never unset and therefore records all locations the agent has been. The
 146 full ode can be found in \textit{./src/domaintask6.pl} or in
 147 Listing~\ref{domaintask6}.
 148
 149 \newpage
 150 \subsection{Part 3: Extending the domain}
 151 \subsubsection{Task 7: Unlocking the Crates}
 152 For adding keys we have added in the instance definition, found in
 153 \textit{./src/instancetask7.pl} or Listing~\ref{instancetask7}, new key fluents
 154 that define were the keys are found. We also changed the crate fluent to arity
 155 $4$ so that it also has a key attached to it. In the domain specification,
 156 found in \textit{./src/domaintask7.pl} or Listing~\ref{domaintask7}, we added a
 157 pickup move that allows the agent to pickup a certain key. When the agent picks
 158 up a key the keyinbag fluent is then set so that the possibility function for
 159 the push action can incorporate the fact that a key has to be picked up to push
 160 a certain crate.
 161
 162 \newpage
 163 \subsection{Part 4: General questions}
 164 \subsubsection{Task 10: Sitcalc expressivity}
 165 Situation calculus(sitcalc from now on) is very expressive because you can
 166 express yourself very detailed without encountering the frame problem. When the
 167 problem space expands the computational strength needed explodes. Sitcalc is
 168 therefore not very usefull when you want to plan far behind. For comparison,
 169 calculating a sokoban path 10 steps in the future already takes hours on a
 170 normal computer.
 171
 172 The model is easy to extend to bigger and more complex problems, it doesn't
 173 scale that well however...
 174
 175 \subsubsection{Task 11: Related work}
 176 Zhou, N. (2013). A Tabled Prolog Program for Solving Sokoban, 124, 561–575. doi:10.3233/FI-2013-849
 177
 178 The paper treats the sokoban problem as a general shortest path problem. And it
 179 also uses lookup tables to speed up the search. This was used in a competition
 180 on certain sokoban problems.