Assignment #1 – Planner

Implement a simple optimal planner with A* algorithm and one of the admissible heuristics that are presented to you in lectures. We have prepared an automatic evaluation of the submitted solutions in faculty's upload system for h^max, LM-Cut, and merge-and-shrink heuristics. However, if you wish to implement some other admissible heuristic instead, don't hesitate to ask. The implementation is possible in the following languages: C, C++, Python, and Java (see details for submissions below).

The submissions will be automatically evaluated on a set of simple problems mainly as a sanity check that there are no fundamental errors in the implementation. The complete set of these problems is available to you for testing. Moreover, we give you the input problems pre-compiled into STRIPS and FDR representations, and we give you a code for loading the problems so you don't have to write the parser yourself. All the problems must be solved by your planner within 10 minutes time limit, so be sure to test your implementation on this set before uploading it.

The upload system will give you only one point if your implementation passes the check (and zero if it doesn't). To get full amount of points, you need to submit your solution in person to your tutor. The tutor will check the code submitted to the upload system, briefly discuss it with you, ask you couple of questions both about your code and about the theory behind A* and the implemented heuristics, and then assign a corresponding number of points. The maximum number of points per selected heuristic is listed below and you will get this amount of points if your implementation is correct and you understand it. Not understanding how your own code works means automatic failure in this course, because in this case, we will simply assume that you didn't write it. If your solution contains some minor errors, then, depending on what you prefer, the tutor will either reduce the resulting number of points or you will get a chance to correct the mistakes to get full amount of points.

The input files with problem definitions have suffix .strips for STRIPS formulations or .fdr for FDR formulations. The files are simple text files that are easy to parse, but you don't need to read or understand them because we provide you with codes for loading these files (see below the section corresponding to the language of your choice). Each problem from the test set has also its corresponding PDDL files and a .plan file. The PDDL files are there just if you are interested how the original description of the problem looks like. The .plan file, however, contains an example of the optimal plan, cost of the optimal plan, and the value of the h^max heuristic for the initial state. The format of the .plan file is simple: lines beggining with ; are comments, empty lines are ignored, and otherwise each line must contain a name of the operator in the plan.

For example, this is the plan file for depot/pfile1 problem (depot/pfile1.plan):

;; Optimal cost: 10
;; h^max for init: 4

(lift hoist0 crate1 pallet0 depot0)
(load hoist0 crate1 truck1 depot0)
(lift hoist1 crate0 pallet1 distributor0)
(drive truck1 depot0 distributor0)
(load hoist1 crate0 truck1 distributor0)
(unload hoist1 crate1 truck1 distributor0)
(drop hoist1 crate1 pallet1 distributor0)
(drive truck1 distributor0 distributor1)
(unload hoist2 crate0 truck1 distributor1)
(drop hoist2 crate0 pallet2 distributor1)

Your program will be called as follows:

  $ ./planner problem.strips problem.fdr

That is, the first argument will be an input file with the problem in STRIPS format, and the second argument will be a file in FDR format.

In your program, you can choose one of these formats and use the provided parser that loads the problem in the corresponding structures (see below details for the language of your choice). Your program must solve the problem and print to standard output (stdout) the solution (i.e., plan) and some additional info. The standard error output (stderr) can be used freely.

The output format is the same as the format of .plan file described above, i.e., you print the resulting plan as a sequence of operators' names as they were loaded by our parser, each name at a separate line. Additionally, you must print the cost of the plan in a comment as ;; Cost: <your-computed-cost> and the heuristic estimate for the initial state as ;; Init: <heur-value-for-init>.

For example, the output of your program implementing A^* with h^max for depot/pfile1 problem could look like this:

;; Cost: 10
;; Init: 4

(lift hoist0 crate1 pallet0 depot0)
(load hoist0 crate1 truck1 depot0)
(lift hoist1 crate0 pallet1 distributor0)
(drive truck1 depot0 distributor0)
(load hoist1 crate0 truck1 distributor0)
(unload hoist1 crate1 truck1 distributor0)
(drop hoist1 crate1 pallet1 distributor0)
(drive truck1 distributor0 distributor1)
(unload hoist2 crate0 truck1 distributor1)
(drop hoist2 crate0 pallet2 distributor1)

You should validate the output of your program to be sure that your planner generates valid plans. One way to do it is to check your plan agains PDDL files by checking one operator at a time and see if the operator is applicable and what is the result of the its application. We would recommend you to avoid this approach if you want to remain sane after this assignment. Another way is to use the software VAL developed at KLC. You can download and compile the program yourself from https://github.com/KCL-Planning/VAL, or you can try to run the following linux binary we pre-compiled for you: validate.zip.

The program validate is called:

  $ ./validate -v domain.pddl problem.pddl problem.plan

where -v is the option that increases verbosity of the program, domain.pddl and problem.pddl are domain and problem PDDL files that are given to you, and the problem.plan file is the file you should generate by your planner. (You can try to call the validator with the plan files we provide to see how it works.)

• Implement A* with one of the admissible heuristics listed below.
• The implementation can be in C, C++, Python, or Java (details below).
• The implementation must be first submitted for automatic evalaution in our upload system and then, if it passes, it must be discussed in person with your tutor.
• Available heuristics and the maximum number of points you can get:

• The test set that is used in the automatic evaluation: pui-teset-set.tar.gz, pui-test-set.zip
• The time limit for the whole test set is 10 minutes in the upload system.
• A much bigger set of pre-compiled problems if you wish to experiment: pui-dataset.tar.gz, pui-dataset.zip

For the implementation in C, we provide the following parser for the .strips and .fdr files: problem.c.zip .

How to use this module should be self-explanatory:

• Include problem.h in your file.
• If you want to use STRIPS formulation, call stripsRead() and stripsFree() for loading the .strips file and for freeing the allocated memory, respectively.
• If you want to use FDR/SAS formulation, call fdrRead() and fdrFree() function.
• Look into problem.h and study the structures.

So, the template for your program looks like this:

#include <stdio.h>
#include "problem.h"
 
int main(int argc, char *argv[])
{
    //strips_t strips;
    fdr_t fdr;
 
    if (argc != 3){
        fprintf(stderr, "Usage: %s problem.strips problem.fdr\n", argv[0]);
        return -1;
    }
 
    // Load the planning problem in STRIPS or FDR
    //stripsRead(&strips, argv[1]);
    fdrRead(&fdr, argv[2]);
 
    // Implement the search here
 
    //stripsFree(&strips);
    fdrFree(&fdr);
}

You have to implement the whole program in one .c file that you upload to uploading system. You don't upload the whole project, but just this one file. In the uploading system, we will copy the problem.c and problem.h files in the same directory and compile the whole project as follows:

  $ gcc -std=gnu99 -Wall -pedantic -c -o problem.o problem.c
  $ gcc -std=gnu99 -Wall -pedantic -o planner <your-file.c> problem.o

And then, for each test problem consecutively, the compiled planner is called like this:

  $ ./planner problem.strips problem.fdr

So, as described above, your planner should solve the problem and print to the standard output the found plan, the heuristic value for the initial state and the cost of the plan.

If you choose to implement the h^max heuristic, the name of the uploaded file must be max.c. For the LM-Cut heuristic it must be lmcut.c.

For the implementation in C++, the instructions are almost identical to the implementation in C. You use the same parser problem.c.zip and the template is identical. The compilation is a little bit different:

  $ gcc -std=gnu99 -Wall -pedantic -c -o problem.o problem.c
  $ g++ -std=c++11 -Wall -pedantic -o planner <your-file.cpp> problem.o

That is, our parser is compiled and linked as C module, but your program is compiled as C++ (see extern “C” { … } in problem.h).

If you choose h^max, the name of the uploaded file must be max.cpp, for LM-Cut lmcut.cpp.

For the implementation in Python, we provide the following parser for the .strips and .fdr files: problem.py.zip .

How to use this module should be self-explanatory:

• Import problem module.
• Use Strips() or FDR() constructors for STRIPS or FDR/SAS formulations, respectively.
• Look into problem.py and study the classes.

So, the template for your program looks like this:

import sys
from problem import *
 
def main(fn_strips, fn_fdr):
    #p = Strips(fn_strips)
    p = FDR(fn_fdr)
 
    # Here implement your planner
 
if __name__ == '__main__':
    if len(sys.argv) != 3:
        print('Usage: {0} problem.strips problem.fdr'.format(sys.argv[0]))
        sys.exit(-1)
 
    main(sys.argv[1], sys.argv[2])

You have to implement the whole program in one .py file that you upload to uploading system. You don't upload the whole project, but just this one file. In the uploading system, we will copy the problem.py file in the same directory and run your planner for each test problem consecutively like this:

  $ python2 <your-file.py> problem.strips problem.fdr

So, the program must be implemented in Python 2, and, as described above, your planner should solve the problem and print to the standard output the found plan, the heuristic value for the initial state and the cost of the plan.

If you choose to implement the h^max heuristic, the name of the uploaded file must be max.py. For the LM-Cut heuristic it must be lmcut.py.

For the Java implementation, the parser for both .strips and .fdr is provided as a Java library: planning.jar (has to be renamed from .zip to .jar because of CW file restrictions) including the sources.

In contrast to the previous languages, you can use more source files and you hand in the result as a compiled JAR including sources, in particular max.jar for h^max, lmcut.jar for LM-Cut. Importantly, in all cases the main class must be named Planner and placed in the package planner. Your code will be run by the following command:

  $ java -Xmx1G -cp planning.jar:<your-planner.jar> planner.Planner problem.strips problem.fdr

The upload system runs java version sunjdk 1.8.u121.

The planner.Planner class can be based on the following code:

package planner;
 
import problem.Parser;
import problem.fdr.FDRProblem;
import problem.strips.StripsProblem;
 
public class Planner {
 
	private final FDRProblem fdr;
//	private final StripsProblem strips;
 
	public Planner(String stripsFile, String fdrFile) {
		Parser problemParser = new Parser();
		fdr = problemParser.parseFDRProblem(fdrFile);
//		strips = problemParser.parseStripsProblem(stripsFile);
	}
 
	public static void main(String[] args) {
		if(args.length != 2) {
			System.out.println("Expected arguments: problem.strips problem.fdr");
			return;
		}
 
		Planner planner = new Planner(args[0],args[1]);
		planner.plan();
	}
 
	public void plan() {
		//TODO: implement your code here
	}
 
}