Думаю, я просто не могу держать язык за зубами после того, как узнал что-то новое. Итак, я участвовал в раунде G Google Kickstart, и последним и, по-видимому, самым сложным вопросом была проблема планирования пути. Я узнал о планировании пути на уроках робототехники и алгоритмов около года назад. Проблема в том, что я все забыл. После соревнований я решил пробудить свою память в поиске пути, я продолжал идти все глубже и глубже, и итогом этого стала эта статья.
Планирование пути
Иногда в робототехнике и играх нам может потребоваться найти оптимальный путь от точки A до точки B. Этот наиболее оптимальный путь может быть кратчайшим путем, путем, на прохождение которого требуется наименьшее количество времени, или путем, который требует наименьшего количества времени. энергии для прохождения. Процесс поиска оптимального пути называется планированием пути.
Другие интересные, прямые и косвенные применения поиска пути:
- Возможность арбитража. Представьте, что вы можете конвертировать 100 000 кенийских шиллингов в 4800 ганских седи, а затем 4 800 ганских седи в 1008 долларов, которые вы конвертируете обратно в 102 020 кенийских шиллингов. Просто конвертируя одну валюту в другую, вы получаете 2020 кенийских шиллингов = 20 долларов. Это может относиться к любому активу.
- Головоломки со словесной лестницей. Представьте, что у вас есть слово «кошка», и вам нужно заменить его на «собака». Однако вы можете изменять только одну букву за раз. И переходить можно только от одного допустимого слова к другому - «кошка», «летучая мышь», «сумка», «болото», «собака».
- Кратчайший путь между городами. Вы хотите отправиться в путешествие из Найроби в Аккра. У вас есть список городов между Найроби и Аккры и различных автомагистралей, соединяющих их. Каждая магистраль, соединяющая два города, имеет свою стоимость и красоту. Как бы вы могли найти самый дешевый маршрут между Найроби и Аккры или самый живописный маршрут?
- Компьютерные сети. В сети компьютеров (например, одноранговое приложение) как найти кратчайший путь от машины A к машине B.
- Социальная сеть. На графике социальных сетей можно найти кратчайшее расстояние между двумя людьми. Это часто называют степенью разделения. Приложения социальных сетей, такие как Facebook, могут использовать это, чтобы рекомендовать вам новых друзей.
- Оптимизация путем создания столбцов. Задачи кратчайшего пути составляют основу всего класса задач оптимизации, которые могут быть решены с помощью метода, называемого генерацией столбцов. Примеры включают проблему маршрутизации транспортных средств и проблему проектирования надежной сети.
Алгоритмы планирования пути
К настоящему времени у вас есть хорошая мысленная модель того, что такое планирование пути и его применение. Вот примеры алгоритмов, которые можно использовать для планирования пути, и их различия:
- Алгоритм волнового фронта. При наличии карты этот алгоритм одинаково исследует все возможные направления.
- Алгоритм Дейкстры. Этот алгоритм отдает предпочтение путям, изучение которых требует меньших затрат.
- Алгоритм A * - это алгоритм поиска наилучшего в первую очередь, поскольку он сначала выполняет поиск наиболее перспективных направлений, то есть направлений, наиболее близких к цели.
Алгоритм A *
Мы собираемся реализовать алгоритм A * для робота, который должен перемещаться из точки A в точку B.
Карта (сетка)
Наша сеточная карта выглядит так, как показано на изображении ниже. Роботу необходимо найти кратчайший путь между точкой A (старт) и точкой B (остановка).
Это можно перевести в код следующим образом. Все проходимые ячейки имеют 0, а все ячейки препятствий имеют 1. Стоимость перехода от одной ячейки к любому из ее соседей равна 1.
Получить соседей
Есть два способа получить соседей ячейки, как показано ниже:
4-точечное подключение
В этом подходе только 4 ячейки (правая, левая, верхняя, нижняя) считаются соседями.
8-точечное подключение
В этом подходе все 8 ячеек, соседних с ячейкой, считаются соседями. Это подход, который мы будем использовать в этом случае. Код на Python реализует иллюстрацию ниже.
Стоимость обхода
Эвристический поиск
Мы будем использовать предполагаемое расстояние от каждого соседа до цели для упорядочивания очереди приоритетов. сосед, ближайший к цели, будет исследован первым.
Стоимость перехода от текущей ячейки к соседней
Если у соседа 0, это означает, что он доступен, и поэтому стоимость перехода от текущей ячейки к соседнему равна 1.
A * Алгоритм
A * использует список приоритетов для определения порядка обхода каждой ячейки.
приоритет = эвристика + стоимость
Вот шаги:
- Поместите начальную ячейку в список приоритетов с приоритетом 0.
- Пока список приоритетов не пуст, выберите из очереди ячейку с наименьшим приоритетом. Если ячейка = цель, перерыв.
- Получите соседей по камере.
- Для каждого соседа вычислите его приоритет (эвристика + стоимость) и добавьте его в список приоритетов.
- Сохраните предшественника каждого узла на карте.
- Верните карту предшественников.
Постройте оптимальный путь
Учитывая карту предшественников из приведенного выше алгоритма A *, теперь вы должны разработать оптимальный путь.
Шаги: начиная с цели, непрерывно получайте предшественника каждой ячейки, пока не дойдете до начальной ячейки. Это называется обратным отслеживанием. Ниже приведен код Python для этого.
Соедините все это красиво:
Вот полный код этого примера
Спасибо за прочтение !!!
