Your task is to implement optimal planner using two heuristics: $h^{max}$ and LM-Cut. Given a FDR task as a SAS file, your planner should find the optimal plan for the task. The planner must be implemented in Python with no extra packages, as they are not installed in the BRUTE image. You should submit all requested files in zip file to BRUTE. The deadline is April 28 May 5.
Given tasks to solve are represented as FDR tasks in SAS files. The structure of that file was discussed in the 3rd tutorial. Detailed information on SAS-files can be found here.
As you recall, both heuristics $h^{max}$ and LM-Cut are based on the delete relaxation of a STRIPS task. To convert an FDR task into a STRIPS task, see Section 1.5 in the lecture notes here. You need only the delete-relaxation of that STRIPS task. So, the translation is actually trivial as you do not need the delete effects.
The LM-Cut heuristic is not unique as it depends on the tie-breaking strategy. When you build the justification graph, you must connect every add effect of any action to its most expensive precondition (see the $\mathrm{argmax}$ in the definition of the justification graph). There can be several facts attending this maximum. To make the output unique, choose among them the fact that is the greatest w.r.t. the lexicographic order, i.e., $\langle v_1, d_1\rangle < \langle v_2, d_2\rangle$ iff $v_1<v_2$ or $v_1=v_2$ and $d_1<d_2$. The pairs of the form $\langle v, d\rangle$ are the facts of the converted STRIPS task, $v$ is the variable number (as specified in the SAS-file), and $d$ is the number of a value from its domain (as specified in the SAS-file).
Try to make your code efficient. Particularly, the function getApplicable
in A* (Algorithm 2 in lecture notes) returns a list of applicable actions in a state and should be implemented efficiently, as it is often called by the A* algorithm. One possibility is to build a tree structure described in the paper on the Fast Downward planner Section 5.3.1.
You are supposed to submit a zip file to BRUTE containing all your Python source files. The zip file must contain the following files:
hmax.py
- Running this file as python hmax.py output.sas
should print the heuristic value using $h^{max}$ for the initial state.
lmcut.py
- Running this file as python lmcut.py output.sas
should print the heuristic value using LM-Cut for the initial state.
planner.py
- Running this file should solve the planning task specified by output.sas
. It prints the plan and its cost to the screen if it finds an optimal plan. There are two possible executions:
python planner.py output.sas hmax
solves the problem by $h^{max}$,
python planner.py output.sas lmcut
solves the problem by LM-Cut.
SAS-file | hmax | LM-Cut | Cost |
---|---|---|---|
blocks-4-0.sas | 2 | 6 | 6 |
sokoban03.sas | 3 | 3 | 10 |
elevators01.sas | 9 | 31 | 42 |
$ python hmax.py elevators01.sas
9
$ python lmcut.py elevators01.sas
31
$ python planner.py elevators01.sas hmax board p2 slow0-0 n2 n0 n1 move-down-slow slow0-0 n2 n1 leave p2 slow0-0 n1 n1 n0 move-up-slow slow0-0 n1 n3 board p1 slow0-0 n3 n0 n1 move-up-slow slow0-0 n3 n4 leave p1 slow0-0 n4 n1 n0 board p1 slow1-0 n4 n0 n1 move-up-slow slow1-0 n4 n6 leave p1 slow1-0 n6 n1 n0 move-up-slow slow1-0 n6 n8 board p0 slow1-0 n8 n0 n1 move-down-slow slow1-0 n8 n4 leave p0 slow1-0 n4 n1 n0 Plan cost: 42
The assignment will be evaluated on 10 private SAS files. For each correctly computed $h^{max}$ value you will be awarded 0.5 point, 5 points in total. For each correctly computed LM-Cut, you will get 1 point, i.e, 10 in total. Then for each found optimal plan with $h^{max}$ you will get 1 point (10 in total) and for each found optimal plan using LM-Cut you will get 1 point (10 in total). The maximum number of points you can get is 35.
$h^{max}$ | LM-Cut | Optimal with $h^{max}$ | Optimal with LM-Cut | |
---|---|---|---|---|
Max points | 5 | 10 | 10 | 10 |
Note, that the timeout for each planning task is X minutes (X is to be decided after testing the evaluation system).