On the Disruptive Effectiveness of Automated Planning for LTLf-Based Trace Alignment

Giuseppe De Giacomo, Fabrizio Maria Maggi, Andrea Marrella, Fabio PatriziAAAI 2017 · DOI

Abstract

Trace alignment is a critical task in business process management, ensuring that recorded activity logs conform to intended declarative models. This paper presents a novel approach by reducing the trace alignment problem to cost-optimal automated planning. By encoding Linear Temporal Logic ($LTL_f$) specifications into PDDL, the authors demonstrate that general-purpose planners like Fast Downward and SymBA*-2 significantly outperform specialized state-of-the-art tools, particularly as model complexity and trace length increase.

Introduction: The Trace Alignment Problem

In modern business environments, process logs (traces) capture the execution of activities, such as loan processing or insurance claims. Ideally, these traces should adhere to a predefined process model. However, real-world data is often "noisy" due to system errors or human deviations.

Trace alignment is the process of finding the minimal set of edits—insertions or deletions—required to make an observed trace conform to a model. While procedural models are common, declarative models using $LTL_f$ offer more flexibility by defining constraints (e.g., "Activity A must precede B") rather than fixed paths. As these models grow in complexity, traditional specialized alignment tools often suffer from state-space explosion.

Methodology: Reduction to Planning

The authors propose a multi-step reduction to transform trace alignment into a cost-optimal planning problem:

  1. Automata Construction: $LTL_f$ constraints are converted into a constraint automaton ($A$), and the observed trace is converted into a trace automaton ($T$).
  2. Augmentation for Repairs: The automata are augmented with "repair" transitions. These allow for "deleting" an event from the trace or "adding" a missing event required by the model.
  3. PDDL Encoding: The problem is translated into PDDL 2.1. Actions include sync (trace matches model, cost 0), add (inserting an activity, cost 1), and del (removing an activity, cost 1).
  4. Cost-Optimal Planning: Off-the-shelf planners find the lowest-cost plan, which directly corresponds to the optimal alignment.

Experimental Evaluation

The approach was evaluated using both real-life financial logs and synthetic datasets with varying complexity (10, 15, and 20 constraints) and noise levels (3 to 6 violated constraints).

Comprehensive performance results across varying constraints and noise levels.

Key Results

The results highlight a significant performance gap between planning-based methods and existing specialized tools.

  • Superior Scalability: On complex synthetic logs with 20 constraints, the planning-based approach completed alignments in approximately 27–28 seconds. In contrast, the previous state-of-the-art specialized tool (an A*-based implementation in the ProM toolkit) required over 223 seconds for the same task.
  • Noise Tolerance: The performance advantage of the planning approach becomes more pronounced as the number of errors in the trace increases.
  • Planner Comparison: SymBA*-2, utilizing bidirectional search, generally exhibited better scaling than Fast Downward as the number of constraints in the process model increased.
Scalability comparison on 20-constraint models showing the performance gap between planning and specialized tools.

Discussion and Key Insights

The "disruptive" effectiveness of this approach stems from the maturity of general-purpose automated planners. These solvers have benefited from decades of research into heuristic optimization, allowing them to navigate complex state spaces more efficiently than many domain-specific algorithms. Furthermore, the use of $LTL_f$ provides a flexible framework that supports any process specification representable in temporal logic, moving beyond the limitations of template-based methods like DECLARE.

Conclusion and Future Work

By treating trace alignment as a planning problem, this research provides a highly efficient and scalable solution for business process monitoring. Future work aims to extend this framework to include data attributes and temporal constraints (e.g., deadlines), potentially leveraging advanced planners capable of handling numeric fluents and native temporal logic.

Summary updated

BibTeX
@inproceedings{giacomo2017disruptive,
  author = {Giuseppe De Giacomo and Fabrizio Maria Maggi and Andrea Marrella and Fabio Patrizi},
  title = {{On the Disruptive Effectiveness of Automated Planning for LTLf-Based Trace Alignment}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.11020},
}
Figure