COMPUTER GRAPHICS

Evgeny I. Artamonov, Founder and first Head of Laboratory No. 18

The Laboratory as an independent subdivision was established on the initiative of Academician Vadim A. Trapeznikov, Director of the Institute, on October 1, 1978. It was based on a research group from Laboratory No. 29, headed at that time by Prof., Dr. Sci. (Eng.) Elena K. Krug. The Laboratory’s Head until his death (November 11, 2013) was the founder: Prof., Dr. Sci. (Eng.) Evgeny I. Artamonov.

The Laboratory’s theoretical and practical activities are associated with design methods for interactive systems (ISs) implemented in hardware or software tools. Such systems interact via input and output devices with an object or user in real time. Due to the peculiarities of external devices and systems, many formats of processed data, including graphics, are used in interactive systems, which significantly complicates the IS structure.

In the early 1970s, E.I. Artamonov developed a general structural design theory for ISs implemented in technical means. The main structural design idea was to create a network IS model based on the operation algorithm and possible relations of data formats with different implementations of separate IS blocks and select formally the best implementation (the shortest path on the network model).

Based on theoretical studies, promising structures were selected, several types of digital controllers were designed and put into operation, and several systems were created, such as control of high-precision gasoline mixing, calculation of parameters of moving objects, and dispatcher control for testing agricultural machinery, etc. More than a dozen of inventor certificates were obtained for their structures.

The gasoline mixing control system was adopted in the early 1970s in Grozny. It was the first digital interactive petroleum mixing system in the USSR with on-flow mixing in the pipeline. For the first time in the USSR, the technological gasoline mixing scheme was changed from sequential mixing of the components in the tanks to parallel on-flow mixing in the pipeline.

Since the mid-1970s, the Laboratory studied structural principles to develop software-implemented interactive systems, particularly computer-aided design (CAD) systems. At that time, conventional CAD systems in the world had the following structure: a central part in the form of an application program and subprograms of graphic packages connected to it (PLOT 10, Grafor, FAP-KF, and others). With this structure, the system had to be recompiled to perform a new task. The Laboratory proposed a new structural approach to develop CAD systems similar to the hardware implementation of special processors. Within this approach, the systems should have an invariant part (including the interaction means of the user with the system and external devices) and a problem-oriented part.

The Annual All-Union Workshop on Computer Graphics, managed by E.I. Artamonov, contributed much to understanding the structural principles of CAD systems (particularly the role of computer graphics) and discussing the data structures and their international standards. Two workshops were held in Izhevsk (1979 and 1982).

In 1981, the structural ideology was developed, and the GRAFIKA-81 interactive integrated software package was created. It includes subsystems for design and production documentation, 3D modeling, the automatic arrangement of elements and wiring on schematic diagrams and circuit boards, and control information for CNC machines. The package was distributed by the Research Institute CenterProgramSystem (Kalinin, now Tver) and implemented at several machine-building enterprises.

The development of CAD systems is quite complicated: it takes much time and requires many highly-qualified developers. The price of some CAD systems ranges from 20 to 50 thousand USD per workstation, whereas the cost of their promotion reaches millions of USD per quarter.

The complexity of developing such systems in Laboratory No. 18 was exacerbated by different hardware and operating systems on which GRAFIKA-81 was successively created (from ICL-4-70, ES-EVM, M-6000, and SM-1420 to personal computers).

In 1975–1985, the Laboratory was involved in organizing CAD systems works, first at the Ministry of Instrument Making and then among 12 ministries of civil machine-building sectors. In 1985–1990, the Laboratory leaded CAD system works within the Complex Program of Scientific and Technical Progress of CMEA Member States. The Program united 300 organizations from the USSR and 300 organizations from the CMEA member states and Yugoslavia.

By the end of the 1990s, the general structural design theory was elaborated for interactive systems implemented in hardware and software tools. To implement the network model for designing software ISs, Laboratory’s employees wrote programs for converting and visualizing widely used and standard data formats: DXF, WMF, Gerber, HPGL, PLT, PCB, STEP, VRML, and others.

The 3D model of Mir

GRAFIKA-81 was used to create 3D geometric models of all modules of the Mir orbital station, the kinematic models of its Ferma-3, and computer movies based on these models. The models were used in the pre-flight training of cosmonauts.

Later, 3D geometric modeling methods, interactive system structures, and software based on virtual reality were developed. For example, a training simulator for emergency escape from the Russian modules of the International Space Station was created in 1998. Also, note the following R&D works in 1999–2004: a training simulator for astronauts deploying a retransmitter on the Mir orbital station in a Russian-Georgian experiment; a 3D geometric model of the Proton engine for modeling engine failures; a visualization subsystem for upper stage tests and environmental monitoring of chemical weapons destruction.

The model of the Proton GS engine

Many employees of Laboratory No. 18 contributed to developing and creating interactive systems.

Dr. Sci. (Eng.), Senior Researcher A.I. Razumovsky develops interactive systems based on virtual reality and data structure transformation software. He created a visualization subsystem for upper stage tests and the environmental monitoring of chemical weapons destruction.

L.N. Sizova developed an interactive software package for designing electronic communication devices, creating schematics, drafting, and finding and displaying the shortest path between any objects.

Cand. Sci. (Eng.), Senior Researcher V.A. Romakin created a 3D geometric model of the large space reflector by the order of RSC Energia within the European Space Agency. Also, he designed an ergonomic analysis system for NPP safety panels and a system of terrain modeling based on virtual reality.

Alexey V. Tolok, Head of Laboratory No. 18

In 2013, Prof., Dr. Sci. (Eng.) Alexey V. Tolok became Head of Laboratory No. 18. He leads R&D works on voxel graphic modeling. Voxel geometric models are described by the apparatus of R-functions. The RANOK system was developed using the results obtained. This system constructs voxel graphic images for the 3D geometric model of the object. Such a model allows qualitative visualization and analysis of differential characteristics. It can be used in optimization related to the R-functional modeling of the surface with critical solution points. The RANOK system implements the gradient method based on graphic data of the voxel geometric model. This method is applied in many optimization problems of mathematical modeling: mathematical programming, determination of volumes and areas for bodies with a complex analytically defined surface, solution of combined equations, and many other problems based on optimization statements. The engineering problems of solid-state design are a promising line in voxel modeling. It seems interesting to pass from complex calculations of the physical state of bodies by the finite-element method to more accurate and visual solutions based on voxel graphical mappings.

Laboratory’s employees developed graphic editor software for the laser layer-by-layer analysis and design of metal powder products. The structures and software tools were created for several training simulators: assembling spacecraft in space and mastering interventional operations of cardiovascular diseases diagnosis and treatment.

Modeling of large space reflector opening

A software system was developed for the computer-aided design of automation means based on the high-temperature jetting technology. An automatic assembly system was created for machine-building structures; a software and hardware complex was developed for the automatic physical modeling of these structures from liquid polymers. Also, 3D model databases were built for space structures, elements of the jetting technology (jointly with Laboratory No. 2), and cardio vessels. Their data structures were optimized by the complexity of software implementation.

Note two R&D projects supported by the Russian Foundation for Basic Research (RFBR). The first project was to develop the theory of magnetic location and motion control for a magnetic endoscope capsule and create a prototype of a measuring and control complex with the capsule. Jointly with Laboratory No. 14 (now part of Laboratory No. 2), algorithms, mathematical support, and software were developed to process input data from the ADC and visualize the calculated data, including the spatial position of the capsule in the object. Also, the theoretical 3D vector model of the endoscope capsule trajectory was compared with the trajectory constructed by the sensor measurements. Within the second RFBR project, algorithms, mathematical support, and software were developed to control the advance of the AMR gradiometer head in the plotter, process the signals of AMR sensors (eliminate the current pulses and noise due to the small signal value and calculate the signal), evaluate their characteristics, and plot these signals (jointly with Laboratory No. 14).

In 2016, A.V. Tolok published his monograph on the method of functional voxel modeling (FVM). The monograph was edited by RAS Academician S.N. Vassilyev. This method underlies local computer geometry, a new line of modern computer geometry developed in the Laboratory. The corresponding course is included in the Master’s program in Engineering and Computer Graphics at the Moscow State University of Technology (STANKIN) and Nizhny Novgorod State University of Architecture and Civil Engineering.

In 2016, Laboratory’s employee Mikhail A. Loktev defended his candidate’s dissertation on functional voxel modeling in pathfinding with obstacles. He developed and investigated calculation means with R-functions and FVM with application to the automatic pathfinding with obstacles based on known analytical approaches. As shown, functional voxel models are efficient for solving optimization problems in the computer modeling of geometrical objects. Path construction based on the Voronoi diagram and unmanned vehicle motion modeling using the gradient descent method were considered. A fundamentally new approach to relief tracing was proposed based on the identification and application of characteristic surface relief forms. Relief tracing was organized on the principles of increasing the space of flat contours describing the obstacle dimensions. The proposed approach and algorithms are easily transferable to the corresponding problems in a multidimensional space.

Since 2017, Laboratory’s employees have been engaged in R&D works on a state order to create and develop an adaptation system for a graphical data package for RSC Energia. They are Senior Researcher, Cand. Sci. (Eng.) A.I. Razumovsky; Senior Researcher, Cand. Sci. (Eng.) V.A. Romakin; Senior Researcher, Cand. Sci. (Eng.) M.A. Loktev; Senior Engineer, postgraduate A.M. Plaksin; Leading Software Engineer L.N. Sizova; Leading Software Engineer K.A. Savel’ev; Software Engineer Yu.V. Gorskaya. The goal is to organize multisystem processing means for the electronic design documentation of spacecraft, adapting them with application to flight training automation.

CAD system interface

The Laboratory staff published over 450 papers and 5 monographs. Also, 7 patents and inventor certificates, including software implementation, were registered.

Quantum technologies are a new research area of Laboratory No. 18. Leading Researcher, Cand. Sci. (Eng.) P.A. Pravilshchikov develops a quantum parallelism mechanism for future quantum computers. Senior Researcher, Cand. Sci. (Eng.) S.V. Smirnov organized the annual international conference “Computer-Aided Design, Manufacturing, and Product Data Management Systems (CAD/CAM/PDM)” in 2000–2018.

The Laboratory has a youth scientific school headed by Prof. A.V. Tolok.

In 2021, Laboratory No. 18 merged Laboratory No. 3 (Logic Control Systems). Laboratory No. 3 was founded by the famous MAG, future Corresponding Member of the USSR Academy of Sciences, Dr. Sci. (Eng.), Prof. Mikhail A. Gavrilov. He was invited to the Commission for Automation, Remote Control and Dispatching established in 1934. The Laboratory for Relay Remote Control (future Laboratory No. 3) was part of the Commission, reorganized into the Institute of Automation and Remote Control in 1939. And M.A. Gavrilov became Head of the Laboratory within the Institute.

Mikhail A. Gavrilov, Head of Laboratory No. 3

In 1938–1946, M.A. Gavrilov developed the theory of relay-contact circuits (RCS). He was the first in the world to propose a rigorous mathematical approach to the main problems of RCS design: formalization of operating conditions and structural analysis and design. For details, see his book Teoriya releino-kontaktnykh skhem (The Theory of Relay-Contact Circuits), published in 1950. In 1958, the USSR Academy of Sciences awarded M.A. Gavrilov the Yablochkov Prize for this theory. In 1963, he was elected a Corresponding Member of the USSR Academy of Sciences.

M.A. Gavrilov created an All-Union scientific school covering all Soviet republics and large cities and promoted world-level achievements in the following areas: analysis and design methods for finite-state machines; collective behavior models for machines; reliable design methods; the theory of self-control schemes; the theory of homogeneous environments; design methods for distributed logical control systems; the theory of logical control languages. Since the early 1960s, more than thirty schools on logic control were held. (Later on, they were named after M.A. Gavrilov.)

About 90 Candidates and Doctors of Sciences defended their dissertations under M.A. Gavrilov’s supervision.

At different times, famous researchers I.V. Prangishvili, P.P. Parkhomenko, A.A. Ambartsumyan, and O.P. Kuznetsov worked in the Laboratory.

After M.A. Gavrilov’s death (1979), his student, Prof., Dr. Sci. (Eng.) Alexander A. Ambartsumyan became Head of the Laboratory.

Alexander A. Ambartsumyan, Head of Laboratory No. 3 for over 30 years

Main R&D areas of Laboratory No. 3 (1980–1990)

Models and methods of logical control:

– The structural theory of finite-state machines and logical algorithms with the estimated complexity of structuring (A.A. Ambartsumyan).

– Design methods for fault-tolerant asynchronous logic devices (A.I. Potekhin) and based on them 3 large-scale integrated circuits (LSI) on basic-modular crystals (development and manufacturing at enterprises of the USSR Ministry of Radio Industry in Zelenograd).

– A set of fault-tolerant programmable automation means with parallel structure (PAM-PS) for the lower level of automated process control systems (APCSs). The main technical ideas were distribution, specialization, fault tolerance, and stability. Since 1997, PAM-PS have been used in safety-critical control systems (nuclear and thermal power engineering, gas and oil production, and the processing industry).

– The concept of next-generation APCSs for nuclear power plants (NPPs) based on programmable logic controllers.

– New principles and methods to develop APCSs with increased protection against human errors.

These R&D works of Laboratory’s leading employees (A.A. Ambartsumyan, A.I. Potekhin, B.A. Lagovier, and others) were the scientific basis for designing next-generation APCSs for NPPs with a high degree of automation, reliability, and industrial control quality.

Main R&D areas of Laboratory No. 3 (1990–2000)

The following APCSs were developed and implemented:

– An elevator control system in Buturlinovka (the Voronezh Region).

– A quality monitoring system for the heat carrier in a central heat supply station (temperature, pressure, flow rate, and other parameters). A pilot project of this system was implemented at two central heat supply stations in the North-Eastern Administrative District of Moscow.

– The technical projects of APCSs (TP-90, TP-NP, and Bushehr). (The latter project was implemented jointly with Rosatom.)

– The conceptual design of APCSs for oil production enterprises (LUKOIL and TNK).

A booster pump station in TNK

Main R&D areas of Laboratory No. 3 (2000–2008)

Theoretical foundations of the discrete-event modeling of automation objects and APCS design methods:

– A new concept and methods to control information and material flows based on the discrete-event models of automation objects: transition from traditional rigid control algorithms (current practice) to control by industrial process models.

– The discrete-event models of control objects and industrial processes (on an example of the oil industry):

• the models of components and units (gate valves, pumps, tanks, etc.);
• the models of processes, i.e., technologically demanded configurations (fragments of the technological network, installations, redevelopments, etc.);
• the models of regulations (active technological scenarios);
• the models of dialogue with the personnel to increase control efficiency and process safety by limiting human activities in the control loop.

Two candidate’s dissertations on the discrete-event modeling of industrial processes were defended in the Laboratory: D.L. Kazansky (2004) and S.A. Branishtov (2008).

The discrete-event modeling of railway systems

Based on rich experience, the Laboratory continues research on fundamental methods for increasing the automation level of industries.

The results found application in an intelligent support system for the railway dispatcher.

Laboratory’s employees develop discrete-event modeling methods for railway objects, supervisor design methods, and group control methods in the transport system to improve safety and throughput. The automation of train preparation and route selection at the station with a branchy track layout was investigated. An analysis method for railway network topologies and a control algorithmization approach for train operation and shunting were proposed. A generalized model was developed to control a group of autonomous components in the discrete-event (DE) system of a railway section. The model includes DE models of the basic control objects on a railway network (stations, runs, switches, locomotives, cars, and marshaling yards and hills). The component models are hierarchical automata and color Petri nets. The structure and interaction rules of the models were determined. Also, a motion control procedure for the vehicles was constructed.

The train control technology on a railway station and dispatcher control automation systems were analyzed. An element database was created for the track layout development of a railway station; daily scheduling algorithms were developed for traffic routing. According to experimental evidence, the algorithm finds a solution in an acceptable time and yields a traffic schedule under different conditions. The algorithm recalculates the traffic schedule in an abnormal situation or emergency and performs operational traffic control.

Based on these approaches, a software prototype was developed for the duty yardmaster workstation. It includes the following functions:

– A track layout development interface. This interface is used to create the track layout of a station from the library of interactive elements: track sections, parking tracks (receipt-departure, park tracks, and deadlocks), shunting and route traffic lights, switches, and others.

– Daily scheduling based on the track layout and train timetables. Traffic routes are automatically built using train timetables and intermediate points under the requirements of safety (the non-crossing of routes, intervals, and speed) and accurate schedule execution.

– The dynamic change of the daily schedule of a station. This function is performed by the duty yardmaster at any time in the case of schedule violation, a complex situation, or an emergency. The scheduling algorithm allows analyzing the efficiency of the schedule and station infrastructure.

The software tools of the duty yardmaster workstation are versatile and can be used for various stations.

The models of mobile robot behavior among humans

New scientific challenges are formulated due to robotics development.

This research area considers motion organization problems for many autonomous mobile robots in an uncertain environment. In other words, the control system has insufficient information about the environment’s properties to calculate the control action for reaching the goal. However, it may know the properties in some local vicinity. Such an environment describes unexplored or variable spaces. For example, this problem arises for a group of autonomous ground robots moving in rooms with people or in an urban environment with many flying robots.

Recently, large groups of robots have been paid much attention. Swarms are systems of many robots (agents) with common behavior rules and a common task. Usually, a swarm of robots operates in a distributed control mode and uses small communication resources. Currently, new control and coordination algorithms are actively developed for such groups. One of the most difficult problems in swarm control is the movement of many robots toward the same goal: the resulting conflicts need time to resolve. This problem arises when the goals of the robots coincide, or when they have intersecting routes.

Most of the results in motion control and collision avoidance have been obtained for structured environments (a known space map): robots navigate along separate routes and their intersections. Conflicts occurring at intersections are resolved through prioritization or action coordination. Such collision avoidance algorithms are developed and tested only for small groups of robots. These algorithms are ineffective for many robots: the mutual communication of all robots is difficult to perform simultaneously under distributed control. In this case, the local collision problem can be solved, but the global one remains open.

In this research area, the Laboratory investigates behavior rules for mobile robots among people when moving in rooms and crowds. Several methods are developed: representing and processing the robot’s knowledge about the surrounding space; searching and estimating movement trajectories; assessing conflict points in the space. Also, basic rules of robot behavior in a crowd are created.

Another significant problem is the coordination of separate autonomous robots. The information exchange area is studied for each robot; depending on its size, the efficiency of information traffic management is evaluated. Requirements are formulated for the content of information exchange. The data network load is evaluated.

The Laboratory’s research interests include routing methods with a known obstacle map, collision avoidance algorithms, path tracking methods, machine vision-based recognition methods for dynamic obstacles, and others.

Since 2007, the youth scientific school has been working in Laboratory No. 3 under the Institute’s grant. There are 3 Candidates in Engineering and 2 postgraduates in the Laboratory. Since its establishment, more than 500 papers have been published by the Laboratory staff. The Laboratory regularly participates in Russian and international conferences, including IFAC symposia and congresses. In 2003, the Laboratory organized an international conference devoted to the 100th anniversary of M.A. Gavrilov. In 2008–2012, three All-Russian and international conferences “Hardware and Software Means for Management, Control and Measurement Systems” were held jointly with other Laboratories of the Institute.