Long range space missions, such as Rosetta, require robust plans of data-acquisition activities and of the resulting data transfers. In this paper we revisit the problem of assigning priorities to data transfers in order to maximize safety margin of onboard memory. We propose a fast sweep algorithm to verify the feasibility of a given priority assignment and we introduce an efficient exact algorithm to assign priorities on a single downlink window. We prove that the problem is NP-hard for several windows, and we propose several randomized heuristics to tackle the general case. Our experimental results show that the proposed approaches are able to improve the plans computed for the real mission by the previously existing method, while the sweep algorithm yields drastic accelerations.

Hierarchical Task Networks were proposed as a method to describe plans by decomposition of tasks to subtasks until primitive tasks, actions, are obtained. Valid plans - sequences of actions - must adhere both to causal dependencies between the actions and to the structure given by the decomposition of the goal task. Plan verification aims at finding if a given plan is valid, that is, if it is causally consistent and it can be obtained by decomposition of some task. The paper describes a novel parsing-based approach for hierarchical plan verification that is orders of magnitude faster than existing methods.

The paper presents attribute grammars as a unifying framework for modeling planning domains and problems. The motivation is to exploit techniques from formal languages in domain model verification, plan and goal recognition, domain model acquisition, as well as in planning. Grammar rules are used for action selection while specific set attributes are used to collect events (preconditions and effects of actions) that are ordered using a global timeline constraint. We show how classical STRIPS, hierarchical task networks, and procedural domain models are transformed to attribute grammars.