Göm menyn

WASP: PDDL Modeling

Introduction

The aim of this lab is to practice modelling planning problems using the formal language PDDL. You will do this by using a classical fragment of PDDL to model a UAV logistics domain. Later this knowledge will be used practically.

Because we are limited in time we will focus on the STRIPS level of expressivity in PDDL. In other words, we will not use negative preconditions, negative goals, conditional effects, or similar extensions.

We start with an introduction to PDDL.

What is PDDL?

PDDL, the Planning Domain Definition Language, was developed with the aim of generating a standard to replace or augment a variety of existing planning domain and problem description languages. It was created mainly to make a series of International Planning Competitions possible. The base concepts used in PDDL mainly coincide with the concepts that were introduced in the WASP planning lecture, but the surface syntax is somewhat different in order to cleanly support a number of extensions.

PDDL supports the full expressivity of earlier languages such as STRIPS and ADL, as well as a large set of extensions of varying complexity. Providing full support for all aspects of PDDL is a very complex task. In fact, many planners support only the smaller STRIPS subset, possibly with a few extensions. Limiting the expressivity in this way allows the use of planning algorithms that use the limiting assumptions to improve performance. This is similar to how one can find special algorithms for linear programming in order to solve such problems faster than using more general algorithms supporting non-linear programming.

We will now give a brief introduction to PDDL. If you want more details, the International Planning Competition web pages contain a list of papers related to PDDL, including definitions of PDDL 1.2, 2.1, 2.2, and 3.0.

Examples

Several examples of PDDL domain and problem definitions may be found, using either the STRIPS subset of PDDL or using object types and some extended ADL features. There are also several variants of the Satellite domain (used in IPC 2002), which illustrate the extended features of PDDL 2.1.

Parts of a PDDL Problem Definition

A PDDL definition consists of two parts: The domain definition and the problem definition. Although not required by the PDDL standard, many planners require that the two parts are in separate files.

Comments

Comments in a PDDL file start with a semicolon (";") and last to the end of the line.

Requirements

Because PDDL is a very general language and most planners support only a subset, domains may declare requirements. The most commonly used requirements are:

:strips
The most basic subset of PDDL, consisting of STRIPS only.
:equality
The domain uses the predicate =, interpreted as equality.
:typing
The domain uses types (see typing below).
:adl
The domain uses some or all of ADL (i.e. disjunctions and quantifiers in preconditions and goals, quantified and conditional effects).

Unfortunately, most planners' parsers are quite simple and often written under the assumption that you already know which parts of PDDL the planner supports. They often ignore the :restrictions clause – if you use a feature of PDDL they don't support, they give you a parse error without further information. Nevertheless, you should declare the correct requirements in any domain you write.

The Domain Definition

The domain definition contains the domain predicates and operators (called actions in PDDL). It may also contain types (see typing, below), constants, static facts and many other things, but these are not supported by the majority of planners.

The format of a (simple) domain definition is:

(define (domain DOMAIN_NAME)
  (:requirements [:strips] [:equality] [:typing] [:adl] ...)
  (:predicates (PREDICATE_1_NAME [?A1 ?A2 ... ?AN])
               (PREDICATE_2_NAME [?A1 ?A2 ... ?AN])
	       ...)

  (:action ACTION_1_NAME
    [:parameters (?P1 ?P2 ... ?PN)]
    [:precondition PRECOND_FORMULA]
    [:effect EFFECT_FORMULA]
   )

  (:action ACTION_2_NAME
    ...)

  ...)

Elements in []'s are optional, for those not familiar with formal grammars.

Names (of domains, predicates, actions, etc.) can usually contain alphanumeric characters, hyphens ("-") and underscores ("_"). There may be planners that allow less. Some planners use the same namespace for different items, so that you cannot (for example) use the same name for a domain and for a type.

Parameters of predicates and actions are distinguished by beginning with a question mark ("?").

For untyped domains, the parameters used in predicate declarations (the :predicates part) have no other function than to specify the number of arguments that the predicate should have, i.e. the parameter names do not matter (as long as they are distinct). Predicates can have zero parameters, but the predicate name still has to be written within parentheses.

Action Definitions

All parts of an action definition except the name are, according to the spec, optional (although, of couse, an action without effects is pretty useless). However, for an action that has no preconditions some planners may require an "empty" precondition, on the form :precondition (). Some planners may also require an empty :parameter list for actions without parameters.

Note: Some planners require that the arguments to an action are all different, i.e. the same object may not be used to instantiate two parameters. This ensures that the planner never tries pointless actions such as move(robot,locA,locA) which would move a robot from a location to the same location. At the same time there are cases where one does want the same argument to be used. For example, if we represent coordinates in a grid as the objects p1,p2,p3,p4,..., the planner should (but might not) allow actions such as move-to(p2,p2).

This may cause some difficulties (e.g. problems becoming unsolvable) if one is not aware of it. See the domain definition slidetile.pddl and the two problem definitions eight01.pddl and eight01x.pddl for an example of this problem and how to fix it.

Actions: Precondition Formulas

In a STRIPS domain, a precondition formula may be:

  • An atomic formula:
    (PREDICATE_NAME ARG1 ... ARG_N)
    The predicate arguments must be parameters of the action (or constants declared in the domain, if the domain has constants).
  • A conjunction of atomic formulas:
    (and ATOM1 ... ATOM_N)

If the domain uses :equality, an atomic formula may also be of the form (= ARG1 ARG2). Many planners that support equality also allow negated equality, which is written (not (= ARG1 ARG2)), even if they do not allow negation in any other part of the definition.

In an ADL domain, a precondition may in addition be:

  • A general negation, conjunction or disjunction:
    (not CONDITION_FORMULA)
    (and CONDITION_FORMULA1 ... CONDITION_FORMULA_N)
    (or CONDITION_FORMULA1 ... CONDITION_FORMULA_N)
  • A quantified formula:
    (forall (?V1 ?V2 ...) CONDITION_FORMULA)
    (exists (?V1 ?V2 ...) CONDITION_FORMULA)

Actions: Effect Formulas

In PDDL, the effects of an action are not explicitly divided into "adds" and "deletes". Instead, negative effects (deletes) are denoted by negation.

In a STRIPS domain, an effect formula may consist of:

  • An added atom:
    (PREDICATE_NAME ARG1 ... ARG_N)
    The predicate arguments must be parameters of the action (or constants declared in the domain, if the domain has constants).
  • A deleted atom:
    (not (PREDICATE_NAME ARG1 ... ARG_N))
  • A conjunction of atomic effects:
    (and ATOM1 ... ATOM_N)

The equality predicate (=) can of course not occur in an effect formula; no action can make two identical objects be not identical or vice versa!

Note that you can't use "exists" in action effects, since that would correspond to non-deterministic effects.

In an ADL domain, an effect formula may in addition contain:

  • A conditional effect:
    (when CONDITION_FORMULA EFFECT_FORMULA)
    The interpretation is that the specified effect takes place only if the specified condition formula is true in the state where the action is executed. Conditional effects are usually placed within quantifiers.
  • A universally quantified formula:
    (forall (?V1 ?V2 ...) EFFECT_FORMULA)

Note that nested use of "when" and "and" will confuse some planners. In general, it is good practice not to nest conditions more than necessary, and to keep expressions simple and readable. Most operators can be written using a single list of effects with a single level of nesting: "(and (p1) (p2) (when (p3) (p4)) (p5) (p6))".

The Problem Definition

The problem definition contains the objects present in the problem instance, the initial state description, and the goal.

The format of a (simple) problem definition is:

(define (problem PROBLEM_NAME)
  (:domain DOMAIN_NAME)
  (:objects OBJ1 OBJ2 ... OBJ_N)
  (:init ATOM1 ATOM2 ... ATOM_N)
  (:goal CONDITION_FORMULA)
  )

The initial state description (the :init section) is simply a list of all the ground atoms that are true in the initial state. All other atoms are by definition false.

The goal description is a formula of the same form as an action precondition. All predicates used in the initial state and goal description should naturally be declared in the corresponding domain. Goals are generally specified as a single conjunction: (and (something) (somethingelse) ...).

In difference to action preconditions, the initial state and goal descriptions should be ground, meaning that all predicate arguments should be object or constant names rather than parameters. (An exception is quantified goals in ADL domains, where of course the quantified variables may be used within the scope of the quantifier. However, even some planners that claim to support ADL do not allow quantifiers in goals.)

Typing

PDDL has a (very) special syntax for declaring parameter and object types. If types are to be used in a domain, the domain should first of all declare the requirement :typing.

Second, the type names have to be declared before they are used (which usually means before the :predicates declaration). This is done with the declaration

  (:types NAME1 ... NAME_N)

Then, to declare the type of a parameter of a predicate or action one writes ?X - TYPE_OF_X. A list of parameters of the same type can be abbreviated to ?X ?Y ?Z - TYPE_OF_XYZ. Note that the hyphen between parameter and type name has to be "free-standing", i.e. surrounded by whitespace.

The syntax is the same for declaring types of objects in the problem definition.

Conclusion

You have now seen a short introduction to PDDL. Please consult the external sources if anything seems unclear. We now move to the main part of the laboration.

Planners

In this lab we will use planners from the International Planning Competitions in 2011 and 2014. The planners will be from the tracks sequential-satisficing (seq-sat) and temporal-satisficing (tempo-sat), where "satisficing" means that the planners try to generate high quality plans but do not necessarily guarantee optimality (as this is computationally very difficult).

Here you should be aware of the rules of the competition, which rewards the highest plan quality that a planner can reach within a time limit of 30 minutes. For this reason, many (but not all) of the planners do not terminate when the first plan is found, but continue searching for the full 30 minutes in the hope of finding a better plan ("anytime" planning). Some of the planners also generate a great deal of output inbetween plans, which means you need to pipe the output through a tool such as "more" or "less" if you want to have a chance to see the plans that are generated.

When running the planners, please take note of parameters that may be passed. For instance, the seq-sat version of yahsp3 should be run with parameters "-y 1 -N" which gives it a suboptimal search with 1 thread and an anytime behavior. If you leave out "-N" nothing will be reported until 30 minutes have passed and if you leave out the "-y 1" part the planner will only report the optimal plan which may take a long time.

Sequential-Satisficing
  • yahsp3, a powerful heuristic forward-chaining search planner. Run with "yahsp3 -y 1 -N -o DOMAIN_FILE -f PROBLEM_FILE -out OUPUT_FILE"

  • lama-2011, another heuristic search planner based on landmarks; the winner of the sequential satisficing competition in 2011. Run with "plan DOMAIN_FILE PROBLEM_FILE OUPUT_FILE"

Temporal-Satisficing
  • yahsp3, a powerful heuristic forward-chaining search planner. Run with "yahsp3 -y 1 -N -K 0.01,0.01 -o DOMAIN_FILE -f PROBLEM_FILE -out OUPUT_FILE"

  • temporal fast downward, another heuristic search planner that uses context-enhanced additive heuristic. Run with "plan DOMAIN_FILE PROBLEM_FILE OUPUT_FILE"

Depending on your platform you may have to build the planners from source. Sources can be found here

Sequential-Satisficing
Temporal-Satisficing
We also provide prebuilt executables and .zip libraries for linux.
Sequential-Satisficing
Temporal-Satisficing

Additional Resources

There exists a PDDL parser that can be used to test your planning domains and problem instances for syntactic correctness. This parser is likely to be more correct and at the same time more informative than most planners' built-in parsers. A prebuilt linux version of the parser can be found here. Run it with "parser domainFile [problemFile]". Alternatively the source is available here if the binary does not work on your system.

Warm-up: Towers of Hanoi

As a warm-up exercise, you should define a PDDL planning domain and a small set of problem instances for the Towers of Hanoi domain.

The domain should allow the use of a variable number of disks and a variable number of pegs. In other words, disks and pegs will have to be distinct object types in the domain. You will also need a number of predicates. For example, you need a static predicate to keep track of which disks are larger than which other disks. You also need one or more dynamic predicates to keep track of the current placement and order of disks on different pegs.

You will have to define at least one operator ("action", in PDDL terminology) to move disks between different pegs. The preconditions of this operator must make sure that it is impossible to place a larger disk on top of a smaller disk.

You can run "makebigger.sh n" to create a suitable "bigger" predicate for n blocks.

When you feel satisfied with your domain, you should run it through the parser to see whether you have the correct syntax. Then create a couple of problem instances of different sizes and run them through at least one seq-sat planner. Verify that the plans that are generated are correct according to your knowledge of the Towers of Hanoi domain!

Remember that it is not sufficient that some plan is generated, because the plan could be faulty. Neither can you simply run the plan through the VAL tool to verify its correctness. This only verifies that the planner you used handles your domain definition correctly, which is important if you are developing new planners. What you need to verify here is that your domain definition is correct in itself, given your knowledge of the actual domain.

Emergency Services Logistics, Initial Version

In the emergency services logistics domain, a number of persons at known locations have been injured. Your task is to deliver crates containing emergency supplies to each person.

The initial version of the domain will be as follows:

  • Each injured person is at a specific location.
  • Each crate is at a specific location and has a specific content such as food or medicine. Note that it might be tempting to introduce predicates such as (is-food-crate ?c) and (is-medicine-crate ?c) to model the contents of crates. But then the domain has to be changed if a new crate type is introduced (water, different types of medicine, ...). Instead you must deal with crate contents in a generic way, so that new contents can easily be introduced in the problem instance.
  • Each person either has or does not have a crate with a specific content. That is, you must keep track of whether they have food or not, whether they have medicine or not, and so on.
  • There can be more than one person at any given location, and therefore it isn't sufficient to keep track of where a crate is in order to know which people have been given crates!
  • Initially all crates are located at a single location that we may call the depot. There are no injured people at the depot.
  • The goal should be that certain people have crates with certain contents. Some people might not need crates, some people might need both food and medicine, and so on. This means that you have to deliver some or all of the crates at the depot. Note that people don't care exactly which crate they get, so the goal should not be (for example) that person1 has crate5, merely that person1 has a crate of food.
  • A single helicopter, initially located at the depot, is available to deliver crates. It can fly directly between arbitrary locations (there is no "roadmap" with specific connections that must be taken). Since we want to be able to expand this domain for multiple helicopters in the future, we use a separate type for helicopters, which currently happens to have a single member in all your problem instances.
  • The helicopter can pick up a single crate, if it is at the same location as the crate. It can then fly to another location with the crate. Finally, it can deliver a crate to a specific person who is at the same location. Doing this will result in three distinct actions in a plan.

You should do the following:

  1. Model the domain in the STRIPS level of PDDL, and manually construct two small problem instances: One with only a single person and a single crate, and one with two people and three crates.
    Note: STRIPS level implies no negative preconditions (and goals).

  2. Run the domain and problem instances through one of the suitable planners. Make sure you get a reasonable plan.

  3. Begin writing your report. It should contain the domain and a small problem. Also describe the ideas behind your model.

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: A helicopter can load up to four crates onto a carrier, which must be at the same location. It can then fly the carrier to a location where there are people needing supplies and unload one or more crates from the carrier. It 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.

Though you currently only need a single carrier for your single helicopter, there should still be a separate type for carriers. 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. Techniques for doing this in non-numeric planners (which include most of the planners we have available) will be discussed during one of the first lectures.

You 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 helicopter is carrying on the carrier, and must therefore be preceded by a suitable pickup action (or whatever you might have called it in domain). Similarly, take-crate-from-carrier must be followed by actually delivering the crate to a person.

You should do the following:

  1. Modify the domain according to the discussion above.

  2. Create a new set of problem instances.

  3. Run the problems you have created through at least one of the seq-sat planners. For the report, discuss the following: What plans are generated? Do they use the carriers? Does this differ among different planners?

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

Emergency Services Logistics, Action Costs

As stated above, the intention behind the use of carriers is that a helicopter 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 loc3, 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 helicopter 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. It might help to use a script for calculating distances, or you might for example assign a cost of 100 to flying between the depot and another location, and a cost of 10 to flying between different locations.

  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.
  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).
  6. Similarly, every problem file must be amended to initialize fly-cost in the :init section. For example, you might add (= (fly-cost loc1 loc1) 0) (= (fly-cost loc1 loc2) 20) and so on. 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. Run the problems you have created through the same planner(s) as before. For the report, discuss: What plans are generated? Do they seem better than before? Do helicopters 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)? Discuss this briefly in your report.

Note that the planners selected for this lab are not optimal planners. Hence it may be that they report suboptimal plans, for instance not using carriers.

Using Sequential Planners for Multiple Agents

We will now consider centralized planning for multiple agents by introducing multiple helicopters in the UAV domain. When multiple agents are available, we generally have opportunities to take advantage of concurrent execution. For example, if we have more than one UAV, we can deliver many crates in parallel.

How do we generate suitable plans for such a scenario? One method would be to simply use a sequential planner as we did before, and then extract "subplans" for each agent with suitable constraints on execution order. For example, if the plan states that uav1 and uav2 deliver two crates in sequence, these actions are in fact independent of each other and can be executed in parallel.

You should do the following:

  1. Create a small set of problem instances that use at least four UAVs.
  2. Run these instances through your selected planner.
  3. For the report: Did the planner generate plans that actually make use of all agents? If not, does it seem like there would be room for improvement?

Introduction to Temporal Concurrent Planning

As you probably just noticed, sequential planners do not always generate plans that make good use of all available agents. The main reason is that they have no reason to do this: They are completely unaware that some parameters represent distinct agents, and given the formal model that is used, the only way of measuring plan quality is by using action costs. These costs may be identical regardless of whether actions are performed by a single agent or spread out across different agents!

We can often get considerably better results when using a planner that can deal with concurrency directly. We will illustrate how this is done using a simple example domain.

Concurrency in the Simple Rover Domain

Suppose that a Mars rover can drive around on the surface and can send scientific data to an orbiter. Suppose also that due to power constraints, the rover cannot both drive and send data at the same time. Our first partial model of this domain might use the following two operators:

    (define (domain simplerover)
        (:requirements :typing)
        (:types rover location data)
        (:predicates
            (at ?rover - rover ?location - location)
            (acquired ?rover - rover ?d - data)
            (sent ?d - data)
            (path-between ?a ?b - location))
    
    (:action drive
        :parameters (?r - rover ?from ?to - location)
        :precondition (and (at ?r ?from) (path-between ?from ?to))
        :effect (and (not (at ?r ?from)) (at ?r ?to)))
    
    (:action send
        :parameters (?r - rover ?d - data)
        :precondition (and (acquired ?r ?d))
        :effect (sent ?d))
    )

Now, suppose that we are in a state where the facts (at rover loc3), (path-between loc3 loc7), (acquired rover data3) are true. Then the following actions will be applicable in the current state:

    (drive rover loc3 loc7)
    (send data3)

A sequential planner by definition uses a plan structure that does not allow two actions to be executed at the same time, so there is no need for us to explicitly tell the planner when concurrency is possible in the "real world". The constraint we have, that one does not drive while transmitting data, will automatically be satisfied by any sequential plan.

But according to their definitions, the actions above are completely compatible with each other – for example, driving and sending never has conflicting effects, which would prevent them from being executed concurrently according to the PDDL semantics. Therefore, a concurrent planner may generate a plan where the rover drives to loc7 and sends data3 at the same time. But such a plan would violate our rovers' energy constraints.

That a concurrent planner may create such a plan is not a fault in the planner. Our model of the world was perhaps sufficient under the assumption of sequential plans, but when we create domains for concurrent planning, we must be more careful to consider potential parallelism and to tell the planner about any limits on concurrency, which we didn't do in the original domain specification. This is in principle no different from the fact that we had to be careful to specify all preconditions of an operator, even for sequential planning.

Such information may also be necessary to prevent a rover from driving to many destinations at the same time, to prevent picking up more than one block at the same time in the blocks world, or for similar purposes.

Preventing Concurrency

How one models limits on concurrency differs between modeling languages. Some languages use an explicit model of resource constraints and mutual exclusion conditions, which leads to slightly more work in defining a planning domain but can also provide a very clear and flexible model of concurrency. PDDL instead provides a temporal model where each action has a specific duration and can have effects both at the beginning and at the end of the action. Note that this model goes beyond the restricted state transition system that was used in sequential planning.

As a first step, we might change our model as follows. The changes are discussed below.

(define (domain simplerover2)
    (:requirements :typing :durative-actions)
    (:types rover location data - object)
    (:predicates
        (at ?rover - rover ?location - location)
        (acquired ?rover - rover ?d - data)
        (sent ?d - data)
        (path-between ?a ?u - location))
    
    (:durative-action drive
        :parameters (?r - rover ?from ?to - location)
        :duration (= ?duration 10)
        :condition (and (at start (at ?r ?from))
                        (over all (path-between ?from ?to)))
        :effect (and 
                   (at start (not (at ?r ?from)))
                   (at end (at ?r ?to))))

    (:durative-action send
        :parameters (?r - rover ?d - data ?loc - location)
        :duration (= ?duration 2)
        :condition (and (over all (acquired ?r ?d))
	                 (over all (at ?r ?loc)))
        :effect (at end (sent ?d)))
)

Now let's take a look at the changes that we made.

  1. We specified that we need durative actions (actions that take place over an interval of time rather than "instantaneously").
  2. We changed :action to :durative-action and specified a constant duration for each action. Durations can also be defined in terms of numeric functions, such as the fly-cost function that was previously used for action costs.
  3. We now need to describe when a certain condition should hold during the execution of an action. Preconditions have therefore been generalized to conditions.
    1. To drive from a location, you must be there at the start of the action, and the path must exist throughout the action.
    2. If you send data, it must remain acquired throughout the action. We also require that the rover is in a certain location (a new condition associated with a new parameter). We don't have any real requirements on which locations are possible, but simply say that you are there (wherever that is) throughout the execution of the action. This ensures that the rover does not drive and send data at the same time.
  4. The drive action now removes the fact that the rover is at ?from at the start of the action, but waits until the end of the action until it adds the fact that it has arrived at ?to. This seems quite intuitive given the nature of driving.

    Note that this change also ensures that the rover cannot drive to two locations at the same time. The first drive action that one applies will immediately (at start) delete the fact that the rover is somewhere. In effect, the rover is "nowhere at all". You can only drive if you are somewhere, so the second drive action can only be applied after the first drive action has ended and (at ?r ?to) has been added.

  5. Similarly, sending data has an effect at the end of the action.

Given this domain, the planner is still allowed to generate actions that send more than one piece of data at the same time, which should not be possible since in reality each piece of data requires its own time slot.

Generating Plans for the Rovers Domain

In this exercise you should extend the domain specification above to ensure that the rover never sends more than one piece of data at a time. This may require modifications to various parts of the domain above. Since we are not interested in driving at the moment, you may begin by using the following simple problem instance with only a single location:

(define (problem rover1)
    (:domain simplerover2)
    (:objects d1 d2 d3 d4 d5 d6 d7 d8 - data 
              r1 - rover loc1 - location)
    (:init (acquired r1 d1) (acquired r1 d2) (acquired r1 d3)
           (acquired r1 d4) (acquired r1 d5) (acquired r1 d6)
           (at r1 loc1))
    (:goal (and (sent d1) (sent d2) (sent d3)
           (sent d4) (sent d5) (sent d6)))
)

Use several temporal satisficing planners to verify that reasonable plans are generated. Describe in your report how you ensured that rovers do not send multiple pieces of data at any given time.

Concurrency in Emergency Services Logistics

We now extend the UAV logistics domain for concurrency with the use of multiple helicopters:

  1. Add multiple helicopters to your problem instances.
  2. Convert your domain to use durative actions. Among other things, this converting action costs to durations (action costs are not supported by the temporal planners we have available, which is not a problem since we only used them to model time requirements).
  3. Ensure that actions are only performed in parallel when this would be possible in reality. For example, a helicopter cannot pick up several crates at the same time, or pick up a crate and fly to a destination at the same time.
  4. Use a temporal satisficing planner and investigate the performance. For the report, discuss: How large problems can be solved in one minute? How is the planner affected when you vary different parameters, such as the number of UAVs or the number of crates?

Sidansvarig: Webmaster
Senast uppdaterad: 2016-09-06