Интеллектуальные системы планирования

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Министерство науки и высшего образования РФ

Федеральное государственное бюджетное образовательное учреждение

высшего образования «Российский государственный университет

им. А.Н. Косыгина (Технологии. Дизайн. Искусство)»

Институт экономики и менеджмента

Кафедра коммерции и сервиса

РЕФЕРАТ

На тему: «Интеллектуальные системы планирования»

Выполнила студентка Енжиевская О.А.

Москва 2022



Оглавление

Введение

1. Терминология

2. Классификация планирования

2.1 Классическое планирование

2.2 Планирование с частичным упорядочиванием

2.3 Планирование с помощью пропозициональной логики

2.4 Планирование иерархической сети задач

3. Планирование и осуществление действий в реальном мире

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

4.1 Решение задачи методом редукции

4.2 Метод ключевых состояний и ключевых операторов

4.3 Метод анализа средств и целей

5. Планирование с помощью логического вывода

Вывод

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



Введение

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

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

Планирование -- это область искусственного интеллекта, к которой в настоящее время проявляют значительный интерес.

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



1. Терминология

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

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

Пространством моделей назовем множество всех возможных состояний моделей мира, описываемых алгоритмической системой объекта.

Моделью элементарного действия системы в мире или оператором называется некоторое отношение, определенное в пространстве моделей.

В соответствии с такими определениями дадим вербальное определение плана.

Планом называется помеченный направленный граф, удовлетворяющий следующим требованиям:

* каждая дуга графа помечена оператором, в общем случае оператором-схемой, т. с. семейством операторов, определенных некоторым параметром;

* с каждой вершиной в графе связана некоторая формула, определяющая, в свою очередь, подмножество множества моделей;

* из одной вершины исходят одинаково помеченные дуги;

* подмножество моделей, соответствующее вершине, содержится в области определения оператора, помечающего дуги, исходящие из этой вершины.

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

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

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

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

Алгоритмическая система, осуществляющая построение планов решения задачи, называется планирующей.

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

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

Рассмотрим два класса миров (сред).

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

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



2. Классификация планирования

2.1 Классическое планирование

2.1.1 Планирование с помощью поиска в пространстве состояний

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

Представление задач в пространстве состояний предполагает задание ряда описаний: состояний, множества операторов и их воздействий на переходы между состояниями, целевых состояний. Описания состояний могут представлять собой строки символов, векторы, двумерные массивы, деревья, списки и т. п. Операторы переводят одно состояние в другое. Иногда они представляются в виде продукций A B, означающих, что состояние A преобразуется в состояние B.

Проблема поиска решения задачи A; B при планировании по состояниям представляется как проблема поиска на графе пути из A в B. Обычно графы не задаются, а генерируются по мере надобности (неявное задание графа).

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

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

Алгоритм кратчайших путей Мура. Исходная вершина x0 помечаетсячислом 0. Пусть в ходе работы алгоритма на текущем шаге получено множество дочерних вершин G (xi) вершины xi. Тогда из него вычеркиваются все ранее полученные вершины, оставшиеся помечаются меткой, увеличенной на единицу по сравнению с меткой вершины xi, и от них проводятся указатели к xi. Далее, на множестве помеченных вершин, еще не фигурирующих в качестве адресов указателей, выбирается вершина с наименьшей меткой и для нее строятся дочерние вершины. Разметка вершин повторяется до тех пор, пока не будет получена целевая вершина.

Алгоритм Дейкстры определения путей с минимальной стоимостью является обобщением алгоритма Мура за счет введения дуг переменной длины.

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

Алгоритм Харта, Нилъсона и Рафаэля. В алгоритме объединены оба критерия: стоимость пути до вершины g (x) и стоимость пути от вершины h (x) -- в аддитивной оценочной функции



f (x) = g (x)+h (x).

При условии h (x) < hp (x), где hp (x) -- действительное расстояние до цели, алгоритм гарантирует нахождение оптимального пути.

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

2.2 Планирование с частичным упорядочиванием

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

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

Планирование с частичным упорядочением может быть реализовано в виде поиска в пространстве планов с частичным упорядочением. Это означает, что поиск начинается с пустого плана. После этого рассматриваются способы уточнения плана до тех пор, пока не удастся составить полный план, который решает данную задачу. Действия, рассматриваемые в этом поиске, являются не действиями в мире, а действиями в планах: добавление в план этапа; наложение упорядочения, согласно которому одно действие должно занять место перед другим.

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

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

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

2.3 Планирование с помощью пропозициональной логики

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

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

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

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



2.4 Планирование иерархической сети задач

интеллектуальный планирование

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

В методе планирования, основанном на иерархических сетях задач или сетях HTN (Hierarchical Task Network), первоначальный план, который описывает задачу, рассматривается как описание на очень высоком уровне того, что должно быть сделано. Планы уточняются путем применения декомпозиции действий. В каждой декомпозиции действия одно действие высокого уровня сводится к частично упорядоченному множеству действий низкого уровня. Поэтому в декомпозициях действий отражены знания о том, как осуществляются действия. Процесс декомпозиции продолжается до тех пор, пока в плане не останутся только примитивные действия.



3. Планирование и осуществление действий в реальном мире

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

Существуют четыре описанных ниже метода планирования для осуществления действий в условиях недетерминированности. Первые два из них применимы для ограниченной недетерминированности, а последние два -- для неограниченной недетерминированности [8, 9].

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

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

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

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

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



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

Практически все задачи построения плана действий (решения задач) можно разбить на два типа, которым соответствуют различные модели: планирование в пространстве состояний (SS-проблема) и планирование в пространстве задач (PR-проблема)

Различают многочисленные методы решения задачи при планировании по состояниям

4.1 Решение задачи методом редукции

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

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

Алгоритм Ченга и Слейгла. Основан на преобразовании произвольного И/ИЛИграфа в специальный ИЛИ-граф, каждая ИЛИ-ветвь которого имеет И-вершины только в конце. Преобразование использует представление произвольного И/ИЛИграфа как произвольной формулы логики высказываний с дальнейшим преобразованием этой произвольной формулы в дизъюнктивную нормальную форму. Подобное преобразование позволяет далее использовать алгоритм Харта, Нильсона и Рафаэля.

4.2 Метод ключевых состояний и ключевых операторов

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

Механизм сведения задачи к подзадачам, независимым от задачи, назовем механизмом редукции. Одним из способов построения механизма редукции задачи в пропозиционном графе являются ключевые состояния и ключевые операторы.

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

Одним из приемов нахождения множеств ключевых состояний является выделение ключевых операторов, т. е. операторов, применение которых необходимо для решения задачи.

4.3 Метод анализа средств и целей

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

В интеллектуальной системе используется эвристический поиск. В процессе работы система находит различие между текущим и целевыми состояниями. На основе этих различий она выбирает оператор, который применяется к текущему состоянию, вырабатывая новое состояние. Далее производится сравнение этого состояния с целевым, и цикл повторяется. В случае неприменимости этого оператора к текущему состоянию, GPS определяет различия, суммирующие причину неприменимости. На основе этих различий выбирается оператор, пригодный для их устранения. Если он применим и устраняет их, то применяется предыдущий оператор. Схема работы GPS рекурсивна, т.к. оператор может быть неприменим или непригоден.

Механизм редукции задачи использует три стандартных метода

*преобразование состояния A в состояние B;

*уменьшение различия D между состояниями A и B;

*применение оператора f к состоянию A.



5. Планирование с помощью логического вывода

Такое планирование предполагает: описание состояний в виде правильно построенных формул (ППФ) некоторого логического исчисления, описание операторов в виде либо ППФ, либо правил перевода одних ППФ в другие. Представление операторов в виде ППФ позволяет создавать дедуктивные методы планирования, представление операторов в виде правил перевода -- методы планирования с элементами дедуктивного вывода.

Дедуктивный метод планирования системы QA3. OP3 не оправдал возлагавшихся на него надежд в основном из-за неудовлетворительного представления задач. Попытка исправить положение привела к созданию вопросно-ответной системы QA3. Система рассчитана на произвольную предметную область и способна путем логического вывода ответить на вопрос: возможно ли достижение состояния B из A? В качестве метода автоматического вывода используется принцип резолюций. Для направления логического вывода QA3 применяет различные стратегии, в основном синтаксического характера, учитывающие особенности формализма принципа резолюций. Эксплуатация QA3 показала, что вывод в такой системе получается медленным, детальным, что несвойственно рассуждениям человека.

Метод продукций системы STRIPS. В этом методе оператор представляет продукцию P, A B, где P, A и B -- множества ППФ исчисления предикатов первого порядка, P выражает условия применения ядра продукции A B, где B содержит список добавляемых ППФ и список исключаемых ППФ, т. е. постусловия. Метод повторяет метод ОРЗ с тем отличием, что стандартные задачи определения различий и применения подходящих операторов решаются на основе принципа резолюций. Подходящий оператор выбирается так же, как в ОРЗ, на основе принципа «анализ средств и целей». Наличие комбинированного метода планирования позволило ограничить процесс логического вывода описанием состояния мира, а процесс порождения новых таких описаний оставить за эвристикой «от цели к средству ее достижения».

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



Вывод

История интеллектуального планирования является долгой и иетересной. Интеллектуальное планирование зародилось на основе исследований в области поиска в пространстве состояний и автоматического доказательства теорем. STRIPS была первой системой, которая базировалась на этих двух методологиях. В 1957 году была начата разработка системы, получившей название «Универсальный решатель задач»(Сепега! Problem Solver --GPS). Авторы этой системы: Алан Ньюэлл, Дж. Шоу и Герберт Саймон.

QA3 (Green, 1969)Система QA3 хотя и была вопросно-ответной системой, однако содержала в себе еще и механизмы для решения задач. В частности, эта система могла отвечать на вопросы такого типа: «Существует ли последовательность действий, такая, что объект object 1 окажется в комнате гооm4, если изначально он находится в комнате гооm2?» Такая формулировка вопроса является, по сути, постановкой задачи планирования.

STRIPS (Fikes and Nilsson, 1971)Первая система, которая создавалась именно для решения задачи планирования.Файке и Нильсон сформулировали задачу планирования такой, какова она и по ссй день. Задача планировщика найти такую последовательность действий, которая преобразует начальное состояние в такое состояние, в котором достигается заранее заданное целевое условие. Состояние представляется множеством формул логики первого порядка. Цель также описывается формулой. Действия описываются в виде специальных конструкций.

HACKER (Sussman, 1973)Система HACKER основана на методе анализа средств и целей и обладает механизмом обучения.В качестве механизма обучения Зюссман использовал упрощенный вариант обучения по прецедентам. Прецеденты сохранялись в библиотеке прецедентов, названной Зюссманом библиотекой ответов.

WARPLAN (Warren, 1973)Еще одно решение проблемы с чередованием шагов в нелинейных планах было предложено Дэвидом Уорреном. Его подход заключался в отказе от STRIPS-овского варианта анализа средств и целей. Вместо него был предложен несколько иной подход, названный регрессией.

INTERPLAN (Tate, 1974)Остин Тейт предложил подход, основанный на переупорядочивании подцелей в процессе планирования. Реализация этого подхода воплотилась в планировщике INTERPLAN.В своей работе Тейт рассматривает в качестве цели конъюнкцию высказываний, выраженных атомарными формулами (будем называть эти высказывания целями-конъюнктами) [5]. Цели-конъюнкты достигаются в определенной последовательности и, будучи достигнутыми, уже не должны разрушаться до конца процесса планирования.

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

NOAH (Sacerdoti, 1975)NOAH --первый планировщик, допускающий частичное упорядочение действий в плане и первый иерархический планировщик.

NONLIN (Tate, 1977)Очередной важной вехой в истории планирования стал планировщик NONLIN (Non-linear planner). Идеологически этот планировщик является развитием планировщика NOAH. Однако Тейт вводит новый термин -- задача, -- положивший начало новому направлению, называемому HTN-планированием (HTN --hierarchical task network -- иерархическая сеть задач).

SIPE (Wilkins, 1983)Этот планировщик известен тем, что осуществляет планирование ресурсов, т. е. работает не только с логическими выражениями, но и с численными величинами.

TWEAK (Chapman, 1987)TWEAK -- еще один планировщик, использующий частичное упорядочивание действий в плане. Однако, в отличие от NOAH и NONLIN, он нс является иерархическим.

ABTWEAK (Yang, Tenenberg, 1990),PABLO (Christensen, 1990), CHEF (Hammond, 1990), и т.д.

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



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

[1] Попов Э. В. Алгоритмические основы интеллектуальных роботов и искусственного интеллекта / Э. В. Попов, Г. Р. Фирдман. -- М.: Изд-ва «Наука», 1976.-456 с.

[2] Достоверный и правдоподобный вывод в интеллектуальных системах / В. Н. Вагин [и др.]; под ред. В. Н. Вагина и Д. А. Поспелова.-- М.: Физ-матлит, 2004. -- 704 с.

[3] Искусственный интеллект. Применение в интегрированных производственных системах / под ред. Э. Кюснаке. -- М.: Машиностроение, 1991.

[4] Лорьер Ж. Л. Системы искусственного интеллекта: пер с франц. В. Л. Стефанюка / Ж. Л. Лорьер. -- М.: Мир. 1991, -- 568 с.

[5] Нильсон Н. Искусственный интеллект. Методы поиска решений: пер. с англ. / Н. Нильсон. -- М.: Радио и связь, 1985, --280 с.

[6] Поспелов Д. А. Семиотические модели в задачах планирования для систем искусственного интеллекта / Д. А. Поспелов, Е. И. Ефимов // Изв. АН СССР. Сер. Техническая кибернетика, -- 1977, --№6.-- С. 60-68.

[7] Рассел С. Искусственный интеллект: современный подход: пер. с англ. К. А. Итицына. -- 2-е изд. / С. Рассел, П. Норвиг. -- М.: Вильямс. 2006.-- 1408 с.

[8] ЧерноруцкийИ. Г. Методы принятия решений / И. Г. Черноруцкий. -- СПб.: БХВ -- Петербург, 2005. -- 416 с.

[9] Newell A. GPS: A Program that Simulates Human Thought / A. Newel, H. Simon // Computers and Thought. -- 1963. -- №4. -- P. 279-293.

Размещено на Allbest.ru

...