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                 hard code 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
 115 \textit{prolog} code except for the visited predicate. The visited predicate
 116 disallows the agent to reverse it's previous move immediately. This makes the
 117 planning much 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 hard coded 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 \textit{forall} that will only satisfy if for
 140 all locations known the visited fluent is true. To generate all locations we
 141 used the fact that all locations are connected to some other location. This
 142 could be implemented more efficiently because in the current situation the
 143 locations 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 \textit{keyinbag} fluent is then set so that the possibility
 159 function for the push action can incorporate the fact that a key has to be
 160 picked up to push a certain crate.
 161
 162 \newpage
 163 \subsection{Part 4: General questions}
 164 \subsubsection{Task 10: Sitcalc expressivity}
 165 Situation calculus(\textit{sitcalc} from now on) is very expressive because you
 166 can express yourself very detailed without encountering the frame problem. When
 167 the problem space expands the computational strength needed explodes.
 168 \textit{Sitcalc} is therefore not very useful when you want to plan far behind.
 169 For comparison, calculating a \textit{sokoban} path 10 steps in the future
 170 already takes hours on a 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 \textit{sokoban} problem as a general shortest path
 179 problem. And it also uses lookup tables to speed up the search. This was used
 180 in a competition on certain \textit{sokoban} problems.