Authors:
Lukas Kirchdorfer、Robert Blümel、Timotheus Kampik、Han van der Aa、Heiner Stuckenschmidt
Paper:
https://arxiv.org/abs/2408.08571
Introduction
Business Process Simulation (BPS) is a technique used to estimate the impact of changes in business processes. Traditional BPS approaches often focus on control-flow-first perspectives, which may not accurately capture the dynamics of real-world processes involving distinct resource behaviors and decentralized decision-making. This paper introduces AgentSimulator, a resource-first BPS approach that models distinct resource behaviors and interaction patterns through a multi-agent system (MAS) discovered from event logs. AgentSimulator achieves state-of-the-art simulation accuracy with significantly lower computation times and high interpretability.
Motivation
The motivation for shifting from control-flow-first to resource-first simulation models is illustrated using a simplified credit application process. This process involves various actors (clerks and credit officers) whose distinct behaviors and interaction patterns influence the execution of cases. Key factors include:
- Process Performance: Execution time varies based on the employee performing the task.
- Resource Availability: Different availabilities of employees affect process execution.
- Control-flow Behavior: The sequence of activities may depend on the actors involved.
- Interaction Patterns: Specific interaction patterns among actors influence workload and delays.
These factors highlight the need for simulation models that can faithfully represent real-world process dynamics, which is achieved by AgentSimulator.
Our Approach: AgentSimulator
AgentSimulator adopts a resource-first perspective by modeling agents in a MAS. The approach consists of two main phases: MAS discovery and simulation.
Definitions
- Event Logs: Input event logs are finite multi-sets of traces, each trace being a sequence of events recording the execution of activities for a single case.
- Multi-agent System (MAS): A MAS is defined as a tuple consisting of a set of agents and general simulation parameters.
- Agent: An agent represents a real-world actor or system, defined by its type, schedule, capabilities, and behavior.
Phase 1: MAS Discovery
AgentSimulator discovers agents and general simulation parameters from an event log. Key steps include:
- Agent Instantiation: One agent is instantiated for each resource in the event log.
- Agent Type: Agents are clustered into types based on the similarity of their executed activities.
- Schedule: Each agent’s schedule is discovered to reflect their availability.
- Capabilities: Agents’ capabilities include the activities they can execute and the distributions over processing times for these activities.
- Behavior: Agent behavior captures activity transition and agent handover patterns, which can be learned for orchestrated or autonomous handovers.
Phase 2: Simulation
The simulation phase uses the discovered MAS to simulate an event log. The simulation proceeds in discrete steps, each representing a time tick. Key steps include:
- Check for New Cases: Determine if a new case arrives based on the inter-arrival distribution.
- Handle All Running Cases: For each running case, determine the next activity and the responsible agent, then start activity execution.
Experiments and Results
Experimental Setup
- Implementation: Implemented in Python using the mesa framework.
- Benchmark Approaches: Compared against Simod, DeepGenerator (DGEN), and DeepSimulator (DSIM).
- Data Split: Temporal hold-out split with 80% training and 20% test sets.
- Metrics: Evaluated using metrics for control-flow (N-Gram Distance), time (Absolute Event Distribution, Circadian Event Distribution, Relative Event Distribution), and congestion (Cycle Time Distribution).
Results
AgentSimulator frequently achieves the best performance across various metrics and event logs. Key insights include:
- Control-flow: AgentSimulator enhances control-flow accuracy compared to control-flow-first approaches.
- Time: AgentSimulator captures temporal patterns well.
- Congestion: AgentSimulator demonstrates superior accuracy in capturing cycle times.
Post-hoc Analysis on Agent Interactions
AgentSimulator accurately reflects interaction dynamics, capturing activity chaining of resources, unlike Simod, which exhibits random interactions.
Runtime
AgentSimulator operates much faster than benchmarks, making it feasible to run a large number of simulations for reliable predictions.
Related Work
Related work includes automated BPS approaches (DDPS, DL, and hybrid models) and agent-based modeling and simulation. AgentSimulator is the first approach to automatically infer MAS models for process simulation from event logs.
Conclusion
AgentSimulator introduces a resource-first approach for data-driven business process simulation, achieving state-of-the-art results with reduced computation times. Future work includes incorporating multitasking, batching, and fatigue effects, and exploring additional MAS architectures.
This blog post provides a detailed overview of the AgentSimulator approach, highlighting its motivation, methodology, experimental results, and related work. The illustrations included help visualize key concepts and findings.
