Гибридный алгоритм ситуационного планирования траектории на плоскости в условиях частичной неопределенности

Описан гибридный алгоритм ситуационного планирования траектории в условиях частичной неопределенности для двумерного пространства, основанный на интеграции волнового и муравьиного алгоритмов, позволяющий строить в реальном масштабе времени траектории минимальной длины с одновременной оптимизацией других критериев качества построенного пути. Процесс прокладки траектории осуществлен пошагово. Выявление ограничений на карте местности, препятствующих прокладке траектории из текущей позиции, осуществлено после достижения траекторией этой позиции. Последовательно на каждом шаге относительно текущей позиции подвижного объекта сформирована зона, в пределах которой с помощью радара выполнена локализация всех препятствий, затем построен участок траектории, являющийся продолжением ранее полученного участка. Вся траектория представляет собой совокупность указанных участков, связывающих исходную позицию подвижного объекта с целевой позицией.Временная сложность этого алгоритма зависит от времени жизни колонии l (число итераций), числа вершин графа n и числа муравьев m и определяется как O (ln²m)

Литература

[1] Пшихопов В.Х., ред. Интеллектуальное планирование траекторий подвижных объектов в средах с препятствиями. М.: Физматлит, 2014. 295 с.

[2] Пшихопов В.Х., Медведев М.Ю. Управление подвижными объектами в определенных и неопределенных средах. М.: Наука, 2011. 215 с.

[3] Гузик В.Ф., Переверзев В.А., Пьявченко А.О., Сапрыкин Р.В. Принципы построения экстраполирующего многомерного нейросетевого планировщика интеллектуальной системы позиционно-траекторного управления подвижными объектами // Известия ЮФУ. Технические науки. 2016. № 2 (175). С. 67–80.

[4] Горбатов В.А. Основы дискретной математики. М.: УРСС, 1994. 340 с.

[5] Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов: пер. с англ. М.: Мир, 1979. 536 с.

[6] Пшихопов В.Х., Медведев М.Ю., Гуренко Б.В. Алгоритмы адаптивных позиционно-траекторных систем управления подвижными объектами // Проблемы управления. 2015. № 4. С. 66–74.

[7] МакКоннелл Дж. Основы современных алгоритмов. М.: Техносфера, 2004. 368 с.

[8] Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. 446 с.

[9] Caro G.Di, Ducatelle F., Gambardella L.M. AntHocNet: An adaptive nature inspired algorithm for routing in mobile ad hoc networks // Transactions on Emerging Telecommunications Technologies. 2005. Vol. 16. Iss. 5. Р. 443–455. DOI: 10.1002/ett.1062

[10] Hoefler T., Snir M. Generic topology mapping strategies for large-scale parallel architectures // ICS11. Proc. of the Int. Conf. on Supercomputing, ACM, 2011. Р. 75–85.

[11] Нейдорф Р.А., Полях В.В., Черногоров И.В., Ярахмедов О.Т. Исследование эвристических алгоритмов в задачах прокладки и оптимизация маршрутов в среде с препятствиями // Известия ЮФУ. Технические науки. 2016. № 3 (176). С. 127–143.

[12] Fatemeh K.P., Fardad F., Reza S.N. Comparing the performance of genetic algorithm and ant colony optimization algorithm for mobile robot path planning in the dynamic environments with different complexities // Journal of Academic and Applied Studies. 2013. Vol. 3. No. 2. Р. 29–44.

[13] Dutta S. Obstacle avoidance of mobile robot using PSO-based neuro fuzzy technique // International Journal on Computer Science and Engineering. 2010. Vol. 2. No. 2. P. 301–304.

[14] Chen S., Eshaghian M.M. A fast recursive mapping algorithm. Department of computer and information science. New Jersey Institute of Technology, 2013. P. 219–227.

[15] Raidl G.R. A unified view on hybrid metaheuristics // International Workshop on Hybrid Metaheuristics. Springer, 2006. P. 1–12.

[16] Dorigo M., Caro G.Di, Gambardella L.M. Ant algorithms for discrete optimization // Artificial Life. 1999. Vol. 5. No. 2. P. 137–172.

[17] Лебедев О.Б. Модели адаптивного поведения муравьиной колонии в задачах проектирования. Таганрог: Изд-во ЮФУ, 2013. 199 с.

[18] Лебедев Б.К., Лебедев О.Б. Моделирование адаптивного поведения муравьиной колонии при поиске решений, интерпретируемых деревьями // Известия ЮФУ. Технические науки. 2012. № 7. С. 27–34.