4

МОДЕЛИ И АЛГОРИТМЫ ОБЕСПЕЧЕНИЯ ГАРАНТИРОВАННОГО ВРЕМЕНИ РЕШЕНИЯ ЗАДАЧ СИСТЕМАМИ, ОСНОВАННЫМИ НА ЗНАНИЯХ

И. В. Котенко

Университет связи, г.Санкт-Петербург, E-mail: ivkote@robotek.ru

Abstract – The paper describes the models and algorithms for maintenance of guaranteed time of the design and development planning of telecommunications systems. These models and algorithms are developed for assurance of the timeliness, design validity and controllability requirements. They are intended for the design technology management and adaptive formation of the rational sequence of design and use for each separate design process of the most acceptable models and algorithms allowing to obtain the decision for allocated time with required (or maximum achievable) validity.

1. Введение

В качестве критерия решения задач (РЗ) системами реального времени, в т.ч. системами реального времени, основанными на знаниях (СРВОЗ), как правило, служит критерий достижения наилучшего качества (обоснованности) вырабатываемых вариантов решений за отведенное время имеющимся ресурсом сил и средств. Поэтому одним из важнейших требований к таким системам является обеспечение гарантированного времени РЗ [1].

Основываясь на результатах в области "интеллектуального управления в реальном масштабе времени", например, [2 - 8 и др.], а также на полученных автором результатах в области построения интеллектуальных автоматизированных систем поддержки принятия решений при проектировании и планировании использования телекоммуникационных систем [1], в работе предлагаются обобщенные модели и алгоритмы, необходимые для обеспечения требований своевременности, обоснованности и управляемости процессов формирования вариантов решений. Эти модели и алгоритмы предназначены для реализации компонента, управляющего технологией РЗ (КУТРЗ), способного адаптивно выбирать (формировать) рациональную последовательность выполняемых автоматизированных процессов (задач) и для каждого отдельного процесса или процедуры реализовывать наиболее приемлемые модели и алгоритмы, позволяющие получать решения в рамках отведенного времени с требуемым (или максимально достижимым) качеством.

В отличие от автоматических решателей задача построения такого компонента для рассматриваемого класса СРВОЗ является существенно более сложной проблемой вследствие использования человеко-машинных процедур принятия решений, в которых главную роль выполняют лица, принимающие решения (ЛПР), а средства автоматизации реализуют, как правило, функцию информационной и вычислительной поддержки принятия решений (хотя в СРВОЗ и предусматривается режим автоматического решателя, при котором ЛПР только выбирают решения из совокупности альтернатив или "утверждают" вариант решения, полученный СРВОЗ).

2. Общая модель удовлетворения временных ограничений

Общую модель удовлетворения временных ограничений (УВО) при РЗ с использованием СРВОЗ зададим в виде: TC=<U_п, T_п^д, R, M_п, S_СРВОЗ, T_СРВОЗ, RA>, где U_п - множество условий РЗ, T_п^д={t_п^k} - временные ограничения (ВО) на РЗ (t_п^k - допустимое время выполнения k-го этапа, k=1,...,N, N - количество этапов РЗ); R={r_l^t} - вычислительные ресурсы СРВОЗ (r_l - количество ресурсов l-го типа в момент времени t); M_п={m_i} - модели реализации процессов, задач и процедур, учитывающие условия их выполнения, состав привлекаемых сил и средств и т.п.; S_СРВОЗ=({s_j},p) - структура модулей СРВОЗ (s_j - j-й модуль СРВОЗ, p - отношение порядка, заданное на иерархии модулей), позволяющих реализовать M_п посредством традиционных и основанных на знаниях процедур, обладающих различной вычислительной сложностью, точностью, определенностью и полнотой учета различных факторов и т.д.; T_СРВОЗ={t_s
j} - профили модулей СРВОЗ (ожидаемые временные затраты при использовании {s_j}); RA: U_п?T_п^д?R? T_СРВОЗ®M_п?S_СРВОЗ - правила выбора моделей и модулей СРВОЗ.

Рассматриваемый подход требует, чтобы КУТРЗ мог “рассуждать” о своих целях, состоянии реализуемого процесса и планах достижения целей из исходного состояния. Способность определения планов необходима не только для распознавания, может ли быть получено ожидаемое решение за отведенное время, но и для оценивания альтернативных путей РЗ, а также проведения экспресс-оценки возможности получения решения, находясь в текущем состоянии в изменившихся условиях. Если грубая оценка времени получения наилучшего возможного решения превышает ВО, КУТРЗ должен провести модификацию своих планов и реализовать "сокращенную" (приближенную) модель РЗ и (или) совокупность "сокращенных" или приближенных процессов и процедур РЗ, называемых аппроксимациями (Ап), которые приводят к компромиссу между качеством решений и необходимым для выполнения временем.

Реализация механизмов УВО предполагается на трех уровнях: 1) уровне сквозной модели решения общей задачи, предписывающей последовательность выполнения отдельных процессов; 2) уровне отдельных процессов; 3) уровне реализации конкретных процедур и задач.

В качестве основных подходов к УВО предлагается использовать 1) "гибкие" и 2) контрактные вычисления [2-8]. Первый подход применим для реализации отдельных процедур и заключается в получении сначала грубого РЗ, а затем использования оставшегося времени для улучшения этого решения. Такой подход основывается на использовании "гибких" вычислений или anytime-алгоритмов, т.е. алгоритмов, приводящих к решению за любое время [2]. Выполнение этих алгоритмов может быть прервано в любой момент, причем к моменту прерывания обеспечивается получение определенного результата, качество которого возрастает с ростом предоставляемого времени. Второй подход может быть использован как на глобальном, так локальном (уровне отдельных процессов, процедур, задач) уровнях, и заключается в формировании (выборе) плана и включении в него необходимых аппроксимаций [4].

Качество формируемых решений, может быть определено посредством следующих показателей: а) достоверности обрабатываемой информации; б) полноты P=f/f₀ обрабатываемой информации (где f - число учтенных факторов, f₀ - число факторов, которое необходимо рассмотреть); в) обоснованности O₁=v/v₀ (или O₂=o/o₀) решений (где v - число учтенных вариантов, v₀ - число вариантов, которое необходимо рассмотреть, o - объем переработанной информации, o₀ - объем информации, необходимый для принятия решения с заданным качеством); г) точности решений и др.

Повышение своевременности может быть достигнуто посредством снижения качества решений по следующим показателям: 1) достоверности обрабатываемой информации (путем использования лишь "грубых" процедур повышения достоверности информации или отказа от их применения); 2) полноте обрабатываемой информации (посредством игнорирования или неполного учета некоторых подцелей, условий, требований, ограничений); 3) обоснованности решений (если некоторые варианты решений анализируются с меньшей глубиной проработки или отбрасываются без оценивания, не рассматривается ряд поддерживающих или отвергающих отдельные элементы решений факторов, показатели и критерии выбора решений не адаптируются к сложившейся ситуации и т.п.); 4) точности решений (за счет приближенного определения вариантов решений) и др. Важно отметить взаимозависимость различных показателей качества решений, что усложняет получение компромиссных решений.

3. Механизмы управления удовлетворением временных ограничений

Обобщенный алгоритм управления РЗ и УВО выполняется в виде непрерывного цикла и состоит из следующих шагов: 1) выбор, генерация и (или) модификация модели (плана) РЗ; 2) прогнозирование требуемого для РЗ времени и параметров качества формируемых вариантов решений; 3) определение, будет ли выполнено РЗ за отведенное время и будут ли варианты решений удовлетворять заданным требованиям. Если ответ - отрицательный, выполняется переход на шаг 5; 4) выполнение РЗ в соответствии с выбранной моделью. Динамическое прогнозирование и отслеживание времени, требуемого для завершения процессов РЗ, и показателей качества формируемых вариантов решений (для сравнения текущих и спрогнозированных значений). В случае расхождения значений - переход на шаг 3. Иначе - завершение алгоритма; 5) идентификация состояния РЗ и выбор (генерация) наиболее приемлемой Ап модели РЗ, его отдельных процессов, процедур и задач. Переход на шаг 2.

Для реализации данного алгоритма КУТРЗ должен обеспечивать следующие основные механизмы: 1) распознавание необходимости применения Ап (выполняется на шагах 2 и 3); 2) выбор (генерация) приемлемых Ап (для шагов 1 и 5); 3) выполнение выбранной Ап (на шаге 4).

1. Распознавание необходимости применения Ап заключается в определении невозможности УВО при использовании полной модели процесса РЗ и, следовательно, необходимости применения Ап, а также выявлении невозможности УВО при применении текущих Ап и переходе к более приближенным моделям. Данный механизм обеспечивается за счет: а) генерации (выбора) плана РЗ (на шагах 1 и 5); б) оценки времени, необходимого для выполнения этого плана, и показателей качества вариантов решений (на шаге 2); в) мониторинга РЗ (на шаге 4), заключающегося в отслеживании выполнения плана РЗ, анализа состояний реализуемого процесса (на шагах 4 и 5) и при необходимости (в случае изменения ситуации) коррекции плана или выбора другого плана (на шаге 5).

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

3. Выполнение выбранной Ап. При переходе от использования полных моделей РЗ к "приближенным" возможно применение различных типов Ап. Предлагается использовать таксономию Ап: 1) "сокращенные" модели всего процесса РЗ, предусматривающие РЗ не в полном объеме; 2) "сокращенные" модели отдельных процессов; 3) "сокращенные" (приближенные) способы выполнения отдельных процедур и решения отдельных задач РЗ. Эти Ап могут быть выполнены за счет: а) традиционных ("жестких") алгоритмов различной вычислительной сложности; б) приближенных стратегий поиска (при использовании "мягких" средств, основанных на знаниях), позволяющих исследовать сокращенное пространство вариантов решений; в) приближенных (обобщенных) данных, обеспечивающих более абстрактный взгляд на необходимые для учета при РЗ факторы, позволяя задействовать упрощенные пространство поиска решений и механизмы вычислений; г) приближенных знаний, упрощающих применяемые в расчетных, логических и эвристических процедурах знания (например, посредством отказа от использования "глубинных" и перехода к "поверхностным" знаниям), так что пространство поиска исследуется быстрее.

4. Модели и алгоритмы выполнения процессов в реальном времени

Шаг выполнения процессов РЗ (шаг 4 обобщенного алгоритма управления РЗ и УВО) является центральной фазой РЗ. Для реализации РЗ важно обеспечить выполнение двух процессов: 1) реализацию отображений между хранимыми и исполняемыми представлениями планов РЗ; 2) собственно управление выполнением РЗ.

Представление, используемое для задания планов РЗ в виде сценариев или прецедентов, не является подходящим для автоматизированного РЗ. Для эффективной реализации процессов РЗ КУТРЗ должен преобразовать зафиксированные в плане выражения в команды для выполнения СРВОЗ и сообщения для проектировщиков. Может потребоваться также обратная трансляция для фиксации реализованных планов в виде прецедентов и сценариев. Поэтому КУТРЗ должен реализовывать три вида отображений: а) отображение плана (модели) РЗ из хранимого формата (в виде прецедента или сценария) в операционное представление (в виде записей действий), используемое КУТРЗ для реализации РЗ; б) отображение последовательности записей действий в трассу выполнения, реализуемое в процессе РЗ; в) отображение трассы выполнения в представление прецедента или сценария для фиксации в базе прецедентов или моделей.

5. Заключение

Решения по построению КУТРЗ опробовались на аналитических и имитационных моделях, а также в результате экспериментов с реализованными прототипами РЗ проектирования и планирования использования телекоммуникационных систем. Для оценки эффективности процессов проектирования в качестве существенных свойств были выбраны: своевременность, обоснованность, управляемость и трудоемкость. Оценка показателей этих свойств проводилась для случаев реализации традиционной технологии и различных вариантов предлагаемой технологии проектирования. Проведенная оценка эффективности позволила сделать вывод, что предложенные средства КУТРЗ, задействующие совокупность многовариантных гибридных моделей реализации процессов, процедур и задач и специальные механизмы выбора и (или) генерации этих моделей, а также выполнения процессов РЗ в реальном времени, позволяют реализовать РЗ за отведенное время с наилучшим возможным качеством.

Литература

Котенко И.В. Теория и практика построения автоматизированных систем информационной и вычислительной поддержки процессов планирования связи на основе новых информационных технологий. СПб.: ВАС, 1998. 404 с.

Boddy M., Dean T.L. Deliberation Scheduling for Problem Solving in Time-Constrained Environments // Artificial Intelligence, 1994, V.67, N 2. P.245-285.

Garvey A., Lesser V. A Survey of Research in Deliberative Real-Time Artificial Intelligence // Journal of Real-Time Systems, 1994, V.6, N 3. P.317-347.

Lesser V.R., Pavlin J., Durfee E. Approximate Processing in Real-Time Problem Solving // AI Magazine, 1988, V.9, N 1. P.49-61.

Zilberstein S., Charpillet F., Chassaing P. Real-Time Problem-Solving with Contract Algorithms // Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI 99, Stockholm. Morgan Kaufmann, 1999. P.1008-1015.

Zilberstein S., Mouaddib A.-I. Reactive Control of Dynamic Progressive Processing // Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI 99, Stockholm. Morgan Kaufmann, 1999. P.1268-1273.

Hansen E.A., Zilberstein S. Monitoring the Progress of Anytime Problem-Solving // Proceedings of the 13th National Conference on Artificial Intelligence. Portland, Oregon. August 1996. AAAI.

Zilberstein S. Using anytime algorithms in intelligent systems // AI Magazine, 1996, V.17, N 3. P.73-83.

Site of Information Technologies
Designed by inftech@webservis.ru.