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
  58
  59 \end{itemize}
  60
  61 \subsubsection{Task 2: Actions}
  62 \begin{itemize}
  63         \item{Q5}\\
  64                 $Poss(move(x, y), s) \equiv \\
  65                 (\exists z: connected(x, y, z)) \wedge\\
  66                 \neg(crate(x, y, s))$
  67         \item{Q6}\\
  68                 $Poss(push(x, y), s) \equiv\\
  69                         agent(x, s) \wedge\\
  70                         (\exists z:
  71                                 connected(x, z, y) \wedge
  72                                 (\exists \gamma: crate(\gamma, z, s))
  73                         \wedge\\
  74                                 (\exists \alpha:
  75                         connected(z, \alpha, y) \wedge
  76                                 (\nexists \beta: crate(\beta, \alpha, s))))$
  77         \item{Q7}\\
  78                 $agent(x, result(z, s)) \rightarrow\\
  79                         (\exists y: z = move(y, x)) \vee\\
  80                         (\exists \alpha:
  81                                 z = push(\beta, \alpha) \wedge
  82                                 connected(\beta, x, \alpha)) \vee\\
  83                         (\exists \epsilon, \gamma:
  84                                 z \neq move(x, \epsilon) \wedge
  85                                 z \neq push(x, \gamma) \wedge
  86                                 agent(x, s))\\
  87                 crate(x, y, result(A, s)) \rightarrow\\
  88                         (\exists z,\alpha:
  89                                 A = push(z, \alpha),
  90                                 (\exists \beta:
  91                                         connected(z, \beta, \alpha),
  92                                         connected(\beta, y, \alpha),
  93                                         crate(x, \beta, s)
  94                                 )
  95                         ) \vee\\
  96                         (\exists z,\alpha:
  97                                 A \neq push(z, \alpha)\wedge
  98                                 connected(z, y, \alpha)\wedge
  99                                 crate(x, y, s)
 100                         )
 101                 $
 102 \end{itemize}
 103
 104 \subsection{Part 2: Implementation}
 105 \subsubsection{Task 3: Translate Axioms}
 106 The only optimization added to the file is the reverse move optimization,
 107 disallowing the agent to reverse a move immediatly.
 108 \inputminted{prolog}{./src/domaintask1.pl}
 109
 110 \subsubsection{Task 4: The Planning Problem in Figure 1}
 111 \inputminted{prolog}{./src/instancetask4.pl}
 112
 113 \subsubsection{Task 5: Crates go to Any Goal Location}
 114 \inputminted{prolog}{./src/instancetask5.pl}
 115
 116 \subsubsection{Task 6: Inverse Problem}
 117
 118 \subsection{Part 3: Extending the domain}
 119
 120 \subsection{Part 4: General questions}
 121 \subsubsection{Task 10: Sitcalc expressivity}
 122 Situation calculus(sitcalc from now on) is very expressive because you can
 123 express yourself very detailed without encountering the frame problem. When the
 124 problem space expands the computational strength needed explodes. Sitcalc is
 125 therefore not very usefull when you want to plan far behind. For comparison,
 126 calculating a sokoban path 10 steps in the future already takes hours on a
 127 normal computer.
 128
 129 The model is easy to extend to bigger and more complex problems, it doesn't
 130 scale that well however...
 131
 132 \subsubsection{Task 11: Related work}
 133 Zhou, N. (2013). A Tabled Prolog Program for Solving Sokoban, 124, 561–575. doi:10.3233/FI-2013-849