Lab 3: Concurrency and Temporal Planning

Updates

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

• 2020-04-10: Updated instructions for demonstrating and handing in results.

• 2021-04-19: Some clarifications in lab 3.1.

• 2021-05-03: Some additional information about ITSAT (green box under lab 3.3) after examining why it fails to find plans quickly in certain domain formulations.

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? Would it be possible 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, could we get a sequential solution stating that uav1 and uav2 deliver two crates in sequence, and then post-process it to say that these actions are in fact independent of each other and can be executed in parallel?

As a brief investigation of this idea, you should do the following:

1. Generate a small set of problem instances containing at least four UAVs.

2. Run these instances through the sequential satisficing planners that you used in lab 1 and 2.

   If you already did the following, it's fine and you don't have to change anything, but if not, check the next paragraph instead: You don't have to wait very long for a "good" plan, in case there are multiple solutions; just take the first plan that is generated for each instance and planner.

   You don't have to wait very long for a "good" plan, in case there are multiple solutions, but please wait for at least 30-60 seconds for each instance and planner. Some planners, such as Arvand, can generate very low-quality initial plans and then quickly improve them a lot.

3. For the report: Which sequential planners generate plans that actually spread their actions across all, or at least multiple, agents? Does this seem to happen consistently? Does it seem like there would be room for improvement if the planner didn't initially create a sequence, but was "aware" of the potential for parallel execution?

Lab 3.2: Theory: Temporality and Concurrency

Clarifications added 2021-04-19

Now we have seen a number of sequential plans where we would actually prefer some actions to execute concurrently. But this isn't true for all actions in these plans – there will be pairs of actions that cannot actually execute concurrently.

For example, we can make the assumption that a single UAV agent cannot execute two of the actions in the current domain specification at the same time. This would involve combinations such as one UAV picking up two crates at the same time, or one UAV picking up a crate while it begins to fly to a new location.

At this point, your task is to determine which pairs of actions (in your own domain) you think should be prevented from executing at the same time by different UAVs. To some extent, this might follow from more or less unavoidable aspects of domain; for example, it seems unreasonable to think that two UAVs should be able to pick up the same crate at the same time, but depending on the exact domain model you have defined, this could turn out to be possible for a concurrent planner (often with strange and unintuitive results). There might also be cases where you have to clarify your own assumptions and make new decisions about what certain parts of your model really mean. For example, is a location large enough for multiple UAVs at the same time? Can two UAVs be sufficiently close to a single person that they can hand over two different packages at the same time? Decide which actions can / cannot be executed in parallel, and then include your findings in your report.

Later, you will also find out how to prevent the planner from scheduling such actions in parallel when they cannot be physically executed in parallel. Right now we are only interested in finding out which action pairs should never be scheduled in parallel, apart from the pairs that involve using the same UAV.

Introduction to Temporal Concurrent Planning

As you probably noticed with some planners 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. Later we will return to the UAV domain again!

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 Rover domain specification above to ensure that the rover never sends more than one piece of data at a time. (Using Rovers at this point allows you to try this out on a domain that is typically much simpler than your own domain.)

To verify that the rover doesn't send multiple pieces of data concurrently, you will check the generated plans, where the first number on each line is the starting time for an action and the last number is its duration; for example, 0.00 (doSomething) [5] means that the doSomething action starts at time 0.00 and continues until time 5.00.

You 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)))
)

You may need to add :fluents to the domain requirements, and remove :action-costs. Beware that there is a built-in type called exactly number that is used for the fly cost function, but that you may also have a num type that is used for your own "pseudo-numbers" used for the carrier capacity.

Use the temporal planners ITSAT, YAHSP3 and Temporal Fast Downward to verify that "non-overlapping" plans are generated with your modified domain. 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 requires removing increase effects and adding durations instead (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). Recall that you can still use the fly-cost function to specify the duration!
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 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 meeting in case additional information is required. Alternatively, your hand-in may be approved without a demonstration.