Lab 3: Concurrency and Temporal Planning

Updates

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

Introduction

We will now consider centralized planning for multiple agents by introducing multiple helicopters in the UAV domain.

Lab 3.1: Using Sequential Planners for Multiple Agents

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. Generate a small set of problem instances that use at least four UAVs.
2. Run these instances through the sequential satisficing planners that you used in lab 1 and 2.
3. For the report: Which sequential planners generate plans that actually make use of all agents? Does it seem like there would be room for improvement?

Lab 3.2: Theory: Temporality and Concurrency

Now we have seen a number of sequential plans that we would actually prefer to execute concurrently. We can assume that a single agent (UAV) cannot execute two actions at a time. Additionally, even if two actions are actually executed by different agents, it may still not be possible (or safe) to execute them concurrently. For example, these actions may require two agents to use the same resources or to be in the same location.

Your task is to identify such actions in your domain, under the assumption that the original plan is sequential. Include your findings in your report.

Introduction to Temporal Concurrent Planning

As you probably noticed in lab 3.1, 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)

We now have three distinct cases:

• Sequential planning, sequential execution. 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.

• Sequential planning, concurrent execution. If a sequential plan is going to be "made concurrent", there is still no need to ensure that the planner does not select two actions in the same state – it is sequential, so it can't. However, after a plan is generated, the procedure that determines which actions can be executed in parallel must be aware of which actions cannot be parallelized.

• Concurrent planning, concurrent execution. According to their definitions, the actions above are completely compatible with each other – for example, driving and sending never has conflicting effects, which would have prevented 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 consumption 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.

Lab 3.3: 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 the temporal planners ITSAT, YAHSP3 and Temporal Fast Downward 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.

Lab 3.4: Concurrency in Emergency Services Logistics

Your second task in this lab is to 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 the temporal planners that you used in the previous part and investigate their performance. How large problems can be solved in one minute? How are the planners affected when you vary different parameters, such as the number of UAVs or the number of crates?

Finishing and handing in the results

When you have finished the lab, you need to demonstrate and discuss the results with your lab assistant.

After the demonstration and discussion, you should hand in your results:

• Create a single ZIP file, named fffll111-fffll222-lab3.zip where fffll111 and fffll222 are your liu-ids (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: 2019-03-18