004-027. 21 Грнти 50. 07. 03; 20. 01. 04
Скачать 1.51 Mb.
|
Глава 2. Алгоритмизация процесса формирования траектории обучения2.1. История формирования планов решения задачИнтеллектуальное планирование зародилось на основе исследований в области поиска в пространстве состояний и автоматического доказательства теорем. STRIPS была первой системой, которая базировалась на этих двух методологиях. Система STRIPS создавалась в качестве модуля планирования для мобильного робота Shakey (проект Стэнфордского исследовательского центра - SRI) [39]. Поиск решения в этой системе была основан на методологии поиска системы GPS, а для проверки истинности предусловий действия в текущем состоянии применялась методология доказательства теорем из системы QA3. Прежде, чем перейти к рассмотрению первого планировщика (STRIPS), рассматривается более ранний период времени, когда были разработаны системы и методологии, лежащие в его основе. В 1957 году была начата разработка системы, получившей название "Универсальный решатель задач" (General Problem Solver - GPS). Эту систему создавали сразу три автора: Алан Ньюэл, Дж. Шоу и Герберт Саймон. Первая публикация по результатам работы появилась лишь 1959 году [39,68]. Название "Универсальный решатель задач" обусловлено тем фактом, что это была первая система для решения задач (problem-solving system), в которой общие методы решения задач были отделены от знаний, определяющих конкретную задачу. Часть программы, осуществлявшая поиск решения, не обладала информацией о конкретном виде задачи, с которой она работала. Специфичные для конкретной задачи знания организовывались в отдельные структуры: объекты и операторы для преобразования объектов. Задача для системы GPS ставилась в виде пары, состоящей из начального объекта и желаемого объекта, в который начальный объект должен быть преобразован. Методология, использованная в GPS, отличается от стандартных методов поиска в пространстве состояний тем, что она выбирает путь, по которому продолжить поиск. Т.е. система пытается искать решение в первую очередь в "наиболее перспективных" ветвях поиска. Такая методология была названа "анализ средств и целей" (means-ends analysis). Ее суть заключалась в том, что сначала отыскивалось различие (difference) между текущим объектом и объектом, который мы хотим получить. Это различие относилось к одному из ряда классов различий. С каждым классом был сопоставлен набор действий, способных уменьшить различие между текущим и целевым объектами. На каждом шаге поиска GPS искал различие объектов и выбирал один из релевантных операторов, который и пытался затем применить к текущему объекту. Поиск подходящей последовательности операторов выполнялся в глубину до тех пор, пока операторы оказывались применимы, а ветвь поиска "выглядела перспективной". Если ветвь поиска была бесперспективной, то выполнялся откат. Важной особенностью анализа средств и целей является то, что всегда выбирается релевантный оператор, уменьшающий различие объектов, даже если он и не применим к текущему объекту. Вместо того чтобы отказаться от неприменимого к текущему объекту оператора, GPS пытался преобразовать текущий объект в объект, пригодный для применения выбранного оператора. Применение такой стратегии привело к появлению рекурсивной, целеориентированной процедуры, которая фиксирует историю поиска в графе с частично проработанными узлами. Несмотря на то, что в качестве объекта могла выступать модель мира, а в качестве оператора - действие, задача планирования перед системой GPS не ставилась. Такой вариант использования GPS был осуществлен значительно позднее, когда была разработана система STRIPS, упомянутая ранее. Ниже мы подробно рассмотрим, как это было реализовано. В июле 1969 года Кордел Грин (Cordell Green) представил публике свою диссертационную работу [39,63], посвященную вопросно-ответной системе, которая называлась QA3. Система QA3 хотя и была вопросно-ответной системой, однако содержала в себе еще и механизмы для решения задач. В частности, эта система могла отвечать на вопросы такого типа: "Существует ли последовательность действий такая, что объект object1 окажется в комнате room4, если изначально он находится в комнате room2?" Такая формулировка вопроса является, по сути, постановкой задачи планирования. Но так как целю системы QA3 были все-таки ответы на вопросы, а не решение задач, да и реализация механизма решения задач имела множество ограничений, эта система не претендует на звание первого планировщика. Первой системой, которая создавалась именно для решения задачи планирования, была система STRIPS (STanford Research Institute Problem Solver). Разработана система была в 1971 году двумя исследователями - Ричардом Файксом и Нильсом Нильсоном. Описание системы опубликовано в трудах 2-ой международной конференции по искусственному интеллекту (IJCAI'71) [61]. Файкс и Нильсон сформулировали задачу планирования такой, какова она и по сей день. Задача планировщика найти такую последовательность действий, которая преобразует начальное состояние в такое состояние, в котором достигается заранее заданное целевое условие (В оригинальной статье используются понятия "модель мира" для обозначения состояния и "оператор" для обозначения действия. Мы будем придерживаться современной терминологии.). Состояние представляется множеством формул логики первого порядка (в оригинальной статье, well-formed formulas (wffs)). Цель также описывается формулой. Действия описываются в виде специальных конструкций, которые мы рассмотрим ниже. STRIPS пользуется методологией доказательства теорем только в рамках одного заданного состояния для получения ответа на вопросы "какие действия применимы" и "достигнуты ли целевые условия" (в отличие от QA3, где методы доказательства теорем использовались и для перехода из состояния в состояние). В STRIPS поиск в пространстве состояний осуществляется по аналогии с системой GPS, а именно, используется стратегия "анализ средств и целей". Формально, постановка задачи в STRIPS включает три составляющие: начальное состояние, множество действий и целевую формулу. Условия применимости действия, называемые также предусловием (precondition), задаются при помощи одной формулы. Для того, чтоб узнать применимо ли действие в некотором заданном состоянии, мы должны проверить истинность предусловия, т.е. доказать, что предусловие является логическим следствием множества аксиом данного состояния. Если предусловие истинно, то действие применимо. Для осуществления поиска плана была использована стратегия GPS, которая определяет "различие" между текущим состоянием и целью и находит действия, способные уменьшить это различие. После того, как подходящее действие найдено, мы решаем подзадачу порождения состояния, к которому данное действие применимо. Если такое состояние обнаруживается, то действие применяется и изначальная цель рассматривается вновь уже в новом состоянии. Когда действие признано подходящим (релевантным), мы еще не знаем, где оно появится в конечном плане. Т.е. может оказаться, что перед ним должны стоять другие действия, которые делают возможным выполнение данного действия. После него также могут оказаться действия, которые обеспечивают выполнение всей цели (ведь одно действие служит уменьшению различия, а не обязательно достижению цели сразу). В следующем году те же авторы совместно с Питером Хартом представили доработку своей системы. В своей статье [62] они описывают механизм для обобщения планов, порожденных STRIPS. Обобщенные планы хранились в специальных треугольных таблицах (triangle tables) и использовались как своеобразные "макрооператоры" для повторного применения в других задачах планирования, а также для мониторинга исполнения плана. Получение и сохранение обобщенных планов являлось некоторого рода формой обучения, которое позволяло уменьшить время, необходимое на поиск плана в схожих задачах. В своем первозданном виде STRIPS выдает в качестве результата полностью конкретизированный план. Ключевым моментом доработки к STRIPS стало обобщение плана путем замены констант параметрами. Другими словами, конкретный план становится схемой плана (plan schema) или макрооператором (macro operator), который подобен примитивным схемам действий, заданным в задаче изначально. Еще через год Джеральд Сусман разработал новую интересную систему для решения задач [71], основанную на методе анализа средств и целей и обладающую механизмом обучения. Эта система получила название HACKER. В качестве механизма обучения Сусман использовал упрощенный вариант обучения по прецедентам. Прецеденты сохранялись в библиотеке прецедентов, названной Сусманом библиотекой ответов (answer library). Когда система HACKER решала очередную задачу, она сначала проверяла, нет ли в библиотеке ответов решения, чей образец применимости (pattern of applicability) соответствует условиям задачи. Если такое решение находилось, то оно применялось. Если нет, то HACKER находил новое решение. При построении нового решения система могла использовать библиотеку ответов для разрешения частных подпроблем, а также старалась избегать ошибок, с которыми она сталкивалась ранее. Новое решение сохранялось в библиотеке ответов, проиндексированное по образцу применимости, выведенному из постановки задачи. Таким образом, оно могло быть использовано для решения подобных задач в будущем. Если решение в момент применения приводило к ошибке, то использовались общие механизмы отладки для классификации и установления природы ошибки. После этого решение редактировалось и перезаписывалось в библиотеке ответов. Часто ошибка сама подвергалась обобщению и запоминанию, для того, чтобы избегать ее уже при построении решения. HACKER - это попытка совместить в одной системе процедурное и декларативное представления знаний о предметной области, чтобы получить одновременно легко расширяемый (декларативное представление) и эффективный (процедурное представление) решатель задач. Ряд проблем система "знает" как решать (эти знания могут приобретаться, например, посредством обучения). Метод решения - это процедурное представление знаний. Процедура описывает порядок шагов и способ избежания негативного взаимовлияния шагов. Процедурное представление обеспечивает высокую скорость поиска известных решений. Декларативное представление знаний служит залогом хорошей расширяемости описания предметной области. В этой форме могут быть легко добавлены новые факты о мире (объекты, отношения). Каждую новую задачу HACKER обрабатывает по следующей схеме. Сначала проверяется, нет ли готового решения общего вида для данной проблемы. Т.е. выясняется, не является ли новая задача частным случаем более общей задачи, метод решения которой уже известен. Фактически, это проверка, нет ли в библиотеке ответов процедуры, чей образец применимости (прототип) соответствует новой задаче. Если такая процедура есть, то она и является планом. HACKER исполняет планы, т.е. эта процедура интерпретируется. Если процедура исполняется успешно, то управление возвращается пользователю, и он оценивает результаты работы. Если же готовое решение отсутствует в библиотеке ответов или найденная процедура не срабатывает, то HACKER "программирует" новое решение или отлаживает старое соответственно. В первом случае HACKER пользуясь знаниями о предметной области и "общих методах программирования" (programming technique) порождает новую процедуру решения задачи. Т.е. фактически решение порождается на основе набора эвристик, названных методами программирования, но в основе этих эвристик лежит анализ средств и целей. Новое решение проверяется на предмет наличия известных видов ошибок и при необходимости корректируется. В конечном счете, оно помещается в библиотеку ответов. Во втором случае (ошибка при исполнении) включается механизм отладки. Определяется вид ошибки и производится попытка корректировки процедуры. Сусман особо выделяет ситуацию, когда некоторое действие плана разрушает результат, достигнутый одним из предшествующих шагов. В системе HACKER предложен механизм, позволяющий контролировать появление таких ситуаций, - механизм защиты (protection mechanism). Он служит основой для выявления некорректных планов такого рода и причин их некорректности. В дальнейшем эти знания могут быть использованы при построении новых планов. Механизм защиты опирается на следующую идею. У каждого шага в плане есть, по крайней мере, одно назначение (purpose). Этим назначением может быть либо вклад в общую цель, либо достижение предусловий последующих шагов плана. Назначение может рассматриваться как некоторое утверждение, являющееся либо частью общей цели, либо требующееся для исполнения последующих шагов плана. Если на интервале от некоторого действия до точки реализации его назначения происходит отрицание этого назначения (как утверждения), то такая последовательность действий считается некорректной. Защитный механизм позволяет обнаруживать такие некорректные случаи. Он контролирует неизменность назначения на соответствующем интервале. Если значение истинности назначения (как утверждения) измениться, то фиксируется ошибка, которая потом анализируется и делаются необходимые поправки. В системе HACKER механизм защиты работает в процессе исполнения плана, хотя эту идею можно легко перенести и на процесс генерации плана. Однако такой защитный механизм не избавляет нас от всех проблем. Простой пример, обнаруженный Аленом Брауном (Allen Brown), демонстрирует несостоятельность такого подхода. Этот пример в дальнейшем стал называться аномалией Сусмана (Sussman anomaly). Отсутствие возможности у STRIPS справляться с аномалией сусмана - не единственная проблема этого планировщика. Сталкиваясь со сложными и большими описаниями предметных областей, STRIPS-эвристики не спасают от комбинаторного взрыва. Нужно было искать другие пути сокращения пространства поиска. Эрл Сасердоти предложил использовать иерархию абстрактных пространств поиска для того, чтобы на каждом уровне абстракции отделять действительно важную информацию от несущественных в данный момент деталей, и тем самым отсекать нерелевантные ветви поиска уже на верхних уровнях абстракции [70]. Его идеи легли в основу планировщика ABSTRIPS (Abstraction-Based STRIPS) - STRIPS-подобного планировщика с поддержкой идеи абстрактных пространств поиска. Хорошая эвристическая функция может отсекать большинство возможных путей в пространстве поиска. Однако, если принимать во внимание все "детали" пространства поиска, то оценочная функция (определяющая, куда идти дальше) будет применена к большому количеству узлов, обусловленных этими "деталями". Предложенный Сасердоти подход выполняет поиск сначала в абстрактном пространстве (abstraction space) - упрощенном представлении пространства поиска, в котором опущены несущественные детали. Когда решение в абстрактном пространстве поиска найдено, все, что остается сделать, это учесть детали связей между шагами в полученном решении. Это можно рассматривать как последовательность подзадач в рамках изначальной задачи. Если эти подзадачи могут быть решены, то решение всей проблемы тоже будет найдено. Если нет, то нужно продолжить планирование в абстрактном пространстве для поиска альтернативного абстрактного решения. Эта идея легко может быть расширена до иерархии абстрактных пространств поиска. Каждый уровень дает все большую детализацию. Детали рассматриваются, только когда найден план в вышележащем уровне иерархии. Таким образом, эвристика на каждом уровне иерархии будет рассматривать значительно сокращенное пространство поиска. Еще одно решение проблемы с чередованием шагов в нелинейных планах было предложено Дэвидом Уорреном [74]. Его подход заключался в отказе от STRIPS-овского варианта анализа средств и целей. Вместо него был предложен несколько иной подход, названный регрессией (regression). В STRIPS поиск подходящих действий велся от цели, но построение плана выполнялось от начального состояния. Регрессия осуществляет построение плана с конца (от цели к начальному состоянию). При этом рассматриваются все возможные способы достижения каждой из подцелей и все возможные порядки их достижения. Достигнутые цели не должны были разрушаться в текущей ветви поиска. Именно, рассмотрение всех возможных порядков позволяет преодолеть проблему с чередованием. NOAH - первый планировщик, допускающий частичное упорядочение (partial order) действий в плане. При таком подходе, план - это набор отношений порядка между действиями. Связный план можно получить из набора частично упорядоченных действий путем линеаризации (linearization). Кроме этого, такой подход делает возможным наличие параллельных ветвей в плане. NOAH - первый иерархический планировщик. Иерархическое планирование предполагает, что процесс составления плана - это процесс постепенной детализации решения. Действия в NOAH могут быть простыми и составными (раскладываться на набор действий-составляющих). Составные действия содержат в себе знания о типовых решениях часто встречающихся задач. Очередной важной вехой в истории планирования стал планировщик NONLIN (Non-linear planner). Идеологически этот планировщик является развитием планировщика NOAH. Однако Тейт вводит новый термин - задача (task) - положивший начало новому направлению, называемому HTN-планированием (HTN - hierarchical task network - иерархическая сеть задач). По своей сути (идее, механизмам) HTN-планирование и иерархическое планирование являются одним и тем же. Однако с точки зрения терминологии, HTN - это такое иерархическое планирование, в котором используется понятие задачи. Планировщик NONLIN появился как часть проекта "The Planning: a joint AI/OR approach" [72,73]. Целью этого проекта было создание программы, помогающей пользователям составлять сетевые графики проектов (project network). Из названия ясно, что проект опирался на два различных подхода: искусственный интеллект (AI) и исследование операций (OR - operational research). При этом AI отводилась роль построения сетевого графика, а на долю OR выпадал анализ критического пути и оптимизация графика. Мы коснемся только вопросов построения графика. Но сначала более детально рассмотрим понятие "задача". Задача является одним из ключевых терминов, которым оперируют составители сетевых графиков. Обычно, проект рассматривается как частично упорядоченный набор задач (task), которые необходимо решить. Этот планировщик известен тем, что осуществляет планирование ресурсов, т.е. работает не только с логическими выражениями, но и с численными величинами. Относится к числу HTN-планировщиков. Разработан Дэвидом Уилкинсом (David Wilkins). TWEAK - еще один планировщик, использующий частичное упорядочивание действий в плане. Однако, в отличие от NOAH и NONLIN он не является иерархическим. Автор этого планировщика - Дэвид Чепмен (David Chapman) - подверг критике большинство ранее разработанных планировщиков за их недостаточно строгое определение методов решения задачи планирования, эвристичность и сложность (особенно это касалось нелинейных планировщиков). Чепмен приводит [60] строгое математическое определение задачи планирования и метода, который он использовал для ее решения. Кроме того, в его работе представлена терминология, которая в дальнейшем получила широкое распространение в планировании. Планировщик SNLP примечателен своей простотой как в плане формализации, так и в отношении самого алгоритма. Основан на методологии формирования частичных планов. Результаты опубликованы в статье [67]. В 1992 году Генри Каутцем (Henry Kautz) и Бартом Селманом (Bart Selman) был предложен принципиально иной подход к задаче планирования [65]. Идея заключалась в следующем. Сначала задача планирования формулируется в виде множества ограничений, выраженных логическими формулами. Ограничения накладываются таким образом, чтобы всякая модель этого множества формул соответствовала корректному плану. Затем находится модель для получившегося множества формул и уже из модели извлекается готовый план. В 1990-95 годах происходит всплеск развития вероятностных планировщиков (probabilistic planners). В отличие от классических планировщиков, предполагающих детерминистичность поведения и точные знания о мире, вероятностные планировщики адаптированы для рассуждений в средах с неопределенностью. Одной из наиболее известных работ (того времени) в этом направлении является планировщик BURIDAN. Он разработан коллективом авторов в составе Николаса Кушмерика (Nicholas Kushmerick), Стива Хэнкса (Steve Hanks) и Даниеля Уэлда (Daniel Weld). Основные результаты опубликованы в работе [66] В BURIDAN источниками неопределенности являются неточные знания о начальном состоянии и эффектах действий. Вместо классического начального состояния в постановке задачи планирования фигурирует распределение вероятностей на множестве возможных начальных состояний. Кроме того, эффекты действий зависят от случайных факторов (вероятности проявления того или иного эффекта задаются в описании схем действий). Использование вероятностной модели усложняет также определение корректного плана. Вместо классического "плана, достигающего цель", используется "план, достигающий цель с вероятностью выше заданного порога". Алгоритм BURIDAN основан на алгоритме SNLP и является полным и корректным. Авторам BURIDAN пришлось разработать новый формализм описания домена и задачи планирования для того, чтобы включить упомянутые факторы неопределенности в модель рассуждений. Рассмотрим новые определения и новые понятия, необходимые для постановки задачи в BURIDAN. |
Похожие:
 | 004-027. 21 Грнти 50. 07. 03; 20. 01. 04 Программа по учебной дисциплине «Мировая художественная культура» разработана в соответствии с требованиями государственного образовательного... | | Научно-исследовательский институт ядерной физики имени Д. В. Скобельцына удк 004. 75+004. 722 Разработка технологий высокопроизводительных вычислений с использованием неоднородных территориально-распределённых вычислительных... |
| Научно-исследовательский институт ядерной физики имени Д. В. Скобельцына... «Развитие, исследование и внедрение средств высокопроизводительных вычислений на основе технологий Грид с поддержкой гетерогенных,... | | Научно-исследовательский институт ядерной физики имени Д. В. Скобельцына... «Разработка архитектуры и программных средств для обеспечения взаимодействия грид-инфраструктуры рдиг/egee и создаваемой системы... |
 | "ок 004-93. Общероссийский классификатор видов экономической деятельности,... Ок 004-93. Общероссийский классификатор видов экономической деятельности, продукции и услуг | | "ок 004-93. Общероссийский классификатор видов экономической деятельности,... Ок 004-93. Общероссийский классификатор видов экономической деятельности, продукции и услуг |
| "ок 004-93. Общероссийский классификатор видов экономической деятельности,... Ок 004-93. Общероссийский классификатор видов экономической деятельности, продукции и услуг (ред от 22. 11. 2011)(утв. Постановлением... | | Формирование компетентности профессионального самосовершенствования... Защита состоится 27 мая 2010 г в 14. 30 час на заседании диссертационного совета д 212. 027. 02 в Волгоградском государственном педагогическом... |
| Фгбу «пияф» удк 001. 89: 004. 31 Федеральное государственное бюджетное учреждение «Петербургский институт ядерной физики им. Б. П. Константинова» | | Удк 004. 9 Коржик И. А Методические рекомендации в помощь преподавателю: издание гаоу спо «Уфимский топливно – энергетический колледж». – Уфа, 2012г |
| Электронных ресурсов «наука и образование» №3 (46) март 2013 удк 51, 002, 004 № офэрниО: 18981 Интерактивный учебный комплекс по математике / фгбоу впо санкт-Петербургский государственный морской технический университет | | Удк 004. 942 : 57. 026 Эволюционно стабильная информационная структура... Федеральный закон от 31. 05. 2001 №73-фз «О государственной судебно-экспертной деятельности» (выдержки) |
| Бионормализующее действие препарата пдс при восстановлении воспроизводительной... Д 220. 004. 01 при фгоу впо «Белгородская государственная сельскохозяйственная академия» по адресу: 308503 | | Интеграционные процессы на постсоветском пространстве Защита состоится 1 апреля 2008 года в 12 часов на заседании диссертационного совета д 446. 004. 02 в Российском государственном торгово-экономическом... |
| Экзаменационные вопросы «гост 12 004-90 Организация обучения безопасности труда» Тестовые задания разработаны преподавателями гигиены детей и подростков кафедры экологии человека и гигиены окружающей среды медико-профилактического... | | Удк 004. 81 Разработка принципов поддержки экономических интересов... В мешке Старика-Годовика собраны признаки самого прекрасного времени года. Ваша задача: найти причину явления, названного в столбике... |
