Grouping

[jmdelfa]

Groupingv2.pptx
This discussion aims to steer the decision-making process wrt the design and implementation approach for Grouping capability in Aerie.

Grouping expands the needs expressed in the tickets below:

• Model activities that are performed in serial.
  Allow groupings of sequential activities in eDSL #870
• Define groups of activities with the intention of avoiding overlapping
  Ability to "Group" Activities Linked via Scheduling #1073

The overall goal of grouping is to allow the user to define group of activities and constraints among them that are known to be repeated in a plan. Grouping is commonly used in space system engineering to construct plans. Previous systems such as ASPEN and current ones such as COPILOT make use of groups for routine operations.

Aerie implementation of grouping shall not be limited to the needs of a specific mission (e.g. CLIPPER), but focus on the most useful approach for current and future customers.

We will implement grouping following the Hierarchical Task Network's formalism (HTN). In particular, we will use the formal definition provided in the book Automated Planning: Theory & Practice (Malik Ghallab, Paolo Traverso, Dana Nau), which is used as reference in most literature on HTNs.

Attached the slides that summarize the current approach

[dandelany]

Notes from today's discussion re: MVP for the Grouping feature:

• Juan is working on prototyping an MVP based on the slides linked above
• MVP will implement compound activity directives which decompose into fully ordered task networks of primitive activity directives
• Compound activity may have multiple possible decompositions ie. task networks
  • User can decide which Method to use, which maps compound to task network
• Primitive & compound activity types, Methods and Task Networks will be defined in the mission model
• Scheduler must be run to decompose compound activities into networks & "ground" them
  • cannot simulate compounds until scheduler is run to decompose
• Can the user modify the primitive activities created by a task network/compound activity after it's been decomposed?
  • & if they do, is this still considered to be a decomposition "satisfying" the associated Compound? Probably not
  • if the primitives are modified, how to get it back to the original version?
• Need to differentiate between task networks of abstract activity directives vs. the grounded group of activity instances derived from the network after simulation
• Future discussion needed with UI designers to decide how to visualize compounds + task networks in the UI
  • and what interactions are allowed, how to modify them

[mattdailis]

Here's a quick sketch of a distinction we discussed between Compound/Task Network definitions and the resulting entities in the plan

[jmdelfa]

Just one correction to @dandelany post.

• Solver must be run to decompose compound activities into networks & "ground" them.
• New code will be required to perform the decomposition. This code should go in a new class for a Planner
• Simulation of a partial plan with compound activities not decomposed should return a partial plan.
• A valid plan can be only generated once all compound activities are decomposed into Primitive Task Networks, that is, a Task Network with no compound activities.

[adrienmaillard]

Here are my notes/questions on the implementation aspects

General notes

• When thinking about the source of truth being in the mission model vs the db is that the user won’t be able to create ad-hoc tasknetworks/compound via the UI.
• Do we want compounds to have parameters ? In the below preliminary impl design, activities in task networks have constant parameters. If we want the user to route some activity parameters, we could add parameters to TN and compounds.

Modeling for exporting the compound/TN information

• ActivityReference is a wrapper around String to designate activities in the task network (you may have several activities of the same type)
• TaskNetwork could be a record (or an interface with one method per member) of
  • String: name
  • ActivityInstantiation which is a record of
    • ActivityReference : name for this task in the network
    • String: activity type name
    • Map<String, SerializedValue>: the list of parameters
  • List<Constraint>
    • Constraint is a sealed interface with one implementation (so far)
      • record Precedes(ActivityReference, ActivityReference)
        • as we only do total order right now
• Compound is a record referencing all the task networks that it can decompose to
  • List<TaskNetwork>
  • String its name
• in MissionModel, we would need a new method
  • List<Compound> getCompoundTasks()
• in MerlinBindings, we need a new request to get this information to the UI

How do users write this in the mission model ?

Easiest would be to have TaskNetwork as an interface and have the users implement each task network in a new class
Then we would have

• A new @WithTaskNetwork(Class) annotation
• A new @WithCompound(name:String, methods:list of Class (impl of TaskNetwork **classes**)
  for reference in the package-info.java

This allows the mission model checker/validator to perform checks and to package the information for the List<Compound> getCompoundTasks external method.

On the DB side, I was wondering if we could get away with adding a boolean to the ActivityDirective table. But we’d have to add a bunch of code to existing methods to discriminate between the 2. It might be easier to have a new CompoundDirective table referencing all the compounds in a plan. This CompoundDirective would contain pretty much the same info as the ActivityDirective table and would reference the name (its type in the ActivityDirective table) of the compound. Maybe we can extract the metadata fields to another table.

We also need some kind of InstantiatedCompound table associating activity directive ids with element from CompoundDirective

Do we need a CompoundSpan table similar to the Span table ? Or the UI could do some machinery with the InstantiatedCompound to show the instantiated compounds as spanning over their whole set of activities ?

The Decomposer would be in scheduler-driver ? Changes would be limited to querying compound activities from the plan from the scheduler-worker and routing them to the PrioritySolver or some higher entity that would organize the call relationship from the Decomposer and the PrioritySolver.

[jmdelfa]

To your first comment about the mission model, we will organize development in different MVPs. The ultimate goal is indeed to be able to create/modify task networks in the UI, but that's a lot of work. In order to expedite the process, we will start by modeling them in Java. We can then transition to EDSL and expose that to the UI if there are enough resources.
Regarding your first question about the compound having parameters, the answer is yes. Parameters for compound are typically used to bound sub-activity values, bound decomposition choices or guide execution.
Regarding modeling, I will arrange a meeting with you. Some of the points you mention require further discussion. For what I can say right now:

• ActivityReference: Not sure about this. We should discuss
• Task Network: It is important to differentiate here between a template and an instantiated task network. To me the first question is what are the current classes in Aerie to look at to define activities. In my opinion, we will have to look if ActivityType and SchedulingActivityDirective need to be modified. In that case, I am not sure yet of whether just records would suffice. For example, ActivityType is implemented as a record in the scheduler server and as class in worker, so maybe the answer is not so straighforward.

How users model them

• Correct, we need additional annotation. I need to check the ticket on annotation to see the status, but we need to further talk about the two annotations you suggest as they are not very clear to me.
• DB: I'm incline to add a boolean because it seems to me that it will result in smaller code and maximizes reusability
• The decomposer shouldn't be in scheduler-driver, as it is not a scheduler. A new package planner driver should be created.
• Other points to be covered in meeting

[adrienmaillard]

So if they have parameters, it is only to "redirect" them to their internal primitive/compounds, right ? as they are not supposed to have their own behaviors.

For modeling: compound do not have run() methods as they are not ran by simulation. To me, they do not have any effects, only primitive do, no ? In the future, we can model declarative planning-like effects in primitive activities but I guess we will always end up generating simulation code (a run() method) from these declarations as we have to run simulations.

[jmdelfa]

Conversation with Matt and Theresa. We explored the synergies of grouping wrt simulation decomposition and concluded that the latter is very specific code for simulation and cannot be extrapolated to HTNs.
We talked about the impact of incorporating networks. It is clear that at the moment we will have to focus on implementation at Java level due to the large number of modifications it would require if exposed at the UI.

[jmdelfa]

Talk to Tiago Vaquero. We explored in further detail alignement of Aerie future HTN with hierarchical modeling in Task Nets and particularly for MEXEC. Follow on meeting on Thursday 20th June.

[jmdelfa]

Here is the proposed roadmap:
Grouping v1
•Full order
•Full decomposition. Partial decomposition not allowed
•Only Temporal constraints
•No backtracking
•No conditional decomposition
•Limited UI capability to display compound activities and their decompositions (to be further refined)
•Parent/Network not linked. Compound is replaced by the TaskNet.

Grouping v2
•Partial order
•Partial decomposition
•Temporal and parametric constraints

Grouping v3
•Conditional decomposition
•Add heuristic interface
•Full UI capability including: 1. creation of methods; 2. creation of task networks

Grouping v4
•Develop simple heuristic

[jmdelfa]

Conversation with @adrienmaillard entering the territory of implementation.

• Modeling
  Compound Activity Type definition
  Agreed to use annotation (e.g. @Compound) to distinguish compound from primitive activities
  Talk about whether a Compound Activity can use the same Activity Type as Primitive.
  Compound activities can be simulated in order to determine their duration (Adrien clarifies that in terms of parameters, they cannot be changed as part of a simulation). In this case, we don't need any new class to model them, just the additional annotation. As a side benefit, that reduces the amount of code: to add a new activity type, modifications in scheduler, ...
  Agreed to use the String Activity Reference to identify an activity type
  The concept of method needs further specification. A compound activity would not have a list of task networks. Rather it has a method which contains a list of constraints or functions that decide what's the best task network to decompose the compound task.

Compound

• String
• Method

Method

• List<Pair<List<Constraints>, TaskNetwork>>

Note: In a meeting with Gregg Rabideau, he clarified that MEXEC uses hooks to external functions that decide what task network to use and return an instantiation of it. The idea of having external funtions that could implement heuristics defined by the user to choose the task network sounds very interesting, but I think it is more straightforward to benefit from current/future Aerie constraint capabilities.

Task Network
Agreed to add the new class Task Network in merlin framework. Compound annotation would go in merlin framework->annnotation.

Planner
Decomposition is part of planning (that is, it adds new activities to a partial plan). In consequence, the decomposer will be constructed in a new planner-worker package. We need a higher level entity to synchronize calls between planner (decomposer) and scheduler

Impact on scheduler
The decomposer will create goals (as a result of decomposing a compound activity into a task network) that are passed to the scheduler. In this way, the impact to the scheduler is expected to be minimal

Other pending design choices:
When decomposing a compound into a task network, the user needs to set a flag to indicate whether the compound remains linked to the task network or not. The consequences are:

• Linked:
  • The compound activity will remain in the plan.
  • Dragging the compound to another starting time will result in moving the linked task network
  • The subactivities are relatively order vs the compound. That means that if the compound is moved, there is no need to re-schedule the subactivities
  • The link is preserved regardless of whether the user modifies the activities/constraints in the task network.
  • Subactivities have as parent the compound activity
• Not linked:
  • Compound dissapears
  • Subactivities order absolutely wrt plan origin
  • User can move subactivities outside the temporal interval of the compound
  • Subactivities do not have parent

Pending to decide:

• Is the task network in the model the same structure used by planner and scheduler?

[jmdelfa]

Conversation with @bradNASA . Incremental sim seems the right approach to handle scenarios in which one of the activities in the decomposed task network fails (e.g. to be scheduled). In that scenario we need to undo the decomposition and try another one.

[jmdelfa]

Conversation with @adrienmaillard and @mattdailis.
The first part focuses on how to model the activities (reference and instance) and constraints.
Activity reference: Agreement on the current way forward, by which an activity is referenced by its type and a unique name. The name must be unique as a tasknet might have several activities of the same type
Constraints: Given that tasknet constraints are binary, we need a new class to model them.
Activity instance: There are doubts on whether to reuse the SchedulerActivityDirective or create a new specific class. My argument to reuse SchedulerActivityDirective is that both planner and scheduler should use a unified definition of activities for temporal/space efficiency. As side effect, that also simplifies code and maintenance.

Moving to implementation, I will continue implementing the elements to be included in the mission model: method, tasknettempalte and tasknetinstance. It is agreed to coordinate with Adrien either once these core classes are finished or whether an opportunity for work paralellization arises.

The first milestone is set to provide an early demo on the side of mission modelling of how HTN modelling would look like.

[jmdelfa]

Conversation with @mattdailis and @dandelany
We focus on how to represent activity instances. I will make a demo with schedulingactivitydirective.
There are two open questions:
Simulation creates a new SchedulingActivityDirective with grounded duration. topParent variable links the simulated directive to the scheduler directive. We need to figure out how do represent hierarchies considering these two activities (sim and scheduler)
We talk about who is responsible for grounding activity arguments. Duration is grounded by simulation called from scheduler. Start time is grounded by scheduler. Activity arguments could be grounded by the user (current approach), decomposer or simulation.
@dandelany suggest using annotation to indicate which activity arguments are meant to be grounded by user/planner or simulation

[jmdelfa]

Summary of assumptions:

1. Total order
2. Total decomposition (no partial decomposition)
3. One level decomposition
4. Only Temporal constraints
5. Only one network per compound type
6. No backtracking
7. No conditional decomposition
8. Acyclic networks
9. When decomposing: compound is maintained in the plan. All subactivities start times are anchored to the compound's start time. subactivities cannot be modified
10. Removing compound implies removing the tasknetwork (backend) and subactivities (frontend and backend)
11. UI: User cannot create tasknets graphically. User cannot modify subactivities. User can only modify compound activity in the following ways: move it, delete it or modify parameters. when compound parameters are modified, it effectively implies that decomposition is not valid, hence it has to be removed and new decomposition performed. when
12. Open questions for UI: how merge works? suggested that the most recent compound wins. For each case: 1. compound is moved: in the merge, the latest compound version is applied (same as current merge policy for activities). 2. and 3. compound is deleted or parameters are modified: latest change applies. In this case, the subactivities need to be removed

[jmdelfa]

The truth table for compound activities based on the booleans CanBeSimulated (CBS) and the existence of methods (ME) for the compound is:
CBS - ME - Outcome
Yes - Yes - Decompose
Yes. - No - Simulate compound
No. - Yes - Decompose
No - No - Error

[jmdelfa]

Work In Progress

This a wrap up on the design, implementation and pending work for Activity Grouping in Aerie. The code is on the feature/grouping branch.

Introduction

CLIPPER requested the capability to group activities to be linked via scheduling. The request was captured in two tickets:

• Ability to "Group" Activities Linked via Scheduling #1073
• Allow groupings of sequential activities in eDSL #870

It can be summarized as follows:

• Capability to treat a specified sequence of activities like an activity, so things can be scheduled relative to it
• The sequence can be scheduled with recurrence and cardinality rules
• Mechanism for providing relative timing within the sequence to encode wait times between activities (to define a sequence of activities) and mutexes to avoid overlapping

Concepts and Formalism

Grouping is the non-technical word that refers to the capability to define hierarchical task network (HTNs).

HTN is the formalism used to implement the groups in Aerie, as defined in [1]
[1] @book{10.5555/975615, author = {Nau, Dana and Ghallab, Malik and Traverso, Paolo}, title = {Automated Planning: Theory & Practice}, year = {2004}, isbn = {1558608567}, publisher = {Morgan Kaufmann Publishers Inc.}, address = {San Francisco, CA, USA} }

The formalism introduces new concepts for Planning and Scheduling in Aerie:

• Planning: Represents the act of automatically adding new activities into the plan. Hierarchical decomposition can be considered a form of planning. It is performed by a software component called Planner.
• Scheduling: Represents the act of automatically assigning start times and durations to the activities in the plan. It is performed by a software component called Scheduler. We will refer to the process of Planning and Scheduling as P&S.
• Primitive Activity: Represent actions that are executable or can be directly translated to executable commands, and can appear in the final plan
• Compound Activity: Represent an abstract task (non-executable) that need to be decomposed by the planner to construct a valid plan.
• Task Network (TN): Contains a list of activities and a list of constraints among the activities. It is typically represented as a directed graph, where the activities are the nodes and the constraints are the edges.
• Method: Establish a map between a compound activity and the Task Networks that decompose it. The Method might contain conditions to guide the selection process among the multiple Task Networks
• Decomposition: Planning process by which the compound activities in a partial plan are decomposed into sub-activities.
• Partial Plan: A plan in which not all constraints have been yet satisfied

Design Principles

HTNs can be implemented with different capabilities, which are enumerated below. For each capability, the design choice for the first MVP is described. Further information on a potential roadmap is presented in the next section.

• Total order: All activities must be fully ordered. There can be only one root activity (activity that doesn't have a predecessor in the TN) and one final activity (activity that doesn't have any successor). There cannot be orphans (activities without predecessors and successors).
• Total decomposition: The P&S process will produce plans in which all compound activities have been decomposed.
• One-level decomposition: A TN cannot have compound activities. In consequence, the decomposition tree only has one level of depth.
• TN Temporal Constraints: The TN can only have MEET constraints to establish the relative order between sub-activities. Parametric constraints are not supported.
• One single TN per method: Each compound activity can be decomposed in one single way, that is, each Method only has one TN. In consequence, the ability to include conditions in the Method to guide the decomposition process is unnecessary.
• No backtracking: Following the current scheduler design, backtracking is not possible, that is, it is not possible to undo a decision made. That leads to a non-complete solver, meaning that it cannot be guaranteed that a solution will be found even if it exists.
• Acyclic networks: If activities are vertices and temporal constraints are edges in the graph representation of a task network, there can't be any cycle in the graph.
• Decomposition Approach: During decomposition, the compound activity is maintained in the plan. All sub-activities start times are anchored to the compound's start time.
• Allowed operations
  • Insertion: The user can insert compound activities directly in the plan or via Aerie goals. The insertion on a compound activity will result in a partial plan that can be made complete by means of decomposition
  • Deletion: Removing a compound activity from the plan results in the deletion of its decomposing TN.
  • Edition: After decomposition, the user is allowed to modify the TN (inserting, moving, deleting sub-activites, changing their parameters). There is no guarantees about the plan validity if the user does so.
• UI representation: The UI will represent the compound activities in the plan in a way that can be expanded to show the sub-activities. Each sub-activity will be also illustrated in its corresponding lane.
• Plan manipulation
  • Merge: The most recent compound wins. Here are the possible use cases: 1. compound is moved: in the merge, the latest compound version is applied (same as current merge policy for activities). 2. and 3. compound is deleted or parameters are modified: latest change applies. In this case, the sub-activities need to be removed.

Roadmap

We have defined a roadmap to incorporate increasing level of complexity into Aerie:

• MVP 1
  • Full order
  • Full decomposition
  • Only Temporal constraints
  • No backtracking
  • No conditional decomposition
  • Limited UI capability to display compound activities and their decompositions (to be further refined)
  • Parent/Network linked
• MVP 2
  • Partial order
  • Partial decomposition
  • Temporal and parametric constraints
• MVP 3
  • Conditional decomposition
  • Add heuristic interface
  • Full UI capability including: 1. creation of methods; 2. creation of task networks
• MVP 4
  • Develop simple heuristic

Design and Implementation

The main design choices are related to how to model Task Networks and the structure of the solvers. In the following, we will describe the final design and current implementation:

• scheduler-driver: Aerie must be expanded to include the planning/decomposition step. The solvers have been redesigned as illustrated in the figure below:

  • MetaSolver: Represents the interface to the rest of Aerie for P&S tasks. It is responsible for collecting all the initial conflicts in the plan, which now can come from either the goals or compound activities directly placed in the plan and calling the appropriate subsolvers (Planner or Scheduler)
    • NexusMetaSolver: Implementation of the MetaSolver. After collecting all conflicts, it past them to the PrioritySolver
  • Subsolver
    • PrioritySolver: Responsible to resolve the goal conflicts and to schedule the activities in the plan by assigning start times and durations. If any of the activities in the plan is compound, it will call the NexusDecomposer subsolver to decompose it before proceeding to schedule it.
    • NexusDecomposer: It decomposes all compound activities in sub-activities.
      
  • Conflicts: A new MissingDecompositionConflict is required as input to the decomposer, containing a reference to the compound activity and the start and end intervals in which it can be placed.

• merlin-sdk: A new sub-package is required to incorporate the new HTN concepts:

  • ActivityReference: Used to represent an uninstantiated activity (ActivityType and serialized parameters) in the Task Network

  • TaskNetworkTemporalConstraint: At present only contains a Meet constraint to fully order the sub-activities.

  • TaskNetTemplate: Interface that the user implements in the mission model to generate the TaskNet data from a compound activity.

  • TaskNetTemplateData: Contains the task network information: a set of sub-activities (activity references) and the constraints (TaskNetworkTemporalConstraint) among them.

  • merlin-framework:

    • @Compound annotation
      • has a shouldBeDecomposed (user specified boolean): States whether a compound activity can or cannot be simulated. In case it cannot, then the activity must be decomposed. The user might want to allow simulation only in case he has an approximation of the behavior of the subactivities.
      • @Method Annotation: The method annotation is used to annotate implementation of TaskNetTemplate to signal the existence of a method
    • Compound activity logic: Compound activities will be managed in different ways depending on the value of two boolean parameters: ShouldBeDecomposed (SBD) and the existence of methods (ME):
      SBD - ME - Outcome
      Yes - Yes - Decompose
      Yes. - No - Error
      No. - Yes - Decompose
      No - No - Simulate compound

  • merlin-framework-processor

    • code processing to process @Compound annotations
    • code generation to generate the ActivityReferences class containing static builders for each activity type. The user uses these builders when building methods (example in TNConsumeBanana in the banananation mission model).
    • code generation to parse/process task networks defined from users and provide a map from compound type to methods in SchedulerModel.getMethods

Pending Work

• The scheduler needs to be adapted to take into account the status of compound activities:
  • If the compound activity hasn't been decomposed, the simulator should ignore it and not simulate it
  • If the compound has been decomposed and all subactivities have been simulated, then simulation should assign to the compound start time the start time of the first sub-activity, and the compound end time will be the end time of the last sub-activity
• Assign to the first sub-activity an anchor to start at the same time as the start of the compound. Assign to the following sub-activities an anchor from their start to the end of the previous sub-activity using exclusively a meets relation
• Simulation
  • Implement how compound activities are managed depending on CBS and ME values
• DB
  • Add boolean to activity type table to state whether a task is compound or not
  • General work to design the behavior of groups under mergen, snapshot
  • Add the notion of group in the DB (whether as a new table or a boolean in the activity directive table)
• UI
  • Expand/collapse compound activity to show subactivities
  • Design behavior of groups when user modified them: As for the first MVP as specified in design