Я исследователь-робототехник и в то же время моё хобби — разработка игр. Моя специализация — планирование многомерного движения манипуляторов роботов. Планирование движения — это очень важная тема для разработчиков игр, она пригождается каждый раз, когда нужно переместить управляемого ИИ персонажа из одной точки в другую.

В процессе изучения разработки игр я находил множество туториалов, в которых рассказывалось о планировании движения (обычно в литературе по разработке игр оно называется «поиском пути»), но большинство из них не вдавалось в подробности того, в чём заключается планирование движения с теоретической точки зрения. Насколько я могу судить, в большинстве игр редко используется какое-то иное планирование движения, кроме одного из трёх серьёзных алгоритмов: поиск по сеткам A*, графы видимости и поля течения. Кроме этих трёх принципов, существует ещё целый мир теоретических исследований планирования движения, и некоторые из них могут быть полезными разработчикам игр.

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

Движение из точки A в точку B: агенты и цели

Давайте начнём с того, что у нас в игре есть управляемый ИИ персонаж, например, враг в шутере или юнит в стратегической игре. Мы будем называть этого персонажа агентом (Agent). Агент находится в определённом месте мира, называемом его «конфигурацией». В двух измерениях конфигурацию агента можно представить всего двумя числами (обычно x и y). Агент хочет добраться до какого-то другого места мира, которое мы будем называть целью (Goal).

Давайте представим агента в виде круга, живущего в плоском двухмерном мире. Предположим, что агент может перемещаться в любом нужном ему направлении. Если между агентом и его целью нет ничего, кроме пустого пространства, то агент может просто двигаться по прямой линии из своей текущей конфигурации к цели. Когда он достигает цели, то останавливается. Мы можем назвать это «алгоритмом Walk To».

Алгоритм: WALK TO

1. Если не цель:
   1. Двигаться к цели.
2. Иначе: Остановиться.

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

Так почему мы считаем прямую линию очевидной? Потому что в каком-то смысле это «наилучший» способ движения. Если принять, что агент может двигаться только с постоянной скоростью в любом направлении, то прямая — кратчайший и самый быстрый способ добраться из одной точки в другую. В этом смысле алгоритм Walk To оптимален. В этой статье мы много будем говорить об оптимальности. В сущности, когда мы говорим об оптимальности алгоритма, мы имеем в виду, что он «лучше всех» при определённом критерии «лучшести». Если вы хотите добраться из точки A в точку B как можно быстрее и на пути ничего нет, то ничто не сравнится с прямой линией.

И на самом деле, во многих играх (я бы сказал, даже в большинстве игр), алгоритм движения по прямой Walk To идеально подходит для решения задачи. Если у вас есть мелкие 2D-враги, находящиеся в коридорах или комнатах, которым не нужно блуждать по лабиринтам или следовать приказам игрока, то вам никогда не понадобится ничего сложнее.

Но если на пути вдруг что-то оказалось?


В этом случае объект на пути (называемый препятствием (Obstacle)) блокирует путь агента к цели. Так как агент больше не может двигаться напрямую к цели, он просто останавливается. Что здесь произошло?

Хотя алгоритм Walk To и оптимален, он не полон. «Полный» алгоритм способен решить все решаемые задачи в своей области за конечное время. В нашем случае область — это круги, двигающиеся по плоскости с препятствиями. Очевидно, что простое перемещение прямо к цели не решает все задачи в этой области.

Чтобы решить все задачи в этой области и решить их оптимально, нам нужно что-то более изощрённое.

Реактивное планирование: алгоритм жука

Что бы мы стали делать при наличии препятствия? Когда нам нужно добраться до цели (например, до двери), а на пути что-то есть (например, стул), то мы просто обходим его и продолжаем двигаться к цели. Такой тип поведения называется «избеганием препятствий». Этот принцип можно использовать для решения нашей задачи перемещения агента к цели.

Одним из простейших алгоритмов избегания препятствий является алгоритм жука. Он работает следующим образом:

Алгоритм : BUG

1. Рисуем прямую линию от агента до цели. Назовём её M-линией.
2. Агент делает единичный шаг вдоль M-линии пока не будет соблюдаться одно из следующих условий:
   
   1. Если агент достиг цели, то остановиться.
   2. Если агент касается препятствия, то следовать вдоль препятствия по часовой стрелке, пока мы снова не попадём на M-линию, если при этом мы ближе к цели, чем были изначально до достижения M-линии. Когда мы достигаем M-линии, продолжить с шага 2.

Шаг 2.2 требует объяснений. По сути, агент запоминает все случаи встречи с M-линией для текущего препятствия, и покидает препятствие, только находясь на M-линии и ближе к цели, чем в любой другой момент до этого. Это нужно, чтобы избежать попадания агента в бесконечный цикл.

На рисунке выше пунктирной линией показана M-линия, а оранжевыми стрелками обозначены шаги, совершаемые нашим агентом до достижения цели. Они называются траекторией агента. Удивительно, но алгоритм жука очень просто решает множество задач подобного типа. Попробуйте нарисовать кучу безумных фигур и убедитесь, насколько хорошо он работает! Но работает ли алгоритм жука для каждой задачи? И почему он работает?

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

Мы уже упоминали концепцию траектории, которая является простой последовательностью конфигураций или движений, совершаемых агентом на своём пути. Алгоритм жука можно считать планировщиком траектории (Trajectory Planner), то есть алгоритмом, получающим начальную конфигурацию и конфигурацию цели, и возвращающим траекторию от начала до цели. (В литературе по разработке игр он также иногда называется «планировщиком пути» (path planner)).

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

В алгоритме жука M-линия является чётким индикатором того, где далее должен находиться агент. Почему мы выбрали следование M-линии, а не, допустим, линию из текущего положения агента к цели? Ответ заключается в том, что M-линия — это просто эвристика. Эвристика — это общее правило, используемое, чтобы сообщить о следующем этапе алгоритма. Это правило наделяет некими человеческими знаниями об алгоритме. Выбор эвристики часто является важной частью разработки такого алгоритма. При выборе неверной эвристики алгоритм может оказаться полностью неработоспособен.

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

Но несмотря на то, что алгоритм жука может решать все задачи этого типа, создаваемые им траектории не всегда лучшие возможные категории, которыми агент может достигнуть цели. На самом деле, алгоритм жука иногда может заставить агента заниматься довольно глупыми вещами (просто попробуйте создать препятствие, малое в направлении по часовой стрелке и огромное в другом направлении, и вы поймёте, о чём я. Если мы определим «лучший» как «занимающий кратчайшее время», то алгоритм жука ни в коем случае не является оптимальным.

Оптимальное планирование: граф видимости

А если нам нужно решить задачу движения кругов среди препятствий по оптимальному (кратчайшему) пути? Для этого мы можем привлечь геометрию, чтобы прикинуть, каким должен быть оптимальный алгоритм решения этой задачи. Для начала заметим следующее:

• На двухмерных евклидовых плоскостях кратчайшей траекторией между двумя точками является прямая линия.
• Длина последовательности прямолинейных траекторий является суммой длин каждой из линий.
• Поскольку многоугольник состоит из прямых линий (или рёбер), то кратчайший путь, полностью обходящий выпуклый многоугольник, содержит все рёбра многоугольника.
• Для обхода невыпуклого многоугольника кратчайший путь содержит все рёбра выпуклой оболочки многоугольника.
• Точка, находящаяся ровно на ребре многоугольника, касается этого многоугольника

Понимание определений «выпуклости», «невыпуклости» и «выпуклой оболочки» не очень важно для понимания этой статьи, но этих определений достаточно для создания планировщика оптимальной траектории. Давайте сделаем следующие допущения:

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

Тогда мы можем найти оптимальный план достижения агентом цели, создав то, что называется графом видимости мира. Кроме геометрии, нам также нужно немного узнать о графах. Теория графов не является темой этой статьи, но по сути своей графы — это просто группы абстрактных объектов (называемых узлами), соединённых с другими узлами абстрактными объектами под названием рёбра. Мы можем использовать мощь графов для описания мира, в котором живёт агент. Мы можем сказать, что узел — это любое место, в котором агент может находиться, ничего не касаясь. Ребро — это траектория между узлами, по которой может двигаться агент.

Учтя это, мы можем определить планировщик графа видимости следующим образом:

Алгоритм: VISIBILITY GRAPH PLANNER

• Создаём пустой граф с названием G.
• Добавляем агента как вершину графа G.
• Добавляем цель как вершину графа G.
• Помещаем все вершины всех многоугольников мира в список.
• Соединяем все вершины многоугольников в граф G в соответствии с их рёбрами.
• Для каждой вершины V списка:
  
  • Пытаемся соединить V с агентом и целью. Если прямая линия между ними не пересекает ни один из многоугольников, то добавляем эту линию как ребро в граф G.
  • Каждую другую вершины в каждом другом многоугольнике пытаемся соединить прямой линией с V. Если линия не пересекает ни один из многоугольников, то добавляем линию как ребро графа G.
  • Теперь выполняем планировщик графов (например, алгоритм Дейкстры или A*) для графа видимости, чтобы найти кратчайший путь от агента до цели.

Граф видимости выглядит следующим образом: (пунктирные линии)


А конечный путь выглядит так:


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

Но что, если наш агент не является точкой? Заметьте, как оранжевый путь проводит агента между трапецоидом и прямоугольником. Очевидно, что агент не сможет протиснуться в этом пространстве, поэтому нам нужно решить эту задачу как-то иначе.

Одно из решений заключается в том, чтобы допустить, что агент — это не точка, а диск. В таком случае мы можем просто раздуть все препятствия на радиус агента, а затем планировать, как будто агент является точкой в этом новом раздутом мире.


В этом случае агент выберет путь слева, а не справа от прямоугольника, потому что он просто не поместится в пространство между трапецоидом и прямоугольником. Эта операция «раздувания» на самом деле невероятно важна. В сущности, мы изменили мир так, чтобы наше допущение о том, что агент является точкой, оставалось истинным.

Эта операция называется вычислением конфигурационного пространства мира. Конфигурационное пространство (или C-Space) — это система координат, в которой конфигурация нашего агента представлена одной точкой. Препятствие в рабочем пространстве преобразуется в препятствие в конфигурационном пространстве размещением агента в обусловленную конфигурацию и проверкой коллизий агента. Если в такой конфигурации агент касается препятствия в рабочем пространстве, то она становится препятствием в конфигурационном пространстве. Если у нас есть некруглый агент, то для раздувания препятствий мы используем так называемую сумму
Минковского.

В случае двухмерного пространства это может казаться скучным, но именно это мы и делаем для «раздувания» препятствий. Новое «раздутое» пространство на самом деле является конфигурационным пространством. В более многомерных пространствах всё становится сложнее!

Планировщик графа видимости — отличная штука. Он и оптимален, и полон, к тому же он не полагается ни на какую эвристику. Ещё одно большое преимущество планировщика графа видимости — его умеренная возможность мультизапросов. Планировщик с мультизапросами способен повторно использовать старые вычисления при работе с новыми целями. В случае графа видимости при изменении местоположения цели или агента нам достаточно только перестроить рёбра графа от агента и от цели. Эти преимущества делают такой планировщик чрезвычайно привлекательным для программистов игр.

И в самом деле, во многих современных играх для планирования используются графы видимости. Популярной разновидностью принципа графа видимости является Nav(igation) Mesh. В Nav Mesh иногда в качестве основы используются графы видимости (вместе с другими эвристиками для расстояния до врагов, предметов и т.д.). Nav Mesh могут изменяться дизайнерами или программистами. Каждый Nav Mesh хранится как файл и используется для каждого отдельного уровня.

Вот скриншот Nav Mesh, использованного в видеоигре Overlord:


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

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

Однако самая серьёзная проблема графов видимости (по моему мнению) в том, что они плохо обобщаются. Они решают одну задачу (планирование на 2D-плоскости с препятствиями-многоугольниками), и решают её невероятно хорошо. Но что, если мы не на двухмерной плоскости? Что, если нашего агента нельзя представить в виде круга? Что, если мы не знаем, какими будут препятствия, или их нельзя представить в виде многоугольников? Тогда мы не сможем без ухищрений использовать графы видимости для решения нашей задачи.

К счастью, существуют другие методы, более близкие к принципу «запустил и забыл», которые решают некоторые из этих проблем.

Поиск по решётке: A* и его вариации

Графы видимости работают потому, что используют оптимизирующие качества поиска по абстрактным графам, а также фундаментальные правила евклидовой геометрии. Евклидова геометрия даёт нам «фундаментально верный» граф для поиска. А сам абстрактный поиск занимается оптимизацией.

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

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

Даже если алгоритм поиска по графам даёт нам «оптимальный» ответ, он является «оптимальным» с точки зрения только его собственной внутренней структуры. Это не подразумевает, что «оптимальный» согласно алгоритму поиска по графам ответ является нужным нам ответом.

Учитывая это, давайте определим граф наиболее распространённым способом: как решётку. Вот, как это работает:

Алгоритм: DISCRETIZE SPACE

• Допустим, что конфигурационное пространство имеет постоянный размер во всех измерениях.
• Дискретизируем каждое изменение так, чтобы в нём было постоянное количество ячеек.
• Каждую ячейку, центр которой находится в конфигурационном пространстве внутри препятствия, пометим как непроходимую.
• Аналогично, каждую ячейку, центр которой не находится в препятствии, пометим как проходимую.
• Теперь каждая проходимая ячейка становится узлом.
• Каждый узел соединяется со всеми смежными проходимыми соседями в графе.

«Смежный» — это ещё один аспект, с которым нужно быть внимательным. Наиболее часто он определяется как "любая ячейка, имеющая хотя бы один общий угол с текущей ячейкой" (это называется «евклидовой смежностью») или как "любая ячейка, имеющая хотя бы одну общую грань с текущей ячейкой" (это называется «смежностью Манхэттена»). От выбора определения смежности очень сильно зависит ответ, возвращаемый алгоритмом поиска по графам.

Вот как будет выглядеть этап дискретизации на нашем учебном примере:


Если мы будем выполнять поиск по этому графу согласно метрике евклидовой смежности, то получим примерно такой результат:


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

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

Методы поиска по графам на дискретной решётке (в том числе и A*) являются согласно их внутренней структуре оптимальными. Также они являются резолюционно-полными. Это более слабая форма полноты, которая гласит, что при стремлении мелкости решётки к бесконечности (т.е. при стремлении ячеек к бесконечно малому размеру) алгоритм решает всё больше и больше решаемых задач.

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

Ещё одним ключевым преимуществом (по моему мнению, главным) методов на основе графов является то, что они совершенно абстрактны. Это значит, что дополнительные затраты (такие как обеспечение безопасности, гладкости, близости нужных объектов и т.д.) могут быть учтены и автоматизированы автоматически. Кроме того, для решения совершенно различных задач можно использовать один и тот же абстрактный код. В игре DwarfCorp мы используем один планировщик A* и для планирования движения, и для планирования символических действий (используемого для представления действий, которые могут совершать агенты, в виде абстрактного графа).

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

Ещё одним серьёзным недостатком метода является то, что поиск по графам сам по себе может занимать достаточно больше время. Если в мире движутся одновременно несколько тысяч агентов или изменяет своё положение множество препятствий, то поиск по решётке может быть неприменим. В нашей игре DwarfCorp планированию уделено несколько потоков. Оно отъедает кучу процессорного времени. В вашем случае такое тоже может быть!

Политики управления: потенциальные функции и поля течения

Ещё один способ решения задачи планировки движения — перестать думать о ней в категориях планирования траекторий и начать воспринимать её в категориях политикой управления. Помните, мы говорили, что алгоритм жука можно воспринимать и как планировщик траектории, и как политику управления? В том параграфе мы определили политику как набор правил, который получает конфигурацию и возвращает действие (или «входной сигнал управления»).

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

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

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

Алгоритм: POTENTIAL FIELD POLICY

• Определяем вещественные константы a и b
• Находим вектор в конфигурационном пространстве от агента до цели и обозначаем его как g.
• Находим ближайшую точку препятствия в конфигурационном пространстве и обозначаем его как o.
• Находим вектор от o до агента и обозначаем его как r.
• Входной сигнал управления имеет вид u = a * g^ + B * r^, где v^ обозначает нормализованный вектор v.
• Перемещаем агента согласно входному сигналу управления.

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


С помощью политики потенциального поля можно заставить агентов двигаться невероятно реалистичным и плавным образом. Также можно легко добавить дополнительные условия (близость к нужному объекту или расстояние до врага).

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

В некоторых играх (особенно в стратегических) такой метод используется с огромной эффективностью. Вот пример полей течения, используемых в стратегической игре Supreme Commander 2, чтобы юниты естественным образом избегали друг друга, сохраняя построение:


Разумеется, функции полей течения и потенциальных полей имеют серьёзные недостатки. Во-первых, они ни в коем случае не оптимальны. Агенты будут распространяться полем течения вне зависимости от того, сколько времени займёт добирание до цели. Во-вторых (и, по-моему, это наиболее важно), они ни в коем случае не полны. Что, если входной сигнал управления обнулится до того, как агент достигнет цели? В этом случае мы скажем, что агент достиг "локального минимума". Вы можете подумать, что такие случаи достаточно редки, но на самом деле их довольно легко сконструировать. Достаточно просто поместить перед агентом большое U-образное препятствие.

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

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

Конфигурационное пространство и проклятие размерности

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

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

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

Что, если агент является не кругом а прямоугольником? Что, если важен поворот агента? Вот как выглядит описываемая мной картина:


В показанном выше случае агент (красный) похож на магазинную тележку, которая может двигаться в любом направлении. Мы хотим переместить агента таким образом, чтобы он оказался ровно поверх цели и был повёрнут в нужном направлении.

Здесь мы предположительно можем использовать алгоритм жука, но нам нужно будет внимательно обращаться с поворотами агента, чтобы он не сталкивался с препятствиями. Мы быстро запутаемся в хаосе правил, которые будут совсем не так элегантны, как для случая с круглым агентом.

А что, если попробовать использовать граф видимости? Для этого нужно, чтобы агент был точкой. Помните, как мы сделали трюк и раздули объекты для круглого агента? Возможно, и в этом случае удастся сделать нечто подобное. Но насколько нам нужно раздуть объекты?

Простым решением будет выбор «наихудшего сценария» и вычисление планирования с таким расчётом. В этом случае мы просто берём агента, определяем описывающий его круг и принимаем агента равному кругу этого размера. Затем мы раздуваем препятствия до нужного размера.


Это сработает, но нам придётся пожертвовать полнотой. Появится множество задач, которых мы не сможем решить. Возьмём например такую задачу, в которой длинный и тонкий агент должен для достижения цели пробраться через «замочную скважину»:


В этом сценарии агент может добраться до цели, проникнув в скважину, повернув на 90 градусов, затем дойти до следующей скважины, повернуть на 90 градусов и выйти из неё. При консервативной аппроксимации агента через описывающий круг эту задачу решить будет невозможно.

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

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

Можно воспринимать это следующим образом: представьте, что агент выполнил определённый поворот (который мы обозначим «тета»). Теперь мы перемещаем агента в каждой точки рабочего пространства с заданным поворотом, и если агент касается препятствия, то мы считаем эту точку коллизией в конфигурационном пространстве. Такие операции для препятствий-многоугольников тоже можно реализовать с помощью сумм Минковского.


На представленной выше схеме у нас имеется одно прохождение агента через препятствие. Красными контурами агента показаны конфигурации, находящиеся в коллизии, а зелёными контурами показаны конфигурации без коллизий. Это естественным образом приводит к ещё одному «раздуванию» препятствий. Если мы выполним его для всех возможных положений (x, y) агента, то создадим двухмерный срез конфигурационного пространства.

Теперь мы просто увеличим тету на некую величину и повторим операцию, получив ещё один двухмерный срез.


Теперь мы можем наложить срезы один на другой, выровняв их координаты x и y, как бы сложили листы миллиметровой бумаги:


Если мы будем нарезать тету бесконечно тонко, то в результате получим трёхмерное конфигурационное пространство агента. Это непрерывный куб, а тета поворачивается вокруг него снизу вверх. Препятствия превращаются в странные цилиндрические фигуры. Агент и его цели становятся просто точками в этом новом странном пространстве.


Это довольно сложно уложить в голове, но в каком-то смысле такой подход красив и элегантен. Если мы можем представить препятствия в двух измерениях, где каждое измерение — это просто положение агента в координатах x и y, то мы также можем представить препятствия и в трёх измерениях, где третьим измерением будет поворот агента.

Что, если мы бы захотели добавить агенту ещё одну степень свободы? Допустим, мы хотели бы увеличивать или уменьшать его длину? Или у него бы были руки и ноги, которые тоже нужно учитывать? В таких случаях мы делаем то же самое — просто добавляем измерения в конфигурационное пространство. На этом этапе его становится совершенно невозможно визуализировать, и чтобы понять их, приходится использовать такие понятия, как «гиперплоскость», «многообразие с ограничениями» и «гипершар».


Пример задачи четырёхмерного планирования. Агент состоит из двух отрезков с соединяющей их осью.

Теперь, когда наш агент — просто точка в 3D-пространстве, мы можем использовать обычные алгоритмы для нахождения решения любой задачи планирования движения. Если бы мы хотели, то могли бы создать сетку из вокселей в новом 3D-пространстве и воспользоваться A*. Если бы подумали, то также могли бы найти представление конфигурационного пространства в виде многоугольного меша, а затем использовали граф видимости в 3D.

Аналогично, для других измерений мы можем сделать следующее:

1. Вычислить конфигурационное пространство агента и препятствий.
2. Выполнить A* или Nav Mesh в этом пространстве.

К сожалению, у этих операций есть две огромные проблемы:

1. Вычисление N-мерного конфигурационного пространства является NP-сложной задачей.
2. Оптимальное планирование в N-мерном конфигурационном пространстве является NP-сложным.

Технический термин из компьютерной науки "NP-сложная" обозначает, что задача при её увеличении становится экспоненциально сложнее, неся за собой множество других теоретических сложностей.

На практике это значит, что если мы начнём добавлять измерения в задачи планирования, то очень скоро исчерпаем вычислительную мощь или память, или и то, и другое. Эта проблема известна как проклятие размерности. В трёх измерениях мы можем обойтись A*, но как только мы доберёмся до 4, 5 или 6 измерений, то A* быстро становится бесполезным (несмотря на недавние исследования Максима Лихачёва, позволившие обеспечить его достаточно хорошую работу).

Простейший пример шестимерной задачи планирования называется "задачей перемещения пианино". Её формулировка: как переместить твердотельный предмет (допустим, пианино) из точки A в точку B в 3D-пространстве, если его можно перемещать и поворачивать в любом направлении?


Пример задачи перемещения пианино из OMPL

Удивительно, но несмотря на свою простоту, эта задача десятилетиями оставалась нерешённой.

По этой причине игры в основном придерживаются простых двухмерных задач и имитируют всё остальное (даже когда наличие решения чего-то вроде задачи перемещения пианино кажется фундаментальной частью ИИ трёхмерной игры).

Нерешённые задачи

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

Сегодня планирование в многомерных пространствах исследовано гораздо лучше. Всё это произошло благодаря двум основным открытиям: рандомизированным планировщикам и быстрым оптимизаторам траекторий. Я расскажу о них в последующих разделах.

Разница между поиском пути и планированием движения

Я заметил, что после публикации черновика этой статьи некоторых читателей сбивала с толку моя терминология. В литературе по разработке игр действие перемещения из точки A в точку B обычно называется "поиском пути", а я называл его "планированием движения". В сущности, планирование движения является обобщением поиска пути с более свободным определением «точки» и «пути», учитывающим пространства большей размерности (например, повороты и шарниры).

Планирование движения можно воспринимать как поиск пути в конфигурационном пространстве агента.

Рандомизированное планирование: вероятностные дорожные карты (Probabilistic Road Maps, PRM)

Одно из первых общих решений задач многомерного планирования называется вероятностной дорожной картой. Оно заимствует идеи Navigation Mesh и графа видимости, добавляя ещё один компонент: случайность.

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

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

Вот, как выглядит алгоритм целиком:

Алгоритм: PROBABALISTIC ROAD MAP (PRM)

• Создаём пустой граф G
• Добавляем в граф G узлы начала и цели.
• За N итераций:
  
  • Находим одну однородную случайную выборку конфигурационного пространства и называем её R. Для этого просто рассматриваем каждое измерение конфигурационного пространства как случайное число и генерируем ровно одну точку как список этих случайных чисел.
  • Если агент находится в коллизии при конфигурации R, то продолжаем.
  • В противном случае, добавляем R к графу G.
  • Находим все узлы в G, находящиеся в пределах расстояния d от R.
  • Для каждого узла N, соответствующего этому критерию
    
    • Пробуем разместить прямую линию без коллизий между R и N
    • Если у ребра отсутствуют коллизии, то добавляем его к G.
    • Выполняем планирование с помощью A* или алгоритма Дейкстры от начала до цели.
    
    
  
  

Если вкратце, то на каждом этапе мы создаём случайную точку и соединяем её с соседями в графе на основании того, какие соседние узлы графа она «видит», то есть если мы уверены, что можно провести прямую линию между любым новым узлом и соседями в графе.

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

Вместо этого PRM рассматривает только структуру созданного ей случайного графа и коллизии между соседними узлами.

Свойства PRM

Мы уже говорили, что алгоритм больше не оптимален и не полон. Но что мы можем сказать о его производительности?

Алгоритм PRM является так называемым "вероятностно полным". Это значит, что при стремлении количества итераций N к бесконечности вероятность того, что PRM решит любой решаемый запрос планирования, равняется единице. Это кажется очень шатким определением (так и есть), но на практике PRM сходится к верному решению очень быстро. Однако это означает, что алгоритм будет иметь случайную скорость и может навечно зависнуть, не находя решения.

PRM также имеет интересные отношения с оптимальностью. При увеличении размера PRM (и росте N до бесконечности) количество возможных путей увеличивается до бесконечности, и оптимальный путь через PRM становится истинно оптимальным путём через конфигурационное пространство.

Как можно представить, из-за своей случайности PRM может создавать очень некрасивые, длинные и опасные пути. В этом отношении PRM ни в коем случае не оптимальна.

Как и графы видимости с Nav Mesh, в фундаментальном плане PRM являются мультизапросными планировщиками. Они позволяют агенту повторно эффективно использовать случайный граф для множества запросов планирования. Также дизайнеры уровней могут «запекать» одну PRM для каждого уровня.

Почему случайность?

Важнейший «трюк» PRM (и других рандомизированных алгоритмов) в том, что она представляет конфигурационное пространство статистически, а не явно. Это позволяет нам пожертвовать оптимальностью решения ради скорости, приняв «достаточно хорошие» решения там, где они существуют. Это невероятно мощный инструмент, поскольку он позволяет программисту решать, какой объём работы должен совершить планировщик, прежде чем вернуть решение. Это свойство называется свойством алгоритма выполнения в реальном времени.

В сущности, сложность PRM растёт с увеличением количества выборок и параметра расстояния d, а не с увеличением количества измерений конфигурационного пространства. Сравните это с A* или графами видимости, которые тратят экспоненциально больше времени при увеличении размерности задачи.

Это свойство позволяет PRM быстро выполнять планирование в сотнях измерений.

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

Рандомизированные деревья случайного исследования (Randomly Exploring Randomized Trees, RRT)

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

В таких случаях мы можем изменить идею создания случайных графов с учётом того, что мы хотим только один раз спланировать движение из точки A в точку B. Один из способов реализации этого — заменить граф на дерево.

Дерево — это просто особый тип графа, в котором узлы упорядочены в «родительские» и «дочерние» так, что каждый узел дерева имеет ровно один родительский узел и от нуля и более дочерних.

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

Если агент находится в каком-то состоянии, то существует несколько других состояний, в которые он может перейти из текущего (или, в нашем случае, бесконечное количество состояний). Из каждого из этих состояний он может перейти в другие состояния (но не будет возвращаться назад, потому что он уже находился в состоянии, из которого пришёл).

Если мы будем хранить состояния, в которых был агент, в качестве «родительских» узлов, а все состояния, в которые агент переходит из них, как «дочерние», то мы можем сформировать древоподобную структуру, растущую из текущего состояния агента во все места, в которых потенциально может находиться агент. Рано или поздно дерево агента направит его к состоянию цели и у нас появится решение.

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

Так можем ли мы случайным образом вырастить дерево из начальной конфигурации агента до достижения конфигурации цели?

Эту задачу стремятся решить два класса алгоритмов. Оба были изобретены в конце 90-х-начале нулевых. Один из подходов является «узлоцентричным» — он выбирает случайный узел в дереве и растёт в случайном направлении. Такой класс алгоритмов называется «EST», то есть «Expansive Space Trees» («расширяемые пространственные деревья»). Второй подход является «ориентированным на выборки»: он начинает со случайной выборки узлов в пространстве, а затем выращивает ближайший узел по направлению к этой случайной выборке. Алгоритмы такого типа называются "RRT" («Rapidly Exploring Randomized Trees», «рандомизированными деревьями случайного исследования»).

В общем случае RRT гораздо лучше, чем EST, но объяснение причин этого выходят за рамки нашей статьи.

Вот, как работает RRT:

Алгоритм: RAPIDLY EXPLORING RANDOMIZED TREE (RRT)

• Создаём пустое дерево T.
• Добавляем к T начальную конфигурацию агента.
• В течение N итераций, или пока не достигнута цель
  
  • Случайным образом делаем выборку для узла R.
  • Находим в T ближайший к R узел. Называем его K.
  • Делаем шаги по лучу от K до R на малую величину эпсилон, пока не выполнится следующее условие:
    
    • При наличии коллизии возвращаемся к созданию случайной выборки.
    • В противном случае добавляем к T новый узел в этой конфигурации.
    • Если мы достигли максимального расстояния d от K, то возвращаемся к созданию случайной выборки.
• Если узел цели теперь находится в пределах расстояния d от любого узла дерева, то у нас есть решение.

На рисунках выше приблизительно показан один шаг алгоритма посередине его выполнения. Мы берём случайную выборку (оранжевую, r), находим ближайший к ней узел (чёрный, k), а затем добавляем один или несколько новых узлов, которые делают «шаг в направлении» случайной выборки.

Дерево будет продолжать так расти случайным образом, пока не достигнет цели. Время от времени мы будем выполнять также случайную выборку к цели, жадным образом пытаясь провести к ней прямую линию. На практике вероятность попадания цели в выборку в лучшем случае будет находиться в промежутке от 30% до 80%, в зависимости от загромождённости конфигурационного пространства.

RRT относительно просты. Их можно реализовать всего в нескольких строках кода (допустив, что мы можем легко найти ближайший узел в дереве).

Свойства RRT

Вы, наверно, уже не удивитесь тому, что алгоритм RRT является всего лишь вероятностно полным. Он неоптимален (а во многих случаях чрезмерно неоптимален).


Манипуляторы робота считаются очень многомерными системами. В этом случае у нас есть два манипулятора с семью шарнирами каждый, держащие одношарнирные кусачки. Система является 15-мерной. Современные исследования планирования движения изучают подобные многомерные системы.

Благодаря своей простоте RRT также обычно оказывается чрезвычайно быстрым (по крайней мере, для многомерных систем). При использовании самых быстрых вариаций RRT решения для семимерных или более многомерных систем находятся за миллисекунды. Когда количество измерений достигает десятков, RRT обычно превосходит все остальные планировщики в решении таких задач. Но стоит учесть, что «быстрый» в сообществе исследователей многомерного планирования означает секунду или около того на выполнение всего конвейера действий в семи измерениях, или до минуты при двадцати и более измерений. Причина этого в том, что пути RRT часто слишком ужасны, чтобы использовать их непосредственно, и должны пройти длительный этап предварительной обработки. Это может потрясти программистов, использующих A*, который возвращает решения двухмерных проблем за миллисекунды; но попробуйте выполнить A* для семимерной задачи — он не вернёт решения никогда!

Вариации RRT

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

RRTConnect — выращивает два дерева из начала и из цели, и пытается соединить их прямой линией через случайные интервалы. Насколько мне известно, это самый быстрый планировщик для задач с высоким количеством измерений. Вот красивая иллюстрация созданной мной реализации RRT connect (белое — препятствия, синее — свободное пространство):


RRT* — изобретён в этом десятилетии. Гарантирует оптимальность благодаря ребалансировке дерева. В тысячи раз медленнее, чем RRTConnect.

T-RRT — пытается создавать высококачественные RRT-пути, исследуя градиент функции затрат.

Constrained RRT — позволяет выполнять планирование с произвольными ограничениями (такими как ограничения расстояния, затрат и т.д.). Медленее, чем RRT, но ненамного.

Kinodynamic RRT — выполняет планирования в пространстве входных сигналов управления, а не в конфигурационном пространстве. Позволяет выполнять планирование для автомобилей, тележек, судов и других агентов, которые не могут произвольно изменять свой поворот. Активно используется в DARPA Grand Challenge. Гораздо, гораздо, ГОРАЗДО медленнее, чем некинодинамические планировщики.

Discrete RRT — реализация RRT для сеток. В двухмерном пространстве сравнима по скорости с A*, в 3D и в многомерных системах быстрее его.

DARRT — изобретён в 2012 году. Реализация RRT для планирования символических действий (ранее считавшихся областью применения A*).

Срезание траекторий и оптимизация

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

В общем случае оптимизатор траекторий — это алгоритм, получающий исходную траекторию и функцию затрат, изменяющий исходную траекторию так, чтобы она имела наименьшую стоимость. Например, если нужная нам функция затрат — это минимизация длины траектории, то оптимизатор по этой функции будет брать исходную траекторию и изменять эту траекторию так, чтобы она была короче. Такой тип оптимизатора называется срезателем траекторий (Trajectory Shortcutter).

Один из самых распространённых и чрезвычайно простых срезателей траекторий (который можно назвать «стохастическим срезателем восхождения», Stochastic Hill Climbing Shortcutter) работает следующим образом:

Алгоритм: Stochastic Hill Climbing Shortcutter

• В течение N итераций:
  • Берём две случайные точки на траектории T (называем их t1 и t2)
  • Если соединение прямой линией t1 и t2 не делает траекторию короче, то продолжаем.
  • В противном случае, пробуем соединить t1 и t2 прямой линией
    
    • Если можно найти прямую линию без коллизий, то срезаем траекторию T от t1 до t2, отбрасывая всё между ними
    
    
  
  

Этот срезатель траекторий можно легко преобразовать, заменив концепцию «краткости пути» на любую другую функцию затрат (например, расстояния от препятствий, плавности, безопасности и т.д.). Со временем траектория попадёт в то, что называется «локальным минимумом» функции затрат. Длина (или стоимость) траектории больше не будет уменьшаться.

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

Оптимизация траектории при планировании

Ещё один способ решения многомерных задач планирования движения — отстраниться от идеи «поиска пространства» для нахождения пути, и вместо этого сосредоточиться непосредственно на оптимизации траекторий.

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

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

Один из способов реализации этого процесса называется градиентным спуском. Если у нас имеется некая функция затрат C(T), где T — это траектория, то можно вычислить градиент D_C(T), который сообщает способ изменения заданной траектории таким образом, чтобы максимально снизить затраты.

На практике это очень сложный процесс. Можно представить его примерно так:

Алгоритм: Gradient Descent Trajectory Optimizer

1. Чем больше траектория проходит через препятствия, тем более она затратна.
2. Начинаем с прямой линии от агента до цели. Назовём её T_0.
3. Во всех точках, где траектория сталкивается с препятствиями, вычисляем направление, в котором точка наискорейшим образом покинет препятствие.
4. Представьте, что траектория - это эластичная резиновая лента. Теперь представьте, что мы тянем каждую точку в направлении, заданном на этапе 3.
5. Вытянем немного все точки согласно 4.
6. Повторяем, пока вся траектория не будет находиться вне коллизий.

Со временем траектория постепенно будет «отталкиваться» от препятствий, тем не менее оставаясь плавной. В общем случае такой планировщик не может быть полным или оптимальным, потому что в качестве сильной эвристики он использует первоначальную гипотезу о прямой линии. Однако он может быть локально полным и локально оптимальным (и на практике решает большинство задач).


Заметьте, что на изображении градиенты точек представляются собой *отрицательный* градиент функции затрат)

На практике, оптимизация траекторий как планирование — это достаточно трудная и запутанная тема, о которой сложно судить в этой статье. Что на самом деле означает вычисление градиента траектории? Что значит восприятие траектории как резиновой ленты? На эти вопросы существуют очень сложные ответы, связанные с вариационным анализом.

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


CHOMP, используемый роботом для поднятия кружки (Иллюстрация из работы Драгана et. al)

За последние годы появилось множество очень быстрых оптимизаторов траекторий, ставших сильными конкурентами RRT и PRM в решении многомерных задач. Один из них, CHOMP, использует градиентный спуск и умное представление препятствий с помощью поля расстояния. Другой, TrajOpt, представляет препятствия в виде выпуклых множеств и использует техники последовательного квадратичного программирования.

Важные темы, которые мы не рассмотрели

Кроме того, что я рассказал, существует ещё целый мир теоретического планирования движения. Вкратце расскажу о том, что есть ещё.

Неголономное планирование

Мы рассматривали только случай, когда агент может двигаться в любом направлении с любой скоростью. Но что, если это не так? Например, автомобиль не может скользить вбок, а должен двигаться вперёд и назад. Такие случаи называются «неголономными» задачами планирования. У такой задачи есть несколько решений, но ни одно из них не является быстрым! На вычисление среднего плана у современного автомобильного планировщика может уйти до минуты.

Планирование с ограничениями

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

Временное планирование

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

Гибридное планирование

Что, если план нашего агента невозможно представить одной траекторией? Что, если агент должен взаимодействовать по пути с другими объектами (а не просто избегать их)? Такие типы задач обычно относят к категории «гибридного планирования» — обычно присутствует некий абстрактный аспект, связанный геометрическим аспектом задачи. Для таких типов задач также нет чётких, повсеместно принятых решений.

Выводы

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

Современный прогресс в исследованиях планирования движения привёл к тому, что широкий диапазон ранее нерешаемых задач теперь можно решать на персональных компьютерах (а потенциально и в видеоигровых движках).

К сожалению, многие из таких алгоритмов по-прежнему слишком медленны для применения в реальном времени, особенно для автомобилей, судов и других транспортных средств, которые не могут двигаться во всех направлениях. Всё это требует дальнейших исследований.

Надеюсь, статья не показалась вам слишком сложной и вы нашли в ней что-то полезное для себя!

Вот сводная таблица всех алгоритмов, рассмотренных в статье (надо учесть, что здесь учитывается только некинодинамическое планирование):