A Graph Matching Algorithm to extend Wise Systems with Semantic

• Autorzy: Dahhani, Abdelhafid , Alloui, Ilham , Monnet, Sébastien , Vernier, Flavien
• Języki publikacji: EN

Abstrakty

EN

Software technology has exponentially evolved leading to the development of intelligent applications using artificial intelligence models and techniques. Such development impacts all scientific and social fields: home automation, medicine, communication, etc. To make those new applications useful to a larger number of people, researchers are working on how to integrate artificial intelligence into real world while respecting the notion of calm technology. This paper fits in the context of the development of intelligent systems termed ``wise systems'' that aim at satisfying the calm technology requirement. Those systems are based on the concept of ``Wise Object'': a software entity -- object, service, component, application, etc. -- able to learn by itself how it is expected to behave and how it is used by a human or another software entity. During its learning process, a Wise Object constructs a graph that represents its behavior and the way it is used. A major weakness of Wise Objects is that the numerical information that they generate is mostly meaningless to humans. Therefore the objective of the work presented in this paper is to extend Wise Objects with semantics that enable them communicate with humans whose attention will consequently be less involved. In this paper, we address the issue of how to relate two different views using two state-based formalisms: State Transition Graph for views generated by the Wise Objects and Input Output Symbolic Transition System for conceptual views. Our proposal extends previous work done to extend the generated information with the conceptual knowledge using a matching algorithm founded on graph morphism. The first version of the algorithm has several limitations and constraints on the graphs that make it difficult to use in realistic cases. In this paper, we propose to generalize the algorithm and raise those restrictions. To illustrate the complete process, the construction of a sample graph matching on a home-automation system is considered.

Słowa kluczowe

PL

informatyka; automatyka domowa; semantyka; oprogramowanie; nauki behawioralne; inteligentny system

EN

computer science; home automation; semantics; software; behavioral science; intelligent system

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2023
• Tom: Vol. 35
• Strony: 411--420
• Opis fizyczny: Bibliogr. 41 poz., wz., rys.

Twórcy

autor

Dahhani, Abdelhafid

• Université de Savoir Mont Blanc, LISTIC laboratoty, Polytech Annecy-Chambery, 5 Chem. de Bellevue, 74940 Annecy, France,

autor

Alloui, Ilham

• Université de Savoir Mont Blanc, LISTIC laboratoty, Polytech Annecy-Chambery, 5 Chem. de Bellevue, 74940 Annecy, France,

autor

Monnet, Sébastien

• Université de Savoir Mont Blanc, LISTIC laboratoty, Polytech Annecy-Chambery, 5 Chem. de Bellevue, 74940 Annecy, France,

autor

Vernier, Flavien

• Université de Savoir Mont Blanc, LISTIC laboratoty, Polytech Annecy-Chambery, 5 Chem. de Bellevue, 74940 Annecy, France,

Bibliografia

• 1. M. Weiser and J. S. Brown, “Designing calm technology,” POWERGRID JOURNAL, vol. 1, 1996.
• 2. A. Tugui, “Calm technologies in a multimedia world,” Ubiquity, vol. 2004, 03 2004. http://dx.doi.org/10.1145/985616.985617
• 3. I. Alloui, D. Esale, and F. Vernier, “Wise objects for calm technology,” in Proceedings of the 10th International Conference on Software Engineering and Applications - ICSOFT-EA, (ICSOFT 2015), INSTICC. SciTePress, 2015. http://dx.doi.org/10.5220/0005560104680471 pp. 468–471 – Section 2.
• 4. S. Lejamble, I. Alloui, S. Monnet, and F. Vernier, “A new software architecture for the wise object framework: Multidimensional separation of concerns,” in Proceedings of the 17th International Conference on Software Technologies - ICSOFT,, INSTICC. SciTePress, 2022. http://dx.doi.org/10.5220/0011355000003266 pp. 567–574.
• 5. R. A. Flores-Mendez, “Towards a standardization of multi-agent system framework,” XRDS, vol. 5, no. 4, p. 18–24, jun 1999. http://dx.doi.org/10.1145/331648.331659
• 6. A. Dorri, S. S. Kanhere, and R. Jurdak, “Multi-agent systems: A survey,” IEEE Access, vol. 6, pp. 1–1, 2018. http://dx.doi.org/10.1109/ACCESS.2018.2831228
• 7. D. Bonino and F. Corno, “Dogont - ontology modeling for intelligent domotic environments,” in The Semantic Web - ISWC 2008, A. Sheth, S. Staab, M. Dean, M. Paolucci, D. Maynard, T. Finin, and K. Thirunarayan, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. http://dx.doi.org/10.1007/978-3-540-88564-1_51 pp. 790–803.
• 8. H. K. Ngankam, H. Pigot, M. Frappier, O. Souza, H. Camila, and S. Giroux, “Formal specification for ambient assisted living scenarios,” UCAmI, pp. 508–519, 11 2017. http://dx.doi.org/10.1007/978-3-319-67585-5_51
• 9. J.-B. Woo and Y.-K. Lim, “User experience in do-it-yourself-style smart homes,” in Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing, ser. UbiComp ’15. New York, NY, USA: Association for Computing Machinery, 2015. http://dx.doi.org/10.1145/2750858.2806063 p. 779–790.
• 10. R. Radziszewski, H. Ngankam, H. Pigot, V. Grégoire, D. Lorrain, and S. Giroux, “An ambient assisted living nighttime wandering system for elderly,” in Proceedings of the 18th International Conference on Information Integration and Web-Based Applications and Services, ser. iiWAS ’16. New York, NY, USA: Association for Computing Machinery, 2016. http://dx.doi.org/10.1145/3011141.3011171 p. 368–374.
• 11. R. S. Michalski, “A theory and methodology of inductive learning,” Artificial Intelligence, vol. 20, no. 2, pp. 111–161, 1983. http://dx.doi.org/10.1016/0004-3702(83)90016-4
• 12. M. Weiser, “The computer for the 21st century,” Scientific American, vol. 265, no. 3, pp. 66–75, January 1991. http://dx.doi.org/10.1145/329124.329126
• 13. Y. Brun, G. D. M. Serugendo, C. Gacek, H. Giese, H. Kienle, M. Litoiu, H. Muller, M. Pezzè, and M. Shaw, Engineering Self-Adaptive Systems through Feedback Loops. Springer Berlin Heidelberg, 2009, pp. 48–70.
• 14. J. Kephart and D. Chess, “The vision of autonomic computing,” Computer, vol. 36, pp. 41 – 50, 02 2003. http://dx.doi.org/10.1109/MC.2003.1160055
• 15. H. Sachs, M. Stiebitz, and R. Wilson, “An historical note: Euler’s königsberg letters,” Journal of Graph Theory, vol. 12, pp. 133–139, 10 2006. http://dx.doi.org/10.1002/jgt.3190120114
• 16. C. Constant, T. Jéron, H. Marchand, and V. Rusu, “Integrating Formal Verification and Conformance Testing for Reactive Systems,” IEEE Transactions on Software Engineering, vol. 33, no. 8, pp. 558–574, Aug. 2007. http://dx.doi.org/10.1109/TSE.2007.70707
• 17. C. Camille, J. Thierry, M. Hervé, and R. Vlad, “Validation of Reactive Systems,” in Modeling and Verification of Real-TIME Systems - For-malisms and software Tools, S, Merz, N, and Navet, Eds. Hermès Science, Jan. 2008, pp. 51–76. ISBN 978-1848210134
• 18. I. Boudhiba, C. Gaston, L. G. Pascale, and V. Prevosto, “Input Output Symbolic Transition Systems Enriched by Program Calls and Contracts: a detailed example of vending machine,” Laboratoire MAS - Centrale-Supelec, Research Report, 2015.
• 19. J. Dörpinghaus, T. Hübenthal, and J. Faber, “A novel link prediction approach on clinical knowledge graphs utilizing graph structures,” in Proceedings of the 17th Conference on Computer Science and Intelligence Systems, ser. Annals of Computer Science and Information Systems, vol. 30. IEEE, 2022. http://dx.doi.org/10.15439/2022F36 p. 43–52.
• 20. A. Dahhani, I. Alloui, S. Monnet, and F. Vernier, “Towards a semantic model for wise systems - a graph matching algorithm,” in ADVCOMP 2022, The Sixteenth International Conference on Advanced Engineering Computing and Applications in Sciences, S. Laura Garcia, Universitat Politecnica de Valencia, Ed., vol. 34, Nov. 2022. ISBN 2308-4499 pp. 27–34.
• 21. M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman and Co., 1979. ISBN 0716710455
• 22. V. A. Cicirello, “Survey of graph matching algorithms,” Geometric and Intelligent Computing Laboratory, Drexel University, Technical Report, March 1999.
• 23. T. Davenport and L. Prusak, Working Knowledge: How Organizations Manage What They Know. Harvard Business School Press, 01 1998, vol. 1. ISBN 1578513014
• 24. P. Moreaux, F. Sartor, and F. Vernier, “An effective approach for home services management,” in 2012 20th Euromicro International Conference on Parallel, Distributed and Network-based Processing, 2012. http://dx.doi.org/10.1109/PDP.2012.45 pp. 47–51.
• 25. M. N. Nicolescu and M. J. Mataric, “Extending behavior-based systems capabilities using an abstract behavior representation,” in AAAI 2000, North Falmouth, MA, 2000, pp. 27–34.
• 26. V. Rusu, H. Marchand, V. Tschaen, T. Jéron, and B. Jeannet, “From safety verification to safety testing,” in Testing of Communicating Systems, 03 2004. http://dx.doi.org/10.1007/978-3-540-24704-3_11. ISBN 978-3-540-21219-5 pp. 160–176.
• 27. V. Rusu, H. Marchand, and T. Jéron, “Automatic verification and conformance testing for validating safety properties of reactive systems,” in Formal Methods 2005 (FM05), ser. Lecture Notes in Computer Science, vol. 3582. Newcastle, United Kingdom: Springer-Verlag, Jul. 2005. http://dx.doi.org/10.1007/11526841_14 pp. 189–204.
• 28. C. Gaston, P. Le Gall, N. Rapin, and A. Touil, “Symbolic execution techniques for test purpose definition,” in Testing of Communicating Systems. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11754008_1 pp. 1–18.
• 29. M. Mashaal, Bourbaki, ser. Bourbaki : A secret society of mathematicians. American Mathematical Society, Jun. 2006. ISBN 9780821839676
• 30. A. Salomaa, I. N. Sneddon, H. M. Stark, and J.-P. Kahane, Theory of Automata : International Series of Monographs in Pure and Applied Mathematics, ser. International series in pure and applied mathematics. - page.1-2. London : Elsevier Science, 2015., 1969-2015. ISBN 978-1483121970
• 31. G. Hahn and C. Tardif, Graph homomorphisms: structure and symmetry. Dordrecht: Springer Netherlands, 1997, pp. 107–166. ISBN 978-94-015-8937-6
• 32. M. Eshera and K.-S. Fu, “An image understanding system using attributed symbolic representation and inexact graph-matching,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-8, pp. 604–618, 1986. http://dx.doi.org/10.1109/TPAMI.1986.4767835
• 33. W.-H. Tsai and K.-S. Fu, “Error-correcting isomorphisms of attributed relational graphs for pattern analysis,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 9, no. 12, pp. 757–768, 1979. http://dx.doi.org/10.1109/TSMC.1979.4310127
• 34. M. Zaslavskiy, “Graph matching and its application in computer vision and bioinformatics,” Theses, École Nationale Supérieure des Mines de Paris, Jan. 2010.
• 35. E. Bengoetxea, “Inexact graph matching using estimation of distribution algorithms,” Ph.D. dissertation, Ecole Nationale Supérieure des Télécommunications, Paris, France, Dec 2002.
• 36. J. R. Ullmann, “An algorithm for subgraph isomorphism,” J. ACM, vol. 23, no. 1, p. 31–42, jan 1976. http://dx.doi.org/10.1145/321921.321925
• 37. H. Bunke and G. Allermann, “Inexact graph matching for structural pattern recognition,” Pattern Recognition Letters, vol. 1, no. 4, pp. 245–253, 1983. http://dx.doi.org/10.1016/0167-8655(83)90033-8
• 38. M. Neuhaus, K. Riesen, and H. Bunke, “Fast suboptimal algorithms for the computation of graph edit distance,” in Structural, Syntactic, and Statistical Pattern Recognition. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. ISBN 978-3-540-37241-7 pp. 163–172.
• 39. D. A. Basin, “A term equality problem equivalent to graph isomorphism,” Information Processing Letters, vol. 51, no. 2, pp. 61–66, 1994. http://dx.doi.org/10.1016/0020-0190(94)00084-0
• 40. M. A. Abdulrahim, Parallel algorithms for labeled graph matching. Colorado School of Mines1500 Illinois St. Golden, CO, 1998.
• 41. J. E. Hopcroft and J. K. Wong, “Linear time algorithm for isomorphism of planar graphs (preliminary report),” in Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, ser. STOC ’74. Association for Computing Machinery, 1974. http://dx.doi.org/https://dx.doi.org/10.1145/800119.803896 p. 172–184.

Uwagi

1. This research was supported by French National Research Agency (ANR), AI Ph.D funding project.

2. Thematic Tracks Regular Papers

3. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).

Identyfikatory

DOI

10.15439/2023F4672