Lab 2: Modeling classical planning domains, part 2

Updates

Any updates or changes we make in the lab instructions during the course will be announced here.

• ---

Writing a Report

After you finish all parts of this lab, you will hand in the domain and problem files you generate, as well as a short(ish) report on your results as discussed in each exercise below. There is no minimum (or maximum) page count for this report, and you do not need to write a long introduction or be extremely formal. Simply write a clear and comprehensible report on the results we ask for. You can include (all or part of) the output from running certain planners if this is helpful in explaining your results. Any suggestions you may have for improving the lab or the instructions are also very welcome – we want your feedback!

The report can be handed in as a simple text file, a PDF document, or a Markdown document in your repository (no Word or OpenOffice documents, please).

Throughout the instructions, we will show what you need to include in the report.

Lab 2.1: Emergency Services Logistics, Carriers

Since injured people are not necessarily close to the depot location, flying to the depot for every single crate that needs to be delivered is quite inefficient. In this part we will consider an alternative way of moving crates, using a carrier.

As partly illustrated above:

• A carrier is a physical entity on which you can place multiple crates. We typically start with empty carriers, but a planning problem instance could also specify that carriers are already loaded with particular boxes.

  The capacity of the carriers (same for all carriers) should be problem specific. That means it should be defined in the problem file.

• At any given time, a UAV can carry/hold either a single crate or a single carrier. It uses the same attachment mechanism to carry either the crate or the carrier.

• To use the carrier, the UAV must first place crates on it. It picks up a crate from some depot location, puts down the crate on a carrier in the same depot location, picks up the next crate, and so on.

  Technically, the UAV must generally fly from the exact position of the first crate to the exact position of the carrier, before the crate can be placed on the carrier. However, including all of these details in the domain definition will place a large burden on the planning algorithm, and will not actually be helpful in any way.

  Instead, it is easier to implement those very short flights as part of the operators: "pick up crate" implicitly means "make sure you are above the crate, which is in this general area, and then pick it up". The "fly" action is then only used to decide when to fly longer distances, such as between a depot and the location of person 7 – this is where the choice of flight actions and destinations really matter for the quality of the plan.

• After placing one or more crates on a carrier, the UAV would pick up the carrier, fly it to a suitable destination, and put it down. Once the carrier is on the ground, the UAV can pick up crates to be delivered to people in need of supplies. The advantage of doing this is greater the farther the people are from the depot:

  

  The UAV may continue by flying the carrier to another location, unloading additional crates, and so on, and does not have to return to the depot until after all crates on the carrier have been delivered.

• You may assume that carriers are initially at the depot location.

• Though you currently only need a single carrier for your single UAV, there should still be a separate type for carriers in preparation for future extensions.

• You need to count and keep track of not only which crates are on each carrier but also how many crates there are in total on each carrier, so that carriers cannot be overloaded.

Note that you should not introduce specific slots on carriers. Keeping track of which crate is in which slot leads to redundancy: The model now makes a difference between having crate A in slot 1 and crate B in slot 2, or crate B in slot 1 and crate A in slot 2. This introduces unnecessary redundancy in the seach space and can make the planner spend much more time trying to find a specific crate placement that works. Since we don't need slots, we should simply count crates.

While updating the domain you should (unless already done) convert it to use :typing instead of type predicates. This means that the predicate (crate ?c) is replaced by a type ?c - crate in predicates and action declaration. Most planners supports subtypes which can further simply declarations.

Numbers

Direct support for numeric state variables (such as the number of crates on a carrier) is comparatively rare. Most planners are non-numeric in this respect, but we can still model a form of pseudo-numbers using standard PDDL objects. For example, we can create a type of pseudo-numbers:

(:types ... num ...)

We can then define a set of value objects in the problem instance:

(:objects ... n0 n1 n2 n3 n4 n5 n6 n7 - num)

To the planner, these are simply objects and have no numeric values. Therefore we have to manually define all operations we may want to apply, such as finding the next number:

(:predicates ... (next ?numA ?numB - num)
(:init ... (next n0 n1) (next n1 n2) (next n2 n3) ... (next n6 n7))

We can then use the value objects in actions and states. For example, in the Schindler Miconic 10 elevator domain, the action of moving up one floor has to increase the floor "number":

(:action move-up
	:parameters (?e - elevator    ?from ?to - num)
	:precondition	(and (at ?elevator ?from)  ;; Where is the elevator?
                     (next ?from ?to) ...) ;; "to" must be the next number
	:effects	(and (not (at ?elevator ?from)) (at ?elevator ?to)))	

Note that we did not define "(next n7 [something])". Therefore (next ?from ?to) cannot be true for any destination when you are at floor n7, so we cannot move up from the topmost floor, as expected. This means that the top floor is implicitly defined by restricting how far one can count in the problem. Note also that you don't need to define a "before", since you can simply use "next" backwards (if you know ?x and want to know the ?y before it, you require (next ?y ?x)).

Operators

Depending on how you structured your previous domain, you most likely also need at least three new operators that we might call load-crate-on-carrier, fly-carrier, and take-crate-from-carrier.

A load-crate-on-carrier action should place a crate that the UAV is already carrying on the carrier, and will therefore end up being preceded by a suitable pickup action (or whatever you might have called it in domain). Similarly, take-crate-from-carrier will simply ensure that the UAV is now carrying the carrier, and will end up being followed by another action that actually delivers the crate to a person.

You should do the following:

1. Modify the domain according to the discussion above. Make sure you do this in a new directory and that you keep the older versions of the domain!

2. Create a new set of problem instances, preferably using the problem generator (with any modifications that might be necessaary), and run these problems through the same planners that you used in lab 1.

   What plans are generated? Do they use the carriers? Does this differ among different planners, and if so, do you see any particular patterns in the differences? Discuss your findings briefly in your lab report.

   You should make sure the problems you generate are of a reasonable size! By this we mean that you do not have to wait for problems that take more than a few minutes to solve, but also that you should not be satisfied if all your problems are solved in less than 30 seconds!

If the plans that are generated do not use the carriers, don't worry: There's an explanation for this, as we will soon discuss.

Lab 2.2: Emergency Services Logistics, Action Costs

As stated above, the intention behind the use of carriers is that a UAV should not need to go back to the depot for every crate. However, it is not necessarily apparent to a planner that going back and forth across long distances is inefficient. Let us consider the following two informal plan segments for delivering four crates to two distinct locations:

    pick up crate1                 pick up crate1			 
    fly to loc1		           load crate1	  			 
    deliver to person1	           pick up crate2			 
    fly to depot	           load crate2	  			 	 
    pick up crate2	           pick up crate3			 	 
    fly to loc2		           load crate3	  			 
    deliver to person2	           pick up crate4			 
    fly to depot	           load crate4	  			 	 
    pick up crate3	           fly carrier between depot, loc1	 	 	
    fly to loc3		           unload crate1	  		 
    deliver to person3	           deliver to person1			 
    fly to depot	           fly carrier between loc1, loc2	 	 
    pick up crate4	           unload crate2	  		 	 
    fly to loc4		           deliver to person2			 
    deliver to person4	           fly carrier between loc2, depot	 	
			           unload crate3	  		 		 
			           deliver to person3			 
	  		           fly carrier between loc3, depot	 
			           unload crate4	  		 
	  		           deliver to person4

The solution that uses carriers is longer – and since we have not told the planner how to calculate the cost of a plan, it has to assume that the cost is proportional to the number of actions. Distances are not part of the domain as given to the planner!

Action costs

The basic idea behind action costs in PDDL is as follows. Previously you have only defined boolean predicates. With action costs, you also define a numeric state variable called total-cost. This state variable should initially be zero and should be explicitly increased by each action that is performed. Planners should then be aware of the function with this specific name and aim to find a plan that minimizes the value of total-cost.

Some actions may have a constant cost. For example, the cost of picking up a crate may not depend on which crate is being picked up or which UAV is involved. Such actions simply increase the total cost by a constant. The cost of flying, on the other hand, definitely depends on the distance that is flown. Such parameter-dependent costs are specified by defining a numeric function, giving it values in the initial state, and using it in the actions.

You should extend the previous domain and problem instances by introducing action costs, as discussed below. Specifically, flying long distances should be expensive. You should preferably use the problem generator and the flight_cost() function, which specifies the cost of flying between randomly generated locations (strongly recommended!). If you don't, make sure your flight costs are sufficiently large (at least 100-200) so that they provide sufficient motivation for wanting to use carriers instead of flying many times!

1. Add :action-costs to the requirements section of the domain specification.

2. After predicates but before actions, you define a total-cost function (state variable) and a fly-cost function as follows, where "location" is the name of your location domain.

   	(:functions (total-cost) - number
   	            (fly-cost ?from ?to - location) - number)

3. For actions with constant cost, you add a new effect increasing total-cost by a constant amount: (increase (total-cost) 10), for example. Only non-negative integers are allowed. Note that some planners requires that the name of the function is exactly "total-cost".

4. For flight actions, you add a new effect increasing total-cost by a non-constant amount: (increase (total-cost) (fly-cost ?from ?to)), for example.

5. Every problem file must be amended to initialize total-cost. In the :init section, you add (= (total-cost) 0). This should be added to the problem generator.

6. Similarly, every problem file must be amended to initialize fly-cost. The problem generator already generates random coordinates for each location and has a function called flight_cost that generates a flight cost depending on the distance between two locations. You should then preferably use flight_cost() to specify values for fly-cost for all pairs of locations (including flying from one location to itself!) in the :init section of the problem file. For example, you might add (= (fly-cost loc1 loc1) 0) (= (fly-cost loc1 loc2) 20) and so on, given that these are the values returned by flight_cost(). Again, only non-negative integers are allowed.

7. Finally, every problem file must specify the following at the end, after the initial state and goal (but before the final closing parenthesis):

   	(:metric minimize (total-cost))

8. Re-generate problems with the same parameters that you used before, but with the modified problem generator.

9. Run the new problem instances through the same planners as before. FF and IPP cannot handle domains with :action-costs so skip these; Madagascar-p accepts but ignores action costs, so keep this in mind in your analysis.

   In the report, you should briefly discuss: What plans are generated? Do they seem better than before? Do UAVs use carriers in those cases where this is better according to the distances (which may not always be the case, if destinations are widely dispersed)?

Please ask us if you have any questions, and see the discussion on modeling action costs in IPC-2008 if you are interested in technical details.

Lab 2.3: Emergency Services Logistics, Optimal Planners

The planners you have used so far may (or may not) take action costs into account, but they don't make any guarantees about the plans that they find. There are also optimizing planners that guarantee that only optimal plans are returned.

You should do the following:

1. Test the performance of optimal planners (seq-opt folder) on your domain and problems. Test by using BJOLP (ipc-2011), SymBA-1 (ipc-2014) and a planner of your choice among AllPACA (ipc-2014), SPM&M (ipc-2014, called spams at the workstations), Rational Lazy A^* (ipc-2014) and SelMax (ipc-2011).

2. After reading the note below, compare the results of the three optimal planners to the results from the satisficing planners in lab 1 (except FF and IPP that cannot handle domains with :action-costs). How do they perform in terms of speed and plan quality (total plan cost)? Are the plans better (cheaper), and if so, how much better? Does it take more time? Do you think it is worth it for this domain? Discuss this briefly in your report.

Finishing and handing in the results

When you have finished the lab, you need to hand in your results. Since we are working at a distance, you should:

• Make sure that your domain files are sufficiently commented, in order to explain how you have chosen to model the domain.
• Make sure that your report covers the issues discussed above.
• Make sure everything is checked in and pushed to the Gitlab project you were assigned: All domain files, problem files and problem generators you have created or modified, clearly named, as well as the report as a simple text file or as a PDF document. Do not use your "own" Gitlab projects for this.
• Then add a submission in the hand-in issue tracker. There is no need to generate zip files; simply provide a link to your repo.

Your assistant may ask you questions or ask for a Zoom/Teams meeting in case additional information is required. Alternatively, your hand-in may be approved without a demonstration.