Такафуми Хориучи

Бакалаврская работа по программированию в ограничениях

Обзор

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

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

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


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

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

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

Модель: сочетание непрерывных и дискретных изменений

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

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

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

Узкое место: больше условий — дольше выполнение

Правило, которое активируется только при выполнении определённого условия, называется ограничением с условием активации (guarded constraint). В модели для оценки правило отскока на участке активируется, только когда шар достигает пола и его горизонтальная координата находится в пределах этого участка.

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

Исследование: на что уходило 96% времени выполнения?

Профилирование модели со 100 участками показало, что на FindMinTime приходится 96% всего времени выполнения. Эта процедура находит самое раннее из возможных следующих событий, многократно проверяя все условия активации, рассматриваемые как кандидаты.

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

Подход: исключить условия, которые больше не станут истинными

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

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

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

Когда направление изменения сохраняется

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

Красная линия поднимается от α в момент времени 0 до β в конце моделирования. Она представляет переменную, которая увеличивается на всём моделируемом интервале.
Монотонность на всём интервале означает, что направление изменения сохраняется на протяжении всего моделируемого промежутка времени.

Когда направление изменения меняется на противоположное

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

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

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

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

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

График времени моделирования в зависимости от N — числа участков поверхности. На всём диапазоне от 10 до 200 участков предложенный метод работает быстрее. При N = 200 он занимает около 250 секунд, исходный алгоритм — около 470 секунд.
В рассмотренных моделях предложенный метод (квадраты) требует примерно вдвое меньше времени, чем исходный алгоритм (круги). На исходном графике подписи даны на английском: original — исходный алгоритм, proposed — предложенный метод. По вертикали — время моделирования в секундах, по горизонтали — число участков N.

Что я вынес из исследования

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

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

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

Takafumi Horiuchi and Kazunori Ueda. “Dynamic Reduction of Guarded Constraints for the Hybrid Systems Modeling Language HydLa.” Proceedings of the 33rd Annual Conference of the Japanese Society for Artificial Intelligence, 2019. DOI: 10.11517/pjsai.JSAI2019.0_1E3OS3b02