Обработка отношений непересекаемости интервалов времени

И. Е. КУРИЛЕНКО

Московский энергетический институт (технический университет)

ОБРАБОТКА ОТНОШЕНИЙ НЕПЕРЕСЕКАЕМОСТИ ИНТЕРВАЛОВ ВРЕМЕНИ

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

Разработка систем временных рассуждений (СВР), реализующих механизм временных рассуждений, решающе важна для современных интеллектуальных систем [1]. В [2, 3] изложен подход к построению СВР на основе точечной модели времени как независимого программного модуля и рассматривается вопрос расширения языка CLIPS возможностью учета фактора времени. На практике при разработке правил удобнее использовать не точечную модель времени, а интервальную. К сожалению ORD-Horn подкласс интервальной алгебры, поддержка которого предусмотрена в рассматриваемой СВР, не содержит отношений неперекрываемости интервалов времени представление которых необходимо для решения задач планирования. К примеру, планируемые действия часто не могут быть назначены одновременно, потому что они конкурируют за одни и те же ресурсы (оборудование, дороги, инструменты и т. п.). Возможность рассуждений о неперекрывающихся во времени действиях или событиях важно и для понимания естественного языка. В связи с этим актуальной является задача построения подклассов интервальной и интервально-точечной алгебр содержащих отношения неперекрываемости и не содержащих отношений задающих порядок. Такие подклассы должны позволять представлять информацию о том, что определенный момент времени (возможно мгновенное действие или начало и конец действия) не должен принадлежать определенному интервалу (в течение которого выполняется другое действие или интервалу между двумя действиями). Такие временные ограничения важны, к примеру, для нелинейного планирования, где предыдущие действия могут назначаться для выполнения предусловий последующих и между ними не должны назначаться действия, которые могут нарушить эти предусловия. Рассмотрим возможность расширения точечной модели времени новыми типами ограничений, позволяющими задавать отношение неперекрываемости. Для четырех элементов u, v,w, z частично упорядоченного множества (по отношению <) определим два трехточечных ограничения - <, и два четырехточечных ограничения , (1-4). Отношения u< и u соответствуют строгому и нестрогому исключению момента времени u из интервала ограниченного w и v. Отношения и соответствуют строгому и нестрогому непересечению интервалов (u,v) и (w,z). Если заменить отношение < в одном из дизъюнктов в определении < и более слабым отношением , то может быть получено еще четыре типа ограничений (5-8).

Отношения u< и u соответствуют строгому исключению момента времени u из интервала (w и v] и [w и v) соответственно. Если ослабить ограничение <, накладываемое на моменты времени, образующие интервал в определениях < и , заменив его на отношения или , то могут быть получены еще 12 типов ограничений (u<,u,u<,u,u<,u,,,,,,). Все 20 отношений временной неперекрываемости представимы с помощью бинарных дизъюнкций в точечной алгебре. Изложенные [2, 3] алгоритмы для поиска согласующего сценария с использованием техники предварительного анализа и опережающего рассмотрения позволяют добиться приемлемого по времени решения задач на временную неперекрываемость средней размерности.

Список литературы

1.  Поспелов знаний о времени и пространстве в интеллектуальных системах / Под ред. . М.: Наука, 1986.

2.  , Куриленко временных рассуждений для интеллектуальных систем поддержки принятия решений реального времени // Программные продукты и системы. №2. 2005. С. 4-163.

3.  , Куриленко системы временных рассуждений со средой CLIPS // труды конференции «Информационные технологии» (IEEE AIS`05).

4.  Куриленко быстродействия алгоритмов временных рассуждений для качественной точечной модели времени // тезисы докладов конференции МИФИ 2006.