AI космического корабля: посадите трехмерный корабль в положение = 0 и угол = 0

Ответ 1

Я постараюсь сохранить это короткое и сладкое.

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

Каноническая статья, которую следует читать, - это Стивен Лаваль Быстрое исследование случайных деревьев: новый инструмент для планирования маршрута, и были миллион статей, опубликованных с тех пор, что они каким-то образом улучшили его.

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

Терминология

"Пространство"

Состояние вашего космического корабля может быть описано его трехмерным положением (x, y, z) и его трехмерным вращением (альфа, бета, гамма) (я использую эти греческие имена, потому что это углы Эйлера).

state space - все возможные положения и вращения вашего космического корабля. Конечно, это бесконечно.

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

свободное пространство - это все, что не является пространством конфликтов.

Общий подход (без ограничений динамики)

Для тела без динамических ограничений подход довольно прост:

• Пример состояния
• Найти ближайших соседей в этом состоянии
• Попытка спланировать маршрут между соседями и состоянием

Я кратко расскажу о каждом шаге

Выборка состояния

Сэмплирование состояния в самом основном случае означает выбор случайных значений для каждой записи в вашем пространстве состояний. Если бы мы сделали это с вашим космическим кораблем, мы бы случайно выбрали для x, y, z, alpha, beta, gamma все возможные значения (равномерная случайная выборка).

Конечно, больше пространства вашего пространства - это пространство препятствий, чем обычно свободное пространство (потому что вы обычно ограничиваете свой объект в какой-то "среде", которую хотите перемещать внутри). Так что очень часто приходится делать ограничивающий куб вашей среды и выборки позиций внутри него (x, y, z), и теперь у нас намного больше шансов на выборку в свободном пространстве.

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

Поиск ближайших соседей в выбранном состоянии

Вы выбрали какое-то фиксированное целое число > 0. Позвольте называть это целое число k. Ближайшие соседи k находятся поблизости в пространстве состояний. Это означает, что у вас есть метрика расстояния, которая может рассказать вам, как далеко друг от друга состояния. Самая базовая метрика расстояния Евклидово расстояние, которое учитывает только физическое расстояние и не заботится о вращательных углах (потому что в простейшем случае вы может вращаться на 360 градусов за один раз).

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

Планирование маршрута между состояниями

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

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

Что здесь происходит, так это то, что ваше дерево растет к образцу. Когда я говорю, что вы шаг за шагом "бит за кусочком", я имею в виду, что вы определяете некоторую "дельту" (действительно маленькое значение) и перемещаетесь по линейной интерполяции, которая почти каждая по времени. В каждой точке вы проверяете, находится ли ваше новое состояние в столкновении с каким-либо препятствием. Если вы нажмете препятствие, вы сохраните последнюю действительную конфигурацию как часть дерева (не забудьте сохранить край каким-то образом!) Итак, что вам нужно для локального планировщика:

• Проверка столкновений
• как "интерполировать" между двумя состояниями (для вашей проблемы вам не нужно беспокоиться об этом, потому что мы будем делать что-то другое).
• Физическое моделирование для timestepping (Интеграция Эйлера довольно распространена, но менее стабильна, чем что-то вроде Runge-Kutta. К счастью, у вас уже есть физическая модель!

Модификация динамических ограничений

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

• Вместо выборочных случайных состояний мы выбираем случайные элементы управления и применяем указанные элементы управления в течение фиксированного периода времени (или до столкновения).

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

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

Сэмплирование элементов управления

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

Какие node (s) применить мои элементы управления к?

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

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

То, что "достаточно близко" , полностью зависит от вас. Кроме того, что-то для вас, чтобы настроить, и есть миллион статей, которые стараются сделать вас намного ближе.

Заключение

Эта случайная выборка может показаться смешной, но ваше дерево будет расти, чтобы быстро исследовать ваше свободное пространство. Смотрите несколько видеороликов YouTube на RRT для планирования маршрута. Мы не можем гарантировать что-то под названием "вероятностная полнота" с динамическими ограничениями, но оно обычно "достаточно хорошо". Иногда будет возможно, что решение не существует, поэтому вам нужно будет добавить некоторую логику, чтобы остановить выращивание дерева через некоторое время (например, 20 000 образцов)

Дополнительные ресурсы:

Начните с них, а затем начните изучать их цитаты, а затем начните смотреть, кто их цитирует.

• Kinodynamic RRT *
• RRT-Connect

Ответ 2

Это не ответ, но он слишком длинный для размещения в качестве комментария.

Прежде всего, реальное решение будет включать в себя как линейное программирование (для многомерной оптимизации с ограничениями, которые будут использоваться во многих подшагах), а также методы, используемые в оптимизация траектории и/или теория управления. Это очень сложная проблема, и если вы можете ее решить, вы можете работать в любой компании по вашему выбору. Единственное, что могло бы ухудшить эту проблему, - это эффекты трения (drag) или эффекты гравитации внешнего тела. Реальное решение также идеально входило бы в интеграцию Verlet или Runt Runtu Kutta 4-го уровня, которые предлагают улучшения по интеграции Euler, которые вы внедрили здесь.

Во-вторых, я полагаю, что ваша "Вторая альтернативная версия" вашего вопроса выше опустила вращательное влияние на вектор позиционного перемещения, который вы добавляете в позицию на каждом временном интервале. В то время как оси струи остаются неподвижными относительно системы координат корабля, они фиксируют не относительно глобальной системы координат, которую вы используете для посадки судна (при глобальной координате [0, 0, 0])., Поэтому вектор [Px', Py', Pz'] (рассчитанный из системы координат корабля) должен пройти соответствующее вращение во всех трех измерениях до того, как будет применен к координатам глобальной позиции.

В-третьих, есть некоторые неявные предположения, которые вы не указали. Например, одно измерение должно определяться как измерение "глубина посадки", а отрицательные значения координат должны быть запрещены (если вы не принимаете огненный крах). Я разработал модель макета для этого, в которой я предполагал, что измерение z является размером посадки. Эта проблема очень чувствительна к начальному состоянию и ограничениям, установленным на струях. Все мои попытки с использованием начальных условий вашего примера выше не приземлились. Например, в моем макете (без вращения вектора 3d-смещения, отмеченном выше) ограничения струи допускают только поворот в одном направлении по оси z. Поэтому, если aZ становится отрицательным в любое время (что часто бывает), корабль фактически вынужден завершить еще одно полное вращение на этой оси, прежде чем он даже попытается снова приблизиться к нулю. Кроме того, без вращения вектора 3d-перемещений вы обнаружите, что Px будет отрицательным только с использованием ваших исходных условий и ограничений, и корабль вынужден либо сбой или отклонение все дальше и дальше на отрицательную ось x, когда он пытается маневрировать. Единственный способ решить это - по-настоящему включить поворот или обеспечить достаточные положительные и отрицательные силы струи.

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

Наконец, как я заметил в разделе комментариев: "14 мая 2015 года исходный код для инженеров-космонавтов был широко доступен для GitHub для общественности". Если вы считаете, что игра уже содержит эту логику, это должно быть вашим стартовым местом. Однако я подозреваю, что вы обязаны быть разочарованы. Большинство космических игровых последовательностей просто управляют кораблем и не имитируют "реальные" векторы силы. Как только вы возьмете под контроль 3-мерную модель, очень легко предопределить 3D-сплайн с поворотом, который позволит кораблю приземляться мягко и с идеальной опорой в заданное время. Зачем любому игровому программисту пройти этот уровень работы для последовательности посадки? Такая логика может управлять ракетами МБР или планетарными воротами для повторного входа, и это просто перехитрить ИМХО для игры (если только сама цель игры не состоит в том, чтобы увидеть, можете ли вы посадить поврежденный космический корабль с произвольными струями и ограничениями без сбоев).

Ответ 3

Для таких проблем есть два метода: поиск и эвристика bruteforce. Bruteforce означает распознать проблему как черный ящик с входными и выходными параметрами, и целью является получение правильных входных параметров для выигрыша игры. Чтобы запрограммировать такой поиск в грубой форме, игровая физика работает в цикле моделирования (физическое моделирование) и через стохастический поиск (минимакс, альфа-бета-притворство), каждая возможность опробована. Недостатком поиска грубой силы является высокий расход процессора.

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

Лучшей практикой решения космической навигации является объединение обеих идей в гибридную систему. Для программирования исходного кода для этой конкретной задачи я считаю, что требуется около 2000 строк кода. Такие проблемы нормализуются в рамках огромных проектов со многими программистами и занимают около 6 месяцев.

Ответ 4

Я могу ввести другой метод в смесь предлагаемых (удивительных) ответов.

Он больше опирается на ИИ и обеспечивает практически оптимальные решения. Он назывался Machine Learning, а точнее Q-Learning, Это удивительно легко реализовать, но трудно получить право.

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

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

оптимальность

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

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

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

Q-обучение работает очень похоже на нас:

• Соблюдайте (секретное) состояние системы
• Выберите действие, основанное на стратегии
  • Если это действие привело систему в желаемое состояние (ближе к цели), отметьте действие/начальное состояние более желательным
• Повторите

Дискретизируйте состояние вашей системы.

Для каждого состояния есть карта, инициализированная квази-случайным образом, которая отображает каждое состояние в Action (это стратегия ). Также назначьте желательность для каждого состояния (изначально нуль всюду и 1000000 для целевого состояния (X = 0, V = 0).

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

Обучение

Поезд AI (автономная фаза):

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

Использование в игре

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

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

Попробуйте это в простой 1D-проблеме, он разрабатывает стратегию очень быстро (несколько секунд).

В 2D я считаю, что отличные результаты могут быть получены через час.

Для 3D... Вы смотрите на вычисления в ночное время. Есть несколько вещей, чтобы попытаться ускорить процесс:

• Попробуйте никогда не забывать предыдущие вычисления и кормить их как исходную стратегию "наилучшего предположения". Сохраните его в файл!

• Вы можете сбросить некоторые состояния (например, рулон корабля?), не теряя при этом оптимальной навигации, но значительно увеличивая скорость вычислений. Может быть, изменить ссылочные позиции, поэтому корабль всегда находится на оси X, таким образом вы снимете размеры x и am! Y

• Государства, которые чаще встречаются, будут иметь надежную и оптимальную стратегию. Может быть, нормализовать состояние, чтобы ваше состояние корабля всегда было близким к "стандартным" состояниям?

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

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