Программные продукты и системы

Введение. Разработка интеллектуальных ме- тодов планирования траектории транспортной платформы для наземной, водной и воздушной среды позволит обеспечить безопасное движение, уменьшая риск столкновения транспорта  и сокращая время перемещения. Поиск оптимального маршрута перемещения транспортного средства (объекта интереса) является одной из важных задач в различных областях применения.

Традиционно определение маршрутов перемещения объектов интереса осуществляется лицом, принимающим решение, с учетом ограниченных вычислительных ресурсов, несо- вершенства математического и программного обеспечения в АСУ и значительных временных затрат на поиск решения задачи.

Методы планирования маршрута можно классифицировать по признаку используемого аппарата формализации на традиционные и эвристические, вытекающие, как правило, из содержательного смысла решаемой задачи [1]. Результатом их работы является последовательность опорных путевых точек, соединяющих начало, конец пути и сглаживающих полученный маршрут [2].

Существующие методы и подходы могут применяться для планирования маршрута при полностью и частично известном окружении  и предназначены для глобального планирования. Однако их использование при неизвестном окружении либо невозможно, либо требует больших вычислительных затрат. Для решения задачи в подобных условиях в работе [3] авторами предложено модифицировать существующие методы, в [4] – проводить адаптацию транспортных средств путем внедрения интеллектуальных средств, а в [5] – использовать алгоритмы, имеющие схожие входные и выходные данные для их изменения на отдельных этапах путем комбинирования различных подходов к решению задачи, что требует сходимости методов.

Учитывая специфику технических характеристик транспортной платформы, можно сделать вывод, что рассмотренные методы и алгоритмы не являются оптимальными по причине их трудоемкости, отсутствия реализации в реальном режиме с динамическими ограничениями, а также ввиду необходимости проведения сложных вычислительных операций. Требует- ся разработка или доработка существующего метода, позволяющего принять во внимание все имеющеюся недостатки с учетом ограничений [3].

Обсудим применение клеточных автоматов для решения задачи маршрутизации. В работе [6] описаны комплексные модели, учитывающие взаимодействие между участниками движения и предсказывающие поведение пешеходов  и транспортных потоков. Модель имеет высокую вычислительную сложность и требует значительных ресурсов для моделирования больших систем. В [7] разработана трехуровневая модель клеточного автомата для сложных транспортных потоков на кольцевых развязках с учетом эффективности и безопасности. Однако следует отметить определенные недостат- ки: сбор данных о траекториях движения транс- портных средств возможен только вручную, существование ограничений в исследовании поведения движения транспортных средств на кольцевой развязке на микроуровне, рассмотрение только взаимодействия между автомобилями на кольцевом перекрестке без учета дорожно-транспортных происшествий. В работе [8] авторы предлагают использовать клеточные автоматы для робототехники и в автономных системах при решении задач маршрутизации. Однако многие модели ориентированы только на определенные сценарии.

Предприняты попытки решения задачи построения маршрутов перемещения объекта интереса.

Отметим общие недостатки существующих подходов:

– сложность алгоритмов, требующая значительных вычислительных ресурсов, что затрудняет их внедрение;

– адаптивность к динамическим условиям: недостаточная гибкость для быстрой адаптации в реальном времени при резких изменениях условий среды;

– ограниченность сценариев применения, фокусирующихся на специфических аспектах, что сужает границы их универсальности;

– сложность интеграции с существующей инфраструктурой.

Метод, предложенный в данной работе, позволяет устранить или по крайней мере смягчить отмеченные недостатки. Он более прост в реализации и требует меньше вычислительных ресурсов, располагает эффективными механизмами адаптации к изменениям, а также универсален, что позволяет расширить границы его использования. Кроме того, предлагаемый метод может быть легко интегрирован в существующую инфраструктуру без необходимости значительных изменений.

Исходными данными для решения задачи являются электронные топографические карты, геопространственная актуальная информация  о местности, данные из открытых геопространственных источников.

При разработке метода авторы взяли в качестве основы модель решетчатого газа, реализованную в клеточном автомате, где пространство представлено равномерной сеткой (клетками),  и дискретное время. Законы мира выражены единственным набором правил локального взаимодействия, в ходе работы клетка на каждом шаге вычисляет свое новое состояние по состояниям ее локальных соседей [9].

Варианты клеточных автоматов представлены на рисунке 1.

Клеточный автомат можно определить как множество конечных автоматов в двумерном пространстве с координатами (i, j), которые могут находиться в одном из возможных состояний D [9]:

Каждый шаг работы автомата характеризуется сменой его состояния по определенным правилам [10]:

где – N(i, j) пространство вокруг клеток с координатами (i, j); k, l – область координат соседних клеток; f(t) – функция изменения сос- тояния клетки.

Предлагаемый метод позволяет выбирать приоритетные пути. По окончании расчета пути оценивается его стоимость и происходит сравнение с возможными другими путями, даже если они будут короче по длине.

Рассмотрим этапы алгоритма решения задачи на основе клеточного автомата решетчатых газов.

1. Задаются начальная и конечная точки маршрута – А(x1, x2) и В(y1, y2) соответственно.

2. Плоскость поиска маршрута разбивается на клетки (v Î V), по которым и будет осуществляться движение. Отмечаем клетки, которые содержат точки А(x1, x2) и В(y1, y2).

Размеры клеток будут определяться длиной и шириной транспортной платформы.

Представим окружение клетки как окружение по Муру [11]:

Согласно правилам разработки клеточного автомата для задачи поиска используем автоматы двух типов – объекты поиска и группа поиска.

Для клеточного автомата на плоскости существует восемь возможных вариантов перемещения (рис. 2).

Решетчатая структура является устойчивой и однородной, в которой каждый узел решетки описывается как транспортная платформа, непреодолимое препятствие, зона с различными способами ее преодоления, цель [9]. Такое представление позволит задать пространственные характеристики реальных объектов.

Реализуем механизм, регулирующий направление движения клетки от текущего поло- жения в заданное. Для этого воспользуемся теорией векторов.

3. Найдем расстояние между точками А и В.

3.1. Построим вектор  → 00 = const из начальной точки движения вертикально вверх.

3.2. Построим второй вектор  от центра клетки v1 к центру клетки v2. Для перехода на следующую клетку определяем векторы (v01, v02, v03, v04, v05, v06, v07, v08) из А в соседние клетки.

В общем виде векторы описываются выражением

3.3. Вычисляем углы α1-8 между векторами  и v01, v02, v03, v04, v05, v06, v07, v08 и  по формуле расчета угла между двумя векторами (рис. 2).

3.4. Определяем минимальную разницу между углами: min {α – αi}, где i = 1 – 8.

4. Осуществляем передвижение на клетку  с минимальной разницей между углами по п. 3, пока не достигнем точки В (данные о пройденном участке сохраняются в памяти программы).

4.1. Выбираем следующий наименьший угол. Когда в очередной клетке с минимальным углом находится непроходимое препятствие, платформа продолжает двигаться к точке В.

4.2. Если автомат остановился, происходит возврат, движение осуществляется в следующую клетку, чей угол был следующим по рангу от min к max. Транспортная платформа продолжает свое движение.

4.3. При равных значениях αi клетка выбирается случайным образом.

5. Маршрут считается построенным при достижении конечной точки В.

Данный метод позволяет выбрать очередной ход за один раз, что упрощает вычисления.

Поиск маршрута отличается от существующих методов [2, 3] добавлением новых элементов и введением дополнительных возможностей, включающих считывание рельефа и высот местности для построения и выбора маршрута перемещения, а также применение технологий ИИ в выборе позиций в динамически изменяющейся обстановке.

Данные возможности позволят решать зада- чи в динамически изменяющейся среде, кон- тролировать уровень проходимости в реальном времени получения данных от источников,  повысить оперативность принятия решения лицом, принимающим решение.

Результаты моделирования с помощью пред- ставленного метода показаны на рисунке 3.

Сравнение предложенного метода с алгоритмами Дейкстры, A* и Беллмана – Форда, отображенное в таблице, позволило оценить его преимущества.

Заключение

На основании изложенного можно сделать вывод о том, что предложенный метод является перспективным для использования в условиях, которые требуют высокой гибкости и адаптивности.

Дальнейшие исследования могут быть направлены на разработку более сложных моделей клеточных автоматов, учитывающих погодные условия, времена года или моральное состояние лиц, принимающих решения. Интерес авторов вызывают и такие аспекты, как интеграция методов машинного обучения для предсказания изменений в обстановке на основе исторических данных, а также исследование возможностей применения данного метода в задачах управления транспортом в условиях городских пробок.

Список литературы

1. Афанасов А.Л. Анализ алгоритмов обхода препятствий и поиска пути в априорно неопределенной среде для мобильного устройства // Вопросы науки и образования. 2019. № 64. С. 18–31.

2. Крутько Д.А, Калашников А.С., Буряченко В.В. Методы построения маршрутов вне населенных пунктов на основе GPS-данных // Сибирский аэрокосмический журнал. 2022. Т. 23. № 2. С. 168–176. doi: 10.31772/2712-8970-2022-23-2-168-176.

3. Qin H., Shao S., Wang T. et al. Review of autonomous path planning algorithms for mobile robots. Drones, 2023, vol. 7, no. 3, art. 211. doi: 10.3390/drones7030211.

4. Wang N., Li X., Zhang K. et al. A survey on path planning for autonomous ground vehicles in unstructured environments. Machines, 2024, vol. 12, no. 1, art. 31. doi: 10.3390/machines12010031.

5. Маховикова Ю.В., Мироненко С.Н., Девятков А.В., Шамлицкий Я.И. Обзор алгоритмов оптимального маршрута транспортных средств // T-Comm: Телекоммуникации и транспорт. 2020. Т. 14. № 2. С. 52–56.

6. Helbing D. The Next Civilization: Digital Democracy and Socio-Ecological Finance – How to Avoid Dystopia and Modernize Society by Digital Means. Springer Publ., 2021, 325 p. doi: 10.1007/978-3-030-62330-2.

7. Liang X., Xie C.-Z.T., Song H.-F. et al. A three-stage cellular automata model of complex large roundabout traffic flow, with a flow-efficiency and safety-enhancing strategy. Sensors, 2024, vol. 24, no. 23, art. 7672. doi: 10.3390/s24237672.

8. Wang G., Peng C., Gu Y. et al. Interactive multiscale integration of 2D and 3D functions to track multiple vehicles. IEEE Transactions Intelligent Transport Sys., 2023, vol. 24, no. 10, pp. 10618–10627.

9. Тоффоли Т., Марголус Н. Машины клеточных автоматов; [пер. с англ.]. М.: Мир, 1991. 280 с.

10. Захарченко И.В., Тристан А.В., Чорногор Н.А. и др. Моделирование мониторинга объектов с помощью 3D- клеточных автоматов // Проблемы региональной энергетики. 2022. Т. 4. № 56. С. 61–72. doi: 10.52254/1857-0070.2022.4-56.06.

11. Wu X., Liu X., Zhang D. et al. Simulating mixed Land-Use change under Multi-Label concept by integrating a convolutional neural network and cellular automata: A case study of Huizhou, China. GIScience & Remote Sensing, 2022, vol. 59, no. 1, pp. 609–632. doi: 10.1080/15481603.2022.2049493.

References

1. Afanasov, A.L. (2019) ‘Analysis of obstacle avoidance and pathfinding algorithms for mobile devices in a priori uncertain environments’, Issues of Sci. and Education, (64), pp. 18–31 (in Russ.).

2. Krutko, D.A., Kalashnikov, A.S., Buryachenko, V.V. (2022) ‘Methods of building routes outside settlements based on GPS data’, Siberian Aerospace J., 23(2), pp. 168–176 (in Russ.). doi: 10.31772/2712-8970-2022-23-2-168-176.

3. Qin, H., Shao, S., Wang, T. (2023) ‘Review of autonomous trajectory planning algorithms for mobile robots’, Drones, 7(3), art. 211. doi: 10.3390/drones7030211.

4. Wang, N., Li, S., Zhang, K. et al. (2024) ‘A survey on path planning for autonomous ground vehicles in unstructured environments’, Machines, 12(1), art. 31. doi: 10.3390/machines12010031.

5. Makhovikova, Yu.V., Mironenko, S.N., Devyatkov, A.V., Shamlitsky, Ya.I. (2020) ‘Review of algorithms for the optimal route of vehicles’, T-Comm: Transport, 14(2), pp. 52–56 (in Russ.).

6. Helbing, D. (2021) The Next Civilization: Digital Democracy and Socio-Ecological Finance – How to Avoid Dystopia and Modernize Society by Digital Means. Springer Publ., 325 p. doi: 10.1007/978-3-030-62330-2.

7. Liang, X., Xie, C.-Z.T., Song, H.-F. et al. (2024) ‘A three-stage cellular automata model of complex large roundabout traffic flow, with a flow-efficiency and safety-enhancing strategy’, Sensors, 24(23), art. 7672. doi: 10.3390/s24237672.

8. Wang, G., Peng, C., Gu, Y. et al. (2023) ‘Interactive multiscale integration of 2D and 3D functions to track multiple vehicles’, IEEE Transactions Intelligent Transport Sys., 24(10), pp. 10618–10627.

9. Toffoli, T., Margolus, N. (1987) Cellular Automata Machines: A New Environment for Modeling. Cambridge, 292 p. (Russ. ed.: (1991) Moscow, 280 p.).

10. Zakharchenko, I.V., Tristan, A.V. et al. (2022) ‘Modeling of object monitoring using 3D cellular automata’, Problems of Regional Energy, 4(56), pp. 61–72 (in Russ.). doi: 10.52254/1857-0070.2022.4-56.06.

11. Wu, X., Liu, X., Zhang, D. et al. (2022) ‘Simulating mixed Land-Use change under Multi-Label concept by integrating a convolutional neural network and cellular automata: A case study of Huizhou, China’, GIScience & Remote Sensing, 59(1), pp. 609–632. doi: 10.1080/15481603.2022.2049493.