2 \subsection{Part
1: Modelling Sokoban
}
3 \subsubsection{Task
1: Knowledge base
}
6 We describe the connections using the four main directional words,
7 namely: $north,south,east,west$. We only define the connection for the
8 $north$ and $east$ directions because we can infer the $south$ and
9 $west$ directions from it.
11 We use the functions $agent(X, S_i), crate(cratename, X, S_i)$ and
12 $target(cratename, X)$ to easily represent the information.
14 $
\begin{array
}{llllll
}
15 connected(loc11, loc21, east) &
\wedge &
16 connected(loc11, loc12, north) &
\wedge &
17 connected(loc12, loc22, east) &
\wedge\\
18 connected(loc12, loc13, north) &
\wedge &
19 connected(loc13, loc23, east) &
\wedge &
20 connected(loc13, loc14, north) &
\wedge\\
21 connected(loc14, loc24, east) &
\wedge &
22 connected(loc21, loc31, east) &
\wedge &
23 connected(loc21, loc22, north) &
\wedge\\
24 connected(loc22, loc32, east) &
\wedge &
25 connected(loc22, loc23, north) &
\wedge &
26 connected(loc23, loc33, east) &
\wedge\\
27 connected(loc23, loc24, north) &
\wedge &
28 connected(loc31, loc32, north) &
\wedge &
29 connected(loc32, loc33, north) &
\wedge\\
30 connected(loc21, loc11, west) &
\wedge &
31 connected(loc12, loc11, south) &
\wedge &
32 connected(loc22, loc12, west) &
\wedge\\
33 connected(loc13, loc12, south) &
\wedge &
34 connected(loc23, loc13, west) &
\wedge &
35 connected(loc14, loc13, south) &
\wedge\\
36 connected(loc24, loc14, west) &
\wedge &
37 connected(loc31, loc21, west) &
\wedge &
38 connected(loc22, loc21, south) &
\wedge\\
39 connected(loc32, loc22, west) &
\wedge &
40 connected(loc23, loc22, south) &
\wedge &
41 connected(loc33, loc23, west) &
\wedge\\
42 connected(loc24, loc23, south) &
\wedge &
43 connected(loc32, loc31, south) &
\wedge &
44 connected(loc33, loc32, south) &
\wedge\\
45 crate(cratec, loc21, s0) &
\wedge &
46 crate(crateb, loc22, s0) &
\wedge &
47 crate(cratea, loc23, s0) &
\wedge\\
48 target(cratea, loc12) &
\wedge &
49 target(crateb, loc13) &
\wedge &
50 target(cratec, loc11) &
\wedge\\
51 agent(loc32, s0) &
\wedge\\
55 crate(cratea, loc12, s)
\wedge
56 crate(crateb, loc13, s)
\wedge
57 crate(cratec, loc11, s)$
60 \subsubsection{Task
2: Actions
}
64 Poss(move(x, y), s) &
\equiv \\
65 & (
\exists z: connected(x, y, z))
\wedge\\
66 &
\neg(crate(x, y, s))
70 Poss(push(x, y), s) &
\equiv\\
71 & agent(x, s)
\wedge\\
73 connected(x, z, y)
\wedge
74 (
\exists \gamma: crate(
\gamma, z, s))
77 connected(z,
\alpha, y)
\wedge
78 (
\nexists \beta: crate(
\beta,
\alpha, s))
84 agent(x, result(z, s)) &
\rightarrow\\
85 & (
\exists y: z = move(y, x))
\vee\\
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
93 crate(x, y, result(A, s)) &
\rightarrow\\
95 A = push(z
\wedge \alpha)
\wedge\\
97 connected(z
\wedge \beta\wedge \alpha)
\wedge
98 connected(
\beta\wedge y
\wedge \alpha)
\wedge
99 crate(x
\wedge \beta\wedge s)
103 A
\neq push(z,
\alpha)
\wedge
104 connected(z, y,
\alpha)
\wedge
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.
116 \caption{Domain description task
1}
117 \prologcode{./src/domaintask1.pl
}
120 \subsubsection{Task
4: The Planning Problem in Figure
1}
122 \caption{Instance description task
4}
123 \prologcode{./src/instancetask4.pl
}
126 \subsubsection{Task
5: Crates go to Any Goal Location
}
128 \caption{Instance description task
5}
129 \prologcode{./src/instancetask5.pl
}
132 \subsubsection{Task
6: Inverse Problem
}
134 \caption{Instance description task
6}
135 \prologcode{./src/instancetask6.pl
}
138 \caption{Domain description task
6}
139 \prologcode{./src/domaintask6.pl
}
143 \subsection{Part
3: Extending the domain
}
144 \subsubsection{Task
7: Unlocking the Crates
}
146 \caption{Instance description task
7}
147 \prologcode{./src/instancetask7.pl
}
150 \caption{Domain description task
7}
151 \prologcode{./src/domaintask7.pl
}
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
164 The model is easy to extend to bigger and more complex problems, it doesn't
165 scale that well however...
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