Abstract
We solve the problem of constructing extended finite state machines with execution scenarios and temporal formulas. We propose a new algorithm pstMuACO that combines a scenario filtering procedure, an exact algorithm efsmSAT for constructing finite state machines from execution scenarios based on a reduction to the Boolean satisfiability problem, and a parallel ant colony algorithm pMuACO. Experiments show that constructing several initial solutions for the ant colony algorithm with reduced sets of scenarios significantly reduces the total time needed to find optimal solutions. The proposed algorithm can be used for automated construction of reliable control systems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Clarke, E., Grumberg, O., and Peled, D., Model Checking, Cambridge: MIT Press, 1999.
Polikarpova, N.I. and Shalyto, A.A., Avtomatnoe programmirovanie (Automata Programming), St. Petersburg: Piter, 2009.
Shalyto, A.A., Algorithmic Graph Schemes and Transition Graphs: Their Use in Software Realization of Logical Control Algorithms. II, Autom. Remote Control, 1996, vol. 57, no. 7, part 2, pp. 1027–1045.
Vel’der, S.E., Lukin, M.A., Shalyto, A.A., et al., Verifikatsiya avtomatnykh programm (Verification of Automata Programs), St. Petersburg: Nauka, 2011.
Gold, M., Complexity of Automaton Identification from Given Data, Inf. Control, 1978, vol. 37, no. 3, pp. 302–320.
Ul’yantsev, V.I., Applying Method for Solving the Boolean Satisfiability Problem for Constructing Controlling Finite State Machines with Work Scenarios, Bachelor’s Thesis, SPSU IFMO, 2011, available at http://isifmoru/diploma-theses/2011/bachelor/ulyantsev/thesispdf.
Luke, S., Essentials of Metaheuristics, Raleigh: Lulu, 2009.
Karpenko, A.P., Sovremennye algoritmy poiskovoi optimizatsii. Algoritmy, vdokhnovlennye prirodoi, (Modern Search Optimization Algorithms: Algorithms Inspired by Nature), Moscow: Mosk. Gos. Tekhn. Univ. im. N.E. Baumana, 2014.
Kureichik, V.V., Kureichik, V.M., and Rodzin, S.I., Teoriya evolyutsionnykh vychislenii (Theory of Evolutionary Computation), Moscow: Fizmatlit, 2012.
Tsarev, F. and Egorov, K., Finite State Machine Induction Using Genetic Algorithm Based on Testing and Model Checking, Proc. 13th Ann. Conf. on Genetic and Evolutionary Computation Companion, New York, 2011, pp. 759–762.
Chivilikhin, D. and Ulyantsev, V., MuACOsm: A New Mutation-Based Ant Colony Optimization Algorithm for Learning Finite-State Machines, Proc. 15th Ann. Conf. on Genetic and Evolutionary Computation, New York, 2013, pp. 511–518.
Heule, M. and Verwer, S., Exact DFA Identification Using SAT Solvers, Proc. 10th Int. Colloquium Conf. on Grammatical Inference: Theoretical Results and Applications, Berlin, 2010, pp. 66–79.
Ulyantsev, V. and Tsarev, F., Extended Finite-State Machine Induction Using SAT Solver, Proc. 10th Int. Conf. on Machine Learning and Applications, Los Alamitos, 2011, vol. 2, pp. 346–349.
Chivilikhin, D., Ulyantsev, V., and Shalyto, A., Combining Exact and Metaheuristic Techniques for Learning Extended Finite-State Machines from Test Scenarios and Temporal Properties, Proc. 13th Int. Conf. on Machine Learning and Applications, Detroit, 2014, pp. 350–355.
Chivilikhin, D., Ulyantsev, V., and Shalyto, A., Extended Finite-State Machine Inference with Parallel Ant Colony Based Algorithms, Proc. 5th Int. Student Workshop on Bioinspired Optimization Methods and Their Applications, Ljubljana, 2014, pp. 117–126.
Chivilikhin, D. and Ulyantsev, V., Inferring Automata-Based Programs from Specification with Mutation-Based Ant Colony Optimization, Proc. 16th Conf. on Genetic and Evolutionary Computation Companion, New York, 2014, pp. 67–68.
Egorov, K.V., Generating Controlling Finite State Machines with Genetic Programming and Verification, PhD Dissertation, SPSU IFMO, 2013, available at http://isifmoru/disser/egorov disserpdf.
Levenshtein, V.I., Binary Codes Capable of Correcting Deletions, Insertions, and Reversals, Soviet Physics Dokl., 1966 vol. 10, no. 8, pp. 707–710,.
Baker, J., Reducing Bias and Inefficiency in the Selection Algorithm, Proc. 2nd Int. Conf. on Genetic Algorithms and their Applications, Hillsdale, 1987, pp. 14–21.
Dorigo, M., Maniezzo, V., and Colorni, A., Ant System: Optimization by a Colony of Cooperating Agents, IEEE Trans. Systems, Man Cybernetics, 1996, vol. 25, no. 1, pp. 29–41.
Duret-Lutz, A., Manipulating LTL Formulas using SPOT 1.0., in Automated Technology for Verification and Analysis, Lect. Notes in Computer Science, Hung, D. and Ogawa, M., Eds., 2013, vol. 8172, pp. 442–445.
López-Ibánez, M., Dubois-Lacoste, J., Stützle, T., et al., The irace Package, Iterated Race for Automatic Algorithm Configuration, Technical Report TR/IRIDIA/2011-004, IRIDIA, Université Libre de Bruxelles, 2011.
Wilcoxon, F., Individual Comparisons by Ranking Methods, Biometrics Bull., 1945, vol. 1, no. 6, pp. 80–83.
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © D.S. Chivilikhin, V.I. Ulyantsev, A.A. Shalyto, 2016, published in Avtomatika i Telemekhanika, 2016, No. 3, pp. 137–151.
Rights and permissions
About this article
Cite this article
Chivilikhin, D.S., Ulyantsev, V.I. & Shalyto, A.A. Modified ant colony algorithm for constructing finite state machines from execution scenarios and temporal formulas. Autom Remote Control 77, 473–484 (2016). https://doi.org/10.1134/S0005117916030097
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0005117916030097