Содержание к диссертации
Введение
1. Аналитический обзор возможных способов построения программных средств обучения и управления интеллектуальными транспортными устройствами 16
1.1. Описание области исследования 16
1.2. Анализ общей структуры программной системы управления интеллектуальным устройством 19
1.3. Методы представления знаний в программных системах управления транспортными устройствами 23
1.4. Построение планирующих систем в программах управления транспортными устройствами 30
1.5. Обучение с подкреплением. Основные понятия 32
1.5.1 Интерфейс программная система обучения и управления (ПСОиУ) - среда 32
1.5.2 Цель, вознаграждение, полное вознаграждение 33
1.5.3 Функция стоимости. Рациональная функция стоимости 37
1.6 Постановка задачи исследования 41
1.7 Выводы и результаты 43
2. Методы обучения и управления с подкреплением для работы в изменяющихся условиях 45
2.1 Метод полного программирования 46
2.1.1 Оценка политики 47
2.1.2. Улучшение политики 49
2.1.3 Итерация политик 52
2.1.4 Итерация функции стоимости 53
2.2 Методы обучения на основе эксперимента 54
2.2.1. Оценка политики 55
2.2.2 Управление методом на основе эксперимента 57
2.2.3 Алгоритм управления методами на основе эксперимента в политике 59
2.2.4 Алгоритм управления методами на основе эксперимента вне политики 60
2.3 Методы временных разностей 64
2.3.1 Оценка политики алгоритмом временных разностей 64
2.3.2 Управление методам временных разностей в политике 66
2.3.3 Управление методом временных разностей вне политики 68
2.4 Выводы и результаты 69
3. Применение методов обучения с подкреплением, к обучению автоматизированного самоходного агрегата 71
3.1 Цели создания модели АСА 72
3.2 Реализация модели 74
3.2.1 Состави содержание модели 74
3.2.2 Блочная структура модели. Основные параметры и переменные модели. Согласованное взаимодействие блоков программы в процессе моделирования 78
3.2.3 Блок обучения и реализации движения АСА 85
3.2.4 Реализация блока обучения на основе
алгоритма обучения на эксперименте 88
3.2.5 Реализация блока обучения на основе алгоритма временных разностей 99
3.2.6 Блок сценария движения по заранее заданной траектории 108
3.3. Анализ результатов моделирования. Оценка эффективности обучения 110
3.4 Выводы и результаты 122
Заключение 123
Литература
- Анализ общей структуры программной системы управления интеллектуальным устройством
- Обучение с подкреплением. Основные понятия
- Итерация функции стоимости
- Блочная структура модели. Основные параметры и переменные модели. Согласованное взаимодействие блоков программы в процессе моделирования
Введение к работе
Создание автоматизированных производств предполагает автоматизацию не только физического, но и интеллектуального труда человека. Для выполнения труднопрограммируемых операций приходится создавать комбинированные человеко-машинные комплексы, в которых управляющее воздействие при решении не запрограммированных задач принимает человек. Однако, во многих областях деятельности присутствие человека нежелательно или невозможно. К ним можно отнести атомную энергетику, космические .исследования, работу в удаленных регионах. Дополнительно задача усложняется тем, что работа устройств протекает в неизвестных условиях, которые могут изменяться. В этой связи, на стадии проектирования и разработки не представляется возможным реализация полной программы работы такого устройства, которое должно демонстрировать интеллектуальное поведение.
Таким образом, актуальной научной задачей является исследование и разработка алгоритмов и программного обеспечения, позволяющих организовать работу автономных технических устройств в изменяющихся условиях, а также проверка разработанных алгоритмов.
В данной работе ставилась задача охватить круг вопросов, связанных с программным управлением автономными транспортными устройствами, движение которых осуществляется за счет перемещения его отдельных частей в заданном направлении движения.
Основные исследования, которые проведены в рамках представленной работы, можно свести к трем направлениям :
1 .Представление знаний и работа с ними. Это - создание специализированных алгоритмов и программных компонентов для представления и накопления знаний в ЭВМ, а также алгоритмов для их преобразования. Проведены исследования по созданию специальных методов, позволяющих пополнять и обобщать знания, хранимые в машине.
2.Планирование целесообразного поведения. Исследования по созданию алгоритмов формирования целей и решения задач планирования действий транспортного устройства для достижения цели, функционирующего в изменяющихся условиях.
3.Исследования по накоплению и обобщению информации, алгоритмов ее обработки и способов адаптации программной системы управления к среде функционирования путем обучения.
Работа посвящена методам построения программных систем управления и обучения транспортных технических устройств.
Основной задачей программной системы управления подобными устройствами является выработка последовательности действий для достижения заранее определенной цели. Таким образом, программа представляет собой планирующую систему, которая, исходя из условий задачи и условий работы устройства, автоматически строит план, или последовательность действий, приводящих устройство в целевое состояние.
Такая последовательность не является единственной. Программа должна обладать способностью принимать решения о выборе плана, возможно, рационального по некоторым критериям [58,61].
Таким образом, основными задачами программной системы автономного устройства являются:
1. Накопление и корректировка знаний на основе восприятия информации об условиях работы и обобщенного опыта.
2. Целенаправленное поведение на основе накопленных знаний для достижения цели.
Необходимо отметить, что рассматриваемый класс устройств обладает возможностью совершать различные виды действий в процессе своей работы. При этом, в зависимости от условий работы устройство может находиться в различных ситуациях, связанных с положением относительно местности работы и внутреннего расположения узлов и механизмов самого устройства, что определяет множество возможных состояний пары среда-устройство. Поскольку условия работы могут изменяться или быть не полностью известны, то возникает задача выбора в каждом из возможных состояний одного из действий таким образом, чтобы данный выбор обеспечивал достижение целевого положения некоторым рациональным образом.
Под изменяющимися условиями автор понимает необходимость изменения выбора одного из возможных действий в каждом из состояний с точки зрения достижения целевого положения рациональным образом.
Программная система управления устройством должна уметь оценить состояние, в котором находится управляемое устройство, выбрать нужное действие для данного состояния. Данный выбор должен осуществляться на основе обучения или сбора информации программой управления.
Таким образом, возникают задачи построения методик и алгоритмов программных средств управления транспортными устройствами, основным функциональным назначением которых являются:
1. Оценка состояния пары среда-устройство управления.
2. Выбор реализуемого действия для определенного программой состояния.
3. Построение последовательности действий с целью достижения целевого положения.
4. Сбор информации или обучение для реализации рационального поведения механизма.
Задачи построения программных планирующих систем рассматривались многими авторами. Упомянем в этой связи имена Попова Э.В., Фридмана Г.Р., Скурихина В.И., Feigenbaum Е.А., McCorduck М.С., Winston P.N., Mitchell Т.М., Sutton R.S., Quinlan J.R.
Задачи построения программных систем обучения и управления трудно поддаются обобщению и классификации. В настоящее время сформировалось три направления в теории обучения. Первый - на основе символьного представления информации, второй - на основе связей и третий основан на принципах генетики или эволюционной теории.
Первый из подходов к обучению сводится к явному представлению в системе знаний об области определения решаемой задачи. На основе своего опыта обучаемая система строит или модифицирует выражение на формальном языке и сохраняет эти знания для последующего использования. Символьные подходы строятся на предположении, что основное влияние на поведение системы оказывают знания об области определения в их явном представлении. К числу наиболее известных программных систем символьного представления знания можно отнести системы LEX [Mitchel Т.М.], ID3 [Quinlan J.R.], Meta-Dendral [Mitchel T.M.], COB-WEB [Fisher D.H.].
Нейронные сети, или сети связей, обучаются на основе символьного языка. Знания программы не явно представлены в общей организации и взаимодействии этих нейронов. Нейронные сети обучаются не за счет добавления новой информации в базу знаний, а за счет модификации своей общей структуры в ответ на получаемую извне информацию. Можно выделить модели Кохонена [Kohonen Т. ] и Хехта-Нильсена [Hecht-Nielsen R.] и конкурентные методы их обучения, алгоритм обучения Хебба [Невв D.O.].
Эмерджентный подход к обучению, основанный на адаптации, отражен в генетических алгоритмах, генетическом программировании и исследовании искусственной жизни. [Conway J.H., Brooks R.A., Holland J.H.]
Машинное обучение - это обширная область исследований, охватывающая большое количество проблем и алгоритмов их решения. Эти алгоритмы различаются своими задачами, исходными данными, стратегиями обучения и способами представления знаний. Однако, все они сводятся к поиску полезной информации в пространстве возможных понятий и ее корректному обобщению. Можно выделить ряд обзоров, посвященных машинному обучению [41,42, 56, 58, 67].
В работе предлагаются новые алгоритмы построения программной системы обучения, в основе которых лежит идея обучения на принципе взаимодействия со средой функционирования устройства [55].
Предлагаемый способ обучения можно сравнить с обучением человека. Человек обычно обучается в процессе взаимодействия с окружающим миром. Однако обратная связь, вызванная действиями человека, не всегда проявляется сразу и в явной форме. Например, в человеческих
взаимоотношениях результаты наших действий сказываются лишь по прошествии некоторого времени. На примере взаимодействия с миром всегда можно проследить причинно-следственные связи, а также последовательности действий, приводящие к реализации сложных целей.
Соединение программы обучения и управления и среды функционирования позволяет получить требуемую информацию об эффективности действий, их последовательности для достижения цели. В работе используется оценочный подход к проблеме обучения во взаимодействии со средой, названный обучением с подкреплением [56, 58].
Базовая идея алгоритмов обучения с подкреплением - собрать наиболее важные аспекты реальной задачи, возникающие перед программной системой устройства в процессе взаимодействия со средой и достижения цели. Очевидно, что профамма управления должна уметь определить и оценить состояние, в котором находится устройство, и принять действия, которые повлияют на это состояние. Кроме того, у устройства должна быть поставлена цель, которую необходимо достичь.
В процессе обучения с подкреплением вырабатывается вычислительный алгоритм перехода от ситуации к действиям, которые максимизируют величину полученного вознафаждения или выифыша. В отличие от большинства форм машинного обучения, обучение с подкреплением не определяет явно какое действие выбрать в конкретной ситуации или состоянии, а исследует действия на предмет вознафаждения, которое может быть получено в случае их выполнения. При этом в большинстве случаев выбор действия влияет не только на непосредственное вознафаждение, но и возможно на последующие ситуации и, таким образом, на все дальнейшие вознафаждения. Действия определяются не только сиюминутным результатом, но и последующими действиями и случайными вознафаждениями. Эти два свойства (метод "проб и ошибок" и подкрепление с задержкой) являются основными характеристиками обучения с подкреплением.
Таким образом, в терминологии обучения с подкреплением можно выделить три важных компонента: действие, вознаграждение и цель. Важно отметить, что устройство работает на основе собственного опыта, что позволяет использовать представленный способ машинного обучения для построения программных систем автономных устройств .
Один из вопросов, возникающих при использовании обучения с подкреплением - это нахождение компромисса между исследованием и эксплуатацией [33]. Для получения большего вознаграждения устройство в каждой ситуации должно предпочесть действие, которое уже использовалось в прошлом и оказалось наиболее эффективным или приносящим наибольшее вознаграждение. Но для этого программа должна выбирать действия, которые еще не были проверены в данной ситуации или состоянии. Для достижения наибольшего вознаграждения необходимо использовать (эксплуатировать) то, что уже известно, при этом исследовать наиболее выигрышные действия в будущем. Проблема в том, что ни эксплуатация, ни исследование не могут быть использованы отдельно, в отрыве друг от друга.
Другая ключевая особенность обучения с подкреплением - наличие определенной цели [35,54], к достижению которой должны вести все действия устройства. В задачах обучения с подкреплением также возможно использование понятия планирования, но в контексте выбора или компромисса между самим планированием и выбором действий в различных состояниях в режиме реального времени.
В обучении с подкреплением участвуют четыре компонента: политика, функция вознаграждения, функция стоимости и модель внешней среды.
Политика определяет выбор программной системы управления в каждом из возможных состояний одного из действий и, соответственно, способ действия устройства в определенное время. Такая политика может быть представлена правилами вывода или простой таблицей поиска.
Функция вознаграждения задает отображение каждого действия для заданного состояния в числовую меру, определяющую степень эффективности принятия действия в данном состоянии для достижения цели. В процессе обучения с подкреплением ставится цель максимизации общего вознаграждения, получаемого в результате решения задачи.
Функция стоимости, или ценности это числовая величина определяемая для каждого состояния среда - устройство, задающая величину вознаграждения, на которое может рассчитывать устройство, продолжая действовать из этого состояния. Если функция вознаграждения определяет сиюминутную эффективность пары "состояние-отклик", то функция ценности задает долговременную перспективу всех дальнейших состояний. Например, пара "состояние-действие" может приводить к низкому сиюминутному вознаграждению, но иметь высокую ценность, поскольку за ней обычно следуют другие состояния с высоким вознаграждением. Низкая ценность соответствует состояниям, не приводящим к успешному решению задачи.
Без функции вознаграждения нельзя определить значение ценности, которую необходимо оценить для получения более высокого вознаграждения. Однако в процессе принятия решений в первую очередь интересует ценность, поскольку она определяет состояния и их комбинации, приводящие к максимальному вознаграждению. Вознаграждение предоставляется непосредственно внешней средой, а стоимость может многократно оцениваться со временем на основе успешного и ошибочного опыта. На самом деле, наиболее критичным и сложным моментом обучения с подкреплением является создание метода эффективного определения ценности.
Последним и необязательным элементом обучения с подкреплением является модель внешней среды. Модель — это механизм реализации аспектов поведения внешней среды. Модели можно использовать не только для выявления сбоев, как в диагностике, но и при определении плана действий. Модели позволяют оценить результаты возможных действий без их реального выполнения. Планирование на основе моделей является дополнением к парадигме обучения с подкреплением, которое позволяет реализовывать возможности обучения без проведения натурных испытаний при физическом отсутствии объекта обучения, что значительно расширяет сферу применения предлагаемого подхода к обучению [4,54,29].
Целью диссертационной работы является исследование и разработка алгоритмов и методов построения программных систем для управления и обучения автономных транспортных устройств при работе в изменяющихся условиях, а также проверка алгоритмов с использованием компьютерного имитационного моделирования при отсутствии реальных условий для испытания.
Основными задачами, решаемыми в рамках данной работы, являются:
1.Анализ и оценка современных методов построения программного обеспечения для обучения и управления автономными интеллектуальными устройствами.
2.Разработка алгоритмов обучения и управления, позволяющих реализовать программное обеспечение интеллектуальных устройств для работы в неопределенных или изменяющихся условиях.
3.Создание имитационной модели для проведения функциональной проверки методик построения алгоритмов обучения и управления. Выбор прототипа для моделирования.
4.Анализ и оценка результатов моделирования.
Научная новизна данной работы заключается в том, что:
1. Предложена и исследована оригинальная методика построения программных систем управления техническим устройством, основанная на обучении во взаимодействии со средой функционирования и получении вознаграждений от работы. При этом отличительной особенностью является отсутствие предварительной информации о среде работы устройства управления.
2.Разработан способ накопления знаний, в основе которого лежат новые алгоритмы обработки вознаграждений принятия устройством действий, полученных от взаимодействия со средой.
3.В первые предложена и реализована компьютерная имитационная модель работы выбранного прототипа. Проведена проверка работоспособности созданных методов обучения и управления на соответствующих тестах в рамках имитационного моделирования.
На защиту выносятся следующие положения, представляющие научную новизну:
1 .Разработанные алгоритмы обучения (накопления знаний) управляющего программного обеспечения технического устройства.
2.Алгоритмы управления на базе накопленных знаний, обеспечивающие построение рациональных планов достижении цели согласно определенным критериям.
3.Программная имитационная модель работы выбранного прототипа устройства в соответствии с разработанными алгоритмами обучения и управления.
Практическую ценность представляют математические методы и алгоритмы обучения и управления автономными устройствами, созданные в рамках данной работы, а также результаты имитационного моделирования прототипа такого устройства. Разработанные методы построения программных систем управления на базе алгоритмов обучения и методика апробации алгоритмов в рамках имитационного моделирования могут быть использованы в различных областях народного хозяйства, требующих полной автоматизации труда человека. В том числе, в космической технике, а также при организации работ в удаленных и труднодоступных регионах, в условиях, при которых присутствие человека невозможно.
Диссертационная работа состоит из введения, трех глав, заключения, списка литературы и приложения.
В первой главе ставится задача построения программной системы обучения и управления автономными транспортными устройствами, приводится обзор существующих подходов к решению данного класса задач. Определяется основное свойство такой системы, как способность к накоплению и корректировке знаний на базе активного восприятия информации о среде функционирования и обобщения опыта и целенаправленного поведения на основе накопленных знаний.
В соответствии с решаемыми задачами определяется общая функциональная структура программной системы, состоящая из системы хранения и накопления знаний, системы планирования и исполнения действий. Проводится анализ существующих способов представления знаний. Рассматриваются представления: декларативное, семантическое, процедуральное. Показывается, что наиболее соответствующим поставленной задаче является представление, определенное в рамках теории обучения с подкреплением. Рассматриваются способы управления, используемые в теории обучения с подкреплением. Установлено, что известные методы управления основываются на решении системы нелинейных уравнений, при необходимости знаний всех значений вероятностей переходов между состояниями и значений получаемых при этом вознаграждений. Ставится задача разработки новых методов управления (нахождения рационального поведения устройства для достижения цели) в рамках теории обучения с подкреплением, без необходимости решения систем уравнений и знания величин вероятностей переходов между состояниями. Кроме того, определяется задача построения имитационной модели прототипа транспортного устройства для функциональной проверки созданных методов управления.
Вторая глава полностью посвящена теории построения программ и алгоритмов обучения во взаимодействии со средой. Показывается, что в подобной интеллектуальной системе требуется сохранение информации о всех состояниях посещенных устройством, определяются способы накопления и обработки знаний, для каждого из состояний. Рассматриваются принципы организации правильного функционирования. Определено, что в каждом из состояний система принимает решение на основе данных о полном вознаграждении принятия того или иного действия. Разрабатывается ряд методов обучения:
1. Метод полного программирования.
2. Метод обучения на основе эксперимента.
3. Метод временных разностей.
Отличительной особенностью представленных методов является то, что обучение носит итеративный характер, что позволяет реализовать нахождение рационального поведения без поиска в пространстве состояний (метод полного программирования) и без знания полных условий работы (методы обучения на основе эксперимента и временных разностей).
На основании предложенных методов обучения разрабатываются алгоритмы управления, которые обеспечивают компромиссное решение между задачами обучения и следования оптимальной политике. Кроме того, во второй главе рассматриваются вопросы рационального поведения и сходимости предложенных методов.
Третья глава является практической частью диссертационной работы. В ней приводятся методики построения имитационной модели работы прототипа устройства в соответствии с разработанными методами обучения. Описывается способ интерпретации теоретического представления информации и управления для конкретного прототипа устройства. Задаются способы реализации среды моделирования, задания входящих воздействий и целей для устройства. В данной главе отражены результаты имитационного моделирования прототипа транспортного автономного устройства при использования различных методик обучения и управления и их анализ. Осуществляется проверка адекватности предложенных методов с помощью экспериментальных данных.
В заключении содержатся основные результаты и выводы по диссертационной работе. Основные положения диссертации докладывались и обсуждались на семи Международных научных конференциях и семинарах в рамках Научных сессии МИФИ в 1997-2005 годах. По результатам конференций работа многократно премирована дипломами Научных сессий МИФИ. По теме диссертации опубликовано четыре статьи и три доклада. Программная система моделирования внедрена в научно-техническом центре мониторинга и оперативного управления ФГУП «Российский научно-исследовательский институт космического приборостроения» и в настоящее время используется в ряде базовых элементов Федеральной системы мониторинга критически важных объектов и особо опасных грузов.
Анализ общей структуры программной системы управления интеллектуальным устройством
Проблеме построения программ управления интеллектуальными устройствами посвящены научные труды многих авторов. В работах [33,45,41] определено, что основной характеристикой программы является целенаправленное поведение в сложном, плохо организованном внешнем мире. С точки зрения построения алгоритмов программ управления поведение можно организовать путем преобразования знаний о текущем состоянии пары среда-устройство, полученных с помощью сенсорных систем, в последовательность действий, направленных на достижение заданной цели. Такое преобразование должно опираться на априорные знания о среде и способах функционирования в данной среде. Это означает, что центральными звеньями программной системы интеллектуального устройства являются система представления знаний и развитая система планирования действий. Другой важной характеристикой является то, что все процессы сбора и преобразования информации должны протекать в реальном масштабе времени.
Обобщенная функциональная структура программной системы изображена на рис. 1.2 [33]. В ней можно выделить три основные взаимосвязанные системы: восприятия, представления знаний, планирования и исполнения действий. Рассмотрим каждую из этих систем.
Рассмотрение удобно начать с системы представления знаний, так как две другие в значительной степени опираются на нее. Выделяют три аспекта, связанные со знаниями в представляемой программной системе: представление знаний, их накопление, корректировка и использование в решении задач. Знания о целях - это информация о глобальных целях, которые устройство должно достигнуть в процессе функционирования, а также о способах их декомпозиции на локальные, реализуемые на промежуточных этапах. Модель среды работы - это формальное описание знаний о среде, в которой функционирует устройство. Эти сведения носят априорный характер в том смысле, что сформированы и сообщены программе заранее. В ряде практических случаев не удается построить заранее модель среды работы требуемой точности и информационной полноты. Это особенно характерно для устройств, предназначенных для работы в мало изученных средах.
Текущая информация, которую получает программа в процессе функционирования, очевидно, может быть использована для повышения точности и расширения знаний о среде работы. Эту функцию выполняет блок накопления и корректировки знаний. В нем производится накопление новых фактов о среде работы, их анализ на непротиворечивость со всеми другими фактами, хранящимися в системе представления знаний. Если новый факт не противоречив, он может быть включен в модель среды.
Связь с внешним миром в программной системе интеллектуального устройства осуществляется через систему восприятия. Конечной целью этой системы является построение модели текущего состояния среды и устройства в этой среде или формирования состояний среда-устройство. Предполагается, что система восприятия формирует ситуационные знания, т. е. знания о текущей ситуации. Источниками информации о среде являются сенсоры, к которым могут относиться тактильные, локационные, силомоментные датчики, приемники визуальной и звуковой информации. Информация от сенсоров обрабатывается и представляется в виде, удобном для дальнейших преобразований.
Дальнейшее преобразование информации, связанное с ее синтаксической и семантической интерпретацией. Синтаксическая интерпретация формирует представление воспринимаемого состояния среды на некотором внутреннем языке. При этом смысл воспринимаемых явлений и объектов остается не раскрытым. Семантическая интерпретация связана с выявлением смысла воспринятой информации. Завершающей процедурой является построение модели текущего состояния среды.
Основное назначение системы планирования и исполнения действий заключается в формировании и реализации программы действий, ведущей к достижению поставленной цели [33,41]. Планирование действий обычно представляется как процесс решения задачи. При этом задача в самом широком смысле трактуется как разница между текущим и желаемым состоянием пары среда-устройство. План или решение задачи — это последовательность действий, переводящая текущее состояние в желаемое.
Под автономностью понимают способность самостоятельно (или относительно самостоятельно) воспринимать информацию об окружающей среде, планировать и выполнять действия по достижению заданной цели.
Планирующие подсистемы являются основной решающей частью программы управления. Синтез планов осуществляется на основе поставленных целей и накопленного знания, причем цели могут как задаваться человеком-оператором, так и вырабатываться самим устройством. При синтезе планов широко используются дедуктивные механизмы планирования, определяющие план как последовательность применимых и пригодных действий, выбираемых из накопленного набора операторов [33]. Поскольку в достаточно сложных задачах планирования имеются альтернативные возможности выбора пригодных действий среди множества применимых, чисто дедуктивные механизмы должны были бы апробовать все возможности. Использование эвристик, т. е. наложение семантики на дедуктивные механизмы, позволяет сделать выбор более направленным, а следовательно, процесс планирования - более эффективным.
Обучение с подкреплением. Основные понятия
Определим основные свойства функции стоимости. Для любой политики П и любого состояния s можно выявить рекурсивную зависимость между стоимостью в состоянии s и стоимостью во всех возможных дальнейших состояниях: т т = +1+ 7 +2 = к=0 J т И = 5 М1
Данное равенство определяет зависимость между ценностью данного состояния s и значениями ценности всех последующих состояний. Выражение (1.9) оценивает значение Vі(s), исходя из множества действий а є A(s), вероятности выбора действия II(s,a) и вероятности перехода в состояние s под действием а. При этом используется значение функции стоимости Vі(s ) следующего возможного состояния. Таким образом, выражение (1.9) проводит усреднение по всем возможным переходам из состояния s, используя для исходного перехода s- s вероятность такого перехода.
Согласно выражению (1.9) стоимость нахождения в состояния s должна определяться стоимостью будущего состояния s и ожидаемым вознаграждением, получаемым в результате перехода s- s .
Как было определено, в основную задачу обучения с подкреплением входит нахождение политики 77, которая обеспечивает достижение наибольшего вознаграждения в течение времени работы устройства. Для МПР возможно точное определение рациональной политики следующим образом. Политика 77 определяется лучшей по отношению к политике 77\ если ожидаемое полное вознаграждение при следовании политики 77 больше или равно полному вознаграждению при использовании политики П , для всех состояний s. Другими словами 77 П , если V"(s) V (s) для всех se S.
Всегда имеется по крайней мере одна политика, лучшая или равная по отношению ко всем другим политикам. Назовем такую политику -рациональной политикой. Обозначим рациональную политику как 77 . Определим понятие рациональной функции стоимости, как: V(s) = maxV (s), (ив) для всех s е S, или Q" (s, a) = max Qv( s.a), (jjj) для всех s є S, а є A(s)
Функция (1.11) определяет ожидаемое полное вознаграждение в случае принятия действия а в состоянии s и следование далее во всех состояниях рациональной политике П. Можно определить, что Q\s, a) = E{rt+l + 7 (54.1)1 =5,0, = 0). (1-12)
Поскольку V является функцией стоимости для политики 77 , она должна удовлетворять равенству (1.9). В то же время, поскольку V является рациональной функцией стоимости, данное равенство (1.9) может быть записано без определенной привязки к произвольной политике 77.
Понятно, что значение стоимости состояния при использовании рациональной политики равно ожидаемому полному вознаграждению принятия наилучшего действия в заданном состоянии: V(«) = твх(Г{8,а) = тахДг і Rt \ St =s. at=a = max E \ V 1krt+k+i st=s,at = a аЄ/(») \.k=0 J = max E I rf+i + «7 У! "tkrt+k+2 \st = s. at= a ЄА[ ) I k=0 I J = max {rt+i+ 7V (sf+1)st = s,af=o} (i.iJJ = E K + V)], (1.14) Для б возможно определить: Q (s.a) = rt+i + «7maxQ (sf+1,af) st = s.ot=oi = E + maxQV: )] fiJ5;
Для конечного МПР равенство (1.14) имеет единственное решение, вне зависимости от используемой политики /7 [53]. В силу конечного числа состояний S для рассматриваемого класса эпизодичных задач выражение (1.14) представляет собой систему равенств, по одному для каждого из состояний и, таким образом, выражение (1.14) определяет систему из N равенств для N состояний с N неизвестными. В случае, если динамика среды ( /?aw» и Р"хх ) известна, представляется возможным решение данной системы уравнений, используя любой из множества подходов решения системы нелинейных уравнений. Аналогично возможно решение системы уравнений для Q .
Решив систему уравнений (1.14) и определив V, представляется возможным найти рациональную политику. Для каждого состояния s в этом случае имеется одно или более действий, для которых достигается максимум в выражении (1.14). Любая политика, которая определяет не нулевые вероятности принятия в состоянии только для этих0 йстЩй н,является рациональной политикой. Данный подход оценивается как одношаговый поиск. Если известна V, то в этом случае действие, которое является лучшим после одношагового поиска, рассматривается как рациональное действие. Преимущество одношагового поиска заключается в том, что оценивается одношаговая последовательность выбора действий, учитывая то, что общая политика действий оказывается рациональной, поскольку при вычислении V последовательность полных вознаграждений всех возможных будущих состояний. Зная и используя V задача оценки полного вознаграждения сводится к задаче оценки немедленного вознаграждения, доступного для каждого состояния. Таким образом, одношаговый поиск обеспечивает выбор рационального действия для получения значения полного вознаграждения.
Зная Q , выбор рационального действия также прост. С Q алгоритм ПСОиУ не должен далее осуществлять одношаговый поиск. Для каждого состояния 5, необходимо просто определить любое действие, которое максимизирует Q (s ,а). Функция стоимости принятия действия Q (S , а) определяет результат всех одношаговых поисков. Она обеспечивает рациональное ожидаемое значение полного вознаграждения как значение вознаграждения, которое непосредственно доступно для каждой пары состояния - действия.
Таким образом, функция Q (s ,а) в отличие от V(s) позволяет выбрать наилучшее действие без необходимости знания обо всех возможных дальнейших состояниях и их ценностях, и таким образом, без знания динамики среды.
Итерация функции стоимости
Один из недостатков рассмотренного подхода итерации политики является необходимость многократных итераций оценки политики на каждом шаге работы алгоритма. Рассмотрим пути к снижению количества шагов итерации.
Рассмотренный в 2.1.3 процесс итерации политики может быть ограничен несколькими способами без потери гарантированной сходимости. Одним из наиболее важных подходов представляет случай, когда процесс оценки политики останавливается после единственного прохода. Данный алгоритм назовем итерацией функции стоимости. Он может быть записан как операция, включающая в себя улучшение политики и ограничение количества шагов оценки политики: Vfc+i(s) = max Е {rt+i 4- TVic(st+i)st = s. a = a} = 2Mx7%pU +7 ), (2.11) » для всех se S
Может быть показано [53], что для произвольного V0, последовательность {V/J сходится к V при тех же условиях, при которых гарантируется существование V . Рассмотрим при каких условиях прекращает работу алгоритм итерации функции стоимости. Как и при оценке стоимости, алгоритм итерации функции стоимости требует бесконечного числа итерации для сходимости к V. На практике предполагается ограничить работу алгоритма, как только изменение значения функции стоимости становится меньше определенного малого значения. Инициализация V произвольно (V(s)=0 для всех seS) п — 0- число выполненных шагов Повтор Д -0 Для каждого se S v - V(s) V{s) «- max, .. 7 [Kaaa, -f 7 V(s )] A -max(A,r/-V(s)) n -n+l Пока A 9 (малое положительное значение) или n N Выходная детерминированная политика П: TT(S) = arg
В отличие от рассмотренных ранее методов, в коллекции методов на основе эксперимента (МЭ) не предполагается наличие полного знания динамики среды ( Rass и P ss )- В рассматриваемом классе методов обучение происходит на основе эксперимента, выборочной последовательности состояний, действии и получаемых вознаграждений от действительного или симулированного взаимодействия со средой. Обучение на базе реального взаимодействия является важным с точки зрения функционирования агрегатов. При этом не требуется предварительных знаний о динамике среды, однако в процессе работы агрегата может быть достигнуто рациональное поведение. Обучение на основе модели также представляется важным. На модель возлагается функциональная обязанность генерации примеров среды для работы устройства, а не полной модели распределения вероятности всех возможных переходов, как в случае обучения методами ПП [41,54].
В основе данного класса методов лежит принцип решения проблемы обучения с подкреплением на базе усреднения получаемых вознаграждений в процессе эксперимента. По окончании очередного эпизода функция стоимости и политика подвергаются оценке и изменению. В этом смысле представленные методы являются эпизод-за-эпизодом инкрементными.
Несмотря на различие между методами обучения на основе эксперимента и методами ПП, основные идеи данных двух подходов совпадают. В подходах предлагаемых методов также производится оценка значения функции стоимости Vа и (У7 для выбранной политики. На основании полученных значений изменение политики 77, с целью нахождения рациональной политики. Причем оба данных процесса повторяются итеративно.
Рассмотрим подход, использованный в методе МЭ для оценки для заданной политики 77. Очевидный подход - оценки исходя из эксперимента, как простое усреднение полных вознаграждений, полученных в результате прохождения через заданное состояние. Чем большее количество раз устройство прошло через заданное состояние, тем более достоверным оказывается оцениваемое значение.
Пусть необходимо оценить значение Vі(s), для состояния 5 в рамках политики 77, имея набор эпизодов, полученных в результате следования политики 77 и проходя через состояние s. Будем рассматривать только методы МЭ первого визита, где для оценки функции стоимости используются усредненные значения полного вознаграждения, полученные после первого визита заданного состояния s. При этом в рамках одного эпизода состояние s может посещаться несколько раз.
Алгоритм оценки значения функции стоимости, выраженный в процедурной форме, приведем ниже: Инициализация П — оцениваемая политика V - произвольное значение функции стоимости Returns(s) - пустые значения, для всех sе S Повтор: а. Генерация эпизода согласно П б. Для каждого состояния s в рамках эпизода R — полное вознаграждение полученное после первого посещения s Добавление R к Return(s) V(s) - average(Return(s)) (Алгоритм4)
Данный алгоритм сходится к Vа(s) при значительном числе первых визитов. Такое утверждение легко доказать, основываясь на законе больших чисел. В этом случае каждое получаемое значение полного вознаграждения является независимой, идентично распределенной оценкой V"(s) . По закону больших чисел последовательность усреднений этих оценок сходится к их ожидаемому значению. Каждое усредненное значение само является оценкой, с ошибкой оценки пропорциональной 1 п , где п - число усредненных вознаграждений. Таким образом, оценка асимптотически сходится к "(s) [54].
Блочная структура модели. Основные параметры и переменные модели. Согласованное взаимодействие блоков программы в процессе моделирования
Определим структуру модели в виде логической блоковой схемы. Целесообразно строить модель по модульному принципу, то есть в виде совокупности стандартных блоков. При таком подходе можно создавать и совершенствовать модель итерационным методом, добавляя к основной модели блок за блоком. Построение модели из стандартных блоков дает возможность экспериментировать при ее реализации и в процессе моделирования. Тем самым обеспечивается необходимая гибкость модели. Отдельные блоки (модули) могут быть изменены и это не вызовет усложнения других блоков или увеличения их количества.
При построении блочной модели происходит разделение ее функций на логические подфункции с более высоким уровнем детализации. Таким образом, модель функционально подразделяется на подмодели. Каждая подмодель может быть разделена на блоки, а блоки - на подблоки. Этот уровень детализации является достаточным.
В функциональной модели АСА можно логически выделить несколько функциональных блоков: 1. Блок задания входных параметров для моделирования. В этот блок входят подблоки: 1.1 подблок задания параметров АСА; 1.2 подблок задания рельефа местности виртуального полигона; І.Зподблок задания расщелин на виртуальном полигоне; 1.4 подблок задания траектории движения; 1.5 подблок записи или считывания рельефа местности виртуального полигона с магнитного носителя. 2. Блок определения текущего положения АСА на виртуальном полигоне в процессе моделирования. Этот блок включает в себя: 2.1 подблок построения сечения рельефа виртуального полигона плоскостями боковых граней главной несущей платформы в виде списка; 2.2 подблок определения и привязки положения АСА относительно построенного списка; 2.3 подблок определения текущего расположения АСА относительно виртуального полигона через построенные списки сечения рельефа. 3. Блок обучения и реализации движения АСА. 4. Блок сценария движения по заранее заданной траектории. 5. Блок рисования. Включает в себя: 5.1 подблок рисования АСА; 5.2подблок отображения текущего сечения ландшафта; 5.3.подблок рисования сетки ландшафта, расщелин и траектории движения. Синхронизацию работы программных блоков осуществляет компонент среды таймер. Задавая частоту пересчета и переполнения таймера возможно изменение скорости работы модели, что дает возможность моделировать функционирование АСА в реальном масштабе времени.
Схема согласованного взаимодействия блоков программы в процессе моделирования приведена ниже (рис.3.3). 1-входные параметры модели. 2-параметры текущего положения относительно полигона моделирования. 3-текущие параметры положения и состояния АСА. 4-новые параметры положения и состояния АСА. Параметры, определяющие новые виды работы.
Рассматривать схему согласованного взаимодействия блоков в процессе моделирования целесообразно совместно с описанием основных параметров и переменных модели.
Одними из основных параметров модели является входные статические параметры АСА4 к которым относятся длина и ширина главной направляющей платформы (dlin, shir), длина и количество колен опор агрегата {opor_dlin, kol_count), максимальный угол поворота (AlfaJMax).
К основным параметрам модели необходимо отнести множество флагов А - набор действий (движений), которые может выполнить АСА: aj - перемещение главной направляющей платформы вперед (перемещение центральной направляющей платформы назад);
