Hide menu

TDDD48 Automated planning (6 ECTS)

Lab 5: Knowledge Intensive Planning

Written by Mikael Nilsson.

Introduction

This lab highlights a different form of knowledge intensive planning as compared to HTN. You will adapt the Emergency Services Logistics domain for TLPlan, a forward chaining planner that uses knowledge about the domain to guide its search. For the lab we provide a minimal domain file and an example problem file. Your task is to use your insights about the domain in two different ways to guide the planner. You will see that it is possible to plan without heuristics if you know the domain well enough.

Updates and Known Problems

Any problems discovered during the lab, and any clarifications we make to the lab instructions, will be announced here.

  • The problem file was incorrect: All instances of "d" should be "depotloc". This has now been fixed.

Resources

The following resources are available, and will be explained in further detail below.

Running TLPlan

Please refer to the Running Planners page for instructions on logging in to Crabbofix and running planners in general. TLplan in particular is executed by invoking

        /home/TDDD48/planners/tlplan/tlplan run.tlp

where run.tlp is a run script that looks approximately like this:

	(reset-domains)
	(set-search-limit 100000)
	(set-trace-level 1)
	(verbose-on)
	(enable pddl-support)
	(def-domain emergency "Emergency Services Logistics Domain." "emergency_domain.tlp")
	(load-pddl-problem "emergency_problem.pddl")
	(plan)
	(exit)

Detailed information about these commands can be found in the TLPlan documentation. A quick overview follows here:

  • (reset-domains) removes all previous information about domains.
  • (set-search-limit 100000) limits the search to expanding 100000 worlds/states.
  • (set-trace-level 1) sets the tracing (debugging) level to a number between 0-3. The higher, the more trace information is generated in the tlplan.log file.
    • Level 0 logs operators, initial state, final state and plan.
    • Level 1 adds each choice of world to expand and the effects of expanding it.
    • Level 2 adds the progressed temporal formula used for guiding the search.
    • Level 3 shows all possible worlds that the planner chose among in each state.
  • (verbose-on) generates some information while the planner works, printing a progress indicator which can be of some use.
  • (enable pddl-support) allows TLPlan to accept problem instance files in PDDL format.
  • (def-domain emergency...) reads and parses the domain file. The first parameter (emergency) is the symbolic name of the domain, which must match what is specified in the problem file. The second parameter is an arbitrary description of the domain, and the third parameter is the name of the file to be read.
  • (load-pddl-problem "emergency_problem.pddl") loads the problem file, which is in the same general format as your earlier PDDL problem instances.
  • (plan) starts the planner.
  • (exit) exists the planner.
  • An example of planner output is shown here:
     $ /home/TDDD48/planners/tlplan/run.tlp
    SizeOfMemory=890000000
    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
    +  Welcome to TLPlan (version April 3rd 2006 0.1).                                 +
    +  Copyright (c) 1997, 2003, F. Bacchus & Michael Ady                              +
    +  This copy can be used only for non-commercial research purposes.                +
    +  You may not reverse engineer, decompile, translate or disassemble the Software. +
    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
    
    Loading file: run.tlp
    Loading PDDL file: emergency_problem.pddl
    Loading file: emergency_domainC.tlp
    Planning "emergency_problem.pddl"
    ................................................................................
    Planning completed.  Plan found.  Elapsed CPU time 0.172 sec.
    
    
    Exiting
    Symbol table usage: 14 out of 200 entries used.
    String table usage: 359 total strings on an open hash table with 617 entries. 84 entries colliding
    

    Information of how the planner searched can be found in the tlplan.log file. When a plan is found for a problem file called name.pddl, it is stored in a file name.pddl.soln.

    Lab 5.1: Control Rules

    Download the domain, problem and script files linked above. The domain file contains a minimum set of operators. The idea is that these operators are all that is required to solve the Emergency Services Logistics problem. TLPlan handles numerical fluents which means that we won't need to mention crates explicitly. Instead we have a number of locations each requiring an amount of each resource type.

    Some comments about the domain:

    • As you see, the syntax is somewhat different from PDDL syntax – TLplan was first developed before PDDL existed, and also supports quite a few features that are not available in PDDL.
    • Predicates are declared using (declare-described-symbols). Note that in addition to the ordinary predicates we also need to use predicates such as (uav ?x) for typing, as TLplan does not support explicit types.
    • Numeric state variables (functions) can be defined in the same section. They can be used in preconditions and altered in effects.
    • Each operator precondition starts by defining the types for each argument, as in "(?u) (uav ?u)". Technically, these are variable-generator pairs, where the first expression is a variable and the second is an expression constraining that variable (which is not necessarily a type predicate). For simplicity, you can think of them simply as a strange way of specifying parameter types.
    • The operators use separate add and delete lists, rather than placing deleted atoms in (not ...) as in PDDL. Effects that modify numeric state variables should be placed in the add part.

    Set the trace level 1 in run.tlp and then try running the planner using the plan script for a few seconds (just enough so it prints a few lines full of periods). Then stop it with ctrl-C. It won't find a plan, since you haven't added any control rules yet and it has to search blindly. Even if you let it run indefinitely, it would have failed due to lack of memory.

    How can this be fixed? Now that you have run the planner for a short while, it has generated a log file showing which actions it tries to apply. Then you can do as follows:

            grep Expanding tlplan.log | less
    

    This will give you some information about the plan prefixes that TLplan has investigated:

    Expanding world 2 at depth 0, priority 0.000000 action: ()
    Expanding world 3 at depth 1, priority 0.000000 action: (pick-up-crate heli0 d depot0 medicine)
    Expanding world 63 at depth 2, priority 0.000000 action: (pick-up-crate heli1 d depot0 medicine)
    Expanding world 121 at depth 3, priority 0.000000 action: (pick-up-crate heli2 d depot0 medicine)
    Expanding world 177 at depth 4, priority 0.000000 action: (pick-up-crate heli3 d depot0 medicine)
    Expanding world 231 at depth 5, priority 0.000000 action: (load-carrier heli0 carrier0 d medicine)
    

    In this case world 2 is actually the initial state. After visiting this state, TLplan continuously increases search depth, which means that it is going depth first into the search tree without backtracking. If depth decreases between two lines, then backtracking has occurred.

    If you continue reading the output of the command above, you might encounter some action sequences that seem strange given the goals of the problem: Helicopters picking up crates that are not needed, flying to locations that already have a full set of supplies, and so on. The main idea with TLPlan is to provide domain knowledge in the form of temporal logic rules to ensure that such strange sequences are not permitted. TLPlan will only expand worlds in which the control rules are true, so by adding more rules, more worlds can be cut from the search tree. Control rules are added in a special section:

    (set-tl-control 
    	(always (and 
    			
    		;Only pickup a type if there is some place to deliver it
    		(forall (?u) (uav ?u) (?t) (type ?t)
    			(implies (not(exists (?x) (location ?x) (not (= (cratesUndelivered ?t ?x) 0))))
    				(next (not (carrying ?u ?t)))))
    
    		;More control rules go here
    										
    )))					
    

    Your task is to add several more rules to make the planner both find plans faster and find better plans. Can you make it use carriers? More information about temporal logic and example control rules can be found in the TLPlan documentation. You can also ask the lab assistant for hints and guidance.

    Hint: As ususal, it will probably be easier to solve these problems incrementally. First create a very small problem file, maybe one where you only have to deliver two crates to a single location, and try to get TLplan to efficiently generate problems for that problem. Then modify that problem, perhaps by delivering to the third location – does the planner still try to fly to the first location? Continue to tackle larger and larger problems.

    Finishing and handing in the results

    When you have finished the lab, you should ask a lab assistant to take a look at your final domain to briefly check whether the model you developed appears reasonable.

    When you hand in your results:

    • Create a single ZIP file, named fffll111-fffll222-lab5.zip where fffll111 and fffll222 are your login names (assuming you are working in pairs).
    • The ZIP file should contain in all domain files, problem files and problem generators you have created or modified, clearly named. It should also contain the report as a simple text file or as a PDF document (no Word or OpenOffice documents, please).
    • Send the ZIP file by e-mail to Mikael Nilsson.

    Page responsible: Jonas Kvarnström
    Last updated: 2012-05-14