report/ass1.tex

   1 \subsection{Part 1: Modelling Sokoban}
   2 \subsubsection{Task 1: Knowledge base}
   3 \begin{itemize}
   4         \item{Q1}\\
   5                 We describe the connections using the four main directional words,
   6                 namely: $north,south,east,west$. We only define the connection for the
   7                 $north$ and $east$ directions because we can infer the $south$ and
   8                 $west$ directions from it.
   9         \item{Q2}\\
  10                 We use the functions $agent(X, S_i), crate(cratename, X, S_i)$ and
  11                 $target(cratename, X)$ to easily represent the information.
  12         \item{Q3}\\
  13                 $\begin{array}{llllll}
  14                         connected(loc11, loc21, east) & \wedge &
  15                         connected(loc11, loc12, north) & \wedge &
  16                         connected(loc12, loc22, east) & \wedge\\
  17                         connected(loc12, loc13, north) & \wedge &
  18                         connected(loc13, loc23, east) & \wedge &
  19                         connected(loc13, loc14, north) & \wedge\\
  20                         connected(loc14, loc24, east) & \wedge &
  21                         connected(loc21, loc31, east) & \wedge &
  22                         connected(loc21, loc22, north) & \wedge\\
  23                         connected(loc22, loc32, east) & \wedge &
  24                         connected(loc22, loc23, north) & \wedge &
  25                         connected(loc23, loc33, east) & \wedge\\
  26                         connected(loc23, loc24, north) & \wedge &
  27                         connected(loc31, loc32, north) & \wedge &
  28                         connected(loc32, loc33, north) & \wedge\\
  29                         connected(loc21, loc11, west) & \wedge &
  30                         connected(loc12, loc11, south) & \wedge &
  31                         connected(loc22, loc12, west) & \wedge\\
  32                         connected(loc13, loc12, south) & \wedge &
  33                         connected(loc23, loc13, west) & \wedge &
  34                         connected(loc14, loc13, south) & \wedge\\
  35                         connected(loc24, loc14, west) & \wedge &
  36                         connected(loc31, loc21, west) & \wedge &
  37                         connected(loc22, loc21, south) & \wedge\\
  38                         connected(loc32, loc22, west) & \wedge &
  39                         connected(loc23, loc22, south) & \wedge &
  40                         connected(loc33, loc23, west) & \wedge\\
  41                         connected(loc24, loc23, south) & \wedge &
  42                         connected(loc32, loc31, south) & \wedge &
  43                         connected(loc33, loc32, south) & \wedge\\
  44                         crate(cratec, loc21, s0) & \wedge &
  45                         crate(crateb, loc22, s0) & \wedge &
  46                         crate(cratea, loc23, s0) & \wedge\\
  47                         target(cratea, loc12) & \wedge &
  48                         target(crateb, loc13) & \wedge &
  49                         target(cratec, loc11) & \wedge\\
  50                         agent(loc32, s0) & \wedge\\
  51                 \end{array}$
  52         \item{Q4}\\
  53                 $goal(s)\rightarrow\\
  54                 crate(cratea, loc12, s) \wedge
  55                 crate(crateb, loc13, s) \wedge
  56                 crate(cratec, loc11, s)$
  57 \end{itemize}
  58
  59 \subsubsection{Task 2: Actions}
  60 \begin{itemize}
  61         \item{Q5}\\
  62                 $\begin{array}{rl}
  63                         Poss(move(x, y), s) & \equiv \\
  64                                 & (\exists z: connected(x, y, z)) \wedge\\
  65                                 & \neg(crate(x, y, s))
  66                 \end{array}$
  67         \item{Q6}\\
  68                 $\begin{array}{rl}
  69                         Poss(push(x, y), s) & \equiv\\
  70                                 & agent(x, s) \wedge\\
  71                                 & (\exists z:
  72                                         connected(x, z, y) \wedge
  73                                         (\exists \gamma: crate(\gamma, z, s))
  74                                         \wedge\\
  75                                 &       (\exists \alpha:
  76                                                 connected(z, \alpha, y) \wedge
  77                                                 (\nexists \beta: crate(\beta, \alpha, s))
  78                                         )
  79                                 )
  80                 \end{array}$
  81         \item{Q7}\\
  82                 $\begin{array}{rl}
  83                         agent(x, result(z, s)) & \rightarrow\\
  84                                 & (\exists y: z = move(y, x)) \vee\\
  85                                 & (\exists \alpha:
  86                                         z = push(\beta, \alpha) \wedge
  87                                         connected(\beta, x, \alpha)) \vee\\
  88                                 & (\exists \epsilon, \gamma:
  89                                         z \neq move(x, \epsilon) \wedge
  90                                         z \neq push(x, \gamma) \wedge
  91                                         agent(x, s))\\
  92                                         crate(x, y, result(A, s)) & \rightarrow\\
  93                                 & (\exists z,\alpha:
  94                                         A = push(z, \alpha),
  95                                         (\exists \beta:
  96                                                 connected(z, \beta, \alpha),
  97                                                 connected(\beta, y, \alpha),
  98                                                 crate(x, \beta, s)
  99                                         )
 100                                 ) \vee\\
 101                                 & (\exists z,\alpha:
 102                                         A \neq push(z, \alpha)\wedge
 103                                         connected(z, y, \alpha)\wedge
 104                                         crate(x, y, s)
 105                                 )
 106                 \end{array}$
 107 \end{itemize}
 108
 109 \subsection{Part 2: Implementation}
 110 \subsubsection{Task 3: Translate Axioms}
 111 The only optimization added to the file is the reverse move optimization,
 112 disallowing the agent to reverse a move immediatly.
 113 \begin{listing}[H]
 114         \caption{Domain description task 1}
 115         \prologcode{./src/domaintask1.pl}
 116 \end{listing}
 117
 118 \subsubsection{Task 4: The Planning Problem in Figure 1}
 119 \begin{listing}[H]
 120         \caption{Instance description task 4}
 121         \prologcode{./src/instancetask4.pl}
 122 \end{listing}
 123
 124 \subsubsection{Task 5: Crates go to Any Goal Location}
 125 \begin{listing}[H]
 126         \caption{Instance description task 5}
 127         \prologcode{./src/instancetask5.pl}
 128 \end{listing}
 129
 130 \subsubsection{Task 6: Inverse Problem}
 131
 132 \subsection{Part 3: Extending the domain}
 133 \subsubsection{Task 7: Unlocking the Crates}
 134 \begin{listing}[H]
 135         \caption{Instance description task 7}
 136         \prologcode{./src/instancetask7.pl}
 137 \end{listing}
 138 \begin{listing}[H]
 139         \caption{Domain description task 7}
 140         \prologcode{./src/domaintask7.pl}
 141 \end{listing}
 142
 143 \subsection{Part 4: General questions}
 144 \subsubsection{Task 10: Sitcalc expressivity}
 145 Situation calculus(sitcalc from now on) is very expressive because you can
 146 express yourself very detailed without encountering the frame problem. When the
 147 problem space expands the computational strength needed explodes. Sitcalc is
 148 therefore not very usefull when you want to plan far behind. For comparison,
 149 calculating a sokoban path 10 steps in the future already takes hours on a
 150 normal computer.
 151
 152 The model is easy to extend to bigger and more complex problems, it doesn't
 153 scale that well however...
 154
 155 \subsubsection{Task 11: Related work}
 156 Zhou, N. (2013). A Tabled Prolog Program for Solving Sokoban, 124, 561–575. doi:10.3233/FI-2013-849