Iterative Plan Construction for the Workflow Satisfiability Problem

DOI10.1613/JAIR.4435MaRDI QIDQ2938473zbMATH OpenOpenAlexFDO

Authors

Publication date 14 January 2015

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.3649

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of organizations, manpower planning in operations research (90B70)

Abstract: The emph{Workflow Satisfiability Problem (WSP)} is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defined by business rules. We are required to decide whether there exists a emph{plan} -- an assignment of tasks to authorized users -- such that all constraints are satisfied. Several bespoke algorithms have been constructed for solving the WSP, optimised to deal with constraints (business rules) of particular types. It is natural to see the WSP as a subclass of the {em Constraint Satisfaction Problem (CSP)} in which the variables are tasks and the domain is the set of users. What makes the WSP distinctive as a CSP is that we can assume that the number of tasks is very small compared to the number of users. This is in sharp contrast with traditional CSP models where the domain is small and the number of variables is very large. As such, it is appropriate to ask for which constraint languages the WSP is fixed-parameter tractable (FPT), parameterized by the number of tasks. We have identified a new FPT constraint language, user-independent constraint, that includes many of the constraints of interest in business processing systems. We are also able to prove that the union of FPT languages remains FPT if they satisfy a simple compatibility condition. In this paper we present our generic algorithm, in which plans are grouped into equivalence classes, each class being associated with a emph{pattern}. We demonstrate that our generic algorithm has running time $O^{\ast }(2^{klogk})$, where $k$ is the number of tasks, for the language of user-independent constraints. We also show that there is no algorithm of running time $O^{\ast }(2^{o(klogk)})$ for user-independent constraints unless the Exponential Time Hypothesis fails.

Recommendations

• Solving sequential planning problems via constraint satisfaction
• On the workflow satisfiability problem with class-independent constraints
• Pattern-based approach to the workflow satisfiability problem with user-independent constraints
• Planning as satisfiability: parallel plans and algorithms for plan search
• Pattern backtracking algorithm for the workflow satisfiability problem with user-independent constraints
• Engineering algorithms for workflow satisfiability problem with user-independent constraints
• Algorithms for the workflow satisfiability problem engineered for counting constraints
• Parameterized complexity of the workflow satisfiability problem
• Informational and Performance Properties of a Class of Iterative Planning Procedures

Cited in

(11)

• On the satisfiability of authorization requirements in business process
• Polynomial kernels and user reductions for the workflow satisfiability problem
• Polynomial kernels and user reductions for the workflow satisfiability problem
• Engineering algorithms for workflow satisfiability problem with user-independent constraints
• Algorithms for the workflow satisfiability problem engineered for counting constraints
• Pattern backtracking algorithm for the workflow satisfiability problem with user-independent constraints
• Parameterized complexity of the workflow satisfiability problem
• Pattern-based approach to the workflow satisfiability problem with user-independent constraints
• On the workflow satisfiability problem with class-independent constraints
• Fixed-parameter tractability of workflow satisfiability in the presence of seniority constraints
• Tight lower bounds for the workflow satisfiability problem based on the strong exponential time hypothesis

This page was built for publication: Iterative Plan Construction for the Workflow Satisfiability Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2938473)