CONTROL OF COMPUTING AND DIAGNOSTICS OF SOFTWARE FOR ON-BOARD COMPUTERS OF ROBOTIC COMPLEXES
Abstract
The aim of the study is to improve the efficiency of high-level design of robotic systems in terms
of management of computing and diagnostics of on-board computer software. Three problems are
considered: assignment, scheduling and diagnostics. The first problem, the assignment task, is to
determine the necessary resources and build the distribution of program modules among the onboard
computer processors in accordance with a given criterion. The article presents a mathematical
formulation of the problem, algorithms are given, and the presence of areas of effective dominance of
algorithms depending on the selected criterion is shown. The second problem, the scheduling problem,
is to determine the sequence of tasks in multi-channel systems in accordance with a given criterion.
A mathematical formulation of the problem is given, algorithms and the results of their study
are given. A feature of the scheduling algorithms under consideration is the use of a unified approach,
namely the concept of the dominance relation between processors and the construction of
solvable classes of systems. The third problem is software diagnostics. The complexity of the task of
diagnosing computer systems is determined not only by their high dimensionality, but also by the
multiplicity of causes of violations. The source of violations of the computing process can be both
hardware failures and errors in the organization of calculations made by developers. The article uses
a hierarchical approach, in this case, the components of the system, connected by an inclusion relation,
are arranged in accordance with the level of complexity in such a way that the model of higherlevel
components is represented by a composition of lower-level models. For each level, own diagnostic
tools are synthesized, focused on failures of information links between the components of the
previous level. The article proposes an approach to test diagnostics using a network dynamic model,
which involves the introduction of redundancy in order to simplify the diagnostic experiment and
reduce the complexity of its preparation. This approach allows you to automatically synthesize diagnostic
tools and detect violations in the addressing of information exchanges when the software of
robotic systems works as intended. Approbation of the algorithms under consideration was carried
out using software developed by the author at the stage of designing on-board systems at JSC «Concern
«Central Research Institute «Elektropribor».
References
vstraivaemykh vychislitel'nykh sistem [Theoretical and methodological bases of high-level design
of embedded computing systems]. St. Petersburg: Universitet ITMO, 2010, 477 p.
2. Harris D., Harris S. Digital Design and Computer Architecture. 2nd ed. Morgan Kaufman,
2012.
3. Liu J.W.S. Real-Time Systems. Prentice Hall. NJ, 2000, 590 p.
4. Toporkov V.V. Modeli raspredelennykh vychisleniy [Distributed computing models]. Moscow:
Fizmatlit, 2004, 316 p.
5. Edward A. Lee and Sanjit A. Seshia. Introduction to Embedded Systems, A Cyber-Physical
Systems Approach. Second ed. MIT Press, 2017.
6. Kellerer H., Pferschy U., Pisinger U. Knapsack Problems. Springer, Berlin, Germany, 2004, 546 p.
7. Burkard R.E., Dell'Amico M. and Mortello S. Assignment problems. SIAM, Philadelphia, 2009.
8. Gonzalez T.F. Handbook of Approximation Algorithms and Metaheuristics. Second ed. Vol. 2:
Contemporary and Emerging Applications. Ed. Chapman, 2018. Available at: https://doi.org/
10.1201/9781351235426.
9. Jansen K. Parameterized Approximation Scheme for the Multiple Knapsack Problem, SIAM
Journal on Computing, 2010, Vol. 39, No. 4, pp. 1392-1412. Available at: https://doi.org/
10.1137/080731207.
10. Cacchiani V., Iori M., Locatelli A. et. al. Knapsack problems - An overview of recent advances. Part
II: Multiple, multidimensional, and quadratic knapsack problems, Computers & Operations Research,
2022, Vol. 143, pp. 105693. Available at: https://doi.org/10.1016/j.cor.2021.105693.
11. Gruzlikov A.M., Kolesov N.V., Skorodumov Yu.M., Tolmacheva M.V. Grafovyy podkhod k
naznacheniyu zadaniy v raspredelennykh sistemakh real'nogo vremeni [Graph approach to assignment
of tasks in distributed real-time systems], Izvestiya RAN. Teoriya i sistemy
upravleniya [Izvestiya of the RAS. Theory and control systems], 2014, No. 5, pp. 84-94.
12. Cottet F., Kaiser J., Mammeri Z. Scheduling in Real-Time Systems. John Wiley & Sons Ltd,
2002.
13. Brucker P., Knust S. Complex scheduling. Springer-Verlag, Berlin, Heidelberg, 2006.
14. Lazarev A.A. Teoriya raspisaniy. Metody i algoritmy [Schedule theory. Methods and algorithms].
Moscow: IPU RAN, 2019, 408 p.
15. Pinedo M.L. Scheduling. Theory: Algorithms and systems. Springer. Science, 2016, 670 p.
16. Gruzlikov A.M., Kolesov N.V., Skorodumov Yu.M., Tolmacheva M.V. Planirovanie zadaniy v
raspredelennykh sistemakh real'nogo vremeni [Task scheduling in distributed real-time systems],
Izvestiya RAN. Teoriya i sistemy upravleniya [Izvestiya of the RAS. Theory and control
systems], 2017, No. 2, pp. 67-76.
17. Gruzlikov A.M., Kolesov N.V. Ispol'zovanie razreshimykh klassov sistem real'nogo vremeni
dlya planirovaniya s minimizatsiey dzhittera [Using solvable classes of real-time systems for
planning with jitter minimization], Izvestiya RAN. Teoriya i sistemy upravleniya [Izvestiya of
the RAS. Theory and control systems], 2021, No. 6, pp. 43-51.
18. Taillard E. Benchmarks for Basic Scheduling Problems, Europ. J. Operational Research,
1993, Vol. 64, No. 2, pp. 278-285.
19. Zhang X., Guo P., Zhang H., Yao, J. Hybrid Particle Swarm Optimization Algorithm for Process
Planning, Mathematics, 2020, Vol. 8, pp. 1745. Available at: https://doi.org/10.3390/math8101745.
20. Isermann R. Fault Diagnosis Application. Heidelberg: Springer, 2011, 354 p.
21. Zaytoon J., Lafortune S. Overview of Fault Diagnosis Methods for Discrete Event Systems,
Annual Reviews in Control, 2013, Vol. 37, pp. 308-320.
22. Gruzlikov A.M., Kolesov N.V., Lukoyanov E.V. Testovoe diagnostirovanie narusheniy
adresatsii informatsionnykh obmenov v vychislitel'nykh sistemakh s ispol'zovaniem
parallel'noy modeli [Test diagnostics of addressing violations of information exchanges in
computing systems using a parallel model], Izvestiya RAN. Teoriya i sistemy upravleniya
[Izvestiya of the RAS. Theory and control systems], 2018, No. 3, pp. 76-89.
23. Gruzlikov A., Kolesov N., Lukoyanov E., and Tolmacheva M. Test-based diagnosis of distributed
computer system using a time-varying model, 10th IFAC Symposium on Fault Detection,
Supervision and Safety for Technical Processes, SAFEPROCESS – 2018.
24. Gruzlikov A.M., Kolesov N.V. Hierarchical model for testing a distributed computer system,
J. Korbicz et al. (eds.), Advances in Diagnostics of Processes and Systems, Studies in Systems,
Decision and Control 313, 14th International Conference on Diagnostics of Processes and
Systems (DPS), 2021.
