https://cw.fel.cvut.cz/wiki/ 2026-04-14T14:36:25+0200 https://cw.fel.cvut.cz/wiki/ https://cw.fel.cvut.cz/wiki/lib/tpl/bulma-cw/images/favicon.ico text/html 2026-02-04T14:14:37+0200 Anonymous (anonymous@undisclosed.example.com) https://cw.fel.cvut.cz/wiki/courses/pui/tutorials/tutorial01?rev=1770210877&do=diff 1. PDDL Modeling The first tutorial aims to model a simple planning problem in the language PDDL. You may check your solution using the Fast Downward planner. If you download the Apptainer (previously Singularity) image, you can find a plan for your PDDL files as follows:$R1, R2, R3$$1-8$$OR$$1$$5$$R1,R2,R3,OR$$5,3,3,3$$\emptyset$$n_1=n_2-1$$0,0,3,3$$8,5,7,4,2$$6,3,1$ text/html 2026-02-04T14:14:37+0200 Anonymous (anonymous@undisclosed.example.com) https://cw.fel.cvut.cz/wiki/courses/pui/tutorials/tutorial02?rev=1770210877&do=diff 2. Heuristic Search Exercise 1: Find an LTS $\Theta=\langle S,A,T,G\rangle$ and a heuristic $h\colon S\to\mathbb{R}_0^+\cup\{\infty\}$ which is admissible but not consistent. Make the LTS $\Theta$ so that GBFS fails to find an optimal $s_0$-plan for an initial state $s_0$. Solution The simplest example of an LTS and an admissible and non-consistent heuristic is simply an LTS built on a chain $a\to b\to c$$c$$1$$h(a)=2$$h(b)=0$$h(c)=0$$h(a)-h(b)=2-0=2>1$$a$$c$$\Theta=\langle S,A,T,G\rangle$$S=… text/html 2026-02-04T14:14:37+0200 Anonymous (anonymous@undisclosed.example.com) https://cw.fel.cvut.cz/wiki/courses/pui/tutorials/tutorial03?rev=1770210877&do=diff 3. Propositional Representation STRIPS and FDR Exercise 1: Blocks World belongs to the oldest planning domain. There are several blocks on a table, and we can build piles out of those blocks. I simplified the domain a bit so that it has only two action schemata: $\Pi=\langle F,A,s_0,g\rangle$$F$\[F=\{on(A,B),on(A,C),on(A,T),on(B,A),on(B,C),on(B,T),on(C,A),on(C,B),on(C,T),cl(A),cl(B),cl(C)\}.\]$on(B,C)$$B$$C$$on(B,T)$$B$$cl(B)$$B$$X,Y\in\{A,B,C\}$$stack(X,Y)$$unstack(X,Y)$$\{on(X,T),cl(X),cl(Y)\… text/html 2026-02-04T14:14:37+0200 Anonymous (anonymous@undisclosed.example.com) https://cw.fel.cvut.cz/wiki/courses/pui/tutorials/tutorial04?rev=1770210877&do=diff 4. Delete relaxation heuristics This tutorial focuses on the computation of the heuristics $h^{max}$ and $h^{add}$ based on delete relaxation. As these heuristics first compute the delete relaxation of a STRIPS task $\Pi$, we will consider here only delete-free STRIPS tasks $\Pi$$\Pi=\Pi^+$$h^*=h^+$$\Pi=\langle F,A,s_0,g\rangle$$F=\{a,b,c,d,e\}$$s_0 = \{a\}$$g = \{b,e\}$$A = \{o_1,o_2,o_3,o_4\}$$o_1$$\emptyset$$\{b,c\}$$4$$o_2$$\{a\}$$\{c\}$$2$$o_3$$\{a,c\}$$\{d\}$$3$$o_4$$\{c,d\}$$\{e\}$$1$$h^… text/html 2026-02-04T14:14:37+0200 Anonymous (anonymous@undisclosed.example.com) https://cw.fel.cvut.cz/wiki/courses/pui/tutorials/tutorial05?rev=1770210877&do=diff 5. Fast-forward heuristic and action landmarks In this tutorial, we will compute the fast-forward heuristic based on the best supporters of facts. Let $\Pi=\langle F,A,s_0,g\rangle$ be a STRIPS task and $s\subseteq F$ a state. When computing $h^{max}(s)$, we must compute the fixed point $\boldsymbol{s}^*$ of $\Gamma_{max}$. Recall that the best supporter $bs(p)$$p\not\in s$$a\in A$$\boldsymbol{s}^*(p)<\infty$$p\in s$$\boldsymbol{s}^*(p)=\infty$$bs(p)=\bot$$\Pi=\langle F,A,s_0,g\rangle$$F=\{a,b… text/html 2026-02-04T14:14:37+0200 Anonymous (anonymous@undisclosed.example.com) https://cw.fel.cvut.cz/wiki/courses/pui/tutorials/tutorial06?rev=1770210877&do=diff 6. LM-Cut heuristic Exercise 1: Consider the following STRIPS task $\Pi=\langle F,A,s_0,g\rangle$ where $F=\{a,b,c,d,e\}$$s_0=\{a\}$$g=\{c,d,e\}$$A=\{o_1,o_2,o_3,o_4\}$ action pre add cost $o_1$ $\{a\}$ $\{b,c\}$ $3$ $o_2$ $\{a\}$ $\{d\}$ $5$ $o_3$ $\{b\}$ $\{c,d\}$ $1$ $o_4$ $\{a,b\}$ $\{e\}$ $4$ In the following exercises, we will compute LM-Cut at $s_0$. As the first step, construct the STRIPS task $\Pi_{s_0}$ extended by new facts $\bot,\top$$\{\bot\}$$\{\top\}$$\Pi_{s_0… text/html 2026-02-04T14:14:37+0200 Anonymous (anonymous@undisclosed.example.com) https://cw.fel.cvut.cz/wiki/courses/pui/tutorials/tutorial09?rev=1770210877&do=diff 7. Pattern databases Recall that a pattern database is an abstraction heuristic defined for an FDR task $\Pi=\langle V,A,s_0,g\rangle$ induced by a projection $\pi_P$ for a subset of variables $P\subseteq V$. The projection $\pi_P$ maps a state $s$ (i.e., a function on the variables $V$) to its restriction on $P$. One can also generalize $\pi_P$$s$\[\pi_P(s)(v)=\begin{cases} s(v) & \text{if }s(v)\text{ is defined and }v\in P,\\ \text{undefined} & \text{otherwise.} \\ \end{cases} \]$\pi_P$$\Pi_… text/html 2026-02-04T14:14:37+0200 Anonymous (anonymous@undisclosed.example.com) https://cw.fel.cvut.cz/wiki/courses/pui/tutorials/tutorial10?rev=1770210877&do=diff 8. LP-based heuristics Exercise 1: Let $\Pi=\langle V,A,s_0,g\rangle$ be an FDR task where $V=\{v_1,v_2,v_3,v_4\}$ and $\mathsf{dom}(v_i)=\{0,1\}$. The initial state is $s_0=\{v_1=0,v_2=0,v_3=0,v_4=0\}$ and the goal $g=\{v_3=1,v_4=1\}$. The actions $A=\{a_1,a_2,a_3,a_4\}$ are defined as follows: action $\mathsf{pre}$ $\mathsf{eff}$ cost $a_1$ $v_1=0$ $v_1=1$ $1$ $a_2$ $v_1=1$ $v_1=0$, $v_2=1$ $2$ $a_3$ $v_2=1$ $v_2=0$, $v_3=1$ $2$ $a_4$ $v_3=1$ $v_4=1$ $3$ Draw the causal … text/html 2026-02-04T14:14:37+0200 Anonymous (anonymous@undisclosed.example.com) https://cw.fel.cvut.cz/wiki/courses/pui/tutorials/tutorial11?rev=1770210877&do=diff 11. Stochastic shortest path (SSP) In this lab, we will solve an SSP problem using the algorithm ILAO*, which generalizes A*. Suppose we have the SSP problem defined by the following graph. It is a problem of what way of transport one should take when traveling to work to minimize the expected travel time. The actions are depicted as black dots with their names and the time they take. If the action has several probabilistic outcomes, the particular probabilities label the respective outgoing… text/html 2026-02-04T14:14:37+0200 Anonymous (anonymous@undisclosed.example.com) https://cw.fel.cvut.cz/wiki/courses/pui/tutorials/tutorial12?rev=1770210877&do=diff 12. Heuristics for SSP This tutorial will consider the factored representation of SSPs, i.e., probabilistic FDR tasks. It is the same representation as FDR, besides the fact that we can have probabilistic effects. In other words, each action can have several effects and a probability distribution over these effects. As mentioned during the lectures, to get an admissible heuristic for such an SSP, one can first turn it into a usual FDR task by all-outcome determinization and then compute any adm… text/html 2026-02-04T14:14:37+0200 Anonymous (anonymous@undisclosed.example.com) https://cw.fel.cvut.cz/wiki/courses/pui/tutorials/tutorial13?rev=1770210877&do=diff 13./14. Lets prepare for exam - Exercises In this tutorial, we will go over several heuristics of classical planning and probabilistic planning as a preparation for exam. If you have your own exercises or you struggle with any topic, prepare it for the tutorial.$\Pi = \langle F, A, s_0, g \rangle$$a = \langle pre_a, add_a, del_a \rangle$$Pi^+ = \langle F, A^+, s_0, g \rangle$$a^+ = \langle pre_{a^+}, add_{a^+}, \emptyset \rangle$$\Pi$$h^*$$\Pi^+$$h^{max}, h^{add}, h^{ff}$$\Pi = \Pi^+$$h^{max} \…