====== Assignment 2 - Classical Planner ======

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 <del>April 28</del> <fc #ff0000>May 5</fc>**.

===== Input structure =====

Given tasks to solve are represented as FDR tasks in SAS files. The structure of that file was discussed in the 3rd [[courses:pui:tutorials:tutorial03|tutorial]]. Detailed information on SAS-files can be found [[https://www.fast-downward.org/TranslatorOutputFormat|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 [[https://drive.google.com/file/d/1-0G8-neNw1uKdwqm0eQkyCQA4-ic_4Bh/view?usp=sharing|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.

===== Notes on LM-Cut =====

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).

===== Notes on Implementation =====

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 [[https://arxiv.org/pdf/1109.6051|Section 5.3.1]].

===== Submission =====

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. 
<note important>All output values should be integers.</note> 

== Sample data ==

^ SAS-file ^ hmax ^ LM-Cut ^ Cost ^
| [[https://drive.google.com/file/d/1MX3vMIgUYJOMym9ynND1cLZnOuWGaVzy/view?usp=sharing|blocks-4-0.sas]] | 2 | 6 | 6 |
| [[https://drive.google.com/file/d/1MYBzJeWIDHFWW6krh13vAj1Fz4rC7QGa/view?usp=sharing|sokoban03.sas]] | 3 | 3 | 10 |
| [[https://drive.google.com/file/d/1MU1h5MsHI-UzxeySrM8UPia8oAEtL1QB/view?usp=sharing|elevators01.sas]] | 9 | 31 | 42 |


== Output examples ==

<code bash>
$ python hmax.py elevators01.sas 
9
</code>

<code bash>
$ python lmcut.py elevators01.sas 
31
</code>

<code bash>
$ 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
</code>

<note>Using the Fast Downward planner, you can easily create your testing data, which generates the SAS-files from PDDL tasks. PDDL instances can be found
[[https://github.com/potassco/pddl-instances|here]]. Consider the STRIPS variants of the problems (i.e., no ADL, numeric fluents etc.)
and rather instances from the optimal track of older IPC competitions.</note>

<note>You can use the Fast Downward planner to solve your SAS testing files, to see an optimal plan and its cost. Moreover, it prints the heuristic value 
for the initial state in its log (the very first one). So you can use it to test the correctness of your $h^{max}$ heuristic. This does not work for LM-Cut as it depends on the tie-breaking strategy.</note>
 
===== Evaluation =====

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**).