Mathematical method of objective function calculation and routing problems solving

Dynamics, ballistics, movement control of flying vehicles


Аuthors

Alliluyeva N. V.1*, Rudenko E. M.2**

1. Joint-stock company “Scientific and production enterprise “Radar-mms”, 37, Novosel'kovskaya str., lit. A, Sankt-Peterburg, 197375, Russia
2. Peter the Great Strategic Missile Troops Academy, 17, Brigadnaya str., Serpukhov, Moscow region, 142210, Russia

*e-mail: allilueva_nv@radar-mms.com
**e-mail: eduard5529@yandex.ru

Abstract

A lot of tasks of unmanned aviation on observation of the objects, in the most general set up is reduced to route selection between the two benchmarks, which lead to mathematical problem of optimization on the graph. It is assumed herewith that the route is closed and passes through all ribs of the graph. The optimization task on the graph meant for calculating the set of closed routes of minimal length relates to the integer programming problem [1].

The goal of the work consists in solving the optimization problem on the graph leading to obtaining optimal closed routes (OCR). The authors suggest genetic algorithm (GA) as an optimization method. For its implementation the objective function of sevral variables was developed, which simplified significantly the program code and reduced the computation time. The objective function represents the sum of three functions. The first function depends on the edges of the graph, and penalizes edges and loops which do not belong to the graph. The second function depends on the Euler model of the original graph, i. e. the method of the graph reduction to the Euler type by adding multiple edges. The third addend depends on the vertices of the graph and accounts for their multiplicity. The minimum of the objective function is achieved on OCR only.

The GA application allows obtain limited quantity of OCRs from a large variety of variants during finite time, which can be reproduced several times by using the group of the graph’s automorphisms. The presence of the OCRs variety allows planning the order of graphs fly-offs afield while solo and group flights, promptly regroup monitoring routes in consecutive and dispersed flight over various ribs and without intersection at vertices.

Keywords:

graph, reference point, optimal closed routes, automorphism, objective function, genetic algorithm

References

  1. Kristofides N. Teoriya grafov (Graph theory), Moscow, Mir, 1978, 427 p.

  2. Nechepurenko M.I., Popkov V.K., Mainagashev S.M. Algoritmy i programmy resheniya zadach na grafakh i setyakh (Algorithms and programs for solving problems on graphs and networks), Novosibirsk, Nauka, 1990, 515 p.

  3. D’yakonov V.P., Kruglov V.V. Instrumenty bioinformatiki i iskusstvennogo intellekta. MATLAB 6.5 SP1/7/7 SP1/7 SP2+Simulink 5/6 (The tools of bioinformatics and artificial intelligence. MATLAB 6.5 SP1/7/7 SP1/7 SP2+Simulink 5/6), Moscow, Solon-Press, 2005, 454 p.

  4. Gladkov L.A., Kureichik V.V., Kureichik V.M. Geneticheskie algoritmy (Genetic algorithms: a tutorial), Moscow, Fizmatlit, 2006, 320 p.

  5. Allilueva N.V., Rudenko E.M. Izvestiya instituta inzhenernoi fiziki, 2017, no. 2 (44), pp. 63-69.

  6. Lebedev G.N., Efimov A.V., Mikhailin D.A. Vestnik Moskovskogo aviatsionnogo instituta, 2012, vol. 19, no.1, pp. 12-16.

  7. Lebedev G.N., Goncharenko V.I., Rumakina A.V. Mekhatronika, avtomatizatsiya, upravlenie, 2016, vol. 17, no. 11, pp. 783–791.

  8. Lebedev G.N., Mikhailin D.A., Rumakina A.V. Trudy MAI, 2016, no. 91, available at: http://trudymai.ru/eng/published.php?ID=75637

  9. Antonov D.A., Zharkov M.V., Kuznetsov I.M., Lunev E.M., Pron’kin A.N. Trudy MAI, 2016, no. 91, available at: http://trudymai.ru/eng/published.php?ID=75632

  10. Guseinov A.B., Makhovykh A.V. Trudy MAI, 2016, no. 90, available at: http://trudymai.ru/published.php?ID=74833

  11. Zenkevich S.L., Khua Chzhu. Mekhatronika, avtomatizatsiya, upravlenie, 2017, vol. 8, no. 1, pp. 30-34.

  12. Gogolev A.A. Trudy MAI, 2017, no. 92, available at: http://trudymai.ru/published.php?ID=77238

  13. Novak K.V., Oleshko V.S., Starikova I.O., Toforov M.S. Trudy MAI, 2017, no. 94, available at: http://trudymai.ru/published.php?ID=80936

  14. Rohde S. Link quality dependent mobility strategies for distributed aerial sensor networks. GLOBECOM Workshops (GC Wkshps), Dortmund, Germany, 2010 IEEE, pp. 1783–1787.

  15. Sahingoz O.K. Networking Models in Flying Ad-Hoc Networks (FANETs): Concepts and Challenges. Journal of Intelligent & Robotic Systems, 2014, vol. 74, no. 1–2, pp. 513–527.

  16. Zenkevich S.L., Bolotin E.I. Mekhatronika, avtomatizatsiya, upravlenie, 2014, no. 11, pp. 21-27.

  17. Zenkevich S.L., Galustyan N.K. Mekhatronika, avtomatizatsiya, upravlenie, 2016, vol. 17, no. 11, pp. 774–782.

  18. Kothari M., Postlethwaite I., Gu D., Multi-UAV path planning in obstacle rich environments using rapidly-exploring random trees. Proc. Of the combined 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference, December 16-18, 2009, Shanghai, P.R. China, pp. 3069–3074.

  19. He P., Dai S. Stealth Real-time Paths Planning for Heterogeneous UAV Formation Based on Parallel Niche Genetic Algorithm. Journal of Computational Information Systems, 2014, pp. 6731–6740.

  20. Hassanzadeh R., Mahdavi I., Mahdavi-Amiri N., Tajdin A. A genetic algorithm for solving fuzzy shortest path problems with mixed fuzzy arc lengths. Mathematical and Computer Modelling, 2013, no. 7 (1), pp. 84–99.

  21. Sharma Y., Saini S.C., Bhandhari M. Comparison of Dijkstra’s Shortest Path Algorithm with Genetic Algorithm for Static and Dynamic Routing Network. International Journal of Electronics and Computer Science Engineering, ISSN-2277-1956/V1N2, 2012, pp. 416-425.

  22. Zhu X., Luo W., Zhu T. An Improved Genetic Algorithm for Dynamic Shortest Path Problems. IEEE Congress on Evolutionary Computation (CEC), Beijing, China, 2014, pp 2093-2100.

  23. Wagner M., Neumann F. Single- and Multi-Objective Genetic Programming: New Runtime Results for SORTING. IEEE Congress on Evolutionary Computation (CEC), Beijing. China, 2014, pp. 125-133.

  24. Kim J.W., Kim S.K. Fitness switching genetic algorithm for solving combinatorial optimization problems with rare feasible solutions The Journal of Supercomputing. September 2016, vol. 72, issue 9, pp. 3549–3571.

  25. Iglin S.P. Matematicheskie raschety na baze MATLAB (Mathematical calculations based on MATLAB), SPb, BHV-Peterburg, 2005, 640 p.

  26. Ligo T., Fomichev A.V. Vestnik MGTU imeni N.E. Baumana, 2016, no. 2, pp. 53-66.

  27. Moiseev D.V., Chin’ Van Min’ Internet-zhurnal Naukovedenie, 2017, vol. 9, no. 3, available at: http://naukovedenie.ru/PDF/102TVN317.pdf

  28. Zadeh S.M., Powers D., Sammut K. Optimal Route Planning with Prioritized Task Scheduling for AUV Missions Article, University, Adelaide, SA 5042, Australia, 2016. pp. 1–8, available at: https://www.researchgate.net/publication/301816813.pdf


Download

mai.ru — informational site MAI

Copyright © 2000-2024 by MAI

 Вход