Труды КНЦ (Технические науки вып. 7/2023(14))

For citation: Zuenko A. A., Fridman O. V. Reasoning with temporal constraints // Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2023. Vol. 14, No. 7. P. 43-51. doi:10.37614/2949-1215.2023.14.7.005. Введение В настоящее время существует большой интерес к разработке систем планирования, которые нацелены на решение практически значимых задач. Отходя от чисто иллюстративных областей, характерных для ранних работ (см. пример задачи планирования из мира блоков (для трех блоков), описанный в п. 3), исследователи обращаются к широкому кругу вопросов, включая рассуждения в неопределенных мирах, взаимодействие с процессами и событиями, находящимися вне прямого контроля агента, и управление механизмами в режиме реального времени. Одна из проблем, возникающих при расширении существующих подходов, — слабая выразительность отображения действий и событий внешнего мира. В связи с вышеизложенным, в течение последних двадцати лет рассуждения с темпоральными ограничениями являются актуальной темой исследований. Важность этой темы была признана во многих областях компьютерных наук и искусственного интеллекта, например, в планировании [1], составлении расписаний [2], понимании естественного языка [3], представлении знаний [4], пространственно-временных базах данных и географических информационных системах [5], базах данных ограничений [6], медицинских информационных системах [7], компьютерной верификации [8], мультимедийных презентациях [9] и т. п. Темпоральные рассуждения — это область, которая значительно выиграла от применения методов программирования в ограничениях, начиная с ранних работ Джеймса Ф. Аллена и др. [10-20]. Программирование с временными ограничениями (Temporai Constraint Programming — TCP) является одной из ключевых техник в поиске решений. В работе [21] Джеймс Ф. Аллен предложил 13 основных отношений между временными интервалами, которые являются различными, исчерпывающими и качественными: • различные, потому что никакая пара определенных интервалов не может быть связана более чем одним из отношений; • исчерпывающие, поскольку любая пара определенных интервалов описывается одним из соотношений; • качественные (а не количественные), потому что не учитываются числовые промежутки времени. Эти отношения и операции над ними образуют интервальную алгебру Аллена. Интервальная алгебра Аллена Тринадцать основных отношений Аллена приведены на рис. 1. Показаны все возможные отношения, которые могут иметь два определенных интервала. Каждое из них графически задается диаграммой, связывающей два определенных интервала а и b. Например, на первой диаграмме показано, что «а предшествует b» означает, что а заканчивается до того, как начинается b, и их разделяет промежуток; вторая диаграмма показывает, что «а встречается с b» означает, что b начинается, когда заканчивается а. Шесть пар отношений являются обратными. Например, обратное «а предшествует b» — это «b предшествует а»; всякий раз, когда верно некоторое отношение, верно и его обратное отношение. На рисунке 1 обратные отношения обозначены прописными буквами. Каждая пара символов обратного отношения состоит из строчных и прописных букв одной и той же буквы. Обычно отношения перечисляют в таком порядке: ( pmoFDseSdfOMP ). Временные отношения между двумя событиями могут быть представлены как элементы булеана множества pmoFDseS dfOMp. Каждое из основных отношений, представленных на рис. 1, является отношением, как и все их комбинации. Полное отношение ( pmoFDseSdfOMp) имеет место между двумя интервалами, о которых ничего не известно. Пустое отношение () является результатом некоторых операций над интервальными отношениями и необходимо для подалгебр интервальной алгебры Аллена. Рассмотрим некоторые операции над отношениями, которые используются при построении планов. Пересечение (п). Пересечение ( r n s ) двух отношений (r) и (s) является их теоретико-множественным пересечением; это отношение, состоящее из всех основных отношений, которые принадлежат как r, так и s. Труды Кольского научного центра РАН. Серия: Технические науки. 2023. Т. 14, № 7. С. 43-51. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2023. Vol. 14, No. 7. P. 43-51. © Зуенко А. А., Фридман О. В., 2023 44