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 ~~April 28~~ May 5.

Input structure

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.

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 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:
1. python planner.py output.sas hmax solves the problem by $h^{max}$,
2. python planner.py output.sas lmcut solves the problem by LM-Cut.

All output values should be integers.

Sample data

SAS-file	hmax	LM-Cut	Cost
blocks-4-0.sas	2	6	6
sokoban03.sas	3	3	10
elevators01.sas	9	31	42

Output examples

$ 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

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

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.

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

Table of Contents