Труды КНЦ вып.9 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 10/2018(9))

обеспечивающий «сужение» доменов переменных, упрощение ограничений и т.п. и, при этом, имеющий низкую вычислительную сложность (оценивается полиномом низкой степени). Алгоритмы, реализующие вывод на ограничениях, называются алгоритмами-распространителями или алгоритмами-пропагаторами. Методы, реализующие стратегии интеллектуального поиска, в отличие от методов вывода, имеют существенную вычислительную сложность, поскольку сопряжены с перебором вариантов гипотез о возможных значениях тех или иных переменных. В отличие от методов динамического программирования, например, метода перемножения числовых матриц (matrix multiplication method), в качестве стратегий поиска в рамках парадигмы программирования в ограничениях, в основном, используются различные варианты информированного поиска в глубину с возвратами, а также методы локального поиска. Особенности архитектуры систем программирования в ограничениях создают предпосылки для унификации совместной обработки разнородной (количественной и качественной) информации (ограничений). Кроме того, технология программирования в ограничениях позволяет организовать процедуры вывода с недоопределенными параметрами, что дает возможность моделировать и аспекты неопределенности, и недетерминированность действий исполнителя, ограниченную конечным перечнем возможных альтернатив. Теперь перейдем к описанию задач, при решении которых применяются (или могут быть применены) методы программирования в ограничениях. Интеллектуальное планирование - это область искусственного интеллекта, которая в настоящее время вызывает значительный интерес [1]. В планировании объединяются два основных направления развития искусственного интеллекта - поиск и логика. Перекрестное обогащение идеями, взятыми из этих двух областей, привело не только к повышению производительности, но и к расширению использования планировщиков в производственных приложениях. Следует различать два направления исследований: интеллектуальное планирование (AI-planning) и составление расписаний (scheduling). В рамках настоящей статьи будем придерживаться точки зрения, принятой в AI-community (сообществе искусственного интеллекта), что задача составления расписаний является одной из разновидностей задач интеллектуального планирования. Составление расписаний (scheduling) - это проблема назначения множества задач множеству рабочих ресурсов, на которые (как на задачи, так и на ресурсы) накладывается ряд ограничений. В качестве примеров ограничений можно привести предельный срок выполнения задачи (deadline), количество рабочих ресурсов, ограничения предшествования на множестве задач, приоритеты задач и т.п. Таким образом, составление расписаний - это распределение (атомарных) задач по исполнителям. Расписание определяет, кто чем занимается (как правило, с привязкой ко времени). То есть здесь действия (задачи), которые нужно выполнить, заданы заранее. Нужно отыскать лишь их порядок и распределение по рабочим ресурсам. В отличие от составления расписаний, планирование заключается в отыскании действий, необходимых для решения задачи, и выстраивании этих действий в последовательность, приводящую к решению. То есть нужно найти не только порядок, но и сами действия, которые позволят решить задачу в целом. В значительной степени, работа по интеллектуальному планированию сосредоточена на задачах, которые включают каскадные уровни выбора действия 22