Document Open Access Logo

Mining Significant Temporal Networks Is Polynomial

Authors Guido Sciavicco , Matteo Zavatteri , Tiziano Villa

PDF
Thumbnail PDF

File

LIPIcs.TIME.2020.11.pdf
  • Filesize: 0.53 MB
  • 12 pages

Document Identifiers

Author Details

Guido Sciavicco
  • Department of Mathematics and Computer Science, University of Ferrara, Italy
Matteo Zavatteri
  • Department of Computer Science, University of Verona, Italy
Tiziano Villa
  • Department of Computer Science, University of Verona, Italy

Funding

This work was partially supported by MIUR, Project Italian Outstanding Departments, 2018-2022 and by INdAM, GNCS 2020, Project Strategic Reasoning and Automated Synthesis of Multi-Agent Systems.

Cite AsGet BibTex

Guido Sciavicco, Matteo Zavatteri, and Tiziano Villa. Mining Significant Temporal Networks Is Polynomial. In 27th International Symposium on Temporal Representation and Reasoning (TIME 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 178, pp. 11:1-11:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.TIME.2020.11

Abstract

A Conditional Simple Temporal Network with Uncertainty and Decisions (CSTNUD) is a formalism that tackles controllable and uncontrollable durations as well as controllable and uncontrollable choices simultaneously. In the classic top-down model-based engineering approach, a designer builds a CSTNUD to model, validate and execute some temporal plan of interest. Instead, in this paper, we investigate the bottom-up approach by providing a deterministic polynomial time algorithm to mine a CSTNUD from a set of execution traces (i.e., a log). This paper paves the way for the design of controllable temporal networks mined from traces that also contain information on uncontrollable events.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Temporal reasoning
  • Information systems → Data mining
  • Computing methodologies → Planning and scheduling
  • Mathematics of computing → Graph algorithms
Keywords
  • Mining temporal constraints
  • cstnud
  • uncertainty
  • significant temporal network

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Rakesh Agrawal, Dimitrios Gunopulos, and Frank Leymann. Mining process models from workflow logs. In EDBT '98, pages 469-483. Springer, 1998. Google Scholar
  2. Massimo Cairo, Luke Hunsberger, Roberto Posenato, and Romeo Rizzi. A streamlined model of conditional simple temporal networks - semantics and equivalence results. In TIME 2017, volume 90 of LIPIcs, pages 10:1-10:19. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.TIME.2017.10.
  3. Alessandro Cimatti, Luke Hunsberger, Andrea Micheli, Roberto Posenato, and Marco Roveri. Dynamic controllability via timed game automata. Acta Informatica, 53(6):681-722, 2016. Google Scholar
  4. Carlo Combi, Roberto Posenato, Luca Viganò, and Matteo Zavatteri. Conditional simple temporal networks with uncertainty and resources. Journal of Artificial Intelligence Research, 64:931-985, 2019. URL: https://doi.org/10.1613/jair.1.11453.
  5. Patrick R. Conrad and Brian C. Williams. Drake: An efficient executive for temporal plans with choice. JAIR, 42(1):607-659, 2011. Google Scholar
  6. Jonathan E. Cook and Alexander L. Wolf. Discovering models of software processes from event-based data. TOSEM, 7(3):215-249, 1998. Google Scholar
  7. Rina Dechter, Itay Meiri, and Judea Pearl. Temporal constraint networks. Artif. Intell., 49(1-3):61-95, 1991. Google Scholar
  8. Joachim Herbst. A machine learning approach to workflow management. In ECML '00, pages 183-194. Springer, 2000. Google Scholar
  9. Luke Hunsberger, Roberto Posenato, and Carlo Combi. The Dynamic Controllability of Conditional STNs with Uncertainty. In PlanEx at ICAPS-2012, pages 1-8, 2012. Google Scholar
  10. Luke Hunsberger, Roberto Posenato, and Carlo Combi. A sound-and-complete propagation-based algorithm for checking the dynamic consistency of conditional simple temporal networks. In TIME 2015, pages 4-18. IEEE CPS, 2015. URL: https://doi.org/10.1109/TIME.2015.26.
  11. Erez Karpas, Steven James Levine, Peng Yu, and Brian Charles Williams. Robust execution of plans for human-robot teams. In ICAPS '15, pages 342-346. AAAI Press, 2015. Google Scholar
  12. Steven J. Levine and Brian C. Williams. Concurrent plan recognition and execution for human-robot teams. In ICAPS '14, pages 490-498. AAAI, 2014. Google Scholar
  13. Ioannis Tsamardinos, Thierry Vidal, and Martha E. Pollack. CTP: A new constraint-based formalism for conditional, temporal planning. Constraints, 8(4):365-388, 2003. URL: https://doi.org/10.1023/A:1025894003623.
  14. Wil M. P. van der Aalst. Daelemans. automated discovery of workflow models from hospital data. In BNAIC '01, pages 25-26, 2001. Google Scholar
  15. Wil M. P. van der Aalst, Boudewijn F. van Dongen, Joachim Herbst, Laura Maruster, Guido Schimm, and A. J. M. M. Weijters. Workflow mining: A survey of issues and approaches. Data Knowl. Eng., 47(2):237-267, 2003. Google Scholar
  16. Wil M. P. van der Aalst, A.J.M.M. Weijters, and L. Maruster. Workflow mining: Which processes can be rediscovered? In Eindhoven University of Technology, pages 1-25, 2002. Google Scholar
  17. Thierry Vidal and Hélène Fargier. Handling contingency in temporal constraint networks: from consistency to controllabilities. Jour. of Exp. & Theor. Artif. Intell., 11(1):23-45, 1999. URL: https://doi.org/10.1080/095281399146607.
  18. Peng Yu, Cheng Fang, and Brian Charles Williams. Resolving uncontrollable conditional temporal problems using continuous relaxations. In ICAPS '14, pages 341-349. AAAI, 2014. Google Scholar
  19. Matteo Zavatteri. Conditional simple temporal networks with uncertainty and decisions. In TIME 2017, volume 90 of LIPIcs, pages 23:1-23:17. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.TIME.2017.23.
  20. Matteo Zavatteri, Romeo Rizzi, and Tiziano Villa. Dynamic Controllability and (J,K)-Resiliency in Generalized Constraint Networks with Uncertainty. In ICAPS 2020, pages 314-322. AAAI Press, 2020. Google Scholar
  21. Matteo Zavatteri and Luca Viganò. Constraint networks under conditional uncertainty. In ICAART 2018, pages 41-52. SciTePress, 2018. URL: https://doi.org/10.5220/0006553400410052.
  22. Matteo Zavatteri and Luca Viganò. Conditional simple temporal networks with uncertainty and decisions. Theoretical Computer Science, 797:77-101, 2019. URL: https://doi.org/10.1016/j.tcs.2018.09.023.
  23. Matteo Zavatteri and Luca Viganò. Conditional uncertainty in constraint networks. In Agents and Artificial Intelligence, pages 130-160. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-05453-3_7.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact