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 only optimization added to the file is the reverse move optimization,
 114 disallowing the agent to reverse a move immediatly.
 115 \begin{listing}[H]
 116         \caption{Domain description task 1}
 117         \prologcode{./src/domaintask1.pl}
 118 \end{listing}
 119
 120 \subsubsection{Task 4: The Planning Problem in Figure 1}
 121 \begin{listing}[H]
 122         \caption{Instance description task 4}
 123         \prologcode{./src/instancetask4.pl}
 124 \end{listing}
 125
 126 \subsubsection{Task 5: Crates go to Any Goal Location}
 127 \begin{listing}[H]
 128         \caption{Instance description task 5}
 129         \prologcode{./src/instancetask5.pl}
 130 \end{listing}
 131
 132 \subsubsection{Task 6: Inverse Problem}
 133 \begin{listing}[H]
 134         \caption{Instance description task 6}
 135         \prologcode{./src/instancetask6.pl}
 136 \end{listing}
 137 \begin{listing}[H]
 138         \caption{Domain description task 6}
 139         \prologcode{./src/domaintask6.pl}
 140 \end{listing}
 141
 142 \newpage
 143 \subsection{Part 3: Extending the domain}
 144 \subsubsection{Task 7: Unlocking the Crates}
 145 \begin{listing}[H]
 146         \caption{Instance description task 7}
 147         \prologcode{./src/instancetask7.pl}
 148 \end{listing}
 149 \begin{listing}[H]
 150         \caption{Domain description task 7}
 151         \prologcode{./src/domaintask7.pl}
 152 \end{listing}
 153
 154 \newpage
 155 \subsection{Part 4: General questions}
 156 \subsubsection{Task 10: Sitcalc expressivity}
 157 Situation calculus(sitcalc from now on) is very expressive because you can
 158 express yourself very detailed without encountering the frame problem. When the
 159 problem space expands the computational strength needed explodes. Sitcalc is
 160 therefore not very usefull when you want to plan far behind. For comparison,
 161 calculating a sokoban path 10 steps in the future already takes hours on a
 162 normal computer.
 163
 164 The model is easy to extend to bigger and more complex problems, it doesn't
 165 scale that well however...
 166
 167 \subsubsection{Task 11: Related work}
 168 Zhou, N. (2013). A Tabled Prolog Program for Solving Sokoban, 124, 561–575. doi:10.3233/FI-2013-849
 169
 170 The paper treats the sokoban problem as a general shortest path problem. And it
 171 also uses lookup tables to speed up the search. This was used in a competition
 172 on certain sokoban problems.