Бакалаврская работа по программированию в ограничениях
Июнь 2019
Обзор
Чем больше возможных событий учитывает модель, тем больше условий симулятору приходится проверять снова и снова. Но если в ходе моделирования становится ясно, что некоторое условие уже никогда не станет истинным, можно ли безопасно пропускать его проверку? Я спроектировал и реализовал метод для HydLa, языка моделирования гибридных систем, который по направлению изменения переменных определяет условия, больше не нуждающиеся в проверке.
На модели, использованной для оценки, метод сократил время выполнения примерно вдвое по сравнению с исходным алгоритмом, не изменив результаты моделирования. Выигрыш был достигнут за счёт использования структуры задачи для сокращения числа рассматриваемых возможностей.
Подход к программированию в ограничениях, сформировавшийся в ходе этого исследования, лежит в основе моих нынешних проектов в портфолио: вместо того чтобы напрямую задавать каждый результат, определить правила, приоритеты и границы, а затем получить решения, которые им удовлетворяют.
Проблема — чем больше возможностей, тем медленнее вычисления
HydLa описывает гибридные системы, сочетающие непрерывные изменения и дискретные события, с помощью математических и логических ограничений. Вместо задания каждого шага процедуры модель объявляет условия, которые должны выполняться, а симулятор находит поведение, удовлетворяющее этим условиям.
В моделях с большим числом условных правил симулятор многократно проверяет большой набор условий-кандидатов. Даже условия, которые уже не могут стать истинными, остаются в этом наборе. По мере роста модели такие лишние проверки увеличивают объём вычислений.
Модель: сочетание непрерывных и дискретных изменений
Отскакивающий мяч является наглядным примером гибридной системы. В воздухе его положение и скорость меняются непрерывно, а в момент удара о пол происходит дискретное событие — отскок. Термостат, автомобиль, робот также обладают этими двумя видами изменений, хотя масштабы различаются.
Для оценки использовалась модель шара, который движется по горизонтали и отскакивает от поверхности, разделённой на участки. Для каждого участка задано условное правило: шар отскакивает, когда достигает этой области. Добавление участков позволяет представить в модели больше объектов, но увеличивает число условий, которые должен проверять симулятор.
Узкое место: больше условий — дольше выполнение
Правило, которое активируется только при выполнении определённого условия, называется ограничением с условием активации (guarded constraint). В модели для оценки правило отскока на участке активируется, только когда шар достигает пола и его горизонтальная координата находится в пределах этого участка.
При увеличении числа участков с 10 до 200 время работы исходного симулятора росло приблизительно пропорционально квадрату этого числа. В более крупных моделях проблема может усиливаться, поскольку они включают больше объектов, областей контакта и возможных событий.
Исследование: на что уходило 96% времени выполнения?
Профилирование модели со 100 участками показало, что на FindMinTime приходится 96% всего времени выполнения. Эта процедура находит самое раннее из возможных следующих событий, многократно проверяя все условия активации, рассматриваемые как кандидаты.
Так удалось определить конкретное направление улучшения: безопасно сократить число кандидатов, передаваемых в FindMinTime. Цель состояла в том, чтобы пропускать только варианты, которые больше не требуют проверки, сохраняя результат моделирования.
Подход: исключить условия, которые больше не станут истинными
Представьте шар, который скачет вниз по лестнице. Когда он миновал ступень и продолжает двигаться вперёд, она уже не может на него повлиять. Человек, глядя на рисунок, сразу перестаёт учитывать ступени позади шара; исходный алгоритм продолжал проверять каждую из них.
Сложность в том, чтобы доказать: исключённое условие не понадобится позже. Если убрать его только потому, что сейчас оно ложно, а затем оно станет истинным, результат может оказаться неверным без каких-либо признаков ошибки. Поэтому предложенный метод использует монотонность: возможность гарантировать, что переменная продолжит увеличиваться или уменьшаться на заданном интервале.
Когда направление изменения сохраняется
Первый подход применим, когда переменная меняется в одном направлении на протяжении всего моделирования. В модели с разделённой поверхностью горизонтальная координата шара всегда увеличивается. Как только шар проходит участок, условие активации этого участка уже не может стать истинным. Методы проверки моделей позволяют установить это свойство до запуска моделирования, чтобы затем безопасно исключать условия по мере того, как они становятся неактуальными.
Когда направление изменения меняется на противоположное
Многие системы не движутся в одном направлении бесконечно: переменная может увеличиваться, а затем начать уменьшаться. Поэтому в работе был предложен второй подход. Он предполагает направление изменения и контролирует это предположение с помощью проверяемых утверждений (assertions). При смене направления процесс сокращения начинается заново, а условия, исключённые на предыдущем монотонном интервале, восстанавливаются. Этот подход был спроектирован, но в рамках проекта не был реализован и не оценивался.
Результат: время выполнения тестовой модели сократилось примерно вдвое
Я реализовал подход для монотонности на всём интервале и оценил его на модели с разделённой поверхностью. Для обоих алгоритмов время выполнения росло с числом участков, но предложенный метод стабильно требовал меньше времени. В аппроксимирующих кривых коэффициент при старшей степени снизился с 1,1463 до 0,6083. В целом время моделирования в этом тесте сократилось примерно вдвое.
Этот результат относится к конкретному тесту. Метод полезен, когда модель содержит много объектов с условиями активации, направление изменения можно доказать, а часть условий в ходе выполнения навсегда теряет актуальность. Это не означает, что любая модель HydLa будет работать вдвое быстрее.
Что я вынес из исследования
В этом исследовании известные свойства поведения системы использовались для сокращения набора возможностей, которые должен рассматривать симулятор. Сужение пространства поиска с сохранением результата — одна из сильных сторон программирования в ограничениях.
Реализация и оценка охватывали переменные, которые продолжали меняться в одном направлении. Обработка смены направления осталась на стадии проектирования и ещё требовала оценки. Выявлять ненужные ограничения могут помочь и другие свойства, помимо монотонности.
Этот опыт связан с моим нынешним интересом к проектированию условий и границ, в которых ИИ может искать решения. При работе со сложными результатами определить, что можно безопасно исключить из рассмотрения, так же важно, как определить, что нужно вычислять.
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