КОМПЛЕКСНЫЙ МНОГОЦЕЛЕВОЙ МОНИТОРИНГ ГРУППОЙ АВТОНОМНЫХ ТРАНСПОРТНЫХ СРЕДСТВ

  • М.Ю. Кензин ИДСТУ СО РАН
  • И.В. Бычков ИДСТУ СО РАН
  • Н. Н. Максимкин ИДСТУ СО РАН
Ключевые слова: Автономные транспортные средства, групповое управление, задача маршрутизации транспорта, мульти-атрибутная маршрутизация, эволюционные алгоритмы

Аннотация

Применение скоординированных групп автономных транспортных средств пред-ставляется наиболее перспективной и многообещающей технологией, позволяющей обес-печивать оперативное освещение труднодоступных регионов с высоким разрешением как по времени, так и в пространстве. При этом неизбежно возникают задачи коллективного распределения заданий и планирования индивидуальных маршрутов, когда каждому транс-портному средству в группе должен быть поставлен в соответствие ряд обследователь-ских работ в разных областях региона. Построение допустимого и эффективного группо-вого маршрута является задачей высокой вычислительной сложности даже в наиболее простых классических постановках с одним типом ограничений. В работе рассматривает-ся задача динамической маршрутизации группы автономных транспортных средств при выполнении комплексного мультиобъектного мониторинга. Задача группы в этом случае заключается в своевременном обследовании заданного множества объектов с установлен-ной периодичностью и в соответствии с требованиями, поставленными в соответствие каждому такому объекту. В качестве требований могут выступать в различном сочета-нии ограничения пространственного, временного или функционального характера. Такие задачи маршрутизации, объединяющие в себе целый спектр ограничений и требований различной природы, в современной литературе принято относить к классу комплексных или мульти-атрибутных задач маршрутизации. Подобные расширенные постановки, наце-ленные на более точное моделирование реальных задач, на данный момент являются недостаточно изученными и, в то же время, представляют большой научно-исследовательский интерес. Для эффективной генерации допустимых маршрутов предлагается использование децентрализованного гибридного эволюционного подхода с примене-нием специализированных эвристик, продвинутых схем локального поиска и дополнитель-ных процедур улучшения решений. Динамическая корректировка внутренних параметров алгоритма в реальном времени обеспечивает максимальную эффективность вычислитель-ной процедуры для каждого конкретного набора условий и на каждом этапе вычислений.Предложенная схема эволюционного алгоритма демонстрирует высокое качество результатов на большом наборе тестовых задач, в том числе на задачах с высокой степенью гетерогенности множества обследуемых объектов.

Литература

1. Kalyaev I.A., Kapustyan S.G., Usachev L.Zh. Metod resheniya zadachi raspredeleniya tselei v gruppe BLA setetsentricheskoy sistemoy upravleniya [The method of solving the problem of the distribution of goals in the group of UAVs by network-centric control system], Izvestiya IYFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering sciences], 2016, No. 12 (185), pp. 55-70.
2. Dunbabin M., Marques L. Robots for environmental monitoring: Significant advancements and applications, IEEE Robotics and Automation Magazine, 2012, Vol. 19, No. 1, pp. 24-39.
3. Cissé M., Yalçındağ S., Kergosien Y., etc. OR problems related to Home Health Care: A re-view of relevant routing and scheduling problems, Operations Research for Health Care, 2017, Vol. 13-14, pp. 1-22.
4. Hartl R.F., Hasle G., Janssens G.K. Special Issue on Rich Vehicle Routing Problems, Central European Journal of Operations Research, 2006, Vol. 14, No. 2, pp. 103-104.
5. Caceres Cruz J., Arias P., Guimarans D., Riera D., Juan A. Rich Vehicle Routing Problem: Survey, ACM Computing Surveys, 2014, Vol. 47, pp. 1-28.
6. Drucker N., Penn M., Strichman O. Cyclic Routing of Unmanned Air Vehicles, AUVSI (Asso-ciation for Unmanned Vehicle Systems International), 2010.
7. Drucker N. Cyclic Routing of Unmanned Aerial Vehicles, Ph.D. thesis, Israel Institute of Technology, 2014.
8. Drucker N., Ho H.-M., Ouaknine J., Penn M., Strichman O. Cyclic Routing of Unmanned Air Vehicles, Journal of Computer and System Sciences, 2019, Vol. 103, pp. 18-45.
9. Ho H.-M., Ouaknine J. The cyclic-routing UAV problem is PSPACE-complete, International Con-ference on Foundations of Software Science and Computation Structures, 2015, pp. 328-342.
10. Smith S.L., Rus D. Multi-robot monitoring in dynamic environments with guaranteed currency of observations, 49th IEEE Conference on Decision and Control, 2010, pp. 514-521.
11. Stump E., Michael N. Multi-robot persistent surveillance planning as a Vehicle Routing Prob-lem, 2011 IEEE International Conference on Automation Science and Engineering, 2011, pp. 569-575.
12. Fargeas J. L., Hyun B., Kabamba P., Girard A. Persistent visitation under fuel constraints, 15th meeting of the EURO Working Group on Transportation (EGWT 2012), 2012, pp. 1037-1046.
13. Kenzin M., Bychkov I., Maksimkin, N. Hybrid evolutionary approach to multi-objective mis-sion planning for group of underwater robots, Mathematical Modeling of Technological Pro-cesses, Communications in Computer and Information Science, 2015, Vol. 549, pp. 73-84.
14. Bychkov I.V., Kenzin M.Yu., Maksimkin N.N. Dvukhurovnevyy evolyutsionnyy podkhod k marshrutizatsii gruppy podvodnykh robotov v usloviyakh periodicheskoy rotatsii sostava [A two-level evolutionary approach to routing a group of underwater robots in the conditions of periodic rotation of the composition], Trudy SPIIRAN [SPIIRAS Proceedings], 2019, No. 2 (18), pp. 267-301.
15. Braysy O., Dullaert W., Gendreau M. Evolutionary Algorithms for the Vehicle Routing Prob-lem with Time Windows, Journal of Heuristics, 2004, Vol. 10, No. 6, pp. 587-611.
16. Laporte G., Ropke S., Vidal T. Chapter 4: Heuristics for the Vehicle Routing Problem, Vehicle Routing, 2014, pp. 87-116.
17. Koc C., Bektas T., Jabali O., Laporte G. Thirty years of heterogeneous vehicle routing, Euro-pean Journal of Operational Research, 2016, Vol. 249, No. 1, pp. 1-21.
18. Solomon M.M. Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research, 1987, Vol. 35, pp. 254-265.
19. Vidal T., Crainic T.G., Gendreau M., Prins C. A hybrid genetic algorithm with adaptive diver-sity management for a large class of vehicle routing problems with time-windows, Computers & Operations Research, 2013, Vol. 40, No. 1, pp. 475-489.
20. Yong M. Solving vehicle routing problem with time windows with hybrid evolutionary algo-rithm, In proceeding of Intelligent Systems (GCIS), 2010 Second WRI Global Congress on, 2010, Vol. 1, pp. 335-339.
21. Or I. Traveling Salesman-Type Combinatorial Problems and Their Relation to the Logistics of Regional Blood Banking – Northwestern University, Evanston, Illinois, 1976.
Опубликован
2020-05-02
Выпуск
Раздел
РАЗДЕЛ II. УПРАВЛЕНИЕ В РОБОТОТЕХНИЧЕСКИХ И МЕХАТРОННЫХ КОМПЛЕКСАХ