Модели и технологии адаптивной обработки информации для частично наблюдаемых систем тема диссертации и автореферата по ВАК РФ 05.13.17, доктор технических наук Коновалов, Михаил Григорьевич

• Коновалов, Михаил Григорьевич
• доктор технических наук
• 2008

Оглавление диссертации доктор технических наук Коновалов, Михаил Григорьевич

ВВЕДЕНИЕ.

1. АНАЛИЗ ОБЛАСТЕЙ ПРИЛОЖЕНИЯ АДАПТИВНЫХ МЕТОДОВ ОБРАБОТКИ ИНФОРМАЦИИ.

1.1. инфотелекоммуниклционные системы.

1.1.1. Маршрутизация.

1.1.1.1. СЕТИ С КОММУТАЦИЕЙ КАНАЛОВ.

1.1.1.2. ШИРОКОПОЛОС11ЫЕ СЕТИ.

1.1.2. Управление потоками.

1.1.2.1. ШИРОКОПОЛОСНЫЕ ИНТЕГРИРОВАННЫЕ СЕТИ.

1.1.2.2. БЕСПРОВОДНЫЕ СОТОВЫЕ СЕТИ.

1.1.2.3. БЕСПРОВОДНЫЕ СПУТНИКОВЫЕ СЕТИ.

1.1.3. Разное.

1.1.3.1. РАСПРЕДЕЛЕННАЯ ВЫЧИСЛИТЕЛЬНАЯ СРЕДА.

1.1.3.2. ОПТИМИЗАЦИЯ СТРАТЕГИИ КЭШИРОВАНИЯ.

1.1.3.3. «АДАПТИВНЫЕ САЙТЫ».

1.1.3.4. КОНТРОЛЬ КАЧЕСТВА.

1.1.3.5. ОПТИМИЗАЦИЯ ВОСПРОИЗВЕДЕНИЯ ВИДЕОПАКЕТОВ.

1.1.3.6. АНАЛИЗ ПРОТОКОЛА IEEE 1394.

1.1.3.7. ПОДДЕРЖКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.

1.2. Производственные системы.

1.2.1. Технологические процессы.

1.2.1.1. ПРОИЗВОДСТВО И СБЫТ.

1.2.1.2. ПЛАНИРОВАНИЕ И ДИСПЕТЧЕРИЗАЦИЯ.

1.2.1.3. БАЛАНСИРОВКА ТЕХНОЛОГИЧЕСКИХ ЛИНИЙ.

1.2.1.4. СБОРОЧНЫЙ ПРОЦЕСС.

1.2.1.5. ГИБКОЕ АВТОМАТИЗИРОВАННОЕ ПРОИЗВОДСТВО.

1.2.1.6. ДРУГИЕ ПРИЛОЖЕНИЯ.

1.2.2. Техническое обслуживание.

1.2.3. Управление запасами.

1.3. Моделирование поведения, искусственный интеллект, роботы.

1.3.1. Искусственные модели.

1.3.2. Физические модели и прототипы реальных устройств.

1.3.2.1. ОБУЧЕНИЕ РОБОТА ХОДЬБЕ.

1.3.2.2. РОБОТЫ НА ПРОИЗВОДСТВЕ.

1.3.2.3. КОСМИЧЕСКИЙ ВЕЗДЕХОД.

1.3.2.4. ФУТБОЛ РОБОТОВ.

1.4. Разные приложения.

1.4.1. Теория расписаний и календарное планирование.

1.4.2. Системы массового обслуживания.

1.4.3. Другие приложения.

1.4.3.1. ПРОДАЖА БИЛЕТОВ АВИАКОМПАНИЯМИ. 1.4.3.2. РЕГУЛИРОВАНИЕ ПОПУЛЯЦИЙ.

1.4.3.3. ВЫБОР НАИЛУЧШЕГО АЛГОРИТМА.

1.4.3.4. ИГРЫ.

1.4.3.5. ДЕНЬГИ, ФИНАНСЫ.

1.4.3.6. СТАБИЛИЗАЦИЯ ЭНЕРГОСИСТЕМЫ.

1.4.3.7. ВОЕННЫЕ ПРИЛОЖЕНИЯ.

1.4.3.8. ПОИСК ЗАПИСЕЙ В ФАЙЛЕ.

1.4.3.9. РАСПОЗНАВАНИЕ ИЗОБРАЖЕНИЙ.

1.4.3.10. МЕХАНИЧЕСКИЕ СИСТЕМЫ.

2. ОСНОВНЫЕ МОДЕЛИ И СТРАТЕГИИ ОБРАБОТКИ ИНФОРМАЦИИ ДЛЯ ЧАСТИЧНО НАБЛЮДАЕМЫХ СИСТЕМ.

2.1. Основные определения.

2.1.1. Общая модель.

2.1.2. Стратегии.

2.1.3. Объекты.

2.1.4. Примеры.

2.2. Однородные стратегии конечной глубины.

3. АДАПТИВНАЯ СТРАТЕГИЯ ПЕРЕБОРА.

3.1. Основные определения.

3.2. Общая теорема.

3.3. Стратегия перебора для регенерируемых объектов.

3.4. Применение к частично наблюдаемым марковским цепям.

3.5. Применение к частично наблюдаемым графам.

4. ГРАДИЕНТНАЯ ОПТИМИЗАЦИЯ ПРЕДЕЛЬНОГО СРЕДНЕГО ДОХОДА НА МАРКОВСКИХ ЦЕПЯХ.

4.1. Определения, предположения и свойства.

4.2. Основная теорема.

4.3. Дополнительные свойства функции предельного дохода.

4.4. Другие представления формулы для частных производных целевой функции.

4.5. Градиентный алгоритм оптимизации функции предельного среднего дохода.

4.6. Распределенное принятие решений в условиях неполного наблюдения

4.7. Методы оценки градиента целевой функции.

4.7.1. Оценка по одному наблюдению.

4.7.2. Оценки «с остановками».

4.7.3. Оценки «сзабыванием».

4.7.4. Численный пример.

5. МЕТОДОЛОГИЯ АДАПТИВНОЙ ОБРАБОТКИ ИНФОРМАЦИИ И ПРИНЯТИЯ РЕШЕНИЙ НА ПРИМЕРЕ СИНТЕЗА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ МОДЕЛИРОВАНИЯ И УПРАВЛЕНИЯ МЕЖДУГОРОДНОЙ ТЕЛЕФОННОЙ СЕТЬЮ.

5.1. Общие положения методологии адаптивной обработки информации и принятия решений в частично наблюдаемых системах.

5.2. Основные аспекты организации трафика в цифровой сети с коммутацией каналов.

5.2.1. Общее описание проблемы.

5.2.2. Характеристика АСУ ЦС ОАО «Ростелеком».

5.2.3. Подсистема управления вторичной телефонной сетью.

5.2.4. Блок управления трафиком.

5.2.5. Объекты сети.

5.2.6. Требования к средствам управления качеством.

5.2.7. Команды управления трафиком.

5.2.8. Маршрутизация в блоке управления трафиком.

5.3. Эрланговская модель сети с коммутацией каналов.

5.3.1. Общие свойства модели.

5.3.2. Распределенный выбор маршрутов соединений.

5.3.3. Минимизация отказов.

5.4. Идентификация матрицы тяготения по результатам сетеметрии.

5.4.1. Предположения об измерениях и постановка задачи.

5.4.2. Общая схема алгоритма идентификации матрицы тяготения.

5.4.3. Расчет градиента целевой функции.

5.4.4. Численный пример.

5.5. Имитационная модель сети с коммутацией каналов.

5.5.1. Описание имитационной модели.

5.5.2. Основные понятия теории взаимодействующих процессов.

5.6. Обобщенные маршрутные таблицы и дополнительные управляющие воздействия.

5.6.1. Параметризация маршрутных таблиц.

5.6.2. Параметризация дополнительных управляющих воздействий.

5.7. Компьютерная реализация комплекса моделей управляемой цифровой сети с коммутацией каналов.

5.7.1. Структура данных.

5.7.2. Начальные данные.

5.7.3. Управляющие воздействия.

5.7.4. Основные процедуры блока имитации.

5.7.4.1. ФУНКЦИОНАЛЬНАЯ АРХИТЕКТУРА И СЦЕНАРИЙ РАБОТЫ БЛОКА ИМИТАЦИИ.

5.7.5.2. МОДУЛ bINIT.

5.7.5.3. МОДУЛЬ CALi.

5.7.5.4. МОДУЛИ SEND(p) И WR.

6. АДАПТИВНОЕ ПРИНЯТИЕ РЕШЕНИЙ В МОДЕЛИ РАСПРЕДЕЛЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СРЕДЫ.

6.1. Построение имитационной модели коллективного взаимодействия взаимно удаленных потребителей и распределенных вычислительных ресурсов.

6.1.1. Общее описание модели.

6.1.2. Формализация модели распределения ресурсов.

6.1.2.1. ПАРАМЕТРЫ МОДЕЛИ.

6.1.2.2. СОСТОЯНИЯ СИСТЕМЫ.

6.1.2.3. ОСНОВНЫЕ ПРОЦЕДУРЫ.

6.2. Постановка задачи и алгоритмы обработки информации для оперативного распределения ресурсов при неполной информации.

6.2.1. Выбор размера пакетов заданий и назначение ресурсов.

6.2.2. Конструкция адаптивной стратегии.

6.3. Экспериментальное исследование свойств адаптивных алгоритмов в модели системы распределенных вычислений.

6.3.1. Пример: один ресурс, один потребитель.

6.3.2. Пример: 10 потребителей, 5ресурсов.

6.3.3. Пример: неоднородный случай.

Введение диссертации (часть автореферата) на тему «Модели и технологии адаптивной обработки информации для частично наблюдаемых систем»

Актуальность темы исследования

Различные области науки и техники поставляют многочисленные задачи, для решения которых необходимо анализировать, оптимизировать, реализовывать взаимодействие субъекта с объектом в условиях недостаточной информации. Наибольшее количество подобного рода задач возникает в информационных и телекоммуникационных системах, автоматизированных производственных процессах, робототехнике, то есть в тех сферах, которые в наибольшей степени связаны с компьютерной обработкой информации.

Неполнота информации имеет двоякое качество. Во-первых, это (частичное) отсутствие априорной информации, даже на уровне представления о структуре объекта, и, во-вторых, ограниченная возможность наблюдения объекта и его идентификации. В предельном случае субъекту заранее известно лишь множество, из которого можно выбирать воздействия на объект, а неполнота наблюдений в неблагоприятных случаях означает, что субъект может лишь оценивать отклики объекта с точки зрения своего предпочтения. В подобных ситуациях первостепенное значение приобретает умение воспользоваться доступной информацией об объекте, в том числе, и главным образом, приобретенной в ходе взаимодействия с ним. Умение субъекта пользоваться для достижения цели информацией, поступающей в процессе функционирования, связано с такими понятиями, как «самоорганизация», «приспособление», «адаптация». Диссертационная работа посвящена преимущественно синтезу, анализу и применению адаптивных стратегий обработки информации.

Основополагающие идеи теории адаптации были заложены в 50-х годах прошлого века [177, 176], а становление теории и ее развитие до конца 80-х годов проходило во многом благодаря усилиям отечественных исследователей [190]. С начала 90-х годов и по настоящее время адаптивное направление переживает большой подъем, а число публикаций исчисляется многими сотнями. Выделилась и получила широкое распространение ветвь этого направления, которая обозначается плохо переводимым на русский язык словосочетанием «reinforcement learning» - «активное обучение». Этот раздел теории в значительной мере ориентирован на приложения и тесно связан с такой областью науки, как искусственный интеллект [193].

Становление теоретических основ адаптации далеко не закончено. Среди нерешенных основополагающих вопросов теории - вопрос о том, как далеко может простираться неведение об объекте и при этом сохраняться принципиальная возможность целесообразного взаимодействия с ним.

Углубившийся интерес к адаптивному направлению связан, помимо потребностей практики, с быстрым прогрессом в области информационных и телекоммуникационных технологий. Новые технологии позволили поставить на гораздо более реальную почву вопрос о практической реализации адаптивных алгоритмов, которые принципиально связаны с быстрой обработкой и передачей больших объемов оперативной информации.

Центральное место в теории адаптации занимает проблематика частично наблюдаемого марковского процесса принятия решений. Традиционный подход, основанный на динамическом программировании, дал результаты, применимые в адаптивном варианте [60, 81]. В то же время, как подчеркивают многие авторы и о чем свидетельствует большой поток публикаций, необходим дальнейший прогресс в этой области, имеющей неоспоримое прикладное значение. «Марковские процессы являются в настоящее время математическим фундаментом для многих работ в области активного обучения (reinforcement learning), теории принятия решений, поиска информации, распознавания речи, активного зрительного восприятия, навигации роботов» [159].

Марковский процесс принятия решений (в другой терминологии управляемые марковские цепи с доходами) с момента их появления и укоренения в научном обиходе заняли одно из центральных мест в ряде областей науки. Причина этого в выразительной способности и универсальности терминологического и понятийного аппарата, а также в плодотворности усилий по решению оптимизационных задач. Первоначальный период характеризовался тем, что исследования были сосредоточены почти исключительно на методах динамического и линейного программирования, причем, главным образом, в постановках задач с полной информацией. Это направление продолжает достаточно интенсивно развиваться. Многочисленные обобщения сделаны в направлении все более сложных пространств состояний и действий, а также постановок задач с новыми целевыми функциями.

Достаточно скоро появилось понимание, что «классическое» направление в теории марковского процесса принятия решений не обеспечивает потребности ее применения на практике. Во-первых, модели реальных систем, как правило, включают слишком большое число состояний, и созданные алгоритмы, хотя и решали формально задачу, но не справлялись с большой размерностью. Созданию более эффективных алгоритмов для задач с полной информацией было уделено и продолжает уделяться много внимания. Второй аспект заключается в необходимости изучения задач с неполным наблюдением. Наконец, третий фактор связан с предположением о наличии полной априорной информации о переходных матрицах. Это предположение справедливо лишь для модельных примеров и для сравнительно узкого класса практических приложений.

Исследования, излагаемые в диссертационной работе, направлены, в частности, на преодоление трудностей, связанных с практическим воплощением теории. Особое внимание в этой связи уделяется изучению градиентного подхода в марковском процессе принятия решений, который появился позже других методов. Первые из известных нам работ этого направления (например, [104]) скорее «обозначали желание» двигаться по градиенту, чтобы оптимизировать целевую функцию, и не дали конструктивных алгоритмов. Основная формула для градиента была, видимо, впервые, опубликована в [21], и там же был указан путь ее использования, в том числе в условиях неполного наблюдения и распределенного характера взаимодействия. Начиная примерно с середины 90-х годов, за рубежом появилось много публикаций и много глубоких результатов, связанных с градиентным подходом [73, 160]. Исследования, которые излагаются в диссертационной работе, проводились независимо.

В целом, развиваемое в диссертационной работе адаптивное направление лежит в русле фундаментальных исследований, как адаптивного, так и не адаптивного характера, в области статистической информатики [37, 199]. Стремительный прогресс в области информационных и телекоммуникационных технологий позволил поставить на гораздо более реальную почву вопрос о практической реализации стохастических алгоритмов, которые принципиально связаны с быстрой обработкой и передачей больших объемов оперативной информации.

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

Цель и задачи исследования

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

Прежде чем приступать к взаимодействию с неким процессом, и имея в виду поставленную цель, желательно составить стратегию (алгоритм, программу, план.), которая определит все дальнейшее поведение субъекта. Подчеркнем этот важный момент: стратегия, как понимается это слово в настоящее время, составляется (или появляется откуда-то у субъекта) до начала взаимодействия с объектом. И стратегия, вообще говоря, отнюдь не предписывает заранее и жестко, что, как и когда делать, оставляя для решений некоторый выбор, который, возможно, сильно сузится в момент их принятия за счет накопленной информации или случайно сложившихся обстоятельств.

Построение стратегии базируется на априорной модели объекта, которая в свою очередь включает в себя априорную информацию об объекте. Легко можно представить ситуацию, когда такая информация не полна или даже вовсе отсутствует (пресловутый «черный ящик»).

Имеются еще обстоятельства, которые фактически могут быть приравнены к отсутствию априорной информации. В некоторых случаях субъект имеет достаточно сведений для составления адекватной модели объекта, но не может воспользоваться этим, потому что, попросту говоря, не знает, как это сделать. (Шахматная игра, как процесс чередования позиций и ходов, полностью определяется небольшим количеством правил, однако до сих пор не удалось создать беспроигрышную стратегию игры, хотя на этом пути многое сделано.) Кроме того, иногда, и даже 9 довольно часто, проблема использования модели связана не только с «неумением», а и с тем, что теоретический рецепт нельзя воплотить на практике, например, из-за большой размерности.

Диссертационная работа посвящена проблеме построения стратегий поведения для субъекта в условиях, когда априорная информация об объекте минимальна. В предельном случае субъекту заранее известно лишь множество, из которого можно выбирать воздействия на объект. Первостепенное значение приобретает возможность приобретения информации об объекте в ходе взаимодействия с ним и, главное, умение использовать ее для достижения цели. В этом смысле следует говорить о стратегиях обработки информации.

Умение субъекта пользоваться для достижения цели информацией, поступающей в процессе функционирования, связано с такими понятиями, как «самоорганизация», «приспособление», «адаптация». Поэтому мы говорим об адаптивных стратегиях обработки информации.

Дополнительным фактором, который осложняет целенаправленное поведение субъекта, является неполнота наблюдений. В самых неблагоприятных случаях субъект может лишь оценивать отклики объекта с точки зрения своего предпочтения («лучше» - «хуже»). В этих случаях объект является лишь частично наблюдаемым, и его идентификация, по крайней мере, полная идентификация - невозможна.

Сформулируем окончательно цель исследований, которая заключается в разработке теоретических основ анализа, синтеза и применения стратегий адаптивной обработки информации и принятия решений в условиях неполного наблюдения.

При проведении исследований были поставлены следующие основные задачи.

1. Разработка теоретических основ синтеза адаптивных стратегий в общих моделях частично наблюдаемых объектов.

2. Изучение класса частично наблюдаемых управляемых однородных марковских цепей. Разработка для этого класса простых, эффективных и универсальных адаптивных алгоритмов, позволяющих решать задачи большой размерности.

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

4. Реализация комплекса действий, связанных с синтезом информационных технологий для моделирования, адаптивной обработки информации и принятия решений на примере крупных прикладных проблем.

Методика исследования.

Методика и средства исследования различны для перечисленных выше задач.

Основным аппаратом для формулировки и изучения общих теоретических вопросов (задача 1) является математическая теория адаптации, которая в значительной мере опирается на теорию вероятностей, стохастический анализ и теорию случайных процессов. Применяются специфические методы теории адаптивного управления, в частности, применяется перебор на счетном множестве вариантов в сочетании известной в теории адаптации идеей «средних времен».

Для решения задачи 2 широко используется теория счетных цепей Маркова. Привлекается и развивается теория марковского процесса принятия решений для случая неполного наблюдения, счетного множества состояний и конечного множества действий. Методом исследования является прямой анализ свойств функции предельного среднего дохода и нахождение аналитических выражений для градиента этой функции. Основная схема синтеза адаптивной стратегии выглядит как алгоритм проекции градиента. Для анализа градиентных алгоритмов привлекается математическое программирование. Для оценки градиента по результатам наблюдений используются рекуррентные схемы, позволяющие «забывать» далекую часть траектории процесса.

Задача 3 решается на основе обзора литературы, посвященной конкретным приложениям, анализу моделей прикладных объектов и указанию взаимосвязи конкретных постановок с разработанной в диссертации теорией.

Задача 4 решена применительно к междугородной телефонной сети, для которой синтезируется информационная технология моделирования и оптимизации трафика. На разных этапах этого синтеза используются: анализ технологических особенностей организации трафика в сети с коммутацией каналов; аналитическая модель «эрланговского» типа; аналитическая модель оценки матрицы тяготения по результатам сетевых измерений;

- имитационное моделирование на основе аппарата теории взаимодействующих процессов;

- параметризация маршрутных таблиц и дополнительных управляющих воздействий;

- адаптивные алгоритмы, разработанные при решении задач 1 и 2;

- компьютерная реализация моделей с использованием объектно-ориентированного языка Delphi.

Методика, использованная для моделирования и оптимизации трафика в междугородной телефонной сети, применена также для моделирования и оптимизации ресурсов в распределенной вычислительной среде.

В обоих указанных случаях синтезированные технологии используются для проведения вычислительных экспериментов с целью проверки свойств адаптивных стратегий.

Краткое содержание работы

Заключение диссертации по теме «Теоретические основы информатики», Коновалов, Михаил Григорьевич

ЗАКЛЮЧЕНИЕ. РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

1. Результаты в области теоретических основ адаптивной обработки информации и принятия решений в условиях неполного наблюдения.

1.1. Построена общая модель взаимодействия субъекта с частично наблюдаемым, априори неизвестным объектом в виде управляемой случайной последовательности общего вида. Формализованы понятия объекта и стратегии (субъекта).

1.2. Дано определение класса регенерируемых объектов, который включает конечные частично наблюдаемые управляемые марковские цепи. Доказано, что для любого объекта из этого класса существует детерминированная однородная стратегия конечной глубины, которая является равномерно (относительно начального распределения) е-оптимальной (по отношению к максимизации предельного среднего дохода).

1.3. Предложена конструкция адаптивной стратегии, основанной на идее «средних времен» и на переборе счетного множества вариантов (стратегия перебора). Стратегия перебора не использует априорную информацию об объекте.

1.4. Доказано, что стратегия перебора способна взаимодействовать с произвольным, априори неизвестным объектом не хуже, чем (неизвестная) наилучшая стратегия из произвольного заданного счетного множества стратегий.

1.5. Доказано, что стратегия перебора (на счетном множестве детерминированных однородных правил конечной глубины) обеспечивает максимально возможный предельный средний доход 1) для произвольного регенерируемого объекта, 2) для произвольной однородной конечной управляемой связной марковской цепи.

1.6. Доказано, что стратегия перебора обеспечивает для произвольного управляемого графа (с неизвестной структурой переходов и с неизвестным числом ненаблюдаемых вершин) предельный средний доход, равный тому максимально возможному, который можно получить в условиях полной информированности.

2. Результаты в области адаптивной обработки информации в марковском процессе принятия решений.

2.1. Получен ряд свойств функции предельного среднего дохода в марковском процессе принятия решений со счетным множеством состояний.

2.2. Получены точные формулы градиента функции предельного среднего дохода для наблюдаемого и ненаблюдаемого распределенного марковского процесса принятия решений со счетным множеством состояний.

2.3. Предложена градиентная адаптивная стратегия для марковского процесса принятия решений с конечным множеством состояний и доказаны ее оптимизационные свойства.

2.4. Предложен способ построения асимптотически состоятельных оценок градиента целевой функции по результатам наблюдений в марковском процессе принятия решений.

3. Результаты в области практических приложений

3.1. Изучены возможности практического использования теории и указаны объекты приложений в областях инфотелекоммуникаций, производственных систем, искусственного интеллекта и других.

3.2. Разработана методология синтеза информационных технологий моделирования и адаптивной обработки информации для широкого класса систем с неполным наблюдением.

3.3. Разработана технология синтеза и реализации эффективных алгоритмов адаптивного принятия решений.

3.4. Решена проблема оперативного управления трафиком в телекоммуникационной сети с коммутацией каналов. Разработана совокупность моделей и информационных технологий для оперативной адаптивной обработки информации в сети с коммутацией каналов.

3.4.1. Построена эрланговская модель управляемой сети с коммутацией каналов, в ее рамках поставлена и решена задача минимизации средних потерь в сети.

3.4.2. Разработаны модель и технология восстановления матрицы тяготения по результатам сетеметрии.

3.4.3. Построена имитационная модель трафика в сети связи с коммутацией каналов, написанная на языке параллельных процессов.

3.4.4. Дана трактовка модели управляемой сети с коммутацией каналов как управляемой марковской цепи с доходами. В этой трактовке введено и формализовано понятие обобщенных маршрутных таблиц, а также формализовано применяемое в практике телефонных сетей понятие «управляющих воздействий». Разработаны технологии адаптивной коррекции маршрутных таблиц и дополнительных решающих правил.

3.4.5. Создана программная система, моделирующая управляемую сеть с коммутацией каналов. В ней реализованы информационная модель управляемой цифровой телефонной сети, а также адаптивные алгоритмы оптимизации маршрутных таблиц и выбора дополнительных решающих правил.

3.4.6. Получены результаты вычислительных экспериментов с моделью, для которой входными данными явились параметры междугородной телефонной сети России.

3.5. Создана информационная технология моделирования системы распределенных вычислений.

3.5.1. Построена информационная модель коллективного взаимодействия взаимно удаленных потребителей и распределенных вычислительных ресурсов.

3.5.2. Поставлена и решена задача адаптивного оперативного распределения ресурсов при неполной информации.

3.5.3. Экспериментально исследованы свойства адаптивных алгоритмов в модели системы распределенных вычислений.

Список литературы диссертационного исследования доктор технических наук Коновалов, Михаил Григорьевич, 2008 год

1. Антонов С. В., Душин Ю. А., Коновалов М. Г., Шоргин С. Я. Разработка математических моделей и методов распределения заданий в системе распределённых вычислений // "Системы и средства информатики". Выпуск 16. Москва. Наука. 2006 г. С. 32-46.

2. Антонов С. В., Захаров В. Н., Коновалов М. Г., Соколов И. А., Шоргин С. Я. Информационные технологии моделирования и динамического управления в многоуровневых сетях коммутации каналов // Наукоемкие технологии, № 4. 2003. - С.70-78.

3. Антонов С. В., Захаров В. Н., Коновалов М. Г., Шоргин С. Я. Комплексная модель цифровой телефонной сети и алгоритмы динамического управления // Системы и средства информатики. Вып. 11. М.: Наука, 2001. - С. 68-77.

4. Антонов С. В., Коновалов М. Г., Соколов И. А., Супрун А. П., Шоргин С. Я. Программные средства моделирования работы сетей с ретрансляцией кадров. Свидетельство об официальной регистрации программы для ЭВМ № 980363, РосАПО, 1998.

5. Байхельт Ф., Франкен П. Надежность и техническое обслуживание. М.: Радио и связь, 1988.

6. Гихман И. И., Скороход А. В. Теория случайных процессов. Т. 1. -М.: Наука, 1971.

7. Душин Ю. А. Модель оценки стоимости гетерогенных ресурсов в Грид // Системы и средства информатики: Спец. вып. Математические модели в информационных технологиях. М.: ИПИ РАН. - 2006. - С. 163-172.

8. Карманов В. Г. Математическое программирование. М.: Наука, 1975.

9. Кемени Д., Снелл Дж., Кнепп А. Счетные цепи Маркова. М.: Наука, 1987.

10. Коваленко В., Коваленко Е., Корягин Д. и др. Управление заданиями в распределенной вычислительной среде // Открытые системы. 2001. № 5-6. С. 22-28.

11. Коваленко В., Корягин Д. Эволюция и проблемы Grid // Открытые системы. 2003. №1. С. 27-33.

12. Коновалов М. Г. Об адаптивном управлении некоторыми классами марковских цепей // Доклады АН СССР. Т. 233, № 5. - 1977. - С. 780-783.

13. Коновалов М.Г. Адаптивное управление периодическими процессами с независимыми значениями // Известия АН СССР. Техническая кибернетика, № 1. 1979. - С. 138-144.

14. Коновалов М. Г. Адаптивная маршрутизация в сети связи с коммутацией каналов // В сб. «Всесоюзная конференция «Теория адаптивных систем и ее применение». 1983.

15. Коновалов М. Г. Об адаптивной маршрутизации в сети связи с коммутацией каналов // Известия АН СССР. Техническая кибернетика, № 3. 1984. - С. 152-155.

16. Коновалов М.Г. Адаптивное управление конечными автоматами с ненаблюдаемыми состояниями // Доклады АН СССР. Т. 291, № 1. - 1986. - С. 59-62.

17. Коновалов М.Г. Метод перебора в адаптивном управлении случайными процессами с дискретным временем. М.: ВЦ АН СССР. — 1989. - 25 с.

18. Коновалов М. Г. Об управлении в сетях с коммутацией пакетов. М.: ВЦ АН СССР.- 1989.-40 с.

19. Коновалов М. Г. Параллельные процессы и имитационное моделирование сетей связи // В сб.: XLVII научная сессия, посвященная Дню Радио. М. 1992.

20. Коновалов М. Г. Адаптивный алгоритм маршрутизации для сетей передачи данных с коммутацией пакетов // В сб.: XLVII научная сессия, посвященная дню Радио. М. 1992.

21. Коновалов М. Г. Опыт моделирования сети передачи данных на языке параллельных процессов // Математическое моделирование. Т. 5, № 2. - 1993. - С. 82-93.

22. Коновалов М. Г. Управляемые марковские последовательности и оптимизация маршрутных таблиц в сетях связи с коммутацией каналов // В сб. «Системы и средства информатики», вып. 11. М.: Наука, 2001 - С. 78-93.

23. Коновалов М. Г. Экспериментальное сравнение некоторых алгоритмов маршрутизации в сетях с коммутацией каналов на примере сети Клоза // Системы и средства информатики. Вып. 13.-2003.-С. 106-121.

24. Коновалов М. Г. Некоторые свойства функции предельного среднего дохода в задаче управления марковскими цепями // Вестник РУДН, серия Прикладная и компьютерная математика. Т. 3, № 1. - 2004. - С. 61-77.

25. Коновалов М. Г. Об оценках градиента функции предельного среднего дохода в марковском процессе принятия решений // В сб. «Системы и средства информатики», вып. 14. М.: Наука, 2004. - С. 68-85.

26. Неве Ж. Математические основы теории вероятностей. М.: Мир, 1969.

27. Попов М. // СЮ, N 2. 2005.

28. Прохоров Ю. В., Розанов Ю. А. Теория вероятностей. -М.: Наука, 1973.

29. Пугачев В. С., Синицын И. Н. Теория стохастических систем. М.: Изд. Логос.2004.

30. Топорков В. В. Модели распределенных вычислений. М.: Физматлит, 2004.

31. Хоар Ч. Взаимодействующие последовательные процессы. М.: Мир, 1989.

32. Экспериментальный GRlD-сегмент МГУ им. М.В. Ломоносова: Руководство для пользователей, http://www.parallel.ru/info/education/msugrid-intro.doc.

33. Akar N., Sahin С. Reinforcement learning as a means of dynamic aggregate QoS provisioning // LNCS 2698. 2003. - P. 100-114.

34. Ash G. R., Cardwell R. H., Murray R. Design and optimization of networks with dynamic routing // Bell System Technical Journal, 60. -1981. P. 1787-1820.

35. Barto A. G., Mahadevan S. Recent advances in hierarchical reinforcement learning // Discrete event dynamic systems: theory and applications, 13. — 2003. — 13 — P. 343-379.

36. Bartolini N. Handoff and optimal channel assignment in wireless networks // Mobile Networks and Applications, 6. 2001. - P. 511-524.

37. Beetz M. Chapter 5: Learning structured reactive navigation plans // Lecture Notes in Computer Science, 2554. 2002. - P. 125-146.

38. Belker Т., Beetz M. Learning to execute navigation plans // Lecture Notes in Computer Science, 2174.-2001.

39. Belker Т., Beetz M., Cremers A. B. Learning action models for the improved execution of navigation plans // Robotics and Autonomous Systems, 38. 2002. - P. 137-148.

40. Berenguer C., Chu C., Grail A. Inspection and maintenance planning: an application of semi-Markov decision processes // Journal of Intelligent Manufacturing, 8. 1997. - P. 467— 476.

41. Berman F, High-performance scheduling // The Grid: blueprint for a new computing infrastructure. Eds. I. Foster, C. Kesselman. San Francisco: Morgan Kaufmann. 1999. - P. 279307.

42. Berman F., Wolski R. Scheduling from the perspective of the application // Proc. of Symposium on High Performance Computing. 1996. -http://grail.sdsc.edu.

43. Berman 0„ Kim E. Dynamic order replenishment policy in internet-based supply chains // Math Meth Oper Res, 53. 2001. - P. 371-390.

44. Berman O., Sapna K. P. Optimal control of service for facilities holding inventory // Computers & Operations Research, 28. 2001. - P. 429^141.

45. Bertsekas D. P. Dynamic programming and optimal control, V. 1,2. Belmont: Athena Scientific, 2001.

46. Bianchi, R. Costa A. Comparing distributed reinforcement learning approaches to learn agent coordination // LNAI, 2527. 2002. - P. 575-584.

47. Blair C., Monahan G. E. Optimal sequential file search: a reduced-state dynamic programming approach // European Journal of Operational Research, 86. 1995. - P. 358-365.

48. Braun T. D., Siegel H. J., Beck N. Comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems // Parallel and Distributed Computing. 2001.

49. Brouns G. A. J. F., Van der Wal J. Optimal threshold policies in a workload model with a variable number of service phases per job // Math. Meth. Oper. Res., 53. 2003. - P, 483-501.

50. Bruns P. Optimality of randomized strategies in a Markovian replacement model // Math Meth Oper Res, 56. 2002. - P. 481-499.

51. Cai K.-Y. Optimal software testing and adaptive software testing in the context of software cybernetics // Information and Software Technology, 44. 2002. - P. 841-855.

52. Cao X.-R. A unified approach to Markov decision problems and performance sensitivity analysis // Automatica 36. 2000. P. 771-774.

53. Cao X.-R. Basic ideas for event-based optimization of markov systems // Discrete Event Dynamic Systems: Theory and Applications, 15. 2005. - P. 169-197.

54. Cao X.-R. From perturbation analysis to Markov decision processes and reinforcement learning // Discrete Event Dynamic Systems: Theory and Applications, 13. 2003. - P. 9-39.

55. Cao X.-R. Introduction to the special issue on learning, optimization, and decision making in DEDS // Discrete Event Dynamic Systems: Theory and Applications, 13. 2003. - P. 7-8.

56. Cao X.-R. Perturbation analysis of discrete event systems: concepts, algorithms, and applications // European Journal of Operational Research, 91. 1996. - P. 1-13.

57. Cao X.-R. Single sample path-based optimization of Markov chains // Journal of optimization theory and applications. -V. 100, N. 3. 1999. - P. 527-548.

58. Cao X.-R. The Relations Among potentials, perturbation analysis, and markov decision processes // Discrete Event Dynamic Systems: Theory and Applications, 8. 1998. - P. 71-87.

59. Cao X.-R., Chen H. F. Perturbation realization, potentials and sensitivity analysis of-Markov processes, IEEE Trans. Automat. Control 42. 1997. - P. 1382-1393.

60. Cao X.-R., Fu M. C., Hu J.-Q. On performance potentials and conditional Monte Carlo for gradient estimation for Markov chains // Annals of Operations Research 87. 1999. - P. 263-272.

61. Cao X.-R., Ren Z., Bhatnagar S., Fu M., Marcus S. A time aggregation approach to Markov decision processes // Automatica, 38. -2002. P. 929-943.

62. Casanova H., Legrand A., Zagorodnov D. et al. Heuristics for scheduling parameter sweep applications in Grid environment // Proc. of the 9th Heterogeneous Computing Workshop. -2000.-P. 349-363.

63. Chang B.-J., Hwang R.-H. Efficient hierarchical QoS routing in ATM networks // Computer Communications, 24. -2001. P. 1648-1660.

64. Chang H., Givan R., Chong E. Parallel rollout for online solution of partially observable Markov decision process // Discrete Event Dynamic Systems: Theory and Applications, 14. -2004.-P. 309-341.

65. Chang H. S., Fu M. C., Hu J., Marcus S. I. Simulation-based algorithms for Markov decision Processes. London: Springer, 2007.

66. Chang X., Subramanian K. R. A cooperative game theory approach to resource allocation in wireless ATM networks. Lecture Notes in Computer Science, 1815. 2000.

67. Chang Y. W., Geraniotis E. Optimal policies for handoff and channel assignment in networks of LEO satellites using CDMA // Wireless Networks, 4. 1998. - P. 181-187.

68. Chen M., Feldman R. M. Optimal replacement policies with minimal repair and age-dependent costs // European Journal of Operational Research, 98 1997. - P. 75-84.

69. Cheng Y., Robertazzi T. Distributed computation for a tree network with communication delays // IEEE Trans. On Aerospace and Electronic Systems. 1988. - V. 24(6). - P. 700712.

70. Chung S.-P., Ross K. W. Reduced load approximations for multirate loss networks, IEEE Transactions on Communications, 41. 1993. - P. 1222-1231.

71. Daws C., Kwiatkowska M., Norman G. Automatic verification of the IEEE 1394 root contention protocol with KRONOS and PRISM // International Journal on Software Tools for Technology Transfer, 5. 2004. - P. 221-236.

72. De Nitto P. V., Grassi V. Optimal access control for integrated services wireless networks // Computer Communications, 21 1998. - P. 1559-1570.

73. Dean Т., Kaelbling L. P., Kirman J., Nicholson A. Planning under time constraints in stochastic domains // Artificial Intelligence, 76. 1995. - P. 35-74.

74. Dekker R., Roelvink I. F. K. Marginal cost criteria for preventive replacement of a group of components // European Journal of Operational Research, 84. 1995. - P. 467-480.

75. Dekker R., Wildeman R. E., Van Egmond R. Joint replacement in an operational planning phase // European Journal of Operational Research, 91. 1996. - P. 74-88.

76. Dellaert N. P., Melo M. T. Approximate solutions for a stochastic lot-sizing problem with partial customer-order information // European Journal of Operational Research, 150. -2003. P. 163-180.

77. Dellaert N.P., Melo M.T. Production strategies for a stochastic lot-sizing problem with constant capasity // European Journal of Operational Research, 92. 1996. - P. 281-301.

78. Dietz D.S., Rosenshine M. Optimal specialization of a maintenance workforce // IIEj

79. Transactions, 29. 1997. - P. 423^133.

80. Do Val J.B.R., Salles J.L.F. Optimal production with preemption to meet stochastic demand // Automatica, 35. 1999. - P. 1819-1828.

81. Draper B.A., Ahlrichs U., Paulus D. Adapting object recognition across domains: a demonstration // Lecture Notes in Computer Science, 2095. 2001.

82. Draper B.A., Bins J., Baek K. ADORE: Adaptive object recognition // Lecture Notes in Computer Science, 1542. 1999.

83. Drouin N., Gautier A., Lamond B. F., Lang P. Piecewise affine approximations for the control of a one-reservoir hydroelectric system // European Journal of Operational Research, 89. -1996.-P. 53-69.

84. Duenyas I., Patana-Anake P. Base-stock control for single-product tandem make-to-stock systems // HE Transactions, 30. 1998. - P. 31-39.

85. Duenyas I., Tsai C.-Y. Control of a manufacturing system with random product yield and downward substitutability // HE Transactions, 32. 2000. - P. 785-795.

86. Dziong Z., Mason L. G. Call admission and routing in multi-service loss networks, IEEE Transactions on Communications, 42. 1994. - P. 2011-2022.

87. Economou A. On the control of a compound immigration process through total catastrophes // European Journal of Operational Research, 147. 2003. - P. 522-529.

88. Eilam T. et al. A utility computing framework to develop utility systems // IBM System Journal. 2004. - V. 43(1). P. - 97-120.

89. El-Fattah Y. M. Gradient approach for recursive estimation and control in finite Markov chains // Adv. Appl. Probab., 13. 1981. - 778-803.

90. Esogbue A. O., Hearnes W. E. A learning algorithm for the control of continuous action Set-point regulator systems // Journal of Computational Analysis and Applications, V.l, N.2.-1999.

91. Ferch M., Zhang J. Learning cooperative grasping with the graph representation of a state-action space // Robotics and Autonomous Systems, 38. 2002. - P. 183-195.

92. Fleischmann M., Kuik R. On optimal inventory control with independent stochastic item returns // European Journal of Operational Research, 151 2003. - P. 1, 25-37.

93. Foster Я. What is the Grid? The three criteria. http://www.gridclub.ru/library/publication.2004-ll-29.5830756248/publfile.

94. Foster I., Kesselman C., Tuecke S. The anatomy of the Grid: enabling scalable virtual organizations // Int. Journal of High Performance Computing Applications. 2001. - V. 15. № 3. - P. 200-222.

95. Fujimoto N., Hagihara K. Near-optimal dynamic task scheduling of precedence constrained coarse-grained tasks onto a computational Grid // Proc. of ISPDC 2003, Ljubljana, Slovenia, October 2003.

96. Gallego G., Ни H. Optimal policies for production/inventory systems with finite capacity and Markov-modulated demand and supply processes // Annals of Operations Research, 126.-2004.-P. 21-41.

97. Gel E.S., Hopp W.J., Van Oyen M.P. Factors affecting opportunity of work sharing as a dynamic line balancing mechanism // HE Transactions, 34. 2002. - P. 847-863.

98. Givan R., Chong E. K. R. Parallel rollout for online solution of partially observable Markov decision processes // Discrete Event Dynamic Systems: Theory and Applications, 14. — 2004.-P. 309-341.

99. Givan R., Leach S., Dean T. Bounded-parameter Markov decision processes // Artificial Intelligence, 122. 2000. - P. 71-109.

100. Glazebrook K. D. Stochastic scheduling and forwards induction // Discrete Applied Mathematics, 57. 1995. - P. 145-165.

101. Goldman R. P., Musliner D. J., Krebsbach K. D. Managing online self-adaptation in real-time environments // Lecture Notes in Computer Science, 2614. 2003. - P. 6-23.

102. Gosavi A. A reinforcement learning algorithm based on policy iteration for average reward: empirical results with yield management and convergence analysis // Machine Learning, 55.-2004.-P. 5-29.

103. Gosavi A., Bandla N., Das Т. K. A reinforcement learning approach to a single leg airline revenue management problem with multiple fare classes and overbooking // HE Transactions, 34. 2002. - P. 729-742.

104. Grolknann A., Poli R. Learning a navigation task in changing environments by multitask reinforcement learning // LNAI, 1812. 2000. - P. 23-43.

105. Hamilton M. D., McKee P., Mitrani I. Optimal caching policies for Web objects // Lecture Notes in Computer Science, 2110. 2001.

106. Hamscher V., Schwiegelshohn U., Streit A., Yahyapour R. Evaluation of job-scheduling strategies for Grid computing // LNCS, 1971. 2000. - P. 191- 202.

107. Hariharan R., Moustafa M. S., Stidham Jr. S. Scheduling in a multi-class series of queues with deterministic service times // Queueing Systems, 24. 1996. - P. 83-99.

108. Hinderer К., Waldmann K.-H. Cash management in a randomly varying environment // European Journal of Operational Research, 130. 2001. - P. 468-485.

109. Hontelez J. A. M., Burger H. H., Wijnmalen D. J. D. Optimum condition-based maintenance policies for deteriorating systems with partial information // Reliability Engineering & System Safety, 51. 1996. - P. 267-274.

110. Howard R. A. Dynamic programming and Markov processes. NewYork: Wiley,1960.127. http://www-cse.ucsd.edu/users/berman/apples.html.128. http://www.globus.org/research/papers/.129. http://www.nas.nasa.gov/.

111. Hwang R.-H. Adaptive multicast routing in multirate loss networks // Telecommunication Systems, 12. 1999. - P. 283-313.

112. Iakovou E., Ip С. M., Koulamas C. Machining economics with phase-type distributed tool lives and periodic maintenance control // Computers & Operations Research, 23. 1996. -P. 53-62.

113. Iakovou E., Ip С. M., Koulamas C. Throughput-dependent periodic maintenance policies for general production units // Annals of Operations Research, 91.- 1999. P. 41-47.

114. Iravani S. M. R., Duenyas I. Integrated maintenance and production control of a deteriorating production system // HE Transactions, 34. 2002. - P. 423-435.

115. Ishii S., Yoshida W., Yoshimoto J. Control of exploitation-exploration meta-parameter in reinforcement learning // Neural Networks, 15. 2002. - P. 665-687.

116. Johansen S. G., Larsen C. Computation of a near-optimal service policy for a single-server queue with homogeneous jobs // European Journal of Operational Research, 134. — 2001. P. 648-663.

117. Keblis M. F., Duenyas I. Control of an assembly system with processing time and sub-assembly-type uncertainty // The International Journal of Flexible Manufacturing Systems, 11,-1999.-P. 353-370.

118. Kelly F. P. Routing in circuit switched networks: Optimization, shadow prices and decentralization // Advances in Applied Probability, 20. 1988. - P. 112-144.

119. Kim E. Stochastic vendor managed replenishment with demand dependent shipment // European Journal of Operational Research, 152. 2004. - P. 723-744.

120. Kim E., Van Oyen M. P. Finite-capacity multi-class production scheduling with set-up times // HE Transactions, 32. 2000. - P. 807-818.

121. Kirchner F., Hertzberg J. A prototype study of an autonomous robot platform for sewerage system maintenance // Autonomous Robots, 4. 1997. - P. 319-331.

122. Konovalov M. G. Management controls in telephone networks // 3 Московская международная конференция по исследованию операций (ORM2001). Москва, 4-6 апреля 2001.-С. 57-58.

123. Konovalov М., Shorgin S., Saverio S. Problems of GRID systems modeling. — Transactions of XXV International Seminar on Stability Problems for Stochastic Models. Maiori (Salerno), Italy, September 20-24,2005. P. 309.

124. Kristensen A. R., Jorgensen E. Multi-level hierarchic Markov processes as a framework for herd management support // Annals of Operations Research, 94. 2000. - P. 69-89.

125. Kuri J., Kumar A. On the optimal control of arrivals to a single queue with arbitrary feedback delay // Queueing Systems, 27. 1997. - P. 1-16.

126. Kyriakidis E. G. Optimal control of a simple immigration-birth-death process through total catastrophes // European Journal of Operational Research, 81. 1995. - P. 346-356.

127. Kyriakidis E. G. Optimal control of a simple immigration-emigration process through total catastrophes // European Journal of Operational Research, 155. 2004. - P. 198-208.

128. Kyriakidis E. G. Optimal pest control through the introduction of a predator // European Journal of Operational Research, 81. 1995. - P. 357-363.

129. Lagoudakis M. G., Parr R., Littman M. L. Least-squares methods in reinforcement learning for control // LNAI, 2308. 2002. - P. 249-260.

130. Lamond B. F., Lang P. Lower bounding aggregation and direct computation for an infinite horizon one-reservoir model // European Journal of Operational Research, 95. 1996. - P. 404-410.

131. Laoutaris N., Boukeas G., Stavrakakis I. Design of optimal playout schedulers for packet video receivers // Lecture Notes in Computer Science, 2156. 2001.

132. Laoutaris N., Stavrakakis I. An analytical design of optimal playout schedulers for packet video receivers // Computer Communications, 26. 2003. - P. 294-303.

133. Laroche P. GraphMDP: A new decomposition tool for solving Markov decision processes // International Journal on Artifical Intelligence Tools, 10, No. 3. 2001. - P. 325-343.

134. Lee Т. E., Lee J.-H. A two-phase approach for design of supervisory controllers for robot cells: Model checking and Markov decision models // Annals of Operations Research, 77. 1998.-157-182.

135. Li H., Baras J. S. A framework for supporting intelligent fault and performance management for communication networks // Lecture Notes in Computer Science, 2216. 2001.

136. Li H., Dagli С. H. Hybrid least-squares methods for reinforcement learning // LNAI 2718.-2003.-P. 471-480.

137. Love С. E., Zhang Z.G., Zitron M. A., Guo R. A discrete semi-Markov decision model to determine the optimal repair/replacement policy under general repairs // European Journal of Operational Research, 125. 2000. - P. 398^109.

138. Luh H., Rieder U. Optimal control of arrivals in tandem queues of constant service time //Math Meth Oper Res. 53. -2001. P. 481—491.

139. Mahadevan S. Average reward reinforcement learning foundations, algorithms, and empirical results // Machine Learning, 22. 1996. - P. 159-195.

140. Mahadevan S. Spatiotemporal abstraction of stochastic sequential processes // Lecture Notes in Computer Science, 2371. 2002.

141. Marbach P., Tsitsiklis J.N. Approximate gradient methods in policy-space optimization of markov reward processes // Discrete Event Dynamic Systems: Theory and Applications, 13.-2003.-P. 111-148.

142. Menache I., Shie Mannor S., Shimkin N. Q-Cut Dynamic discovery of sub-goals in reinforcement learning // LNAI, 2430. - 2002. - P. 295-306.

143. Merke A., Riedmiller M. Karlsruhe Brainstormers A reinforcement learning approach to robotic soccer // Lecture Notes in Computer Science, 2377. — 2002.

144. Morisset В., Ghallab M. Learning how to combine sensory-motor modalities for a robust behavior // Lecture Notes in Computer Science, 2466. 2002. - P. 157-178.

145. Munos R. A study of reinforcement learning in the continuous case by the means of viscosity solutions H Machine Learning, 40. 2000. - 265-299.

146. Munos R., Moore A. Variable resolution discretization in optimal control // Machine Learning, 49. 2002. - P. 291-323.

147. Nobel R. D., Tijms H. C. Optimal control for an Mx/G/1 queue with two service modes // European Journal of Operational Research, 113. 1999. P. 610-619.

148. Pendrith M. D. Reinforcement learning in situated agents: theoretical problems and practical solutions // LNAI 1812. 2000. - P. 84-102.

149. Price В., Boutilier C. Imitation and reinforcement learning in agents with heterogeneous actions // LNAI 2056. 2001. - P. 111 - 120.

150. Puliti P., Tascini G, Montesanto A. Reactive navigation using reinforcement learning in situations of POMDPs // LNCS 2085. 2001. - P. 444^150.

151. Ranganathan K., Foster I. Decoupling computation and data scheduling in distributed data-intensive applications //The 11th IEEE Int. Symposium on High Performance Distributed Computing: Proc. Edinburgh, Scotland. 2002.

152. Ravindran В., Barto A. G. Model minimization in hierarchical reinforcement learning // Lecture Notes in Computer Science, 2371. 2002.

153. Recommendation E.412 (10/92). Telephone network and ISDN. Quality of service, network management and traffic engineering. Network management controls. ITU, 1993.

154. Regan P. J., Pate-Cornell M. E. Normative engineering risk management systems // Reliability Engineering & System Safety, 57. 1997. - P. 159-169.

155. Reiman M.I., Shwartz A. Call admission: a new approach to quality of service // Queueing Systems 38. 2001. - P. 125-148.

156. Ribeiro C. Reinforcement learning agents // Artificial Intelligence Review, 17. 2002. -P. 223-250.

157. Robbins M. A sequential decision problem with a finite memory // Proc. Nat. Acad. Sci. USA. V. 42, N 3. - 1956.

158. Robbins H., Monro S. A stochastic approximation method // Ann. Math. Stat. V. 22. -1951.-P. 400^407.

159. Sahin I., Zahedi F. Control limit policies for warranty, maintenance and upgrade of software systems // HE Transactions, 33. 2001. - P. 729-745.

160. Sahin I., Zahedi F. Optimal policies under risk for changing software systems based on customer satisfaction // European Journal of Operational Research, 123. 2000. - P. 175— 194.

161. Schoknecht R., Riedmiller M. Reinforcement learning on explicitly specified time scales // Neural Comput & Applic, 12. 2003. - P. 61-80.

162. Schoknecht R., Riedmiller M. Speeding-up reinforcement learning with multi-step actions // LNCS 2415. 2002. - P. 813- 818.

163. Senkul S., Polat F. Learning intelligent behavior in a non-stationary and partially observable environment // Artificial Intelligence Review, 18. 2002. - P. 97-115.

164. Senouci S.-M., Beylot A.-L., Pujolle G. Call admission control for multimedia cellular networks using neuro-dynamic programming // Lecture Notes in Computer Science, 2345. -2002.

165. Shan H., Oliker L., Biswas R. Job superscheduler architecture and performance in computational Grid environments // Proc. of the 2003 ACM/IEEE conference on Supercomput-ing. -2003. P. 44.

166. Shao G., Wolski R., Berman F. Performance effects of scheduling strategies for master/slave distributed applications // UCSD CSE Technical Report CS98-598. University of California, San Diego. 1998.

167. Sloan T.W., Shanthikumar J.G. Using in-line equipment condition and yield information for maintenance scheduling and dispatching in semiconductor wafer fabs // IIE Transactions, 34.-2002.-P. 191-209.

168. Smith W., Foster I., Taylor V. Predicting application run times using historical information // Lecture Notes on Computer Science. 1998. - Vol. 1459. - P. 122-142.

169. Smith W., Wong P. Resource selection using execution and queue wait time predictions // NAS Technical Report. NAS-02-003. 2002. 7 p.

170. Sohn J., Robertazzi T. G., Luryi S. Optimizing computing costs using divisible load analysis // IEEE Trans. Parallel and Distributed Systems. 1998. - V. 9, N. 3, - P. 225-234.

171. Sragovich V. G. Mathematical theory of adaptive control. Singapore: World Scientific, 2006.

172. Sun R., Sessions C. Automatic segmentation of sequences through hierarchical reinforcement learning // LNAI 1828. 2000. - P. 241-263.

173. Sutton R., Barto A. Reinforcement learning. MIT Press, 2000.

174. Tadepalli P., Ok D. Model-based average reward reinforcement learning // Artifical Intelligence, 100. 1998. - P. 177-224.

175. Tannenbaum Т., Wright D., Miller K., Livny M. Condor A distributed job scheduler // Beowulf Cluster Computing with Linux, The MIT Press, MA, USA, 2002.

176. Tesauro G. J. TD-Gammon, a self-teaching backgammon program, achieves master-level play, Neural Computation, 6. 1994. - P. 215-219.

177. Thickins G. Utility Computing: The next new IT model // Darwin Magazine. April2003.

178. Tong H., Brown Т. X. Reinforcement learning for call admission control and routing under quality of service constraints in multimedia networks // Machine Learning, 49. 2002. — P. 111-139.

179. Unsupervised adaptive filtering. V. 1,2. Edited by S. Haykin. New York: John Willey & Sons, Inc, 2000.

180. Vadhiyar S., Dongarra J. A metascheduler for the Grid // Proc. of the 11th IEEE Symposium on High-Performance Distributed Computing. 2002. — P. 343-351.

181. Van der Schouten D., Vanneste S.G. Mainetance optimization of a production system with buffer capacity // European Journal of Operational Research, 82. 1995. - P. 323-338.

182. Wijnmalen D. J. D., Hontelez J. A. M. Coordinated condition-based repair strategies for components of a multi-component maintenance system with discounts // European Journal of Operational Research, 98. 1997. - P. 52-63.

183. Williams В. К. Adaptive optimization of renewable natural resources: Solution algorithms and a computer program // Ecological Modelling, 93. 1996. - P. 101-111.

184. Wuest С. C., Verhaegh W. F. J. Quality control for scalable media progressing applications // Journal of Scheduling, 7. 2004. - P. 105-117.

185. Xiaobo Z., Ohno K., Nakade K. An optimal cart moving policy for a flexible manufacturing system // IEE Transactions, 34. 2002. - P. 34, 41-50.

186. Xiaobo Z., Ohno K., Nakade K. Modeling for flexible manufacturing systems and structural properties of optimal work routing policy // Journal of Intelligent Manufacturing, 8. -1997.-P. 497-503.

187. Yao D. D., Zheng S. Sequential quality control in batch manufacturing // Annals of Operations Research, 87. 1999. - P. 3-30.

188. Yoshimoto J., Ishii S., Sato M. System identification based on online variational Bayes method and its application to reinforcement learning // LNCS, 2714. 2003. - P. 123— 131.

189. Yu J., Buyya R., Tham С. K. A cost-based scheduling of scientific workflow applications on utility Grids // In 1st IEEE International Conference on e-Science and Grid Computing, Melbourne, Australia, Dec. 5-8, 2005.

190. Zheng S. Dynamic release policies for software systems with a reliability constraint // HE Transactions, 34. 2002. - P. 253-262.

191. Zhu J., Hong J., Hughes J. G. Using Markov chains for link prediction in adaptive Web sites // Lecture Notes in Computer Science, 2311. 2002.

192. Zilberstein S., Washington R., Bernstein D. S., Mouaddib A.-I. Decision-theoretic control of planetary rovers // Lecture Notes in Computer Science, 2466. 2002. - P. 270-289.