Часть 1. Общий алгоритм поиска

Введение

Поиск пути

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

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

В этом руководстве рассмотрен простейший алгоритм поиска пути, основанный на алгоритме Дейкстры. Этот алгоритм также известен под названием поиск по первому наилучшему совпадению, ключевая логика у него общая со многими другими алгоритмами, например, A*, заливка методом наводнения и диаграммы Вороного.

Здесь мы рассмотрим практическое применение этого алгоритма. Вам понадобятся базовые знания программирования и языка Python.

Привет! Меня зовут Константин Яковлев, я научный работник и вот уже более 15 лет я занимаюсь методами планирования траектории. Часто эта задача сводится к поиску пути на графе, для чего обычно используется алгоритм эвристического поиска A*. Этот алгоритм был предложен в 60-х годах XX века и с тех пор используется повсеместно. Скорее всего, юнит вашей любимой RTS бежит по карте с помощью той или иной вариации A*. Точно так же, под капотом беспилотного авто вы, наверняка, найдёте A*, хотя там, конечно, не только он.

A* — это хороший алгоритм, но его вычислительная эффективность сильно зависит от эвристической функции, которую должен задать разработчик. Основная проблема стандартных эвристик заключается в том, что они не учитывают расположение препятствий на карте и ведут поиск буквально напролом, тратя на это ресурсы (итерации поиска). Почему бы нам не воспользоваться современными нейросетями для решения этой проблемы, а именно попросить нейросеть посмотреть на карту и подсказать поиску как лучше обходить препятствия, чтобы быстрее (за меньшее число итераций) найти нужный путь?

Этот текст посвящен как самому алгоритму A*, так и попыткам повысить его эффективность с помощью методов искусственного интеллекта. Заодно я расскажу о том, какие новшества в этом направлении придумали мы с коллегами: научная статья на эту тему опубликована в сборнике конференции AAAI 2023.

Следование по пути и управление движением

Технические требования

… Молвит он: «Коль жив я буду, чудный остров навещу, у Гвидона погощу».

Приступаем к работе

Классификация лабиринтов

Навигация по лесу

Алгоритм A*

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

Введение

При разработке своей игры, я дошёл до момента создания первых NPC. И появился вопрос как заставить NPC обойти стену а не "идти в неё".

Полазив по интернету я нашёл такие алгоритмы:

• Поиск в ширину (BFS, Breadth-First Search)
• Алгоритм Дейкстры (Dijkstra)
• А Star "A со звёздочкой"
• Поиск по первому наилучшему совпадению (Best-First Search)
• IDA (A с итеративным углублением)
• Jump Point Search

И решил попробовать реализовать свой A* на воксельной 3д сетке.

Предыстория

Вот собственно и он:

Привет, Друзья!

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

Пример использования на огромном графе:

Поиграться с демо можно здесь

В библиотеке используется мало-известный вариант A* поиска, который называется NBA*. Это двунаправленный поиск, с расслабленными требованиями к функции-эвристике, и очень агрессивным критерием завершения. Не смотря на свою малоизвестность у алгоритма отличная скорость сходимости к оптимальному решению.

Описание разных вариантов A* уже не раз встречалось на хабре. Мне очень понравилось вот это, потому повторяться в этой статье я не буду. Под катом расскажу подробнее почему библиотека работает быстро и о том, как было сделано демо.

Раньше обращение человека к компьютеру голосом можно было увидеть только в фантастическом кино. В настоящее время больше половины пользователей предпочитают голосовые запросы. Это очень удобно: не нужно отвлекаться от текущих дел, чтобы напечатать свой вопрос, поэтому ежедневно люди разговаривают со своими девайсами. Да и сказать гораздо быстрее, чем ввести текст, даже если в настоящий момент руки свободны.

Распространено убеждение, что голосовой ввод заменяет собой текст. На самом деле письменный формат остаётся основным: компьютер умеет всего лишь фиксировать речь, но не обрабатывать её. Алгоритмы переводят сказанную фразу в тестовый формат, а только потом анализируют и ищут в глобальной сети ответ на запрос.

Привет, Хабр! В этом посте делюсь опытом разработки на Svelte, демонстрируя это на моем пет-проекте.

Код проекта: GitHub
Лайв демо: ivan-sem.com