Выпускная работа по программированию с ограничениями

Обзор

Симулятор неоднократно анализирует различные условия по мере увеличения числа возможных событий. Так что, если мы можем судить по прогрессу, что «это состояние больше никогда не будет проведено», можем ли мы безопасно остановить эту проверку? Используя направление изменений значений как подсказку, мы разработали и реализовали метод гибридного языка моделирования систем HydLa, который устраняет ненужные условия из активного поиска.

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

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

Проблема — чем больше возможностей, тем медленнее вычисления

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

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

Тема — система, в которой смешаны непрерывное и дискретное

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

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

Узкое место — количество условий увеличивает вычислительную сложность

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

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

Исследование — где находилось 96% времени обработки

При измерении времени обработки в модели с 100 секциями 96% всего времени использовалось на FindMinTime. Это обработка поиска «наиболее раннего следующего события» среди кандидатов. Для этого все условия охраны repeatedly проверялись.

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

Подход — безопасно снимать условия, которые больше никогда не будут выполнены

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

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

В случае, если направление изменения не меняется

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

Если направление изменения меняется на середине

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

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

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

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

Перспектива, полученная из этого исследования

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

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

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