Modified ant colony algorithm for constructing finite state machines from execution scenarios and temporal formulas
- Authors: Chivilikhin D.S.1, Ulyantsev V.I.1, Shalyto A.A.1
-
Affiliations:
- ITMO University
- Issue: Vol 77, No 3 (2016)
- Pages: 473-484
- Section: Logical Control
- URL: https://journals.rcsi.science/0005-1179/article/view/150265
- DOI: https://doi.org/10.1134/S0005117916030097
- ID: 150265
Cite item
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.
About the authors
D. S. Chivilikhin
ITMO University
Author for correspondence.
Email: chivdan@rain.ifmo.ru
Russian Federation, St. Petersburg
V. I. Ulyantsev
ITMO University
Email: chivdan@rain.ifmo.ru
Russian Federation, St. Petersburg
A. A. Shalyto
ITMO University
Email: chivdan@rain.ifmo.ru
Russian Federation, St. Petersburg
Supplementary files
