Method for correcting the work plan of the ground automated spacecraft control complex based on the search for the maximum clique in sparse network graph of operations

DOI: 10.34759/trd-2021-118-17

Аuthors

Kolpin M. A., Protsenko P. A.^*

Mlitary spaсe Aсademy named after A.F. Mozhaisky, Saint Petersburg, Russia

*e-mail: prosvka@gmail.com

Abstract

The necessity of automating the process of correcting the work plan of the ground automated spacecraft control complex in the interests of increasing the operativeness of countering emergency is reasoned. Method for correcting the work plan of spacecraft control agency is proposed. The plan in question can be represented as sparse network graph of operations. This circumstance makes it possible to reduce the problem of plan correction to the search for maximum cliques in independent subgraphs of the original graph using the known optimal and suboptimal algorithms of graph theory. This approach is implemented in two stages. At the first stage, the complement of the initial operations graph is constructed and a set of disconnected subgraphs is searched in it using known algorithms for finding the components of the graph’s connectivity (in depth or width). The advantage of these algorithms is the linear convergence time relative to the number of vertices and edges in the graph.

At the second stage, the search for maximum cliques of the found subgraphs is carried out. If the subgraph has less than 70 vertices, then the Bron-Kerbosch algorithm is used; otherwise, suboptimal procedures that allow finding acceptable solutions in polynomial time are used.

The modeling of the process of correcting the work plan of the control agency using the developed method and heuristic procedures FIFO and LIFO has been carried out. It is concluded that the use of the developed method provides an increase in the correction completeness index due to optimization procedures when solving the problem of redistributing of the resources of the ground automated spacecraft control complex.

The method developed can be used for:

— creation of software tool for automated correction of the work plan of spacecraft control agency;

— conducting scientific research to assess the stability and operativeness of spacecraft control.

Keywords:

Ground Automated Control Complex, spacecraft, control operation, planning, correction, maximum click, technology management cycle

References

1. Manuilov Yu.S., Kalinin V.N., Goncharevskii V.S., Delii I.I. Upravlenie kosmicheskimi apparatami i sredstvami nazemnogo kompleksa upravleniya (Control spacecraft and ground control complex), Saint Petersburg, VKA imeni A.F. Mozhaiskogo, 2010, 609 p.

2. Maksimov A.M., Raikunov G.G., Shuchev V.G. Kosmonavtika i raketostroenie, 2011, no. 4 (65), pp. 5 — 12.

3. Zolotarev A.N., Sokhrannyi E.P. Kosmonavtika i raketostroenie, 2011, no. 1 (62), pp. 162 — 171.

4. Manuilov Yu.S., Novikov E.A. Ekonomicheskaya kibernetika: sistemnyi analiz v ekonomike i upravlenii, 2005, vol. 12, pp. 56 — 61.

5. Dudko A.N., Kucherov B.A., Litvinenko A.O., Sokhrannyi E.P. Kosmonavtika i raketostroenie, 2014, no 1 (74), pp. 155 — 163.

6. Litvinenko A.O. Trudy MAI, 2016, no. 86. URL: http://trudymai.ru/eng/published.php?ID=67829

7. Sokhrannyi E.P. Trudy MAI, 2019, no. 108. URL: http://trudymai.ru/eng/published.php?ID=109504. DOI: 10.34759/trd-2019-108-11

8. Dudko A.N., Kucherov B.A., Litvinenko A.O., Sokhrannyi E.P. Kosmonavtika i raketostroenie, 2016, no. 1 (86), pp. 103 — 109.

9. Voronovskii V.V., Dudko A.N., Matyushin M.M., Sokhrannyi E.P., Usikov S.B., Sokhrannaya A.E. Kosmonavtika i raketostroenie, 2018, no. 1 (100), pp. 89 — 99.

10. Matyushin M.M., Lutsenko Yu.S., Gershman K.E. Trudy MAI, 2016, no. 89. URL: http://trudymai.ru/eng/published.php?ID=72869

11. Kondrashin M.A., Arsenov O.Yu., Kozlov I.V. Trudy MAI, 2016, no. 89. URL: http://trudymai.ru/eng/published.php?ID=73411

12. Emelichev V.A., Mel’nikov O.I., Sarvanov V.I., Tyshkevich R.I. Lektsii po teorii grafov (Lectures on graph theory), Moscow, Nauka, 1990, 392 p.

13. Kolpin M.A., Protsenko P.A., Frolov O.P. Izvestiya rossiiskoi akademii raketnykh i artilleriiskikh nauk, 2020, no. 4, pp. 69 — 75.

14. Kolpin M.A., Protsenko P.A., Slashchev A.V. Trudy MAI, 2017, no. 92. URL: http://trudymai.ru/eng/published.php?ID=77144

15. Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi The worst-case time complexity for generating all maximal cliques and computational experiments, Theoretical Computer Science, 2006, vol. 363, issue 1. pp. 28 — 42. DOI: 10.1016/j.tcs.2006.06.015

16. Kormen T., Leizerson Ch., Rivest R. Algoritmy: postroenie i analiz (Algorithms: Construction and Analysis), Moscow, Vil’yams, 2005, pp. 622 — 632.

17. Gribkov M.A., Alekseevskii A.V., Spirin S.A., Korotkova M.A. Trudy Instituta sistemnogo analiza Rossiiskoi akademii nauk, 2006, vol. 25, pp. 185 — 192.

18. Alvarez A., Erwin R. An Introduction to Optimal Satellite Range Scheduling, Springer, 2015, 162 p.

19. Zufferey N., Amstutz P., Giaccari P. Graph colouring approaches for a satellite range scheduling problem, Journal of Sheduling, 2008, no. 11 (4), pp. 263 — 277. DOI:10.1007/s10951-008-0066-8

20. Preindl B., Seidl M., Mehnen L., Krinninger S., Stuglik S., Machnicki D. A performance comparison of different satellite range scheduling algorithms for global ground station networks, In 61st International Astronautical Congress, Prague, Czech Republic, 2010, pp. 253 — 257.

    
    Download